2022牛客多校2

发表于 分类于

link

对于 Alice 先手必胜的情况，Alice会取走尽可能多的石子使得最后异或和为零。

对于先手必败的情况，Alice会取走一个 $1$，使得剩下的情况满足大家都必须只能取走一个就可以了。

二分答案，然后求 ln 后用spfa判正环即可。

E. Falfa with Substring

设 $g_m$ 表示选 $m$ 个位置，其他地方任选的方案数。$f_m$ 表示恰好选 $m$ 个位置的方案数。

显然有：$g_m=\binom{n-2m}{m}26^{n-3m}$。

然后二项式反演一下就可以了。

F. NIO with String Game

离线，将Trie树建出来，然后将 s 在Trie上跑，需要记录当前 $s$ 在哪个位置，延伸出去多少个字母，延伸出去的第一个字母是什么。需要在Trie中快速查找从某个点出发往下 $k$ 步后到达的位置。可以使用 $26$ 次树剖或倍增解决。

之后用数据结构维护一下 dfs 序中的一些东西即可。

很坑的地方是 $k$ 是 long long，然而题意说只有 $10^9$。

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define VI vector<int>
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
template<class T>inline void read(T &x)
{
	x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	if(f) x=-x;
}
template<class T,class... V>
inline void read(T &a,V&... b){read(a); read(b...);}
#define CASET int ___;for(read(___);___--;)

const int N=4e5+5;
const int M=4e5+5;

#define lc (u<<1)
#define rc (u<<1|1)
#define ls lc,l,mid
#define rs rc,mid+1,r
int sum[M<<2];
void add(int u,int l,int r,int p,int x)
{
	sum[u]+=x;
	if(l==r) return;
	int mid=(l+r)>>1;
	if(p<=mid) add(ls,p,x);
	else add(rs,p,x);
}
int ask(int u,int l,int r,int L,int R)
{
	if(L>R) return 0;
	if(L<=l&&r<=R) return sum[u];
	int mid=(l+r)>>1,ans=0;
	if(L<=mid) ans+=ask(ls,L,R);
	if(mid<R) ans+=ask(rs,L,R);
	return ans;
}

const int S=26;
struct query{
	int opt; ll x; char c;
};
pair<int,int> as[M];
pair<int,int> hap[M];
namespace Trie{
	int ne[M][S],siz[M],cnt=1;
	void ins(const string &s,int x,int len,const vector<int> v)
	{
		int u=1;
		fo(i,1,len)
		{
			int c=s[i-1]-'a';
			if(!ne[u][c]) ne[u][c]=++cnt;
			if(i>x) hap[v[i-x-1]]={u,ne[u][c]};
			u=ne[u][c];
			if(i==x) siz[u]++;
		}
	}
	int dd[S][M],_dd[S][M],dw[S][M],tim,now;
	void cal(int u)
	{
		dd[now][u]=++tim;_dd[now][tim]=u;
		int v;
		if(v=ne[u][now]) cal(v),dw[now][u]=dw[now][v]+1;
		else dw[now][u]=0;
		fo(i,0,S-1) if(i!=now&&(v=ne[u][i])) cal(v);
	}
	struct node{
		int pos; ll k; int c;
		node() {}
		node(int _p,ll _k,int _c){pos=_p; k=_k; c=_c;}
	};
	struct node2{
		ll k; int c;
	};
	node f[M];
	node2 st[M];
	int top;
	node get(node x,node2 t)
	{
		if(x.k!=0ll) return node(x.pos,x.k+t.k,x.c);
		ll len=dw[t.c][x.pos];
		if(len>=t.k) return node(_dd[t.c][dd[t.c][x.pos]+t.k],0,-1);
		return node(_dd[t.c][dd[t.c][x.pos]+len],t.k-len,t.c);
	}
	void work(const string &t,vector<query> p)
	{
		fo(i,0,S-1) now=i,tim=0,cal(1);
		int m=p.size()-1;
		int n=t.length();
		int c;
		f[top=0]={1,0,-1};
		fo(i,1,n)
		{
			c=t[i-1]-'a';
			if(!top||st[top].c!=c) st[++top]={1ll,c};
			else st[top].k++;
			f[top]=get(f[top-1],st[top]);
		}
		fo(i,1,m)
		{
			if(p[i].opt==2)
			{
				for(;p[i].x;)
				{
					ll d=min(st[top].k,p[i].x);
					st[top].k-=d; p[i].x-=d;
					if(!st[top].k) top--;
				}
				if(top) f[top]=get(f[top-1],st[top]);
			}
			else if(p[i].opt==3)
			{
				c=p[i].c-'a';
				if(!top||st[top].c!=c) st[++top]={p[i].x,c};
				else st[top].k+=p[i].x;
				f[top]=get(f[top-1],st[top]);
			}
			else if(p[i].opt==4)
				as[i]={f[top].pos,f[top].c};
		}
	}
	int dfn[M],ppos[M][S];
	void dfs(int u,int pre)
	{
		dfn[u]=++tim;
		int v;
		fo(i,0,S-1)
		{
			ppos[u][i]=tim;
			if(v=ne[u][i]) dfs(v,u);
		}
	}
}
using Trie::ins;
using Trie::dfs;
using Trie::work;
using Trie::dfn;
using Trie::ppos;
using Trie::cnt;
string s[N],t;
int n,q;

