Trick

Trick:

• \(x\) 与各位数之和模 \(9\) 同余（CF10C Digital Root）
  
• st 表 和 线段树 可以存 \(\gcd\)
  
• 注意函数增减性（CF1632D New Year Concert）
  
• dp 时若下标太大，可以调换下标和存储的数值（CF1974E Money Buys Happiness）
  
• 贪心不成立时，可以用反悔贪心（CF1974G Money Buys Less Happiness Now）
  
• 乘法一般比加法更优（CF1872G Replace With Product）
  
• '(' 看成 \(+1\)，')' 看成 \(-1\)（CF1976D Invertible Bracket Sequences）
  
• atan2 可以求角度（CF257C View Angle）
  
• 正难则反（容斥原理）（CF803F Coprime Subsequences）
  
• 抓住数据的特殊性质，如 \(10^{18}\)（CF468C Hack it!）
  
• 可以贪心+dp（贪心推性质，用 dp 做），经典单调队列优化 (CF797F Mice and Holes)
  
• 可以先取一个特殊点来做，通过特殊点的特殊性质来解题 (CF1559D2 Mocha and Diana (Hard Version))
  
• 数据很大时，可以考虑能否缩小范围，后面特殊处理 (CF1956E2 Nene vs. Monsters (Hard Version))
  
• 设 \(f_{i,j,k}\) 表示消除区间 \([i,j]\) 及 \(j\) 右边恰好 \(k\) 个与位置 \(j\) 相同字符的答案（CF1107E Vasya and Binary String）
  
• 位运算可以在二进制下一位一位考虑（P4551 最长异或路径）
  
• mex 等价于 总和出现过的数的异或和^去重后的数的异或和->类似于 hh 的项链 树状数组维护（CF703D Mishka and Interesting sum）
  
• 减少不必要的查询->建线段树时用 st 表维护值（CF803G Periodic RMQ Problem）
  
• 求 \(1\) 到 \(n\) 的最小公倍数，可以筛质数的同时找每个质数的 \(x\) 次是否存在来更新答案以及 \(x\) （P4626 一道水题 II）
  
• 对于非递增序列 \(d_1,d_2,\dots,d_n\)，该度数序列可简单图化当且仅当 \(\forall k\in [1,n],\sum_{i=1}^{k}\le k(k-1)+\sum_{i=k+1}^{n} \min(d_i,k)\)（Erdős–Gallai 定理）（CF1091E New Year and the Acquaintance Estimation）
  
• \(\gcd(a_l,a_{l+1},\dots,a_r)=\gcd(a_l,\gcd(a_{l+1}-a_l,\dots,a_r-a_{r-1}))\)（P10463 Interval GCD）
  
• 非重组合 \(C_{n}^{m}\)，可重组合 \(C_{n+m-1}^{m}\)。上升 -> 组合后排序 （P5135 painting）
  
• 分类讨论边的类型（最小生成树上边 or not）来计算答案（CF733F Drivers Dissatisfaction）
  
• 并查集可以跳过很多无效答案，可以用来优化暴力 （CF200A Cinema）
  
• 可以把石子看成网格图，从左下角出发，每堆石子拿一个看成往上走（AT_agc002_e Candy Piles）
  
• 可以考虑枚举因子来计算（CF1499D The Number of Pairs）
  
• 转化题目给定的条件，差分来做（CF1710B Rain）
  
• dp 前可以构造一下，如（CF1930D2 Sum over all Substrings (Hard Version)），通过构造发现，对于 \(s\) 中每个 \(1\)，只需要 \(i\) 的贡献，而且不需要考虑前两个，由此得到转移方程
  
• 发现从小到大取最优，就从小往大做，直接把选了的数扔进 set 里，用树状数组维护删掉后的贡献（CF387E George and Cards）
  
• 对于不容易求的量，可以通过其他相关的量来转移（P4550 收集邮票）
  
• 一段数 \(+1\) 等价于 其他数 \(-1\)（P6544 [CEOI2014] Cake）
  
• 可以拆贡献，分为 不变的 和 变化的（与位置有关），分别维护 （CF396C On Changing Tree）
  
• 考虑环的情况，如 CF2045G X Aura 正环倒过来走成了负环，于是题目转化为树的情况
  
• 恰好 \(=k\) 转化为 \(\ge k\) 的方案数,前后差分,得到 恰好（CF1188C Array Beauty）
  
• 直接高精度维护会超时，考虑延迟更新，只要每次 /2 的时候更改后两位就可以了（P5513 [CEOI2013] Board）
  
• 树链剖分性质：dfn 连续，所以可以用 set 来维护，查询时二分（ZR 2858 苹果树）
  
• 线段树上挂 vector （P4215 踩气球 & P10590 磁力块）
  
• 线段树可以对应一个 \(2^n\) 长的序列（CF1401F Reverse and Swap）
  
• 总和 = 期望 \(\times\) 总方案数（AT_agc030_d Inversion Sum）
  
• 一个合法的括号序列的前缀和总大于等于零且本身的和为零
  
• 抽象成平面直角坐标系，从 \((0,0)\) 出发，每一个 \(1\) 看成 \((0,0)->(1,1)\)，\(0\) 看成 \((0,0)->(1,-1)\)（P1641）
  
• 可以对每一个深度都建一颗主席树（CF893F Subtree Minimum Query）
  
• 设原本在位置 \(i\) 上的逆序对数为 \(c_i\)，冒泡排序一轮后，位置 \(i\) 上的逆序对数变为 \(\max(0,c_{i+1}−1)\)（P6186 [NOI Online #1 提高组] 冒泡排序）。
  
• \((p-1)! \bmod p=\left\{\begin{aligned}-1 & & p \in P\\2  & & p=4\\0  & & \text{otherwise}\\\end{aligned}\right.\)（CF1957E Carousel of Combinations）
  
• \(C_{j}^{i} \bmod j = C_{j \bmod j}^{i \bmod j} \times C_{\lfloor\frac{j}{j}\rfloor}^{\lfloor\frac{i}{j}\rfloor}= \lfloor\frac{i}{j}\rfloor\)（CF1957E Carousel of Combinations）
  

代码部分:

<ol>vector 最好不要直接排序，常数大，可以用索引来排序。
注意算术优先级（加括号）！!
数组越界要特判，比如下标从 \(0\) 开始时 i-1 要特判一下。
图论时的输入有时从下标 \(2\) 开始读入。
二分时 \(l+r\) 若超出 long long 范围，可以用 \(mid=l+(r-l)/2\)。
不要写 unordered_map，用 map。
string 类如果写了 s=" "+s; 之类，n=s.size() 应写在前面。
st 表要调用 log 的预处理！！
n