CF1149

Posted on | Edited on | Views:

$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(len_1,len_2,len_3)\leq n$ 是否成立.成立则为 $YES$ ,否则为 $NO$ .
  • 并不能 $O(q\cdot 250^3)$ 暴力 $dp$ .注意每次加一个字符时(假定加在第一个串上),前面的 $dp$ 值不会被影响,只需计算 $f(len_1+1,j,k)$ 这 $250^2$ 个状态.每次删字符时直接让 $len$ 减 $1$ 就可以了.下次会覆盖掉多余的值.
  • 时间复杂度 $O(q\cdot 250^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
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​$ .
  • 考虑两个点的距离为 $dep_u+dep_v-2dep_{lca}​$ ,在欧拉序中.和用 $RMQ​$ 做 $LCA​$ 一样,两个点的 $lca​$ 一定位于这两个点的中间,且深度最小.
  • 那么找直径就转化为找三个位置 $u\leq lca\leq v$ ,使得 $dep_u+dep_v-2dep_{lca}$ 最大.
  • 每次修改交换两个括号,中间那一段 $dep$ 都会 $+2/-2$ .于是用线段树维护每个位置的 $dep$ , $dep_l-2dep_i$ , $dep_r-2dep_i$ 的 $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$ 边会连接两个联通块,将联通块状压,就可以记录哪些联通块已经走过了.
  • 注意到对一个点数 $\leq 3$ 的联通块,不可能进入它后再走出去,因为这样的长度至少为 $2b$ ,而它内部长度最长才 $2a$ .所以可以不记这些联通块.状态数目在 $O(2^{n/4}m)$ 级别,就可以直接做了.

CF1149E Election Promises

  • 博弈论.
  • 结论: $SG_u=mex(SG_v),sum(x)=\oplus_{SG_i=x}h_i$ , $\oplus$ 表示异或和.先手能胜,当且仅当 $\exists x ,sum(x)\not=0​$ .
  • 如果所有的 $sum$ 都为 $0$ ,那么先手随意操作一次,都会使得有 $sum$ 变为非 $0$ .然后后手再操作一次,所有 $sum$ 又可以被修改为 $0$ :找到最大的 $x$ , $sum(x)>0$ 进行修改.