CF1709总结和题解

发表于 更新于 分类于

CF1709 总结和题解

A

略

B

略

C

题意

有个合法括号序列，部分字符被 ? 替换了，问是否存在唯一的一种填 ? 的方案，使得括号序列合法，即判断填 ? 使得括号序列合法的方案数是否等于1。存在唯一方案输出 YES，方案不唯一输出 NO

序列长度 \(\sum n\le 2\times 10^5\)，测试点数 \(T\leq 5\times 10^4\)

第一行输出测试点总数 \(T\)。

之后每一行一个字符串 \(s\) 表示替换掉部分字符后的合法括号序列。

题解

考虑一个括号序列，令 ( 为 1，) 为 -1，记形成的新序列为 \(c\)，然后对该序列做前缀和得到 \(s\)，容易发现括号序列合法的充要条件是 \(s_n=0\) 且 \(\forall i\in[1,n],s_i\ge0\)。

已知给定的带 ? 的序列是一个合法序列变来的，所以考虑统计三种字符的个数，?,(,) 分别个数记为 cnt cnt0 cnt1，发现如果出现 cnt + min(cnt0,cnt1)=n/2 一定是 YES，因为每个 ? 的填法已经确定了。

因为一定要合法，所以 \(s_n\) 一定为 0，现在就需要让每一个 \(s_i\) 尽量大，方法就是把 ( 尽量往前面填，这样会让每个 \(s_i\) 都尽可能大。

然后我们考虑一种稍稍不那么优秀的方案，就是交换一组由两个 ? 构成的 () 序列，发现交换 () 交界处的那两个一定最优，所以求一下交界处的 min 看看是否大于 2 就行。

可以证明，如果这样交换不行，那么其它任何交换方案都不行。

我写麻烦了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
#define y1 y3647
#define INF 1000000000
#define LL long long
#define pii pair<int,int>
using namespace std;
template<typename _type>
inline void read(_type &x){
	x=0;int f=1;char ch=getchar();
	while(ch!=45&&(ch>'9'||ch<'0'))ch=getchar();
	if(ch==45){f=-1,ch=getchar();}
	while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getchar();}x*=f;
}
template<typename _type1,typename _type2>void cmin(_type1 &a,const _type2 b){if(a>b)a=b;}
template<typename _type1,typename _type2>void cmax(_type1 &a,const _type2 b){if(a<b)a=b;}
const int N=1e6+10;
int i,j,k,n,s,t,m,tp1,tp2;
char ch[N];
int c[N];
signed main()
{
// 	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
//	freopen(".in","w",stdout);
	read(t);
	while(t--){
		scanf("%s",ch+1);
		n=strlen(ch+1);int cnt=0,cnt0=0,cnt1=0;
		for(i=1;i<=n;i++){
			if(ch[i]=='?')cnt++;
			if(ch[i]=='(')cnt0++;
			if(ch[i]==')')cnt1++;
		}
		if(cnt<=1||cnt+min(cnt0,cnt1)==n/2){
			puts("YES");
			continue;
		}
		int flag=0,top=0,t1=0;
		for(i=1;i<=n;i++){
			if(ch[i]=='(')top++;
			if(ch[i]==')')top--;
			if(ch[i]=='?'&&cnt0!=n/2)top++,t1++,cnt0++;
			else if(ch[i]=='?'&&cnt0==n/2)top--;
			c[i]=top;
		}
		int lst=0,min_val=INF,all=0;
		for(i=1;i<=n;i++){
			if(ch[i]=='?'){
				all++;
				if(min_val>=2&&all==t1+1)flag=1;
				lst=i;
				min_val=INF;
			}
			cmin(min_val,c[i]);
		}
		if(flag)puts("NO");
		else puts("YES");
	}
	return 0;
}


D

题意

有一个 \(n\times m\) 的网格，第 \(i(i\in[1,m])\) 列的 \([1,a_i]\) 行被锁定了。

你有个机器人，你可以给它发命令，让它向上下左右移动一格，但是机器人有 Bug，你发的每个命令都会被执行 \(k\) 次不是瞬移 \(k\) 格，而是走 \(k\) 次，每次一格。在任何一个时刻，机器人都不能处于被锁定的格子或者网格外。

给定 \(q\) 组询问，每组询问给定五个参数 \(x_s,y_s,x_f,y_f,k\)，代表起点终点坐标和参数 \(k\)，问能否从起点到终点，能输出 YES，不能输出 NO。

第一行输入 \(n,m\)。

第二行输入一个长度为 \(m\) 的数组表示 \(a\)。

第三行一个整数 \(q\)

接下来 \(q\) 行每行 \(5\) 个整数 \(x_s,y_s,x_f,y_f,k\) 描述一个询问。

$ 1 n ^9 ; 1 m ^5 ; 1q ^5$

