09/10的一周

• 第 310 场周赛
  • 这一周两场CF打的实在太烂了，还好周赛T4高抬贵手出了个模板题（其实用单调栈也可以做），挤了个CN榜前十（看到大家都是上模板我就放心了）
  • 出现最频繁的偶数元素: 模拟
  • 子字符串的最优划分: 贪心
  • 将区间分为最少组数: 差分（在xhs@绿子 大佬那里了解了这个方法的名字，以前都是自己叫成平摊、反离散化hhh）
  • 最长递增子序列 II: 线段树。或者单调栈也可以。本质就是一个特殊的单调递增dp问题。
• [CF1728] Educational Codeforces Round 135 (Rated for Div.
  2)
  • A. Colored Balls: Revisited: 模拟。一开始以为是求所有可能留下的颜色种类的个数，心想现在A都那么难了吗hhh
  • B. Best Permutation: 构造。
  • C. Digital Logarithm: 贪心。这题有点卡的不服气，赛后用O(nlogn)的方法A了，但是其实也存在O(n)的做法：就是遍历两次unordered_map，第一次去重，第二次把大于9的变成小于9的。但不知道是不是哈希表常数过大了，会TLE
  • D. Letter Picking: 博弈论，最大最小搜索。太久没写了没有写完
    • 在CF中慎用memset，有可能test cases很大导致TLE。然而总的n其实没有那么大。
  • E. Red-Black Pepper 贪心排序+扩展欧几里得。又是一题5h但是可以独立1A的题目，hh还是整理思路的速度不够快。
• [CF1726] Codeforces Round #819 (Div. 1 + Div. 2) and Grimoire of
  Code Annual Contest 2022
  • A. Mainak and Array: 贪心+构造
  • B. Mainak and Interesting Sequence: 构造。比赛的时候因为把<看成<=卡了好一会 T_T
  • C. Jatayu’s Balanced Bracket Sequence: 并查集+模拟
  • [TODO]: D. Edge Split: 图+构造。需要用到m<=n+2的性质
  • [TODO]: E: Almost Perfect: 数学学学学。推出来了循环组，但是不知道怎统计结果…看了下题解真的是太nan了T_T
• [CF1037] Manthan, Codefest 18 (rated, Div. 1, Div. 2)
  • 找了场旧比赛来练手，说实话虽然是div1+2，但是A-E都不是很难，就是很考验手速。F居然也独立做出来了，就是花了很久debug哈哈哈
  • A. Packets: 数学题
  • B. Reach Median: 贪心
  • C. Equalize: 贪心即可，不必要dp
  • D. Valid BFS?: 对BFS的考察，像是一道面试题
  • E: Trips: 图+类似拓扑排序+逆序处理query（看到输出每次增增减减边之后的答案就应该联想到逆序处理）
  • F. Maximum Reduction: 数学。
    • 有许多类似的题目是要求统计数组元素某些操作/比较之后的和。
    • 通常叙述题目的方式是：对于某个操作/比较，某个元素会被选出来加到最后的答案；然而我们可以思考成：对于每个元素，有哪些的操作/比较，它会被选中。
    • 这题也是这样，把问题规约成：对于每个元素，选中它的操作是哪些，最后的答案S=sum_i(选中a[i]的次数 * a[i])
    • debug很久并且没有1A的原因在于我没有平移每个元素的坐标，用的是原始坐标去思考，导致很多+1/-1的地方被卡了。应该把它们平移到以0开始的情况其实会更好思考。