My experience

不开 long long 见祖宗！
当题目中一个数字很大时，我们可以枚举另一个值域较小的变量。
有些状态对于某种情况下是一样的，例如，比中位数大的可以看做同一个数；除元音外的都看做同一辅音……
多次修改加一次查询可以使用差分来解决，对于需要翻转区间的我们可以使用链表进行存储。链表比数组删除、添加、重新排序等更有优势。
遇到有些题目正这来不合适，可以反着来。添加就变成了更简单的删除。
最大值最小可以一眼二分。
二分是在单调的答案区间内二分答案，使得找到某一个端点 $x$ ，满足 $[1，x-1]$ 不满足条件， $[x，n]$ 满足，这样就找到了最小值。
差分只是一种对暴力算法的优化、加速，起到降低时间复杂度的作用，所以有些题目可以先想暴力，再想使用差分优化。
双指针即枚举某一端点，然后对另一端点进行收缩，即可求得满足条件的区间个数、区间长度最小值，且指针移动方向相同。
有时候，如果不能使用人人为我的递推，可以换成我为人人的递推。
遇到有些题目，如果我们不关心具体的数值，而是每个数字之间的大小关系时，我们可以对其进行差分，或者减去第一项，有时候仅仅是知道大小关系时，可以离散化。
一定要排完序后再求前缀和、差分。
有时候，使用二进制中 $0$ 和 $1$ 来抽象两个数值。
双向边要开两倍数组！
调试用的 freopen 注释掉。
同一快内元素地位是等价的，我们不用在意块内元素的顺序。
一道题目如果存在多个变量难以下手，可以尝试去枚举其中一个变量，这样就只用维护生下来的变量了。
比较复杂的动态规划可以先写记忆化搜索，再写动态规划
要根据数据范围选择对应时间复杂度的算法。例如一道题目有 $q$ 个询问，每个询问的规模是 $p_i$，数据范围中有 $\sum{p_i}\leqslant k$ 并且我们可以接受 $\Theta(k)$ 的时间复杂度，那么每次询问的时间复杂度就是 $\Theta(p)$。
难想的题目尝试使用 dp 解决，先找出题目中的所有状态，然后列出朴素状态转移方程，然后进行优化。
遇到题目先思考弱化的问题，然后思考如何优化这个算法。
某些题目如果没有严谨的证明，不能轻易使用贪心算法，而是尝试使用 DP。
这就是哈希的原理了：判定时构造一个必要不充分条件，但这个“不充分”实际上有非常大非常大的概率充分，以至于不充分性可以忽略不计，从而达到充要判定的效果。读者应当熟悉的字符串哈希，也是同样的原理。
千万注意背包问题的不可贪心！
unique 之前要 sort！
处理反边 i ^ 1 时，记得 eid 初值为 $1$。
$n$ 个数的 $mex$ 的范围为 $[0,n-1]$。
$cin$ $cout$ 解绑后不要用 $puts$ $scanf$ $printf$ ！！！
开 $long long$ 后scanf printf 格式符一定要改成 %lld
判断double是否与int相等的时候,以及输出保留几位小数的时候+1e-7(避免掉精度或者开 lond double 格式化输出为 %Ld）int x = sum + eps; if(fabs(sum-x)<=eps)....
通常取eps的值为：$10^{-10}$ ~ $10^{-8}$ 之间。
位运算不清楚优先级的情况下一定要加括号！
bfs 时的状态要考虑全面(比如逃离地下城身上的的钥匙要用二进制存)
解绑后不能用getchar()!!!
定义变量时不要外面定义一个里面定义一个，错调试很难调
调用函数搞清楚别写错
对于冒泡排序类找性质的题目，一个点向右移动多少次等价于右边有多少个数可以超过它。
对于链式前向星的head，memset为-1的时候不要写 memset(head,-1,sizeof(int)*( n+1))，要写就写memset(head,-1,sizeof head);
字符串追加字符:
- a = a + c; // $O(3 \times n)$
- a += c; // $O(1)$
判断 ans 以判断是否有解时，应当根据情况和转移方程判断而不是一味地写 if(ans == inf)
关于UB e.g modify(a[t].l,a[t--].r) 这样写是错的，应为函数传参数没有先后顺序，t-- 应当分开写
对于不写万能头时，有时候忘记写如#include<vector> 之类编译器上可以运行但交上去就CE，所以要仔细检查，科学完善
碰到数区间问题无非两个套路：枚举右（左）端点或分治或数据结构
两个字符数组如果从下标 $1$ 开始输入，不要使用 $strcmp(a,b)$ ，要用的话要将 a[0] = b[0] = '#'
数学预处理要注意：在所有输入后再处理；注意从 0/1/2 开始推，同时注意初始值
遇到两个人博弈,求一个人收益的最大值时
- 考虑只用 $dfs(i,j)$ 表示 $i \sim j$ 先手能获得的最大价值。转移的时候想要获得本次操作先手的收益，只需要把价值之和减去后手作为先手的收益。即用 sum[n] - sum[i] - dfs(i + 1, n) 来计算 $i \sim n$ 先手获得的价值。
- 计算先后手价值之差，再使用 $min,max $
$dp$ 的优化
- 数据结构
- 决策单调性
- 继承结果，前缀结果
- 形式由记搜变为循环，便于优化
有关 $exCRT$ 的题目时要注意更据实际情况更正结果（比如 $0$ 的特殊情况应该变为 $lcm$）
经过这个题，我们可以得出关于 $CDQ$ 维护偏序问题时的两个小技巧。
对于有交叉关系的偏序式子，可以尝试合并和简化。（实际上本题并没有减少不等式的数量，但是我们把它转化成可以用 CDQ 解决的形式）
较复杂的不等式优先使用数据结构解决。
xxx 在 xxx 时间点出现在 xxx时间点消失，问若干个时间点的状态 $\to$ 线段树分治
对于难以直接求得的问题应当转化，得出可以整合有关信息的式子 $[l,r] 中 x 的第一次出现位置与最后一次出现位置之差 \to ∑ i-pre_{a_i}[pre_{a_i}>=L]$
构造：
对于一条边来讲：
- 如果最小生成树里所有被修改的边权都被赋成了 $+\infin$，而它未出现在树中，则证明它不可能出现在 $(l,r)$ 这些询问的最小生成树当中。所以我们仅仅在的边集中加入最小生成树的树边。
- 如果最小生成树里所有被修改的边权都被赋成了$-\infin$而它未出现在树中，则证明它一定不s会出现 $(l,r)$这段的区间的最小生成树当中。这样的话我们就可以使用并查集将这些边对应的点缩起来，并且将答案加上这些边的边权。
$a ? b,c : d,e$ 会被理解为 $(a ? b,c : d),e$ 所以别混着写，写 $if$ 。
初始化代码中有用到输入数据的务必要将初始化内容放在输入后！！！
斜率优化中，不要直接计算$slope$ 值，应当拆成 $dx,dy$ 写；注意要保证 $dx$ 应当是非负数，应为两边同乘负数要变号！
$eps$ 该加的还是要加，不要觉得无所谓
斜率优化 $dx,dy$ 相乘时要注意有没有爆 $int$
斜率优化有时候要边做边二分
对于数据结构优化 $dp$，一般有两种形式：
- 利用数据结构对于先前的最优状态进行选择统计；
- 将上一阶段 $dp$ 放入数据结构中，进行转移。
整体二分遇到不可加贡献，利用可撤销整体二分
奇环树上 $dp$ 可以考虑处理完子树再链上 $dp$ ，也可以直接拆环做 $dp$
处理修改（如离散化）结构体要引用 for(P &s : v)
数据范围较小的，用暴力；对于具有特殊性质的数据，找规律
遇到不适合除的时候，记下前缀积和后缀积
类似概率期望的题目不一定是概率期望，应当结合具体情况，进行分析；
有向关系+非树图，想到 $DCC$，$SCC$。
判断两点是否在一个点双里：
- 维护 $who$，$bt[x]$，其中 $x$ 为割点也要维护；
- $bt[a] == bt[b] || who[bt[a]]==b || who[bt[b]] == a$
测试图时，可以先用特殊结构的图，比如树、菊花图、链等等。
注意 #define for_edge 时，里面循环变量改为程序中不会用到的，比如_。
用并查集维护已经处理过的东西，防止多次处理，直接往后跳即可。
边的先后关系：拓补排序、贪心
我们有些看似复杂的题目，我们应当分析并提出性质，并进一步证实（证明或用暴力测数据），从而简化题目。
函数传数组使用的是指针时，memset(dis,0x3f,(n+5)*sizeof(int))，而不能直接写sizeof dis。
一二题一般都是简单题，很少有数据结构。如果有，操作也会比较简单。但是如果是树套树之类，那就是你写错了。
在做计数类题目的时候不能被其无序性迷惑，一定记住进行某种自定义的排序，使其变得有条理。
转化模型、寻找性质，以及拆贡献。
如果你 kmp 的 get_nxt() 结果有问题，多半是没在字符串前面垫一个#。
首先得知道矩阵可以解决这类经典问题：

给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值

把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=AA，那么C(i,j)=ΣA(i,k)A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要二分求出A^k即可。
矩阵一定要初始化大小和内容（包括重定义运算）
判断字符串是否相等使用哈希，自然溢出哈希会被卡。
线性基是一种很奇妙的东西，在求关于异或的东西的时候非常实用。同时，要注意它要与其它一些可以使用异或的数据结构区分，如01trie等。

它主要的用途有：
```
  1. 最大/最小/ $k$ 大异或和
  2. 异或和数量
  3. 异或和的和
```
同时又可以找到“子集”“子序列”等字眼，或者是图论中的某条路径的异或和时，就可以往线性基方向想了。
斜率优化尽量将 X 和 k 的负号去掉。
李超树维护区间最值时候记得 min(min(f(res[p],min(R,r)),f(res[p],max(l,L))),ans)。
以后不要直接用 map 做 string 的映射，应当自己弄出 Hash 值
写双 Hash 防止被卡
对于一个问题，将其关键信息提取，首先考虑设计 dp 状态
比较类问题，可以预处理倍增的 Hash，后类似 LCA 地跳
要去关注到相邻 f 的关系，从而得到上下界之类的性质，用于优化时间复杂度
对于环上向后填充的一个 trick：有一条边没有人经过，可以断开这里并转换为链上问题
$16$ 子集枚举；$20$ 状压，单个转移
构造排列：
- 不断插入
- 当放入合法数时，为了保持排列的性质，改变原来有的数（比如关心相对顺序时，加入$k$，对于原有 $\ge k$ 的数都 $+1$）
套路删边变加边
对于这种最终结果依赖于最后一次操作的时候，考虑使用“浮水法”，反转操作顺序，它被操作后就不再变化了，而实际操作顺序就是新操作顺序的逆序。
点分治要统计以 $u$ 为起点的路径
看到最值+位运算应当想到按位操作
树上，对于下方决策会对上方产生影响的，不防用 $set$ 记录方案集合，上传处理
先模拟，后体会并思考算法
对于一些问题，可以转化为多种数学问题思考并解释
看到区间中位数，想到二分
对于子树统计，有一重要构造，一子树中有 $ ∑ d_i = (n \cdot 2) - 1$
对于二维多次处理，可以考虑二维差分（可以在扫过来的过程中边差分边处理）
对于互相独立的多个二分询问，考虑离线整体二分
遇到封闭图形求图形内权值和可以转化为对行最一遍前缀和，然后按顺时针，计算所有向下的边减去所有向上的边就行了。
带依赖的背包 $\to$ 树上背包$\to$ 上下界优化/后序遍历优化
线段树合并是要注意 $y$ 在此之后会不会被修改，如果会，每次合并要新开节点，并注意线段树要开大空间
动态加点
- 倍增
- 离线+树剖
区间 $dp$ 的优化：开辅助数组统计关键信息，减少枚举。

C. 火星细菌 - 暑期练习33 - 比赛 - ZLOJ
$2-SAT$ 枚举限制以模拟无限制情况，不用全部枚举，只要包含所有状态即可。

F. 游戏 - 暑期练习33 - 比赛 - ZLOJ
2-SAT前缀优化建图注意边界的建图，不能遗漏！
矩阵的 trick：
- 类似转移时若状态可以停留在原地，那么将点向新建的 $0$ 节点连一条边并在 $0$ 建自环；
- 对于同条边不同边权，参见迷路的 trick，如果有权值 $W$ 大于 $1$ 的边，则将一个点分为 $W$ 份，设原图第 $i$ 个点分成的第 $j$ 份为 $V_{i,j}$。则 $V_{i,j}$ 向 $V_{i,j+1}$ 连边（$j<W$）；设原图上 $x$ 到 $y$ 有一条边权为 $z$ 的边，则 $V_{x,z}$ 向 $V_{y,1}$ 连边。
DAG 删点最长路：处理出以每个节点为起点和终点的最长路，按照拓补顺序不断将在第一堆里的点拿出，并放入第二堆，用可删堆维护两堆之间的 $f_u+1+g_v$ 的最大值。删点 / 边加查询最长 / 短路
交互题：1. 分治 2. 二分 3. 增量法
强制转化的时候长点眼睛！写成 ((__int128)x*y)而不是(__int128)(x*y)!
对于需要双指针维护不可差分信息（$gcd$，背包等），考虑维护两个栈，$l$ 到 $mid$，$mid+1$ 到 $r$，动态维护并定期重构。
排列的下标与值得对应关系可类比为二分图
同种元素之间将对距离不变可能是 DP 突破口
注意写的 add 函数可能有负数！！！
发现一次函数形式并且要求最值的，可以用李超线段树维护。
正确的状态有利于发现正解的突破口（即使时间复杂度更劣），应当从体面所给的信息（或找出的性质）出发，特意地被引导到正确的方向。
注意有取模时要注意模数的大小，有可能两倍会爆int导致答案错误. 同时答案之间如果是加减可以if (ans >= P) ans-=P; 否则要 ans=1LL*ans*X%P
如果读入数据里有负数不能直接用读入挂，要判负号.
使用位运算时要注意可能会溢出(如1<<35和1>>35 均会溢出).(实例可见 Topcoder SRM 613 Div2 Level three)
三目运算符（？：）的优先级很低，甚至低于+、-，尽量少用或加括号.
部分位运算的优先级较高，如！、~，相当高，然后是*、/，再是+、-，最后是>>、<<，更低的有&、^、|.
涉及到LCA的问题要注意可能在同一个子树内计算.(CF715E)
结构体排序的operator一定要这样打:

bool operator < (const node &A)const{
    return ...
}

注意两个const不能掉.

处理割点时注意根节点的处理，当且仅当获得的搜索树中根节点的儿子不止一个时才算上.
double型，printf()用%f输出，而scanf用%lf来接受输入(POJ3744)
有关概率dp常常是正推，期望可能是逆推，并且一定要注意到除数不为0，注意特判
EPS可以取1e-9, 往往比较保险，double精度..
Splay在Insert是如果遇到val==x时return的情况注意先splay一遍，更有利于把查找频率大的节点放在根附近达到均摊复杂度的目的
用Splay解决问题的时候一定要注意删除节点时对sz的影响，初始化节点的时候一定要son[x][0]=son[x][1]=0;
延迟更新是对节点u 的所有儿子使用的，对于节点p是直接更新的.（注意Splay 的规范性）

标签：二分,题目,优化,可以,experience,注意,My,dp
From： https://www.cnblogs.com/fight-for-humanity/p/18492275

相关文章

赞助商

阅读排行