吴国庆

分类

acm(50) Codeforces(6) Xcpc(4) 未归档(2) 算法学习(6) 题解(38)

/ 注册

全部文章（共106篇）

Codeforces Round #629 (Div. 3)

第一次AK写篇题解庆祝一下~~ 文章目录 A.Divisibility Problem B. K-th Beautiful String C. Ternary XOR D. Carousel E. Tree Queries F. Make k Eq...

2020-05-04

0 531

The 13th Chinese Northeast Collegiate Programming Contest

文章目录 B. Balanced Diet C. Line-line Intersection E. Minimum Spanning Tree D. Master of Data Structure F. Mini-game Before Contest 坑...

2020-05-04

0 677

Codeforces Round #630 (Div. 2) E. Height All the Same 思维

链接操作1可以将所有的高度变成0 or 1（像俄罗斯方块一样）并且这其中的0和1可以全局互换操作2和操作1可以移动这些1，并且将相邻的0 0 -> 1 1 那么问题就转换成，放置偶数个位置0，或偶数个位置1 所以当n*m%2==1时 0和1总会有一个是偶数否则，也可以简单的构造出一...

2020-05-04

0 497

整除分块证明

2020-05-04

0 492

Codeforces Round #630 (Div. 2) F. Independent Set 树形dp

链接显然一颗树的独立集可以很容易的转移过来 dp[u][0]=∏(dp[v][0]+dp[v][1]) dp[u][1]=∏(dp[v][0]) 最后答案为dp[1][0]+dp[1][1] 加上子集其实就相当于在转移的时候把当前边断开的贡献加上去就可以了，可以得到 dp[u][0]=∏(d...

2020-05-04

0 551

Educational Codeforces Round 85 (Rated for Div. 2) E Divisor Paths

链接最短路:x->gcd(x,y)->y 然后就是一个有重复数字的错排问题，设每种数字分别出现k1,k2,k3…kp次，并假设该错排的答案为f 那么f*k1!*k2!k3!…*kp!= ( sigma(ki) )! #pragma GCC optimize(2) #inclu...

2020-05-04

0 506

Codeforces Round #635 Kaavi and Magic Spell

链接考虑S串中第i个字母的贡献，那么我们就可以记录一下前i-1个字母组成的各个区间的个数dp[i] [j] 表示T串的i~j区间匹配出现的次数，那么当加入第i个字母时，所有长度为i-1的dp区间答案已经得到，所以我们在T串中直接枚举所有长度为i的区间，即为当前字母的贡献。转移方程：dp...

2020-05-04

0 681

Master of Data Structure 虚树

链接 m<2000 建虚树后暴力维护虚树中两点间的实际点的个数模拟即可巨丑的代码 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 ...

2020-05-04

0 533

Educational Codeforces Round 86 (Rated for Div. 2) E - Placing Rooks

链接想使所有格子全被覆盖，要么所有行都有棋子，要么所有列都有棋子。假设现在是所有行都有棋子，那么其中k对棋子互相攻击就可以看成n-k列放n个棋子。那么答案就为2*C(n,n-k)*把n个物品放n-k个集合的方案数。最后一项为第二类斯特林数，记S｛n,k｝为n个物品放k个集合的方案数公...

2020-05-04

1 603

Codeforces Global Round 1 Magic Stones

链接很有意思的规律：将：b->a+c-b 之后的查分数组：a,c-b,b-a 本来的差分数组:a,b-a,c-b 可以发现，题目的操作就是交换差分序列的操作，所以问题就转化为怎么交换原数组的差分序列，使其和目标序列的差分序列使相等的。那么我们只需要需处理出两个序列的差分序列，排下...

2020-05-04

0 663