感想 12/19-12/26

这周刷了70-80道atc（难度相当于lchard），然后两个周赛都翻车了。

Atc收获（general）

Atc的题给我感觉就很技巧，基本没有可以背板子的（除了数论的某些题）。总结一点东西：

1. 第一件事就是把题目的外衣剥掉，抽象出题目到底要我们解决什么问题。
2. 多个变量的情况，试着fix一个。这往往意味着加入O(N)来枚举一个变量，但是减少变量数之后经常就好做多了。这里给我印象深刻的是ABC102D Equal Cut。
   • 如果感觉题目要求太复杂，可以先去除一个限制，看看能不能做。 ABC100D 选蛋糕
   • 问题空间如果太大，试着缩小范围。 ABC086 Checker
   • 多个维度，可能可以独立考虑。经典的场景如曼哈顿距离的xy分别考虑 ABC082 FT Robot。
3. 递推。ABC116D Various Sushi
4. “操作”题。比如说对一个序列/一堆东西做某几种操作，求操作最小次数之类的。
   • 先试着排除一些没用的操作，或者有些操作一定在前/在后。ABC128D equeue
   • 即使题目说操作是按照顺序的，也很可能不需要按照顺序。使用类似贪心的操作即可解决。ABC085D Katana Thrower ABC119C Synthetic Kadomatsu
   • 对于同一个元素，根据题目的性质，常常只需要对其操作一次。这时就可以贪心做。ABC127D Integer Cards
5. 构造题。
   • 最好把他给的次数全用上。
   • 尽量考虑简单的，极限的情况。ABC081D Non-decreasing ABC092 Grid Components ABC096D 构造合数
   • 二进制构造出现频率挺高的。ABC102D All Your Paths are Different Lengths

Atc收获（具体知识点）

1. XOR的各种性质。
   • 每个位独立看。
   • a+b = a ^ b的条件是不能同时为1.
2. ”只回头一次“类型的题。基本是预处理。
3. 子数组和的问题，基本是转前缀和。
4. “中位数” “第k个” 之类的基本是二分。
5. 动态维护中位数可以用两个pq。
6. “找出A中所有的B”，常常不能在A中枚举所有的B。而是将B分解成很多b，对于每个b找出出现的次数。ABC

做得比较好的类型

1. 抽象成图的各种问题。
2. 离线算法（Events）的各种问题。
3. 用到模板（变化不大）的各种问题。

还较弱的方面以及如何改进

1. 目前最大的弱点是DP。什么时候可以用DP还不明确，目前都是随缘。
2. 贪心什么时候是正确的，什么时候是错误的。
3. 思维还不够灵活，看到题还不能很快地看到解题方向。

如何改进：

1. 研读《挑战程序设计竞赛》的暴力、贪心、DP、二分这些章节。
2. 刷cfR1500以下的DP题。不需要写，但是一定要把DP的要素写下来。
3. 刷cfR1500以下的构造题锻炼思维。