做题策略

寻找充要条件

很多题我们需要转化题意，无论是换成代数形式，还是简化模型，我们都需要抓住充要条件。

下标和值域的转化

这个在数据结构很常用。

P7514 [省选联考 2021 A/B 卷] 卡牌游戏。

这道题直接做不好做，所以我们考虑在值域上面做。我们把 abab 放在数轴上排序，然后我们利用双指针维护可行的区间，最后答案就是最小的。

动态规划 dp

概率论逆序对

fi,jf_{i,j} 表示 ii 位置上大于 jj 的概率（ai>aja_i>a_j）。

数据结构优化

可以用线段树维护可行区间的区间最小值进行快速转移。CF1557D Ezzat and Grid。

数据结构

树状数组

树状数组二分

P6619 [省选联考 2020 A/B 卷] 冰火战士。我们发现树状数组一个点 ii 存储了 [i−lowbit(i)+1,i][i - \text{lowbit}(i) + 1,i] 的所有信息**，所以我们在树状数组上二分，像倍增一样，从大到小依次枚举这个点加上 2i2^i 的祖先，如果能跳就跳。从高位到低位，从 now 尝试跳到 k = now | (1<<j) 时，由于二分是从高位到低位构造的，此时 lowbit(k) 恰好等于 1<<j。

线段树

pushup 优化

这个是一个很神奇的优化，P4198 楼房重建。我们考虑优化 pushup 使其做到 log⁡\log。

遇到一些问题，区间外的一些会影响区间内的时候，我们就需要利用这个 trick 优化我们的算法。这个问题很大可能是一个有关 max⁡\max 的一个问题，我们可以通过 max⁡\max 所处位置进行分类。本质上是每一个节点的计算只需要进入 左儿子/右儿子。

代码
C++
int get(int x,int l,int r,double mx){
	if(t[x].mx<mx)return 0;
	if(l==r){
		return t[x].mx>mx;
	}
	if(t[ls].mx<=mx)return get(rs,mid+1,r,mx);
	return t[x].res-t[ls].res+get(ls,l,mid,mx);
}

void pushup(int x,int l,int r){
	t[x].mx=max(t[ls].mx,t[rs].mx);
	t[x].res=t[ls].res+get(rs,mid+1,r,t[ls].mx);
}

区间计数问题

求 (max−min)=(r−l)(max−min)=(r−l) 的个数，转化成 (max−min)−(r−l)=0(max−min)−(r−l)=0，也就是维护 (max−min)−(r−l)(max−min)−(r−l) 最小值的个数。

值域小的问题

对于每一个字母开一颗线段树，然后按照顺序处理。很多时候这样是可行的。

两个维度的问题

可以主席树，本质就是一个维度维护了差分版本信息，另一个维度维护值域。

和位置关系不大的题目考虑值域。

分治解决子区间最大问题

子区间最大值问题可以考虑分治。

与两个此消彼长的，例如值域与个数有段的问题

和数字值，个数的东西有关的可以想想根号分治。

价值求和问题

二分第 kk 大区间的值。

CF1034D Intervals of Intervals。真的很神奇。

有关 tag 的

注意：

  • 有翻转赋值 tag 赋值优先级高。但是有赋值也可以有后面的翻转。

图论

LCA

LCA 的深度

uu 和 vv 的 LCA 的深度就相当于把 uu 到根结点的路径填成 11，然后问 vv 到根结点的路径的权值和。P4211 [LNOI2014] LCA。

最短路相关

双向多源 dij

让关键点作为源点，然后两个方向都 dij 一遍，最后就可以寻找出最短路径了。[GXOI/GZOI2019] 旅行者。

最大/最小的限制模型

直接同余最短路就可以了，可以进行限制。关于 min⁡\min 和 max⁡\max 的计数有时也可以，比如 CF1473E Minimum Path，我们发现减去的是最小值，加上的是最大值，所以我们可以想到对于没一条路径，我们需要让其权值更小，这让我们想到了分层图最短路，是否已经决定了最大/小值。

带有很多点的点集

这种点很多的题目我们可以考虑 LCA。我们考虑点集的 LCA 和加上特殊点的。P6071 『MdOI R1』Treequery。

二分图判定

判断二分图的充要条件是没有奇环，可以用扩展域并查集判断。

矩形包含问题

一个点向右做射线，与图形竖线的交点个数为奇数的时候，这个点在这个图形里面。射线不要和边线重合。

欧拉定理

定理公式：V−E+F=2V - E + F = 2

VV 代表顶点数，EE 代表棱数，FF 代表面数。

数学

计数

突破口

高斯消元求概率

CF113D Museum。P3211 [HNOI2011] XOR和路径。

由于这一类问题的转移是无限的，所以我们需要把转移列成方程，然后利用高斯消元解出来。

前者需要设两点的位置为一个状态。

一般有两种设法：

  • 设一个位置经过的次数。从 11 正着转移。
  • 设一个点经过的概率。从 nn 倒着转移。

gcd 计数

最常见的逻辑：直接枚举 gcd 的值，反演或者普通计数都用得到。

