Loading [MathJax]/jax/output/HTML-CSS/jax.js

CF1149

Posted on | Edited on | Views: 26

Div.1

CF1149A Prefix Sum Primes

  • 构造 + 贪心.
  • 可以先线性筛预处理一个质数表.于是就变成了用一定数量的 1,2​ 来填每个位置差分的值.
  • 从前往后填,如果当前能放 2​ 的话肯定不会劣于放两个 1​ .于是能放 2​ 就放,否则放 1​ ,直到放完为止.
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e6+10;
int prime[MAXN],cnt=0,ism[MAXN];
void init(int N)
{
	ism[1]=1;
	for(int i=2;i<=N;++i)
	{
		if(!ism[i])
			prime[++cnt]=i;
		for(int j=1;j<=cnt && i*prime[j]<=N;++j)
		{
			ism[i*prime[j]]=1;
			if(i%prime[j]==0)
				break;
		}
	}
}
int bgs[3];
void solve()
{
	for(int i=1;i<=cnt;++i)
	{
		int dif=prime[i]-prime[i-1];
		int us2=min(bgs[2],dif/2);
		for(int j=1;j<=us2;++j)
			printf("2 ");
		bgs[2]-=us2;
		dif-=2*us2;
		int us1=min(bgs[1],dif);
		for(int j=1;j<=us1;++j)
			printf("1 ");
		bgs[1]-=us1;
		if(bgs[1]+bgs[2]==0)
			return;
	}
}
int main()
{
	init(1000000);
	int n=read();
	for(int i=1;i<=n;++i)
		bgs[read()]++;
	solve();
	return 0;
}

CF1149B Three Religions

  • 贪心 + dp .
  • 首先可以发现如果三个串匹配到了一定位置,最后在原串中用的字符位置肯定越靠前越好.
  • 于是可以设 f(i,j,k) 表示三个串分别匹配了 i,j,k 的长度时,最后用的字符在原串中的位置.
  • 可以预处理 nx(i,j) 表示原串中第 i 个字符往后跳,跳到的第一个字符为 j 的位置.跳不到设为 n+1 .那么就可以借助 nx 来完成 f 的转移.
  • 那么计算完成后,只需要判断 f(len1,len2,len3)≤n 是否成立.成立则为 YES ,否则为 NO .
  • 并不能 O(q⋅2503) 暴力 dp .注意每次加一个字符时(假定加在第一个串上),前面的 dp 值不会被影响,只需计算 f(len1+1,j,k) 这 2502 个状态.每次删字符时直接让 len 减 1 就可以了.下次会覆盖掉多余的值.
  • 时间复杂度 O(q⋅2502).
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
97
98
99
100
101
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10,L=251;
const int Siz=26;
char buf[MAXN];
int n,Q,nx[MAXN][Siz];
int minpos[Siz];
int f[L][L][L];
int len[4];
int s[4][L];
int main()
{
	n=read();
	Q=read();
	scanf("%s\n",buf+1);
	for(int i=0;i<Siz;++i)
		minpos[i]=n+1;
	buf[0]='a';
	for(int i=n+1;i>=0;--i)
	{
		memcpy(nx[i],minpos,sizeof minpos);
		minpos[buf[i]-'a']=i;
	}
	f[0][0][0]=0;
	while(Q--)
	{
		char tp[2],newchar[2];
		int id;
		scanf("%s%d",tp,&id);
		if(tp[0]=='+')
		{
			scanf("%s",&newchar);
			s[id][++len[id]]=newchar[0]-'a';
			if(id==1)
			{
				for(int i=len[1];i<=len[1];++i)
					for(int j=0;j<=len[2];++j)
						for(int k=0;k<=len[3];++k)
						{
							int res=n+1;
							if(i)
								res=min(res,nx[f[i-1][j][k]][s[1][i]]);
							if(j)
								res=min(res,nx[f[i][j-1][k]][s[2][j]]);
							if(k)
								res=min(res,nx[f[i][j][k-1]][s[3][k]]);
							f[i][j][k]=res;
						}
			}
			else if(id==2)
			{
				for(int i=0;i<=len[1];++i)
					for(int j=len[2];j<=len[2];++j)
						for(int k=0;k<=len[3];++k)
						{
							int res=n+1;
							if(i)
								res=min(res,nx[f[i-1][j][k]][s[1][i]]);
							if(j)
								res=min(res,nx[f[i][j-1][k]][s[2][j]]);
							if(k)
								res=min(res,nx[f[i][j][k-1]][s[3][k]]);
							f[i][j][k]=res;
						}
			}
			else
			{
				for(int i=0;i<=len[1];++i)
					for(int j=0;j<=len[2];++j)
						for(int k=len[3];k<=len[3];++k)
						{
							int res=n+1;
							if(i)
								res=min(res,nx[f[i-1][j][k]][s[1][i]]);
							if(j)
								res=min(res,nx[f[i][j-1][k]][s[2][j]]);
							if(k)
								res=min(res,nx[f[i][j][k-1]][s[3][k]]);
							f[i][j][k]=res;
						}
			}
		}
		else
			--len[id];
		puts(f[len[1]][len[2]][len[3]]<=n?"YES":"NO");
	}
	return 0;
}