vector<query> p;
int l[N],len[N];
vector<int> v[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>q>>t;
	p.resize(q+1);
	fo(i,1,n)
	{
		cin>>s[i];
		l[i]=len[i]=s[i].length();
	}
	fo(i,1,q)
	{
		int opt; ll x; string ch;
		cin>>opt;
		if(opt!=4) cin>>x; else x=0;
		if(opt==1||opt==3) cin>>ch;
		else ch="-";
		p[i]={opt,x,ch[0]};
		if(opt==1)
		{
			s[x]+=ch;
			v[x].pb(i);
			len[x]++;
		}
	}
	fo(i,1,n) ins(s[i],l[i],len[i],v[i]);
	Trie::work(t,p);
	Trie::tim=0;
	dfs(1,0);
	fo(i,1,cnt) add(1,1,cnt,dfn[i],Trie::siz[i]);
	fo(i,1,q)
	{
		int opt=p[i].opt;
		if(opt==1)
			add(1,1,cnt,dfn[hap[i].fi],-1),add(1,1,cnt,dfn[hap[i].se],1);
		else if(opt==4)
			printf("%d\n",ask(1,1,cnt,1,as[i].se==-1?dfn[as[i].fi]-1:Trie::ppos[as[i].fi][as[i].se]));
	}
	return 0;
}

由 Dilworth 定理，将最长上升子序列长度转换为最长不上升子序列的最大划分个数，由于是排列，不上升=下降。

那么答案为 $\lceil \sqrt{n} \rceil$。

随便构造。

H. Take the Elevator

对于上升的情况，设有 $a_i$ 个区间跨过了 $[i,i+1]$，那么至少需要 $\lceil \frac{a_i}{m} \rceil$ 次。下降的情况同理。

然后来个后缀最大值统计一下就好了。

需要离散化，离散化需要push_back一个 $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
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define VI vector<int>
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
template<class T>inline void read(T &x)
{
	x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	if(f) x=-x;
}
template<class T,class... V>
inline void read(T &a,V&... b){read(a); read(b...);}
#define CASET int ___;for(read(___);___--;)
const int N=4e5+5;
int n,m,fuck;
int a[N],b[N],c[N];
int f[N],g[N];
VI vec;
int main()
{
	read(n,m,fuck);
	vec.pb(1);
	fo(i,1,n)
	{
		read(a[i],b[i]);
		c[i]=(a[i]<b[i]);
		if(a[i]<b[i]) b[i]--;
		else a[i]--;
		vec.pb(a[i]),vec.pb(b[i]);
		vec.pb(a[i]+1); vec.pb(b[i]+1);
	}
	sort(all(vec));
	vec.resize(unique(all(vec))-vec.begin());
	fo(i,1,n) a[i]=lower_bound(all(vec),a[i])-vec.begin()+1;
	fo(i,1,n) b[i]=lower_bound(all(vec),b[i])-vec.begin()+1;
	fo(i,1,n)
		if(c[i])
			f[a[i]]++,f[b[i]+1]--;
		else
			g[b[i]]++,g[a[i]+1]--;
	int cnt=vec.size();
	fo(i,1,cnt) f[i]+=f[i-1];
	fo(i,1,cnt) g[i]+=g[i-1];
	fo(i,1,cnt) g[i]=max((g[i]+m-1)/m,(f[i]+m-1)/m);
	fd(i,cnt,1) g[i]=max(g[i],g[i+1]);
	ll ans=0;
	fo(i,1,cnt-1) ans+=1ll*g[i]*(vec[i]-vec[i-1]);
	printf("%lld\n",ans*2);
	return 0;
}

I. let fat tension

矩阵乘法结合律模板题。

最小二乘法模板题。

设 $f_{i,j,k}$ 表示考虑到第 $i$ 个，匹配到 $j$，左括号-右括号为 $k$ 的方案数。

随便DP。

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
const int N=205;
int n,m;
char s[N];
const int mod=1e9+7;
int f[N][N][N];
void add(int &x,int y){x+=y; if(x>=mod) x-=mod;}
int main()
{
	CASET
	{
		read(n,m);
		scanf("%s",s+1);
		fo(i,0,m) fo(j,0,n) fo(k,0,m) f[i][j][k]=0;
		int ne;
		f[0][0][0]=1;
		fo(i,1,m)
		{
			fo(j,0,n)
				fo(k,0,m)
					if(f[i-1][j][k])
					{
						ne=(j==n)?n:(s[j+1]=='('?j+1:j);
						if(k!=m) add(f[i][ne][k+1],f[i-1][j][k]);
						ne=(j==n)?n:(s[j+1]==')'?j+1:j);
						if(k) add(f[i][ne][k-1],f[i-1][j][k]);
					}
		}
		printf("%d\n",f[m][n][0]);
	}
	return 0;
}

直接从前往后推就好了。。。

用个滚动数组优化一下即可。