补补以前做过的题

约瑟夫用脑玩 · 2024-01-16 22:25:42 · 个人记录

• [AGC032B] Balanced Neighbors

  绿题这么有实力的吗（

  首先读懂题，naive 的想法就是所有点连起来权值和均为 sum=\sum_{i=1}^n i，且显然保证连通。

  但发现权值和不能算自己，于是每个点 i 根据自身编号断相应某个点使得权值和均为 sum-C 即可，不难想到 (i,n-i) 配对的方法。

  不过正解补图的思路惊为天人，真震撼吧，不过如果先猜一种构造方案再去解释还是能简单看出的，不过这个总结太精妙了。

  总结：能猜先猜，再进行总结证明。

• [AGC033F] Adding Edges

  神秘题解，看了一晚上自己以前的题解没看懂，下次再说？

• [AGC040B] Two Contests

  神秘贪心题，核心是一定有一个 mxl，它无论如何一定是两组中其中一组交集的 l，于是我们枚举这一组交集的 r，这组权值已定由于贪心另一组权值得最大，我们尽量把能放的区间都放在这一组避免影响隔壁的最大长度。

  这样的前提是反面一定有一个 mnr，且在另一组，这样多的区间若放在那边一定会干扰 l 更大从而不优，综合考虑发现特殊情况，mxl,mnr 在一组，则这组所以区间都可以放进来，且无论如何都不会被干扰，那么另一组特殊贪心只取一个区间。

  感觉莫名很难思虑周全刚好想到，但最后的做法却又意外的简单而合理，还是 mxl,mnr 一起考虑更好！

  总结：全局中的最大最小极限必出现而带来更方便（有前提条件的）讨论。

• [AGC040E] Prefix Suffix Addition

  看了一半，下次再说。

• P8054 A 质因数

  逆天，首先 n 给定，然后 m 肯定找 <n 中 f(m) 最大的那个便于判断，显然是 m=2^k 最大为 f(2^k)=k，考虑判断 f(n)?k，发现若有 p_i\ge 5，那么一定有 p_i> 2^2，导致在质数个数上至少大 1，先把相同的 2 这个质因数全部排掉，又不能大于 5，只能是 3 嘛，但是 3^2\ge 2^3，如果有多个 3，显然也会导致质数个数的增加，总之就是排除 2，只能有一个 3，才是合法情况！

  如果还是觉得难以看出或者难以想到，可以打个表发现合法情况很少，分析一下质数因子都是些啥就会很显然的找到结论，再像上述一样证明，很显然。

  总结：奇怪的可能是规律输出题（这题还只有 0，1），可以先打表找相关结论。

• CF1422F Boring Queries

  裸题就是神题。强制在线区间 lcm。——摘自一位故人

  题解，下次再总结。

• CF698F Coprime Permutation

  映射神题，下次看。

• c++神仙操作技巧合集

  很喜欢抄的一句话：

  抵制不良压行，拒绝全压一行。注意保护代码，谨防编译错误。适度压行益脑，沉迷压行伤身。合理安排压行，享受愉快生活。

• 博弈论

• 早年经典成果：竞赛图&哈密尔顿路

• SAM复习！！！

• 严格别名

  别乱用指针，这会导致同一个东西被当作两个东西丢了进去，更不要主动尝试这种行为，是 ub！！！

想看的太多了，今晚没时间下次再补吧！！！