10.03 模拟赛 by FXT

wgyhm

2023-10-05

NOIP模拟赛, dp, 决策单调性, 对顶栈, 状压

10.03 模拟赛

这场可能称为 CSP 模拟赛更好一点。？

T1

Ptz 2020 Winter Day 4 B QOJ 686

Solution

签到题。对于每只虱子分开考虑。

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 2000005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,m,w[maxn];
struct yyy {
	int l,r;
}a[maxn],id[maxn];
vector<int>to[maxn];	
int d[maxn],s[maxn],s2[maxn],g[maxn],anss;
int Ans[maxn];
signed main(void){
	int i,j,tot,x,y;
	read(n);read(m);
	for (i=1;i<=m;i++) read(w[i]);
	for (i=1;i<=n;i++) {
		read(a[i].l),read(a[i].r);read(x);
		while (x--) {
			read(y);
			to[y].push_back(i);
		}
	}
	for (j=1;j<=m;j++) {
		tot=0;
		for (auto y:to[j]) g[++tot]=a[y].l-1,g[++tot]=a[y].r;
		sort(g+1,g+1+tot);
		tot=unique(g+1,g+1+tot)-g-1;
		int nums=0;
		for (auto y:to[j]) {
			++nums;
			id[nums].l=lower_bound(g+1,g+1+tot,a[y].l-1)-g;
			id[nums].r=lower_bound(g+1,g+1+tot,a[y].r)-g;
			d[id[nums].l+1]++,d[id[nums].r+1]--;
		}
		for (i=1;i<=tot;i++) {
			d[i]+=d[i-1];
			s[i]=s[i-1]+(d[i]>0)*(g[i]-g[i-1]);
			s2[i]=s2[i-1]+(d[i]==1)*(g[i]-g[i-1]);
		}
		nums=0;
		anss+=s[tot]*w[j];
		for (auto y:to[j]) {
			++nums;
			Ans[y]-=(s2[id[nums].r]-s2[id[nums].l])*w[j];
		}
		for (i=1;i<=tot+5;i++) d[i]=s[i]=s2[i]=0;
	}
	for (i=1;i<=n;i++) printf("%lld%c",anss+Ans[i]," \n"[i==n]);
	return 0;
}

T2

Ptz 2020 Winter Day 4 C QOJ 687

原来 $2^nn^2$ 在 $n=20$ 是 $4\times 10^8$，我算成 $4\times 10^7$ 然后自信离场。

Solution

考虑状态压缩。令 $f_S$ 表示集合 $S$ 为前缀的拓扑序的方案数，$g_S$ 表示集合 $S$ 为后缀的拓扑序的方案数。两者都可以 $O(2^nn)$ 预处理出来。

然后是统计答案。外层枚举第 $i$ 行，令 $T=C_U^{S\cup i}$ 先判断 $S+i+T$ 是否合法，然后让 $Ans_{x,i}\gets Ans_{x,i}+f_S\times g_S$。直接做是 $O(2^n n^2)$ 的。考虑用一个类似于懒惰标记的东西。令 $h_S$ 表示 $S$ 的方案数。如果 $S$ 中包含至少两个元素，令 $x$ 为其任意的一个元素，则 $T=C_S^$ 则有 $h_x\gets h_S,h_{T}\gets h_S$。这样直接传下来，复杂度就是 $O(2^n n)$。

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,m;
int to[25],pre[25],f[(1<<20)+5],g[(1<<20)+5],h[(1<<20)+5];
#define lowbit(x) ((x)&(-x))
void solve(void) {
	int i,j,k,s,t,x,y,a,b;
	read(n);read(m);
	int N=(1<<n);
	for (i=0;i<=n;i++) to[i]=pre[i]=0;
	for (i=1;i<=m;i++) {
		read(x),read(y);
		to[y-1]|=(1<<x-1);
		pre[x-1]|=(1<<y-1);
	}
	for (i=0;i<N;i++) f[i]=g[i]=0;
	f[0]=g[0]=1;
	for (i=1;i<N;i++)
		for (j=0;j<n;j++) {
			if ((i&to[j])==to[j]) f[i]+=f[i^(1<<j)];
			if ((i&pre[j])==pre[j]) g[i]+=g[i^(1<<j)];
		}
	for (k=0;k<n;k++) {
		for (s=0;s<N;s++) h[s]=0;
		for (s=N-1;s>=0;s--) {
			if (((s>>k)%2==0)&&(s&to[k])==to[k]) {
				int t=(N-1)^(1<<k)^s;
				if ((pre[k]&t)==pre[k]) {
					h[s]+=f[s]*g[t];
				}
			}
			if (s!=lowbit(s)) h[s^lowbit(s)]+=h[s],h[lowbit(s)]+=h[s],h[s]=0;
		}
		for (i=0;i<n;i++) printf("%lld ",h[1<<i]);
		put();	
	}
}
signed main(void){
	int T;
	read(T);
	while (T--) solve();
	return 0;
}