\(a[y_s] < x_s \le n ; 1 \le y_s \le m ; a[y_f] < x_f \le n; 1 \le y_f \le m; 1 \le k \le 10^9\)

题解

假设全部点都没有 \(lock\)，考虑从 \((x_1,y_1)\) 能到 \((x_2,y_2)\) 的充要条件，显然是 \(k|abs(x_1-x_2)\) 并且 \(k|abs(y_1-y_2)\)。

现在加入限制。允许 \([n-a_i,n]\) 走太麻烦了，翻转一下，变成允许 \([1,a_i']\) 走。

然后最优方案就是先走到当前的最底下，然后横着走过去。

所以找到最低能走到哪个位置，然后做个区间 min，判断最低位置 \(x\) 和区间 min 的关系，如果 \(x\le \min\)，显然可以，否则不行。

区间 min 用 ST 表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
#define y1 y3647
#define INF 1000000000
#define LL long long
#define pii pair<int,int>
using namespace std;
template<typename _type>
inline void read(_type &x){
	x=0;int f=1;char ch=getchar();
	while(ch!=45&&(ch>'9'||ch<'0'))ch=getchar();
	if(ch==45){f=-1,ch=getchar();}
	while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getchar();}x*=f;
}
template<typename _type1,typename _type2>void cmin(_type1 &a,const _type2 b){if(a>b)a=b;}
template<typename _type1,typename _type2>void cmax(_type1 &a,const _type2 b){if(a<b)a=b;}
const int N=4e5+10;
int i,j,k,n,s,t,m,q;
int st[25][N],lo[N];
int ask(int l,int r){
	if(l>r)swap(l,r);
	int len=lo[r-l+1];
	return min(st[len][l],st[len][r-(1<<len)+1]);
}
signed main()
{
// 	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
//	freopen(".in","w",stdout);
	read(m),read(n);
	
	for(i=2;i<=n;i++)lo[i]=lo[i>>1]+1;
	for(i=1;i<=n;i++)
	read(st[0][i]),st[0][i]=m-st[0][i];
	
	for(i=1;i<=20;i++)
	for(j=1;j+(1<<i)-1<=n;j++)
	st[i][j]=min(st[i-1][j],st[i-1][j+(1<<i-1)]);
	read(q);
	for(i=1;i<=q;i++){
		int x1,x2,y1,y2;
		read(y1),read(x1),read(y2),read(x2),read(k);
		if(k==0){
			if(x1==x2&&y1==y2)puts("YES");
			else puts("NO");
			continue;
		}
		y1=m-y1+1,y2=m-y2+1;
		if(abs(x1-x2)%k||abs(y1-y2)%k||ask(x1,x2)<(y1%k==0?k:y1%k))puts("NO");
		else puts("YES");
	}
	return 0;
}


E

题意

你有一棵无根树，点数为 \(n\)，每个点有个点权 \(a_u\)，定义一条路径 \(P(u,v)\) 的权值为经过的所有点的点权的异或和。定义一棵树是合法的，当且仅当树上所有简单路径（只经过每个点一次的路径）的的权值都不为 \(0\)。

你可以对权值进行修改，可以改成任意正整数，问最少修改多少次才能让这棵树合法。

输出最小修改次数。

\(n\leq 2\times 10^5,a_i\leq 2^{30}\)

题解

发现路径权值为 \(sum[u] \bigoplus sum[v] \bigoplus a[lca(u,v)]\)，\(sum[u]\) 表示从 \(1\) 到 \(u\) 的路径上所有点点权的异或和，每一条路径，我们在路径 \(lca\) 处考虑是否不合法（权值为 0）。

我们称一个点不合法当且仅当有一条 \(lca\) 为这个点的不合法路径经过它。我们从深到浅处理每一个不合法的 \(lca\)

如果一条路径不合法，修改方案可以分为改 \(lca\) 和非 \(lca\)，可以说明改 \(lca\) 是最优的。首先，可以说明，改一个点 \(u\) 的最优方案之一是改成 \(2^{u+32}\)，因为这样的话所有经过这个点的路径都一定合法。然后说明改 \(lca\) 最优。如果不改 \(lca\)，以这颗子树中的点为起点的路径仍然有可能不合法，而改 \(lca\)，以这颗子树中的点为起点的路径一定都合法。我们假设了当前处理的 \(lca\) 是最深的，所以这颗子树内所有的不合法路径一定经过了 \(lca\)，所以改了 \(lca\)，所有路径就一定合法了。所以改 \(lca\) 最优

怎么判断一个 \(lca\) 处有不合法路径，拿个 set 维护下每颗子树内的 \(sum\)，然后加入一颗子树时，枚举加入子树的所有点 \(v\)，判断当前 set 中是否存在元素 \(a_[lca]\bigoplus sum[v]\)，如果存在，\(lca\) 就不合法，我们给答案加一，在这颗子树的父亲计算时忽略该子树。

发现合并 set 的代价是 \(O(\sum size_u)=O(n^2)\) 的，但是可以启发式合并。

具体的，一个点 \(u\) 继承它最大的儿子的 \(set\)，然后在把它自己和其它子树加入到这个 set 中，同时判断是否存在不合法路径。考虑这样的复杂度，证明和树链剖分的复杂度证明相同，继承操作可以用 std::swap，这个函数交换两个 STL 容器的复杂度，在 C++11 以上标准是 \(O(1)\) 的。

对于一个点，我们考虑它什么时候会被合并一次（就是作为非最大子树，被合并上去）。每一个点所在的 set，被合并时，它所在的新 set 的大小至少变为 \(2\) 倍（因为新 set 最开始的大小一定比该点所在的 set 大，否则该点所在的 set 会作为最后保留的 set 而不对复杂度做贡献），最后的 set 大小为 \(n\)，所以每个点合并 \(\log n\) 次。

总复杂度 \(O(n\log^2 n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
#define y1 y3647
#define INF 1000000000
#define LL long long
#define pii pair<int,int>
using namespace std;
template<typename _type>
inline void read(_type &x){
	x=0;int f=1;char ch=getchar();
	while(ch!=45&&(ch>'9'||ch<'0'))ch=getchar();
	if(ch==45){f=-1,ch=getchar();}
	while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getchar();}x*=f;
}
template<typename _type1,typename _type2>void cmin(_type1 &a,const _type2 b){if(a>b)a=b;}
template<typename _type1,typename _type2>void cmax(_type1 &a,const _type2 b){if(a<b)a=b;}
const int N=2e5+10;
int i,j,k,n,s,t,m,tp1,tp2,ans;
int fa[N],sz[N],son[N],a[N],sum[N];
vector<int> e[N];
set<int> st[N];
void pre_dfs(int u){
	sz[u]=1;
	for(auto v:e[u]){
		if(fa[u]==v)continue;
		fa[v]=u;sum[v]=sum[u]^a[v];
		pre_dfs(v),sz[u]+=sz[v];
		if(sz[v]>sz[son[u]])son[u]=v;
	}
}
void redfs(int u,int flag=0){
	if(son[u]){
		redfs(son[u]);
		swap(st[son[u]],st[u]);
	}
	if(st[u].find(sum[u]^a[u])!=st[u].end())flag=1;
	st[u].insert(sum[u]);
	for(auto v:e[u]){
		if(v==son[u]||v==fa[u])continue;
		redfs(v);
		for(auto val:st[v]){
			if(st[u].find(val^a[u])!=st[u].end())
			flag=1;
		}
		for(auto val:st[v])
		st[u].insert(val);
	}
	if(flag)ans++,st[u].clear();
}
signed main()
{
	read(n);
	for(i=1;i<=n;i++)read(a[i]);
	sum[1]=a[1];
	for(i=1;i<n;i++){
		int x,y;read(x),read(y);
		e[x].push_back(y),e[y].push_back(x);
	}
	pre_dfs(1);
	redfs(1);

	cout<<ans<<endl;
	return 0;
}


F

题意

定义二进制串为只包含 \(01\) 的字符串。

给你 \(n,k,f\)，\(1\le n\leq 15,1\le f,k\leq 2\times 10^5\)，你需要给每个长度不超过 \(n\) 的二进制串 \(s\) 确定一个 \(c_s\in [0,k]\) 的权值。然后你需要选出一个只包含长度恰好为 \(n\) 的二进制串的可重集合，使得这个可重集合最大。并且满足对于所有长度小于 \(n\) 的二进制串 \(s\)，集合元素中，\(s\) 作为集合中元素前缀的次数不超过 \(c_s\)。

求安排 \(c\) ，使得集合最大大小恰好为 \(f\) 的方案数，对 \(998244353\) 取模。

题解

考虑取到最大值 \(f\) 的条件，不妨令 \(n=1\)，发现要求就是 \(c_0+c_1=f\)，然后我们考虑一些长度为 \(n\) 的二进制串。

因为要对每个长度小于 \(n\) 的串都确定一个 \(c\)，然后我们又发现，记一个前缀 \(s\) 的数量限制为 \(w_s\)，实际上 \(w_s=\min(c_s,w_{s+'0'}+w_{s+'1'})\)。

然后我们就可以对一个确定的 \(c\) 序列，像树形 \(dp\) 一样算出最大大小。

考虑对这个树形 \(dp\) 的过程计数，本质上，由于树是满二叉树，所以 dp 出每个值的 \(c\) 序列的方案只于层数有关。

所以设 \(dp[i][j]\) 为考虑到深度为 \(n-i\) 的满二叉树，值为 \(j\) 的安排方案总数。

转移限制有两种，第一个是 \(c\) 限制，第二种是子树限制，考虑先算一个 \(sum[i][j]\) 表示子树和为 \(j\) 的方案数。

然后可以得到 \(dp[i][j]=sum[i][j]*(k-j+1)+\sum\limits_{t> j}sum[i][t]\)。分别表示两种限制的贡献。

算出 \(sum\) 后是 \(O(k)\) 转移的。考虑 \(sum[i][j]=\sum\limits_{s+t=j} dp[i-1][s]\times dp[i-1][j]\)。就是个卷积，NTT 板子上去就行。

注意边界，处理最顶层的时候，\(dp[n][i]\) 只能由子树和来限制，因为这个点本来就是长度为 0 的串，不能填 \(c\)，我在这里想当然的认为只要 \(i\le k\) 的时候有值，所以没有 AK，实际上这里 \(k< i\le 2k\) 也是有值的，因为这个点本身不会限制。

如果 TLE 了换成 64bit 的机子再交一次，64 bit 的 long long 运算要快一些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
#define y1 y3647
#define INF 1000000000
#define int long long
#define pii pair<int,int>
using namespace std;
template<typename _type>
inline void read(_type &x){
	x=0;int f=1;char ch=getchar();
	while(ch!=45&&(ch>'9'||ch<'0'))ch=getchar();
	if(ch==45){f=-1,ch=getchar();}
	while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getchar();}x*=f;
}
template<typename _type1,typename _type2>void cmin(_type1 &a,const _type2 b){if(a>b)a=b;}
template<typename _type1,typename _type2>void cmax(_type1 &a,const _type2 b){if(a<b)a=b;}
const int N=1<<19,mod=998244353;
namespace NTT{
	const int N=1<<20,mod=998244353,g=3,gi=332748118;
	int i,j,k,n,s,t,m;
	int a[N],b[N],rk[N];
	int quick(int a,int s,int ret=1){
		while(s){
			if(s&1)ret=ret*a%mod;
			a=a*a%mod,s>>=1;
		}
		return ret;
	}
	void NTT(int *a,int type)
	{
		for(i=0;i<1<<s;i++)
		if(rk[i]>i)swap(a[rk[i]],a[i]);
		for(int len=1;len<=s;len++)
		{
			int w=1,wn=quick(g,mod-1>>len);
			if(type==-1)wn=quick(wn,mod-2);
			for(j=0;j+(1<<len)<=1<<s;j+=1<<len,w=1)
			{
				for(k=j;k<j+(1<<len-1);k++,w=1ll*w*wn%mod)
				{
					int x=a[k],y=a[k+(1<<len-1)];
					a[k]=(x+1ll*w*y%mod)%mod,a[k+(1<<len-1)]=(x-1ll*w*y%mod)%mod;
				}
			}
		}
	}
	void init(int nn,int c[],int res[]){
		n=m=nn;
		memset(a,0,sizeof(a)),memset(b,0,sizeof(b));
		for(i=0;i<=n;i++)a[i]=c[i];
		for(i=0;i<=m;i++)b[i]=c[i];
		while(1<<s<=n+m)s++;
	
		for(i=1;i<1<<s;i++)rk[i]=rk[i>>1]>>1|(i%2?1<<s-1:0);
		NTT(a,1),NTT(b,1);
		for(i=0;i<1<<s;i++)a[i]=1ll*a[i]*b[i]%mod;
		NTT(a,-1);int inv=quick(1<<s,mod-2);
		for(i=0;i<=n+m;i++)
		res[i]=(1ll*a[i]*inv%mod+mod)%mod;
	}
}
int i,j,k,n,s,t,m,tp1,tp2,f;
void Inc(int &a,int b){
	a+=b;if(a>=mod)a-=mod;
}
int quick(int a,int s,int ret=1){
	while(s){
		if(s&1)ret=ret*a%mod;
		a=a*a%mod,s>>=1;
	}
	return ret;
}

int dp[16][N<<1],sum[16][N<<1],p[N];
signed main()
{
// 	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
//	freopen(".in","w",stdout);
	read(n),read(k),read(f);
	for(i=0;i<=k;i++)dp[0][i]=1;
	for(i=1;i<=n;i++){
		NTT::init(k,dp[i-1],sum[i]);
		for(j=0;j<=2*k;j++){
			if(i!=n)dp[i][j]=sum[i][j]*(k-j+1)%mod;
			else dp[i][j]=sum[i][j];
		}
		if(i!=n)for(j=2*k-1;j>=0&&i!=n;j--){
			if(j<=k)Inc(dp[i][j],sum[i][j+1]);
			Inc(sum[i][j],sum[i][j+1]);
		}	
	}
	cout<<(dp[n][f]+mod)%mod;
	return 0;
}