应试篇

策略

应试策略

• 首先应当把整份试题看一遍, 对整份试题有一个大致地了解.
  
  • 对于每一道题, 要至少审两遍, 看清题面以及数据范围.
  • 样例要手动画一画. 如果样例实在太大了, 那么自己构造一个小的样例理解一下题目.
  • 大致地想一想题目, 看看有什么想法, 对题目有个整体的感知.
• 接下来将每道题仔细的推一下, 制定好策略.
  
  • 每道题首先用平常的方法想, 如果想不到就用自己积累的方法想.
  • 注意一场考试的结果, 很重要都是靠能否写正解的. 如果觉得一道题很可能可以想出正解, 那就多花一点时间, 使劲地想.
  • 想不到要明白自己是哪里想不到, 在想不到的地方换一种方法继续想.
  • 想到的方法要手动地测一测样例, 看看有没有什么细节的问题.
  • 预估一下每一道题需要的时间, 确定一个做题的顺序.
• 实现, 调整.
  
  • 考虑实现代码. 先想好怎么实现, 然后再开始实现.
  • 如果发现某个地方的做法是不对的, 那么不要慌张, 考虑重新制定策略. (尽量在之前避免这种情况)

代码能力

• 代码总体策略
    写完, 编译, 编译成功, [来一发样例试一试, 肉眼检查代码, 如果找不出错那么就动态调试], 调试完, 检查代码的鲁棒性, 如果有条件就对拍, 测试极端数据, 检查文件输入输出.
• 写代码之前
    有一种情况要防止出现: 写到一半时, 发现自己的方法是错的!
    为了避免这一种情况, 我们先要验证自己方法的正确性: 考虑手算, 或者写一个原理一样但不易错的代码(例如矩阵快速幂时写直接乘), 或者直接写出来.
• 鲁棒性检查
  
  • 数组大小: 开够没有, 是否会爆空间
  • 初始化
  • 参数设置
  • 访问非法: 可能是 for 后面加了分号
  • 非明显变量
  • long long, double, char, 运算越界
  • 取模, 负数
  • 特判, no solution, 边界, 特殊情况
  • continue, break, return
  • if, while, for
• STL的调试技巧
    静态输出.
• 查出错时的一些技巧
    如果发现代码某个地方出了错, 那就检查类似的地方有没有出错.

分析手段

分析思路

  理解 -> 转化 -> 优化

• 理解
  
  • 首部分析法
    
    • XSY 1845
• 转化
  
  • 枚举转化
  • 逐步满足转化
    
    • 合并
      
      • XSY 2060 - Rectangle Query
      • XSY 2140 - 计数
    • 嵌套
  • 数形结合转化
    
    • 二维平面
    • 二维表格
  • 代数转化
    
    • 量化
      
      • 判断是否有多个状态同时存在?
         我们对每个状态进行量化, 使得这么多个状态同时存在的异或值为0, 求这些状态的线性基即可, 判断线性基的大小是否为 $0$ .
        
        • BZOJ 3569
• 优化
  
  • 算法
    
    • 平衡规划
    • 分治
  • 数据结构

最优性问题

• 二分答案
• 动态规划，贪心
  
  • XSY 2243
• 最短路径，最小生成树，网络流
  
  • XSY 2164

计数问题

• 容斥原理，减法原理转化
• 递推

构造性问题

• 网络流
• 特性分析

多组询问

• 非强制在线( 全部询问 以及 在线 )
  
  • 直接求解
    
    • XSY 2032
  • 离线处理
    
    • 固定左端点，移动右端点
    • 转移，莫队, 在线莫队
      
      • BZOJ 2120
    • cdq分治，整体二分
    • 启发式合并
• 强制在线
  
  • 离线转在线
    
    • 可持久化数据结构，启发式合并
      
      • BZOJ 4026
    • 树套树

树

• 树形dp
  
  • HDU 5293
  • BZOJ 2159
• 点分治，动态点分治
  
  • XSY 1122
  • XSY 1230
  • XSY 2180
  • XSY 2150
• 树上倍增
  
  • XSY 1010
  • XSY 2247
• 树链剖分, DFS序剖分
  
  • XSY 1019
  • XSY 1112
  • XSY 2068
• 启发式合并
  
  • XSY 2247
• 主席树
• 树上莫队
• 树的直径
• 序的应用
  
  • XSY 2176 - tree (树链的并)
  • HDU 5266 (集合的LCA)
  • Minimal Distrance (点到路径的最短距离)
  • XSY 2123 (拓展的DFS序维护毛毛虫)
  • SDOI 2015 - 寻宝游戏
• 虚树
  
  • BZOJ 3572 - 世界树
