Educational Codeforces Round 26

A. Text Volume

简单模拟题,按题意模拟

 

B. Flag of Berland

巧妙的模拟题,我的做法是每种颜色找到边界,看边界是不是里面都是该颜色,之后再判断个数是不是 \frac{n*m}{3}, 并且边界跟整个旗子的边界重合。

 

C. Two Seals

依旧是一道考验代码功底的模拟题,穷举两个印章,看是否可以放下,统计答案。

 

D. Round Subset

DP, 首先理解 0 的个数与因子 2 和 5 的个数有关。 F_{i,j} 表示当取了 j 个数,有 i 个因子 5 时,因子 2 最多有多少个。F_{i,j} = max\{F_{i - x_k,j-1} + y_k\}, 其中 x_k, y_k 分别表示 a_k 有多少个因子 5 和 2.复杂度约为 O(n^2k). 注意边界。

 

E. Vasya's Function

首先一点 f(a, b) = f(\frac{a}{gcd(a, b)}, \frac{b}{gcd(a, b)}).
我们发现 b 始终是一个一个递减直到它与 a 不互质,所以我们可以穷举 a 的质因子,算出 ba 不互质最少要减多少个数。然后减掉递归求解。注意特判边界。

完结

这两场多校发挥的不是特别好,所以有些题目还没补上,总结也会之后补上。诶,开的坑太多了。😡

One thought on “Educational Codeforces Round 26

发表评论

电子邮件地址不会被公开。 必填项已用*标注