吴国庆

Codeforces

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

/ 注册

全部文章 / Codeforces （共6篇）

Educational Codeforces Round 80 (Rated for Div. 2)ADE

D. Minimax Problem 二分答案，由于m<=8，所以可以把每行对于一个mid的状态存储下来，然后枚举所有状态即可利用二进制存储信息的思想，并分析题目的特点，可以很清晰的想到解法 A. Deadline n，d<1e9 求方程 x+ceil（d/(x+1)）&l...

2020-05-04

0 565

Codeforces Round #626 Instant Noodles

l链接 Answer ：本题突破口在于 gcd ⁡ ( ...

2020-05-04

0 482

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

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