• LCT
  
  • SDOI 2017 - 树点涂色

字符串

• SA，SAM
  
  • XSY 2247
  • XSY 2132
  • 后缀数组 - 总结
• Hash
  
  • XSY 2114
• AC自动机，Fail树
• KMP，Extended-KMP
  
  • XSY 2202
     KMP的原理的应用.
  • XSY 1903
     覆盖子串与循环节.
  • XSY 2181
• FFT
  
  • XSY 1903
• Manacher，回文自动机
  
  • XSY 2242

环 & 基环树

• 倍长
   倍长的问题有两种形式: ① 删除 $[L,R]$ ② 保留 $[L,R]$
  
  • XSY 1903
  • XSY 2048
• 枚举第一位的情况
• 分开来处理
  
  • BZOJ 1040

和式的处理技巧

• $\phi$ 和 $\mu$ 的变形
   ① $\sum_{d|n}\mu(d)=[n=1]$ , 注意这意味着 $n=1$ 和 $n\ne 1$ 的情况都可以处理.
   ② $\sum_{d|n}\phi(d)=n$
  
  • BZOJ 2005 - 资源采集
  • XSY 2316
• 改变求和指标
   在处理 $\sum_{1\le i,j\le n}\gcd(i,j)$ 的时候, 我们枚举 $\gcd(i,j)$ .
  
  • BZOJ 2002
  • XSY 2139 - 链上求和

求f[1,...,n]

• 递推
• 待定系数 + 解方程
• 反演
  
  • BZOJ 4174
     二项式反演.
• 积性
  
  • XSY 2106
• 研究函数的性质(打表 & 分析)

n^2 信息统计

• 分治
• 合并
• 逐个处理, 每处理完一个维护之前所有的信息, 查询之前所有的信息
  
  • AHOI 2013 - 差异
• FFT
  
  • BZOJ 2179
  • XSY 2182
  • XSY 2263 - Grasshoppers
  • XSY 2106
  • XSY 2181

完全二叉树

• 树高为 $\log n$ , 考虑暴力.
  
  • XSY 2117

置换

• 对于置换 $\begin{pmatrix}1&2&3&...&n\\a_1&a_2&a_3&...&a_n\end{pmatrix}$ , 我们可以当做将 $i$ 与 $a_i$ 进行连边构成的图, 这幅图由若干个环构成, 每个环的大小被称为循环节. 一个数在置换作用下, 相当于在图沿着边走一步.

无向

• 定向
  
  • 无根树: 枚举根，转化为有根树
    
    • XSY 2164
  • 无向边: 定向
    
    • 混合图欧拉回路
• 拆边
  
  • 无向边: 转化为两条有向边
    
    • BZOJ 4289 Tax

对数（以及 离散对数）

• 将 指数函数 转化为 线性函数
  
  • XSY 2037
• 比大小

整数分解

• 一个数的质因子个数期望是 $O(\log n)$ ，上限是 $O(\sqrt n)$ ，可以暴力。总个数是 $O(n\log n)$ ，可以枚举。
• 按照 $\sqrt n$ 进行分类。对于大于 $\sqrt n$ 的因子，每个数只有一个；小于 $\sqrt n$ 的因子，个数不多，可以用复杂度高的方法。
  
  • 51Nod 1386 - 双马尾机器人
  • XSY 2160

二维递推式

• 数形结合求路径数。
  
  • XSY 2158
• 找规律
  
  • XSY 2160

区间

• 区间加法
• 区间减法
• 差分序列
  
  • XSY 1568
     线性基.
• 转化为二维平面的一个点

博弈论

• 找规律
• 对抗搜索
• DP
  
  • XSY 1874
  • XSY 2158
• SG函数

图的连通性

• 一阶连通性
  
  • 并查集
  • Flood Fill
    
    • 从边界开始 Flood Fill
  • LCT
    
    • XSY 1173
  • 构建生成森林
• 二阶连通性
  
  • 构建生成森林
  • Tarjan

max

• 差分转化
  
  • BZOJ 4298

二维空间 以及 高维空间

• 先考虑较低维的空间的问题(例如二维, 例如线段) . 然后将其与高维进行联系.
  
  • 空间切割
    
    • XSY 2240
       矩形切割 & 状压dp.
• 代数方法
  
  • BZOJ 1013

树的一次连通性

• 枚举连通块的一个点作为根, 如果一个点在连通块中, 那么它的父亲一定在连通块中.
• 点分治
  
  • hdu某道fwt可做的题
• LCT
  
  • XSY 2048

概率与期望

• 期望的线性性质
• dp
  
  • XSY 2051
• 高斯消元