枚举 gcd⁡\gcd，然后 gig_i 是为 ii 的倍数的贡献，fif_i 是为 ii 的贡献。

拆分技巧

2x−y=x+(x−y)2x-y=x+(x-y) 可以转化成等差数列。

拆分问题

有二进制拆分，相对应的，也有质因数分解拆分，将问题让每一个质因数做一遍。AT_arc192_d [ARC192D] Fraction Line。

容斥

子集容斥

这应该是一个很重要的模型了。

P3349 [ZJOI2016] 小星星。如果设类似 fsf_s 的这种状态来转移，转移的时间复杂度是 O(n3)O(n^3) 的，这个可以用容斥优化。我们直接钦定整个转移过程中的集合是 ss，最后容斥一下，就能得到恰好是 ss 的了。

反射容斥

CF1204E Natasha, Sasha and the Prefix Sums。我们发现对于一个 ii，就相当于图上的路径需要和 y=iy=i 有交点。如果起点终点在直线两侧，答案就是总数。如果不在同一侧，我们就要“反射”一下，这样并不会影响重点哦。然后现在上移了 n+in+i 步，下移了 n−in-i 步。然后我们又可以求出总数了。

数论

降幂/拆根号技巧

同时 ln

P5319 [BJOI2019] 奥术神杖。

左右同时 ln⁡\ln：

ln⁡Ans=1c∑i=1cln⁡wi\ln\mathrm{Ans}=\frac{1}{c}\sum_{i=1}^{c}\ln w_i
原根

神秘的降幂方式：用原根。CF1106F Lunar New Year and a Recursive Sequence。

博弈论

SG 函数

SG 值就是下一个状态的 mex，多个起点就把 SG 异或起来。

只要状态转移跟选手是谁无关就行了，这个可以直接得到，也可以转化得到。

bitset 优化：对于一个 sg 值维护拥有 TA 的下标。CF1091H New Year and the Tricolore Recreation。

计数

考虑维度

对于排列计数，有两种方法，从位置考虑，从值域考虑。

字符串

  • 好吧，很多难的字符串题可以用哈希做。。。

AC 自动机

AC 自动机上 dp

fi,jf_{i,j}：长度为 ii，在 AC 自动机节点 jj 的最大得分。

P3041 [USACO12JAN] Video Game G。P4052 [JSOI2007] 文本生成器。

fail 树

我们可以每一个点的 fail 都是这个点的父亲，然后这棵树的性质就是每一个点如果在序列出现过，其父亲链上的所有的一定都出现过。

kmp

Border Theory

所有 border 长度构成的序列，可以划分为 O(log⁡k)O(\log k) 个等差数列。

字符串循环节

直接 kmpi−ikmp_i-i 就是一个循环节，因为可以一一对应上。CF432D Prefixes and Suffixes。

Height 数组

lcp

lcp(p,q)=min⁡{hrkp+1,hrkp+2,...,hrkq}lcp(p, q) = \min\{ h_{rk_{p}+1}, h_{rk_{p}+2}, ..., h_{rk_{q}} \}

构造

黑白格

AT_agc027_d [AGC027D] Modulo Matrix。

白格质数相乘。

ad-hoc

缩小范围

拆分一个序列长度的种数一定是根号级别的

1+2+⋯+k=n1+2+\cdots+k=n 这种 kk 一定第根号级别的。

排序

a+b 和 b+a 比较

这个是一个很厉害的性质呢。P1012 [NOIP 1998 提高组] 拼数，结论是比较 a+ba+b 和 b+ab+a，证明方法：

证明

a×10n+b−(a+b)>b×10m+a−(a+b)a\times 10^n+b-(a+b)>b\times 10^m+a-(a+b) a×10n−a>b×10m−ba\times 10^n-a>b\times 10^m-b a×(10n−1)>b×(10m−1)a\times(10^n-1)>b\times (10^m-1)

\tag{A} \frac{a}{10^m-1}>\frac{b}{10^n-1}

\tag{B} \frac{b}{10^n-1}>\frac{c}{10^r-1}

\tag{C} \frac{a}{10^m-1}>\frac{b}{10^n-1}>\frac{c}{10^r-1}

二分 01 排序

P2824 [HEOI2016/TJOI2016] 排序。因为只问一个数，可以直接二分 midmid，只需要把 ≥mid\ge mid 的设成 11，看最后这一位是 00 还是 11，0101 排序线段树维护。

贪心

Exchange Argument

这个是一个思想，就是贪心地进行排序。

比如 AT_agc023_f [AGC023F] 01 on Tree。 设节点 a,ba,b 所在连通块的 0,10,1 个数分别为 a0,a1,b0,b1a_0,a_1,b_0,b_1，那么如果 aa 排在 bb 前面，跨过连通块的贡献为 a1×b0a_1\times b_0。也就是说，aa 排在 bb 前面更优的条件是

a1×b0<b1×a0a_1\times b_0<b_1\times a_0

即 a1a0<b1b0\frac{a_1}{a_0}<\frac{b_1}{b_0}

P4437 [HNOI/AHOI2018] 排列 这个也比较像。