| Solved | A | B | C | D | E | F | G | H | I | J | K |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 11/12 | O | . | Ø | Ø | Ø | O | Ø | O | Ø | O | Ø |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A
题目描述
有 $n\le 1e5$ 个长度为 $100$ 的字符串，字符集大小 $64$。对于每一个 $i$ ，找到一个大小最小的前缀集合 $S$，满足前 $i$ 个字符串均能在 $S$ 中找到某个前缀，且后面的所有字符串均不能在 $S$ 中找到前缀。
32M 内存限制。
解题思路
32M 内存限制让普通的 trie 开不下，考虑暴力求解。
维护这个集合 $S$，加入一个字符串的时候尝试合并，如果 $len(lcp)>0$ 且该 $lcp$ 不为后 $n-i$ 个字符串中任意一个的前缀时，则可以合并。不停暴力尝试合并即可。
AC代码
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
typedef long long ll;
using namespace std;
char s[N][101];
char ss[101],sss[101];
struct S{
char* s;
S(char*_s){s=_s;}
bool operator<(const S &a)const{
return strcmp(s,a.s)<0;
}
};
int getlcp(char* s1,char* s2){
int i;
for(i=0;;i++)if(s1[i]!=s2[i]||(!s1[i]&&!s2[i]))return i;
}
int main(){
int i,j,n;
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%s",s[i]);
set<S>s1,s2;
for(i=0;i<n;i++)s2.insert(S(s[i]));
for(i=0;i<n;i++){
S tmp=S(s[i]),tmp2=S(ss);
s2.erase(tmp);
while(1){
auto it1=s1.lower_bound(tmp),it2=it1,it=it1;
int lcp1=-1,lcp2=-1;
if(it1!=s1.end()){
lcp1=getlcp(tmp.s,it1->s);
}
if(it!=s1.begin()){
it2=--s1.lower_bound(tmp);
lcp2=getlcp(tmp.s,it2->s);
}
int lcp=max(lcp1,lcp2);
if(lcp==lcp1)it=it1;
else it=it2;
if(lcp<=0){
s1.insert(tmp);
break;
}
for(j=0;tmp.s[j];j++)ss[j]=tmp.s[j];
ss[lcp]='\0';
//tmp.s[lcp]='\0';
auto its2=s2.lower_bound(tmp2);
if(its2!=s2.end()&&getlcp(tmp2.s,its2->s)==lcp){
s1.insert(tmp);
break;
}
s1.erase(it);
strcpy(s[i],ss);
}
printf("%d\n",s1.size());
// for(auto q:s1)printf("%s ",q.s);
// puts("");
}
return 0;
}
B
题目描述
解题思路
AC代码
2
C
题目描述
有 $n\le 3e4$ 对男士女士，每个女士有 $k\le 100$ 个不喜欢的男士，要找一个完美匹配。
解题思路
以下不是正解！正解还是得看题解。
先对被讨厌比较多的 $x$ 个男士匈牙利暴力配对，然后剩余部分猜测可以根据霍尔定理必定存在完美匹配。设被讨厌次数 $\ge n-d$ 的点都进行暴力配对，想要最小化 $d$，让尽量少的点跑暴力的匈牙利。
具体证明：总边数 $100n$，设选择了 $p$ 个剩余男士，则每个男士最少和 $d$ 个女士之间有连边。设如何不满足霍尔定理：大小为 $d+1$ 的集合的男士都连了同样的 $d$ 个女士，则至少需要 $(d+1)\times (n-d)$，要 $kn\ge (d+1)(n-d)$，再稍微调大一些就可以保证贪心匹配的时候能不会去掉本应是解的解，调成 $d=200$ 就过了。
AC代码
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
typedef long long ll;
using namespace std;
int mt[N],vis[N],ind[N],p[N];
vector<int>dislike[N],G[N];
set<pii>dislikes;
set<int>single_lady;
int dfs(int p,int t){
for(auto q:G[p]){
if(vis[q]!=t){
vis[q]=t;
if(!mt[q]||dfs(mt[q],t))return mt[q]=p;
}
}
return 0;
}
int main(){
int i,j,n,k,x;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&k);
while(k--){
scanf("%d",&x);
ind[x]++;
dislike[i].pb(x);dislikes.insert(mp(i,x));
}
}
for(i=1;i<=n;i++)p[i]=i;
sort(p+1,p+1+n,[&](const int&a,const int&b){return ind[a]>ind[b];});
// match high ind ppl
int mx=0,match=0;
for(i=1;i<=n;i++)if(ind[p[i]]>=n-200)mx=i;
for(i=1;i<=mx;i++)for(j=1;j<=n;j++)if(!dislikes.count(mp(j,p[i])))G[p[i]].pb(j);
for(i=1;i<=mx;i++)if(dfs(p[i],i))match++;
if(match!=mx)return printf("-1"),0;
// match others
for(i=1;i<=n;i++)if(!mt[i])single_lady.insert(i);
for(i=mx+1;i<=n;i++){
int flag=0;
for(auto q:single_lady){
if(!dislikes.count(mp(q,p[i]))){
flag=1;
mt[q]=p[i];
single_lady.erase(q);
break;
}
}
if(!flag)assert(false);
}
for(i=1;i<=n;i++)printf("%d ",mt[i]);
return 0;
}
D
题目描述
问所有含有 $n\le 500$ 个点的带标号树直径之和。
解题思路
对这种问题，要找的就是一种能够快速计数的方式。最开始我们考虑的是枚举根节点，讨论左右子树的直径和连出来的长度，光状态数就是 $O(n^3)$，难以进一步优化。
对于直径，可以直接考虑直径的中心。如果直径 $d$ 是奇数，中心是一条边，那么相当于连接了两棵深度为 $\frac {d-1}2$ 的树；否则相当于一个深度为 $\frac d2$ 的树，且至少含有两个深度为 $\frac d2-1$ 的子树。
设 $f_{n,i}$ 表示 $n$ 个点，深度（不是直径！）为 $i$ 的树有多少种。但这不好转移，考虑设 $g_{n,i}$ 表示 $n$ 个点，深度 $\le i$ 的树有多少种，再用容斥计算 $f$。
转移的时候，每次将根节点连上一个深度 $\le i-1$ 的子树，编号与原树编号进行一下不重复的插入。考虑如何计数才能不重不漏。
将一棵树的编号拉成一个序列，要求最后一个序号必须位于最后加入的子树，即可保证不重不漏。设子树分别表示为 $0,1,2,3$ （忽略内部编号顺序）并顺序加入，根表示为 $9$，形成过程如下：
$\begin{aligned}&009\\ \rightarrow&10110119\\ \rightarrow&12011012212229\\ \rightarrow&120131013221232239\end{aligned}$
最后，当整个树被加到其他树中时，根节点可以插到整个序列中任意一个位置。
于是，有转移：$g_{n,i}=\sum_{k=1}^{i-1}g_{n-k,i}g_{k,i-1}k\binom{i-2}{k-1}$
最后统计答案的时候用类似的编号方式处理即可。
AC代码
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
typedef long long ll;
using namespace std;
ll c[N][N],mod,n;
ll f[N][N],g[N][N];
int main(){
int i,j,k,d;
scanf("%lld%lld",&n,&mod);
c[0][0]=1;
for(i=1;i<N;i++){
c[i][0]=1;
for(j=1;j<=i;j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
f[1][0]=1;
for(j=0;j<=n;j++)g[1][j]=1;
for(i=2;i<=n;i++){
for(j=1;j<=i;j++)
for(k=1;k<i;k++)
g[i][j]=(g[i][j]+g[i-k][j]*g[k][j-1]%mod*k%mod*c[i-2][k-1]%mod)%mod;
for(;j<=n;j++)
g[i][j]=g[i][j-1];
for(j=1;j<=n;j++)
f[i][j]=(g[i][j]-g[i][j-1]+mod)%mod;
}
ll ans=0;
for(d=1;d<=n;d++){
if(d&1){
for(i=1;i<n;i++)
// i*n-i: label; c_{n-1}{i}: insert right subtree and let 1 in right subtree
(ans+=d*f[i][(d-1)/2]%mod*f[n-i][(d-1)/2]%mod
*c[n-1][i]%mod*i%mod*(n-i)%mod)%=mod;
}else{
// all d/2
(ans+=d*f[n][d/2]%mod
*n%mod)%=mod;
for(i=1;i<n;i++)
(ans+=mod-d*g[n-i][d/2-1]%mod*f[i][d/2-1]%mod
*c[n][i]%mod*i%mod*(n-i)%mod)%=mod;
}
}
printf("%lld",ans);
return 0;
}
E
题目描述
给一个 $k\le 3e5$ 维的国际象棋，其大小用向量 $\vec{a}$ 表示。初始时，有一个棋子在 $\vec{x}$，它可能是王、后、马、车、象。问他能一步走到的格点数（不能跳出棋盘）；$q$ 次移动，每次移动后问他一步能走到的格点数。
王：每维可以任意走 $-1,0,1$ 步。
后：可以选择任意多维度走任意多相同步数。
马：可以选择两维，一维走 $-1,1$ 步，一维走 $-2,2$ 步。
车：任选一维走任意多步。
象：任选两维走任意多相同步数。
要求每一步都需要移动，即不能停在原地。
解题思路
车的答案不变，为棋盘大小 $\sum_{i}a_i-1$。
王维护一下在 $x_i=1$ 以及 $x_i=a_i$ 的个数即可快速求解。
马维护一下每个维度能不能 $-2,-1,+1,+2$，也可快速求解。
象和后维护起来稍麻烦一些。
对于象来说，设每一维可以向左、右走的步数分别为 $(x_i,y_i)$，则象选择两维，固定一维 $(x_i,y_i)$，对于所有的 $j\ne i$ 计算一下 $i,j$ 维的贡献：
$\sum_jmin(x_i,x_j)+min(x_i,y_j)+min(y_i,x_j)+min(y_i,y_j)$
静态求可以用 set 存一下 $x_i,y_i$ 分别有哪些，询问的时候二分就是一个前缀和+后缀个数和。但是要动态维护，用线段树维护一下即可。
同样的思路处理后，相当于是选一个集合的前缀最小值，维护一个当前最小值为 $i$ 的方案数，则 $(x,y)$ 对其影响可以分类讨论，是一个区间乘 $2$ 或者 $3$。同样线段树维护一下即可。
AC代码 - by nikkukun & Potassium
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
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int, int> pint;
typedef tuple<int, int, int> tint;
const int N = 1e6 + 5;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
ll qpow(ll bas, int t) {
ll ret = 1;
while (t) {
if (t & 1) ret = ret * bas % MOD;
bas = bas * bas % MOD;
t >>= 1;
}
return ret;
}
namespace Queen {
const int M = N * 4 + 5;
const int INV2 = (MOD + 1) / 2;
const int INV3 = (MOD + 1) / 3;
const int INV4 = 1LL * INV2 * INV2 % MOD;
const int SUM = 1LL * (1 + 1000000) * 1000000 / 2 % MOD;
struct SegTree {
int t[M], lazy[M];
pint prod[M];
int dd[M];
void build(int o, int L, int R) {
lazy[o] = 1;
if (L == R) {
t[o] = 0;
prod[o] = {1, 1};
dd[o] = 1;
return;
}
int M = (L + R) / 2;
build(lch, L, M);
build(rch, M + 1, R);
}
void tag(int o, int w) {
t[o] = 1LL * t[o] * w % MOD;
prod[o].se = 1LL * prod[o].se * w % MOD;
lazy[o] = 1LL * lazy[o] * w % MOD;
}
void pushdown(int o) {
if (lazy[o] == 1) return;
tag(lch, lazy[o]);
tag(rch, lazy[o]);
lazy[o] = 1;
}
void maintain(int o) {
t[o] = (t[lch] + t[rch]) % MOD;
}
void add(int o, int L, int R, int pos, int w, int d) {
if (L == R) {
prod[o].fi = 1LL * prod[o].fi * w % MOD;
dd[o] = (dd[o] + d) % MOD;
t[o] = 1LL * L * (prod[o].fi - dd[o]) % MOD * prod[o].se % MOD;
return;
}
pushdown(o);
int M = (L + R) / 2;
if (pos <= M) add(lch, L, M, pos, w, d);
if (M + 1 <= pos) add(rch, M + 1, R, pos, w, d);
maintain(o);
}
void mul(int o, int L, int R, int qL, int qR, int w) {
if (qL <= L && R <= qR) {
tag(o, w);
return;
}
pushdown(o);
int M = (L + R) / 2;
if (qL <= M) mul(lch, L, M, qL, qR, w);
if (M + 1 <= qR) mul(rch, M + 1, R, qL, qR, w);
maintain(o);
}
int query() {
return (t[1] + MOD) % MOD;
}
};
SegTree seg;
void modify(int x, int y, int op) {
if (x > y) swap(x, y);
if (x < y) {
seg.add(1, 0, 1e6, x, op == 1 ? 2 : INV2, 0);
seg.add(1, 0, 1e6, y, op == 1 ? 2 : INV2, 0);
if (x != 0)
seg.mul(1, 0, 1e6, 0, x - 1, op == 1 ? 3 : INV3);
if (y != 0)
seg.mul(1, 0, 1e6, x, y - 1, op == 1 ? 2 : INV2);
seg.add(1, 0, 1e6, x, op == 1 ? (3LL * INV4 % MOD) : (4LL * INV3 % MOD), 0);
} else {
seg.add(1, 0, 1e6, x, op == 1 ? 3 : INV3, 0);
if (x != 0)
seg.mul(1, 0, 1e6, 0, x - 1, op == 1 ? 3 : INV3);
}
}
void solve(int n, int q) {
vector<int> lim(n + 1), st(n + 1);
for (int i = 1; i <= n; i++) {
scanf("%d", &lim[i]);
}
seg.build(1, 0, 1e6);
vector<pint> rng(n + 1);
for (int i = 1; i <= n; i++) {
scanf("%d", &st[i]);
rng[i] = {lim[i] - st[i], st[i] - 1};
auto pr = rng[i];
auto x = pr.first, y = pr.second;
modify(x, y, 1);
}
printf("%d\n", seg.query());
while (q--) {
int d;
scanf("%d", &d);
while (d--) {
int dim, det;
scanf("%d%d", &dim, &det);
auto pr = rng[dim];
auto x = pr.first, y = pr.second;
modify(x, y, -1);
rng[dim].fi -= det;
rng[dim].se += det;
x = rng[dim].fi;
y = rng[dim].se;
modify(x, y, 1);
}
printf("%d\n", seg.query());
}
}
}; // namespace Queen
namespace Rook {
void solve(int n, int q) {
int ans = 0;
vector<int> lim(n + 1), st(n + 1);
for (int i = 1; i <= n; i++) {
scanf("%d", &lim[i]);
ans = (ans + lim[i] - 1) % MOD;
}
for (int i = 1; i <= n; i++) {
scanf("%d", &st[i]);
}
printf("%d\n", ans);
while (q--) {
int d;
scanf("%d", &d);
while (d--) {
int dim, det;
scanf("%d%d", &dim, &det);
}
printf("%d\n", ans);
}
}
} // namespace Rook
namespace Bishop {
const int M = N * 4 + 5;
int L[M], R[M], s[M], cnt[M];
int _n;
void build(int p, int l, int r) {
L[p] = l;
R[p] = r;
s[p] = 0;
cnt[p] = 0;
if (l == r) return;
build(p << 1, l, (l + r) / 2);
build(p << 1 | 1, ((l + r) >> 1) + 1, r);
}
// l \in [0, ]
void modify(int p, int l, int x) {
if (L[p] > l + 1 || R[p] < l + 1) return;
if (L[p] == R[p]) {
if (x)
(s[p] += l) %= MOD, cnt[p]++;
else
(s[p] -= l) %= MOD, cnt[p]--;
return;
}
modify(p << 1, l, x);
modify(p << 1 | 1, l, x);
s[p] = (s[p << 1] + s[p << 1 | 1]) % MOD;
cnt[p] = (cnt[p << 1] + cnt[p << 1 | 1]);
}
pii query(int p, int l, int r) {
if (L[p] > r + 1 || R[p] < l + 1) return mp(0, 0);
if (L[p] >= l + 1 && R[p] <= r + 1) return mp(s[p], cnt[p]);
auto pl = query(p << 1, l, r);
auto pr = query(p << 1 | 1, l, r);
return mp((pl.fi + pr.fi) % MOD, (pl.se + pr.se) % MOD);
}
int calc(int x) {
auto pr = query(1, 0, x);
int sum = pr.fi, cnt = pr.se;
return (sum + (2LL * _n - cnt - 2) * x) % MOD;
}
void solve(int n, int q) {
ll ans = 0;
_n = n;
vector<int> lim(n + 1), st(n + 1);
int INV2 = (MOD + 1) / 2;
build(1, 1, 1000001);
for (int i = 1; i <= n; i++) {
scanf("%d", &lim[i]);
}
for (int i = 1; i <= n; i++) {
scanf("%d", &st[i]);
modify(1, st[i] - 1, 1);
modify(1, lim[i] - st[i], 1);
// printf("modify: %d\n",st[i]-1);
// printf("modify: %d\n",lim[i]-st[i]);
}
for (int i = 1; i <= n; i++) {
int x = st[i] - 1;
int y = lim[i] - st[i];
modify(1, x, 0);
modify(1, y, 0);
(ans += calc(x) + calc(y)) %= MOD;
modify(1, x, 1);
modify(1, y, 1);
}
ans = ans * INV2 % MOD;
printf("%lld\n", (ans + MOD) % MOD);
while (q--) {
int d;
scanf("%d", &d);
while (d--) {
int dim, det;
scanf("%d%d", &dim, &det);
int x = st[dim] - 1, y = lim[dim] - st[dim];
modify(1, x, 0);
modify(1, y, 0);
ll tmp = -calc(x) - calc(y);
st[dim] += det;
x = st[dim] - 1, y = lim[dim] - st[dim];
tmp += calc(x) + calc(y);
modify(1, x, 1);
modify(1, y, 1);
(ans += tmp) %= MOD;
}
printf("%lld\n", (ans + MOD) % MOD);
}
}
} // namespace Bishop
namespace Knight {
struct T {
// a +1, b +2, c -1, d -2
int a, b, c, d;
} t[N];
const int mod = 998244353;
ll sa = 0, sb = 0, sc = 0, sd = 0;
ll sab = 0, sad = 0, scb = 0, scd = 0;
void add(T x, int flag) {
sa += flag * x.a;
sb += flag * x.b;
sc += flag * x.c;
sd += flag * x.d;
sab += flag * x.a * x.b;
sad += flag * x.a * x.d;
scb += flag * x.c * x.b;
scd += flag * x.c * x.d;
}
T calc(int st, int lim) {
T t;
t.a = t.b = t.c = t.d = 0;
if (st >= 2) t.c = 1;
if (st >= 3) t.d = 1;
if (st <= lim - 1) t.a = 1;
if (st <= lim - 2) t.b = 1;
return t;
}
ll getans() {
ll ans = 0;
ans = (sa * sb + sa * sd + sc * sb + sc * sd) % mod;
(ans -= sab + sad + scb + scd) %= mod;
return (ans + mod) % mod;
}
void solve(int n, int q) {
ll ans = 0;
vector<int> lim(n + 1), st(n + 1);
for (int i = 1; i <= n; i++) {
scanf("%d", &lim[i]);
}
for (int i = 1; i <= n; i++) {
scanf("%d", &st[i]);
t[i] = calc(st[i], lim[i]);
add(t[i], 1);
}
printf("%lld\n", getans());
while (q--) {
int d;
scanf("%d", &d);
while (d--) {
int dim, det;
scanf("%d%d", &dim, &det);
add(t[dim], -1);
st[dim] += det;
t[dim] = calc(st[dim], lim[dim]);
add(t[dim], 1);
}
printf("%lld\n", getans());
}
}
} // namespace Knight
namespace King {
const int mod = 998244353;
int a0 = 0, a1 = 0, a2 = 0, _n;
ll pw3[N], pw2[N];
void init() {
pw3[0] = pw2[0] = 1;
int i;
for (i = 1; i < N; i++) pw3[i] = pw3[i - 1] * 3 % mod, pw2[i] = pw2[i - 1] * 2 % mod;
}
ll getans() {
ll ans = pw3[_n - a0 - a1 + a2] * pw2[a0 + a1 - 2 * a2] - 1;
return (ans % mod + mod) % mod;
}
void add(int st, int lim, int flag) {
if (st == 1) a1 += flag;
if (st == lim) a0 += flag;
if (st == 1 && st == lim) a2 += flag;
}
void solve(int n, int q) {
ll ans = 0;
init();
_n = n;
vector<int> lim(n + 1), st(n + 1);
for (int i = 1; i <= n; i++) {
scanf("%d", &lim[i]);
}
for (int i = 1; i <= n; i++) {
scanf("%d", &st[i]);
add(st[i], lim[i], 1);
}
printf("%lld\n", getans());
while (q--) {
int d;
scanf("%d", &d);
while (d--) {
int dim, det;
scanf("%d%d", &dim, &det);
add(st[dim], lim[dim], -1);
st[dim] += det;
add(st[dim], lim[dim], 1);
}
printf("%lld\n", getans());
}
}
} // namespace King
int main() {
int n, q;
scanf("%d%d", &n, &q);
static char s[N];
scanf("%s", s);
if (strcmp(s, "King") == 0) King::solve(n, q);
if (strcmp(s, "Queen") == 0) Queen::solve(n, q);
if (strcmp(s, "Rook") == 0) Rook::solve(n, q);
if (strcmp(s, "Bishop") == 0) Bishop::solve(n, q);
if (strcmp(s, "Knight") == 0) Knight::solve(n, q);
return 0;
}
F
题目描述
给一个 $n\le 1e6$ 的括号序列， 左括号代表入栈一个元素，栈右括号代表出栈一个元素。对于每个入栈的元素分配一个颜色，使得每次刚刚入栈结束后的栈内元素的颜色状态唯一。给定所有入栈元素初始的颜色，可以将元素重新排序，求合法的序列。
解题思路
solved by nikkukun
相当于构建一棵树，入栈则增加新节点，出栈则退回到父节点。于是贪心的将出现次数多的颜色放在靠近根节点的位置即可。
AC代码 - by nikkukun
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
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int, int> pint;
typedef tuple<int, int, int> tint;
const int N = 2e6 + 5;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
int top;
int pa[N];
vector<int> a[N];
char s[N];
int tmp[N];
priority_queue<pint> cnt;
int ans[N];
bool solve(int u) {
if (cnt.size() < a[u].size())
return false;
vector<int> del;
for (auto v: a[u]) {
auto o = cnt.top();
cnt.pop();
ans[v] = o.se;
}
for (auto v: a[u]) {
if (tmp[ans[v]] != 0) {
tmp[ans[v]]--;
cnt.push({tmp[ans[v]], ans[v]});
}
}
for (auto v: a[u]) {
if (!solve(v)) return false;
}
return true;
}
int main() {
int n;
scanf("%d", &n);
scanf("%s", s + 1);
int o = 0;
for (int i = 1; i <= 2 * n; i++) {
if (s[i] == '(') {
int nxt = ++top;
a[o].push_back(nxt);
pa[nxt] = o;
o = nxt;
} else {
o = pa[o];
}
}
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
tmp[x]++;
}
for (int i = 0; i < N; i++)
if (tmp[i] != 0)
cnt.push({tmp[i], i});
bool flag = solve(0);
if (!flag) {
printf("NO\n");
} else {
printf("YES\n");
for (int i = 1; i <= n; i++)
printf("%d ", ans[i]);
printf("\n");
}
// cout << 1.0 * clock() / CLOCKS_PER_SEC << endl;
return 0;
}
G
题目描述
$n$ 个人围在一圈玩游戏，每个人随机选定一个人，同时开枪，每人命中的概率均为 $p$。问一局结束后，$i$ 个人活着的概率是多少。
解题思路
设最多死了 $S$ 里面的人的概率为 $g_S$，则枚举 $S$ 集合里、外的人该怎么打，容易得到
$g_S=(p\frac{|S|-1}{n-1}+q)^{|S|}(p\frac{|S|}{n-1}+q)^{n-|S|}$，仅与集合大小有关，设为 $h_{|S|}=g_S$。
于是恰好 $S$ 全部死亡的概率
$f_S=\sum_{T\subseteq S}(-1)^{|S|-|T|}g_T=\sum_{|T|=0}^{|S|}(-1)^{|S|-|T|}\binom{|S|}{|T|}h_{|T|}$
恰好 $x$ 个人死亡的概率
$p_x=\binom{n}{x}\sum_{i=0}^{x}(-1)^{x-i}\frac{x!}{i!(x-i)!}h_i$，是卷积形式，NTT 优化一下。
AC代码
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
typedef long long ll;
using namespace std;
const int mod=998244353;
ll qp(ll a,int p){
ll ans=1;
for(;p;p>>=1,a=a*a%mod)if(p&1)ans=ans*a%mod;
return ans;
}
namespace NTT{
const int g=3,invg=332748118;
int rev[M+5];
int mx,lim;
int w[3][M+5];
void fft_prepare(int _mx,int _lim){
int i;
mx=_mx;lim=_lim;
for(i=0;i<lim;i++)rev[i]=rev[i>>1]>>1|((i&1)<<(mx-1));
}
void fft_prepare(int n){
int i;
mx=0,lim=1;
while(lim<n)lim<<=1,mx++;
fft_prepare(mx,lim);
}
inline void ntt(int *a,int len,int flag){
int i,mid,j;
int inv=qp(len,mod-2);
for(i=0;i<len;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
for(mid=1;mid<len;mid<<=1){
ll gn=qpow(flag==1?g:invg,(mod-1)/(mid<<1));
for(i=0;i<len;i+=(mid<<1)){
ll g0=1;
for(j=0;j<mid;++j,g0=g0*gn%mod){
int x=a[i+j],y=g0*a[i+j+mid]%mod;
a[i+j]=(x+y)%mod,a[i+j+mid]=(x-y+mod)%mod;
}
}
}
if(flag==-1)for(i=0;i<len;i++)a[i]=1LL*a[i]*inv%mod;
}
void conv(int *x,int *y,int *z,int n,int m,int mod){
assert(mod==998244353);
int i;
static int X[M+5],Y[M+5];
for(i=0;i<=n;i++)X[i]=(x[i]+mod)%mod;
for(;i<lim;i++)X[i]=0;
for(i=0;i<=m;i++)Y[i]=(y[i]+mod)%mod;
for(;i<lim;i++)Y[i]=0;
ntt(X,lim,1);
ntt(Y,lim,1);
for(i=0;i<lim;i++)X[i]=1LL*X[i]*Y[i]%mod;
ntt(X,lim,-1);
for(i=0;i<lim;i++)z[i]=X[i];
}
}
int x[M],y[M],z[M];
int fac[M],inv[M];
int main(){
int i,n,a,b;
fac[0]=1;
for(i=1;i<M;i++)fac[i]=fac[i-1]*1LL*i%mod;
inv[M-1]=qp(fac[M-1],mod-2);
for(i=M-2;i>=0;i--)inv[i]=inv[i+1]*(i+1LL)%mod;
ll p,q;
scanf("%d%d%d",&n,&a,&b);
p=a*qp(b,mod-2)%mod;
q=1-p;
int invn=qp(n-1,mod-2);
for(i=0;i<=n;i++){
x[i]=qp((q+p*(i-1LL)%mod*invn)%mod,i);
x[i]=1LL*x[i]*qp((q+1LL*p*i%mod*invn)%mod,n-i)%mod;
x[i]=1LL*x[i]*inv[i]%mod;
x[i]=(x[i]+mod)%mod;
y[i]=(i&1)?mod-1:1;
y[i]=1LL*y[i]*inv[i]%mod;
}
NTT::fft_prepare(n+n+3);
NTT::conv(x,y,z,n+1,n+1,mod);
for(i=n;i>=0;i--){
int g=(1LL*z[i]*fac[i]%mod+mod)%mod;
g=1LL*g*fac[n]%mod*inv[i]%mod*inv[n-i]%mod;
printf("%d\n",g);
}
return 0;
}
H
题目描述
给一个 $n$ 维超立方体，欧氏距离 $1$ 的点之间连边，求 $01$ 染色，使得每个点周围与自己同色的点数不超过 $\lceil\sqrt n\rceil$。
解题思路
直接根据 $1$ 的个数黑白染色即可。
AC代码
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
typedef long long ll;
using namespace std;
int main(){
int i,n;
scanf("%d",&n);
for(i=0;i<1<<n;i++){
if(__builtin_popcount(i)%2)printf("0");
else printf("1");
}
return 0;
}
I
题目描述
在 H 题的基础上，要求染为白色的点数与染为黑色的点数不同。
解题思路
在上一题基础上，要选出一个奇数大小的集合并翻转颜色，要求两个集合间的二分图最大度数不超过 $\lceil\sqrt n\rceil$。以 $\lceil \sqrt n\rceil$ 为大小进行分块，如果有一块全为 $0$ 就翻转。则相邻同色的情况当且仅当有一块一个数 $a$ 全为 $0$ 一个数 $b$ 仅有一个 $1$ 且 $b$ 没有任何一块全为 $0$ ，符合条件。
证明奇偶性符合条件：
0 当且仅当：存在一块全为 0 且 1 个数为奇数；或不存在一块全为 0 且个数为偶数。
1 当且仅当：存在一块全为 0 且 1 个数为偶数；或不存在一块全为 0 且个数为奇数。
设个数分别为 $A,B,C,D$，有 $A+D=B+C=2^{n-1}$，$A+C$ 为奇数（考虑 $00,01,10$ 但不能选 $11$）。于是满足条件。
AC代码
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
typedef long long ll;
using namespace std;
int main(){
int i,j,n,_n;
scanf("%d",&n);_n=ceil(sqrt(n));
for(i=0;i<1<<n;i++){
int c=__builtin_popcount(i)%2,f=0;
for(j=0;j<n;j+=_n)if(!((i>>j)&((1<<_n)-1)))f=1;
printf("%d",c^f);
}
return 0;
}
J
题目描述
给一个 $n\le 2e5$ 点的凸多边形，外面有 $m\le 2e5$ 个点光源，问至少要多少个点才能照亮整个凸多边形，并输出方案。
解题思路
solved by nikkukun
对每个点光源可以求两凸包切点，于是变成了最小区间的环覆盖，去除被包含的小区间后固定右端点能延伸的长度是固定的，将环拆成长度 $2n$ 的链后可以倍增处理，然后枚举左端点求解。
AC代码 - by nikkukun
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
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int, int> pint;
typedef tuple<int, int, int> tint;
const int N = 4e5 + 5;
const int K = 20 + 2;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
struct Point {
ll x, y;
Point operator-(Point b) const {
return (Point){x - b.x, y - b.y};
}
ll operator*(Point b) const {
return x * b.y - y * b.x;
}
};
ll onLeft(Point p, Point a, Point b) {
return (b - a) * (p - a);
}
pint tangentsConvex(Point P, vector<Point> &p, int np) {
int left = 0, right = 0;
for (int k = 20; k >= 0; k--) {
int delta = (1 << k) % np;
if (onLeft(P, p[left], p[(left + delta) % np]) <= 0) {
left += delta;
left %= np;
}
if (onLeft(P, p[left], p[(left + np - delta) % np]) <= 0) {
left += np - delta;
left %= np;
}
if (onLeft(P, p[right], p[(right + delta) % np]) >= 0) {
right += delta;
right %= np;
}
if (onLeft(P, p[right], p[(right + np - delta) % np]) >= 0) {
right += np - delta;
right %= np;
}
}
return make_pair(left, right);
}
vector<Point> ch;
Point pts[N];
int id[N];
int nxt[N][K];
int main() {
ios::sync_with_stdio(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
ch.push_back({x, y});
}
vector<tint> seg;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
pts[i] = {x, y};
auto [r, l] = tangentsConvex(pts[i], ch, ch.size());
if (l <= r) {
seg.push_back({l, r - 1, i});
seg.push_back({l + n, r - 1 + n, i});
} else {
seg.push_back({l, r - 1 + n, i});
}
}
sort(all(seg));
int right = 0, rightId = 0;
int p = 0;
for (int i = 0; i < 2 * n; i++) {
while (p < seg.size() && get<0>(seg[p]) <= i) {
if (get<1>(seg[p]) + 1 > right) {
right = get<1>(seg[p]) + 1;
rightId = get<2>(seg[p]);
}
p++;
}
if (i < right) {
nxt[i][0] = right;
id[i] = rightId;
}
}
for (int i = 2 * n - 1; i >= 0; i--) {
for (int k = 1; k < K; k++)
nxt[i][k] = nxt[nxt[i][k - 1]][k - 1];
}
int ans = INF, ansSt = 0;
for (int st = 0; st < n; st++) {
int now = 0;
int o = st;
for (int k = K - 1; k >= 0; k--)
if (nxt[o][k] != 0 && nxt[o][k] < st + n) {
o = nxt[o][k];
now += 1 << k;
}
o = nxt[o][0];
now++;
if (o != 0 && o >= st + n && now < ans) {
ans = now;
ansSt = st;
}
}
if (ans == INF) {
cout << -1 << endl;
} else {
vector<int> vec;
int o = ansSt;
while (o < ansSt + n) {
vec.push_back(id[o]);
o = nxt[o][0];
}
cout << vec.size() << endl;
for (auto x: vec)
cout << x << ' ';
cout << endl;
}
return 0;
}
K
题目描述
在一个 $n\times m(n,m\le 5e5)$ 的格点中，初始在 $(a,b)$，每次可以左右前后移动一格，但不能移出边界，问走 $t\le 5e5$ 步的方案数。
解题思路
可以把两维分开计算，设 $x$ 方向走 $i$ 步的方案数为 $f_i$，$y$ 方向走 $j$ 步的方案数为 $g_j$，则答案为 $\sum_{i=0}^{t}f_ig_{t-i}\binom{t}{i}$。于是考虑计算 $f_i$，即在 $x$ 轴上初始在 $a$，范围 $[1,n]$ 走 $i$ 步的方案数。
设 $h_{i,j}$ 表示走了 $i$ 步，最后位置在 $j$ 的方案数，有
$\begin{aligned}h_{0,j}&=[j=a]\\h_{i,j}&=[j> 1]h_{i-1,j-1}+[j<n]h_{i-1,j+1}\end{aligned}$
则 $f_i=\sum_{j}h_{i,j}$。这样做 $dp$ 是 $O(nt)$ 的。
考虑 $f$ 的递推，有 $f_i=2f_{i-1}-h_{i-1,1}-h_{i-1,n}$，这启示我们如果能快速算出 $h_{i,1}$ 和 $h_{i,n}$，那么就可以 $O(t)$ 递推出来 $f$。考虑如何求 $h_{i,1}$。
借用 $Catalan$ 数的策略：初始在 $(0,a)$，每一步从 $(x,y)$ 走到 $(x+1,y+1)$ 或 $(x+1,y-1)$，限制就变成了折线始终在 $[1,n]$ 内， $(0,a)\rightarrow(i,1)$ 的方案数。
如果不考虑限制，很明显方案数为 $\binom{i}{\frac{i+(a-1)}{2}}$。
考虑减掉先跨过上界、先跨过下界两种的方案数。
先考虑下界 $1$ 的限制，假设某时刻跨越了下界 $1$ 到达 $(j,0)$，可以将 $[j,i]$ 的折线翻转到 $y<0$ 半轴，即 $(0,a)\rightarrow (i,-1)$ ，则跨过下界的贡献可以在答案中减掉。
但是先跨过上界，再跨过下界的也会被计算到，因此需要加回上-下的贡献；但下-上-下的贡献会被多计算，因此需要减掉下-上-下贡献；如此往复容斥。一共会进行 $\frac tn$ 次翻转。
因此， $n\le \sqrt t$ 时，使用暴力 $dp$，否则使用容斥，最终复杂度 $O(t\sqrt t)$。
AC代码
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
typedef long long ll;
using namespace std;
const int mod=998244353;
int f[N],g[N],fac[N],inv[N];
ll qp(ll a,int p){
ll ans=1;
for(;p;p>>=1,a=a*a%mod)if(p&1)ans=ans*a%mod;
return ans;
}
int c(int n,int m){
assert(n>=m&&n<N&&m>=0);
return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int calc(int dx,int dy){
if((dx+dy)%2||dy>dx)return 0;
return c(dx,(dx+dy)/2);
}
int calc(int x1,int y1,int x2,int y2){
return calc(abs(x1-x2),abs(y1-y2));
}
// (0,a) -> (i,1) without passing y=1 y=n
int calch(int a,int i,int n){
ll res=calc(0,a,i,1);
// down, up down, down up down, ...
int cur=1;
while(1){
int t=0;
cur=2*0-cur;
t-=calc(0,a,i,cur);
if(!t)break;
cur=2*(n+1)-cur;
t+=calc(0,a,i,cur);
(res+=t%mod+mod)%=mod;
}
// up, down up, up down up, ...
cur=1;
while(1){
int t=0;
cur=2*(n+1)-cur;
t-=calc(0,a,i,cur);
if(!t)break;
cur=2*0-cur;
t+=calc(0,a,i,cur);
(res+=t%mod+mod)%=mod;
}
return res;
}
void calc(int* f,int n,int a,int t){
static int h[2][N];
int i,j;
f[0]=1;
if(1LL*n*n<=t){
int cur=0;
for(j=1;j<=n;j++)h[cur][j]=j==a;
for(i=1,cur^=1;i<=t;i++,cur^=1){
f[i]=0;
for(j=1;j<=n;j++){
h[cur][j]=((j>1?h[cur^1][j-1]:0)+(j<n?h[cur^1][j+1]:0))%mod;
(f[i]+=h[cur][j])%=mod;
}
}
}else{
for(i=1;i<=t;i++)
f[i]=(2LL*mod+f[i-1]*2LL-calch(a,i-1,n)-calch(n-a+1,i-1,n))%mod;
}
}
int main(){
int t,n,m,a,b,i,ans=0;
scanf("%d%d%d%d%d",&t,&n,&m,&a,&b);
fac[0]=1;
for(i=1;i<N;i++)fac[i]=fac[i-1]*1LL*i%mod;
inv[N-1]=qp(fac[N-1],mod-2);
for(i=N-2;i>=0;i--)inv[i]=inv[i+1]*(i+1LL)%mod;
calc(f,n,a,t);
calc(g,m,b,t);
for(i=0;i<=t;i++)(ans+=1LL*f[i]*g[t-i]%mod*c(t,i)%mod)%=mod;
printf("%d",ans);
return 0;
}