2020 年 10~12 月水题选做

本来早就想整理这么一个集合的，然后咕到了现在（ $10$ 月的第一个提交记录：[Link](/record/39091736)（咋还爆零了 \[捂脸\]），本博客整理从该提交记录以后的 AC 的**有一定价值的**题目。 现在已经是 $2021$ 年了 qwq，在 $2020$ 年的 $10\sim 12$ 月，我共有 $970$ 条提交记录，其中 AC 记录共 $345$ 条（均含私题）。 以下为部分题目收录，难度评分从 $0$ 到 $10$，仅供参考。 $\color{#1ac4c2}0$ $\color{#1ac463}1$ $\color{#52c41a}2$ $\color{#5ac41a}3$ $\color{#95c41a}4$ $\color{#c4be1a}5$ $\color{#c4a01a}6$ $\color{#c4821a}7$ $\color{#c4411a}8$ $\color{#c41a52}9$ $\color{#c41a99}10$ --- # 1. [P4688 \[Ynoi2016\]掉进兔子洞](/problem/P4688) 难度评分 $\color{#c4be1a}5$。 想了想最后还是把这题放进来了，还是比较考验基本功的，大概思路就是离散化后莫队维护 bitset。 ~~楼叉楼：我辛辛苦苦出的 Ynoi 就这么被你当水题做？？？~~ # 2. [CF33C Wonderful Randomized Sum](/problem/CF33C) [SP7507 CF33C - Wonderful Randomized Sum](/problem/SP7507) 双倍经验。 难度评分 $\color{#1ac463}1$。 经过数学推导可得，答案为中间重叠部分的两倍减去数列的总和，问题转化为求数列的最大子段和，代码非常简单。 # 3. [P6830 \[IOI2020\]连接擎天树](/problem/P6830) 难度评分 $\color{#5ac41a}3$。 分几种情况讨论，初步判断无解后，对于每个连通块分树或基环树两种情况处理，详见 [我的题解](/blog/ak-ioi/solution-p6830)。 # 4. [P3857 \[TJOI2008\]彩灯](/problem/P3857) 难度评分 $\color{#52c41a}2$。 看懂题面后，可以根据开关的性质，将输入的内容状态压缩成数，然后发现是线性基的基础题。 # 5. [CF1375F Integer Game](/problem/CF1375F) 难度评分 $\color{#c4a01a}6$。 一道比较有难度的结论题，经过亿些数学推导后得到先手三步必胜，详见 [我的题解](/blog/ak-ioi/solution-cf1375f)。 # 6. [CF1375G Tree Modification](/problem/CF1375G) 难度评分 $\color{#c41a52}9$。 可以使用换根法树形 dp，也可以转化模型为二分图进行黑白染色，比较烧脑的结论题。 # 7. [CF1148F Foo Fighters](/problem/CF1148F) 难度评分 $\color{#c4411a}8$。 有点毒瘤的贪心题，详见 [我的题解](/blog/ak-ioi/solution-cf1148f)。 # 8. [CF980E The Number Games](/problem/CF980E) 难度评分 $\color{#5ac41a}3$。 同学：“一道树剖过不去的树剖题。” 引理：$\displaystyle2^n\gt\sum_{i=1}^{n-1}2^i$，很好证，这里不多说了。 因此 $n$ 号城镇必定要选，然后使用 dfs 序 BIT 维护路径上的操作进行选取即可。 # 9. [CF843B Interactive LowerBound](/problem/CF843B) 难度评分 $\color{#52c41a}2$。 随机询问若干位置，然后根据期望遍历即可，详见 [我的题解](/blog/ak-ioi/solution-cf843b)。 # 10. [CF468C Hack it!](/problem/CF468C) 难度评分 $\color{#c4a01a}6$。 题目思路极其清奇，解题思路也挺清奇，数学推导即可。 # 11. [CF1451E1 Bitwise Queries (Easy Version)](/problem/CF1451E1) 难度评分 $\color{#5ac41a}3$。 赛时竟然想出了 div.2 的 E1 题，还是交互，涨了不少分 \[狂喜\]。 主要考察位运算的基本性质： ```text a|b-a&b=a^b a&b+a|b=a+b a1+a2=(a1|a2)*2-(a1^a2) ``` ## 11.5 [CF1451E2 Bitwise Queries (Hard Version)](/problem/CF1451E2) 难度评分 $\color{#c4be1a}5$。 在上面的基础上进行简单推导即可，可惜的是赛时没做出来。 # 12. [P2508 \[HAOI2008\]圆上的整点](/problem/P2508) 难度评分 $\color{#c4821a}7$。 挺复杂的数学题，推了半天。 # 13. [P5457 \[THUPC2018\]生生不息](/problem/P5457) 难度评分 $\color{#c4be1a}5$。 挺有意思的一道题，推导可知所有生命一定会在 $60$ 代内死亡（如果会死），可以连边跑最短路，对于 $n=m=5$ 的数据可以在 $10\sim 20$ 秒得到答案。目前看来好像只能这么打表。 # 14. [P2184 贪婪大陆](/problem/P2184) 难度评分 $\color{#5ac41a}3$。 开两个树状数组，维护开始和结束的点，差分一下。 # 15. [P3640 \[APIO2013\]出题人](/problem/P3640) 难度评分 $\color{#c4be1a}5$。 大概就是给数据范围，放一些算法过，再把一些算法卡 TLE。 其实本题意义并没有前面那些题那么大，对选手来讲的帮助可能就是通过卡别人算法了解各个算法的优缺点，对出题人来讲大概就是涨涨经验（？）。 # 16. [P4588 \[TJOI2018\]数学计算](/problem/P4588) 难度评分 $\color{#52c41a}2$。 用线段树维护每一次修改，操作 $1$ 则将对应位置改成 $m$，操作 $2$ 则将 $pos$ 位置改成 $1$，查询区间乘积模 $mod$ 的值。 （中间 WA 了几次是因为线段树节点没开 ll，其他都开了） --- 先整理这么多吧，如果有时间接着整理。