T3

JOI Open 2018 T1 Bubble Sort 2 QOJ 2643

妙妙题。

Solution

首先答案具有单调性。

原式：
$$
\min\limits_{i=l}^r a_i+\max\limits_{i=l}^r a_i>r-l+1
$$
考虑一个满足要求的区间 $[l,r]$，随便减去不是最大值的端点，则左式不减，右式减小。一定满足。

考虑一种双指针，枚举右端点 $r$，令当前的最大值为 $ans$，则 $l$ 从 $r-ans+1$ 开始向左枚举，判断合法性。

先不考虑判断合法性的复杂度。先考虑正确性。如果枚举到答案区间的最大值，则左端点根据单调性一定会移动答案区间的左端点。

然后来看端点的移动次数，每次为了保证区间的长度大于等于最大值，每次移动右端点时，左端点最多往右移动一格。左端点最多只能向左移动 $O(2n)$ 次，所以移动次数为 $O(n)$ 的。

现在的复杂度瓶颈在于判断区间的合法性。也就是要动态求出区间的最大值和最小值。除了四毛子树这种不可能写的东西以外。有一种神奇的东西：对顶栈。他的算法流程如下：

以一个点为中心，维护前后缀的最大最小值。
如果加减前后首位且区间包含中心点，$O(1)$ 维护前后缀。
如果不包含中心点，暴力重构，取当前区间的中点作为中心点。

考虑分析复杂度，如果一个长度为 $n$ 的序列被重构了，则至少操作了 $n/2$ 次。所以复杂度是 $O(n)$，其中 $n$ 为操作次数。

对顶栈感觉可以适用于这种双指针强行让你 $O(n)$ 的题目中。如果预处理或者查询有一个可以做到 $O(n\log n)$ 或者以上，就没有使用的必要了，感觉不如 ST 表。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 1000005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,m,a[maxn];
int L,mid,R,sl[maxn],sr[maxn],ml[maxn],mr[maxn];//min,max
void build(int L,int R) {
	mid=L+R>>1;int i;
	for (sl[mid]=ml[mid]=a[mid],i=mid-1;i>=L;i--) sl[i]=min(sl[i+1],a[i]),ml[i]=max(ml[i+1],a[i]);
	for (sr[mid+1]=mr[mid+1]=a[mid+1],i=mid+2;i<=R;i++) sr[i]=min(sr[i-1],a[i]),mr[i]=max(mr[i-1],a[i]);
}
int query(int l,int r) {
	if (l==r) return 2*a[l];
	return max(mr[r],ml[l])+min(sr[r],sl[l]);
}
void solve(void) {
	int i,ans=0,l=1,r;mid=1;sl[l]=ml[l]=a[l];
	for (i=0;i<=n;i++) sl[i]=sr[i]=ml[i]=mr[i]=0;
	for (r=1;r<=n;r++) {
		if (r>mid+1) sr[r]=min(sr[r-1],a[r]);else sr[r]=a[r];
		if (r>mid+1) mr[r]=max(mr[r-1],a[r]);else mr[r]=a[r];
		if (mid<l||mid>=r) build(l,r);
		if (query(l,r)<=r-l+1) l++;
		else {
			sl[l-1]=min(sl[l],a[l-1]);
			ml[l-1]=max(ml[l],a[l-1]);
			while (l>=2&&query(l-1,r)>r-l+2) {
				l--;
				sl[l-1]=min(sl[l],a[l-1]);
				ml[l-1]=max(ml[l],a[l-1]);
			}
		}
		ans=max(ans,r-l+1);
	}
	printf("%d\n",ans);
}
signed main(void){
	int i,x,y;
	read(n);read(m);
	for (i=1;i<=n;i++) read(a[i]);
	solve();
	while (m--) {
		read(i);
		while (i--) read(x),read(y),swap(a[x],a[y]);
		solve();
	}
	return 0;
}

T4

Ptz 2022 Winter Day 1 F QOJ 2544

Solution

本质上就是一个体积很大 $10^{14}$，权值只有 $0\le w\le 4$ 的 01 背包。

一种做法是将权值相同的内部体积从小到大排序。考虑权值为 $i$ 的向 $i+1$ 的转移，有决策单调性。分治 $O(wn\log n)$ 解决。

另一种做法是根据权值的特殊性，$2,4$ 分为一组合并，$1,3$ 分为一组合并，最后双指针或者三分之类的找答案。

考场贪心代码，其实很优，直接过了，要卡还是能卡，但是意义不大，不贴了。