Day24h

CF

2019 Multi-University Training(2) 2019牛客暑期多校训练营(1) Record My Feelings(5) 动态规划(23) 图论(4) 字符串(3) 数学(20) 数据结构(8) 未归档(5) 模板(23)

/ 注册

全部文章 / CF （共37篇）

Elections

C. Elections 证明自己赢的时候获得的票数与贿赂所需的最小代价的函数是一个凸函数：从自己赢的票数等于 n 的时候往小推，每一次减去一个最大的代价，但是要保证在该情况下能赢刚开始是单调递增的，但是随着自己的票数越来越少以及某些人的票数越来越多，我们想要自己赢的票数再少一点，那...

三分

2020-01-17

0 509

Petya and Exam

C. Petya and Exam 重要的事情说三遍！认真读题！认真读题！认真读题！思维要开阔一点，不要被局限住了。因为 t 很大，所以我们不能遍历 t，但是 n 只有1e5，所以我们可以遍历每道题的截止时间。然后在其多余的时间内尽可能多的做后面还没有做过的简单题，做完了...

思维贪心

2020-01-14

0 462

Molly's Chemicals

C. Molly's Chemicals 这道题的思路跟C. Summarize to the Power of Two十分的相似。都是要求关于某个数的倍数。优化方式都是用一个 map 来储存存在的数字，然后用某个数的幂次方减去当前遍历数字，看 map 是否存在有这个值。因为转化为幂次...

前缀和

2020-01-12

0 409

DNA Alignment

C. DNA Alignment 来推导一下这个题：假设在给定的 s 串中，A，T，C，G分别有 a，b，c，d 个，而要匹配的串中有 A，B，C，D 个，所以其 ρ 值为\(Aa+Bb+Cc+Dd\)，而 \(A+B+C+D=a+b+c+d=n\)，我们可以自己掌控 A B C D 的多...

思维快速幂

2020-01-12

0 416

Vasya and Robot

C. Vasya and Robot 关键算法：二分、前缀和刚看到题的时候一点想法都没有... 先观察一下数据范围$(1≤n≤2⋅10^5)(−10^9≤x,y≤10^9) $ 可以用两个数组\(x[i],y[i]\)来表示在\(i\)操作完之后的机器人的位置 fo...

前缀和二分

2020-01-12

0 351

Hyperset

B - Hyperset Codeforces Round #612 (Div. 2) A~E2 题解如果直接枚举的话，复杂度是\(O(n^3)\)，显而易见会超时，但是我们会发现一个道理，当其中两个确定的时候，另外一个也就已经确定下来了，而我们要做的工作只是去寻找有没有这样一个东西，与...

思维暴力

2020-01-07

0 444

Portals

D - Portals 参考：CF1271D Portals dp 贪心主要要明白两点：如果a和b都能够派兵前去把守c，且a>b，那么从a派兵去把守c是更优解派兵要派往分数最大的地方，要把有限的派兵机会用在最值的地方要实现这两步，要学会反悔贪心法，即如果当...

2020-01-07

0 423

Harmonious Graph

D. Harmonious Graph 好后悔在写这个题之前浪费了几分钟时间，不然我就写出来了.... 因为他就是连通块之间的合并问题，所以就用并查集就好了复杂度好像也只是线性的吧... 然后就A了代码： // Created by CAD on 2019/1...

并查集

2019-12-05

0 427

Send Boxes to Alice

E. Send Boxes to Alice 首先求出每一个位置的前缀和。对答案进行复杂度为\(\sqrt{a[n]}\)的遍历，因为最后的答案不可能大于\(\sqrt{a[n]}\) for(ll j=2;j*j<=a[n];++j) if(a[n]%j==0) ...

前缀和思维

2019-11-23

0 400

Feeding Chicken

D - Feeding Chicken 从左上角开始，往右下角开始遍历，但是遍历的时候需要注意一点，就是遍历的时候需要连起来，就比如第一行从左往右进行遍历，但是第二行不能从左往右了，因为这样就分开了，所以第二行就应该从右往左遍历，因此，奇数行从左往右遍历，偶数行从右往左遍历。实现代码：...

思维遍历地图

2019-11-23

0 403