CF1149C Tree Generator™

  • 给的括号序列就是一个欧拉序(进出都记录).
  • 容易处理出每个点的 dep​ ,遇见 (​ 就 +1​ ,否则 −1​ .
  • 考虑两个点的距离为 depu+depv−2deplca​ ,在欧拉序中.和用 RMQ​ 做 LCA​ 一样,两个点的 lca​ 一定位于这两个点的中间,且深度最小.
  • 那么找直径就转化为找三个位置 u≤lca≤v ,使得 depu+depv−2deplca 最大.
  • 每次修改交换两个括号,中间那一段 dep 都会 +2/−2 .于是用线段树维护每个位置的 dep , depl−2depi , depr−2depi 的 max 即可.

注意合并节点,标记的细节.

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=2e5+10;
int n,Q;
int dep[MAXN];
struct SegTree
{
	struct node
	{
		int res;//dep[l]+dep[r]-2dep[i]
		int tag;
		int mxdep,negdep;//dep[i],-2dep[i]
		int ldep,rdep;//dep[l]-2dep[i],dep[r]-2dep[i]
	}Tree[MAXN<<2];
#define root Tree[o]
#define lson Tree[o<<1]
#define rson Tree[o<<1|1]
	void pushup(int o)
	{
		root.mxdep=max(lson.mxdep,rson.mxdep);
		root.negdep=max(lson.negdep,rson.negdep);

		root.ldep=max(lson.ldep,rson.ldep);
		root.ldep=max(root.ldep,lson.mxdep+rson.negdep);

		root.rdep=max(lson.rdep,rson.rdep);
		root.rdep=max(root.rdep,lson.negdep+rson.mxdep);

		root.res=max(lson.res,rson.res);
		root.res=max(root.res,lson.mxdep+rson.rdep);
		root.res=max(root.res,lson.ldep+rson.mxdep);
	}
	void BuildTree(int o,int l,int r)
	{
		root.tag=0;
		if(l==r)
		{
			root.mxdep=dep[l];
			root.negdep=-2*dep[l];
			root.rdep=root.ldep=-dep[l];
			root.res=0;
			return;
		}
		int mid=(l+r)>>1;
		BuildTree(o<<1,l,mid);
		BuildTree(o<<1|1,mid+1,r);
		pushup(o);
	}
	void modifiy(int o,int c)
	{
		root.tag+=c;
		root.mxdep+=c;
		root.negdep-=2*c;
		root.ldep-=c;
		root.rdep-=c;
	}
	void pushdown(int o)
	{
		if(root.tag)
		{
			modifiy(o<<1,root.tag);
			modifiy(o<<1|1,root.tag);
			root.tag=0;
		}
	}
	void update(int o,int l,int r,int L,int R,int c)
	{
		if(L>r || l>R || L>R)
			return;
		if(L<=l && r<=R)
		{
			modifiy(o,c);
			return;
		}
		pushdown(o);
		int mid=(l+r)>>1;
		if(L<=mid)
			update(o<<1,l,mid,L,R,c);
		if(R>mid)
			update(o<<1|1,mid+1,r,L,R,c);
		pushup(o);
	}
}T;
#define pr printf("%d\n",T.Tree[1].res);
char buf[MAXN];
int main()
{
	n=read(),Q=read();
	scanf("%s",buf+1);
	for(int i=1;i<=2*n-2;++i)
	{
		dep[i]=dep[i-1];
		if(buf[i]=='(')
			++dep[i];
		else
			--dep[i];
	}
	T.BuildTree(1,1,2*n-2);
	pr;
	while(Q--)
	{
		int L=read(),R=read();
		if(L>R)
			swap(L,R);
		if(buf[L]=='(')
			T.update(1,1,2*n-2,L,R-1,-2);
		else
			T.update(1,1,2*n-2,L,R-1,2);
		pr;
		swap(buf[L],buf[R]);
	}
	return 0;
}

CF1149D Abandoning Roads

  • 最小生成树 + 状压 dp.
  • 用 kruskal 做最小生成树的时候,会先考虑权值为 a 的边,那么可以先预处理出由 a 边连接出的联通块.
  • 从 1 到 p 跑最短路,每条 b 边会连接两个联通块,将联通块状压,就可以记录哪些联通块已经走过了.
  • 注意到对一个点数 ≤3 的联通块,不可能进入它后再走出去,因为这样的长度至少为 2b ,而它内部长度最长才 2a .所以可以不记这些联通块.状态数目在 O(2n/4m) 级别,就可以直接做了.

CF1149E Election Promises

  • 博弈论.
  • 结论: SGu=mex(SGv),sum(x)=⊕SGi=xhi , ⊕ 表示异或和.先手能胜,当且仅当 ∃x,sum(x)≠0​ .
  • 如果所有的 sum 都为 0 ,那么先手随意操作一次,都会使得有 sum 变为非 0 .然后后手再操作一次,所有 sum 又可以被修改为 0 :找到最大的 x , sum(x)>0 进行修改.

Gitalking ...