Competitive Programming Techniques

模板化仅仅是为了提速，打开思维是首要的

等价/更优变换贪心

存在一种变换策略，使得当前方案等价或更优

对任意一种方案采取该策略，均得到具有某种特征的局面

则最优方案一定存在于所有具有该特征的方案当中

这种策略实质是缩小了最优解所在的集合

Two-pointer

在一些区间上统计信息，若将区间按L，R排序后

得到的区间序列其R单调不减，此时可用two-pointer来维护区间，统计信息

• p1移动后，p2从上一次的位置开始移动，在O(n)内可得到所有区间
• 信息论的角度：相当于利用单调不减的性质，利用上一次p2的位置信息，对信息的利用更加充分

离散化

O(nlogn)的值域映射（hash：(O(1)映射)）

{ai}放在数轴上，从左往右依次标号1,2,3…n，即映射的结果

值域：[min{ai},max{ai}]->[1,card{ai}]

映射后序关系保持不变，对于答案只与大小关系相关，与具体数值无关的题目，可研究映射后的情况

离散化映射后缩减了值域，有助于优化算法的时间和空间

代码风格

多组数据涉及的问题

全局变量失去了一个优势，即初始值为零,仅剩的优点是多维变量定义起来更加方便

而vector本身也是放在堆上的，且vector亦可方便的初始化，且提前reserve/resize/assign可避免指数级增长的内存，且局部lambda函数可访问局部变量,所以理论上vector可完完全全平替掉数组

且vector具有兼容STL更好,易于初始化的优点

不过尊崇国内OI遗风，规定代码风格如下

多组数据时：

基本全用 vector，除开：多维数组(static+memset)

注意提前分配内存，这样每次push_back的时间和空间才是O(1)的

功能简单的函数，局部lambda定义即可

OI风格的单组数据：基本用数组，除开：维护可变数组（集合）

不开全局longlong(内存翻倍,容易遭卡)

涉及到乘法,累加的变量和与之进行运算的变量均开成long long即可

且要处理好表达式的细节,防止爆掉

0-index:第i个元素对应的下标是i-1,没有冗余的元素,适合用于维护变化的集合

1-index:第i个元素对应的下标是i(形成良好的对应关系),且0对应有元素有助于递推

适合:需要有某种对应关系的,需要递推的(eg:sum)

递归传递string的优化

1.0: foo(const string& t)：引用传值+不会修改父函数string

2.0: string cur cur.append() cur.resize()：外部去维护string

3.0: 完全避免对string操作

• PS：实际上1.0中t+(string)仍会在函数内创建临时的长变量

　分类讨论

将方案集合进行切割划分，子集合对应不同的处理情况

多层的if判断和切割相对应,通过逻辑值真假使得if内对应情况是切割出的子集

对于特殊情况的处理:

特判或特殊处理,使其能够兼容一般情况