牛逼题

CF1770F，首先由对称可知n是偶数就为0，否则，我们考虑钦定中间那个数的值，我们发现or=y限制很强，考虑容斥一下，然后我们需要去枚举y的每个子集，有一连串连乘\([ai⊆y']\)的东西，我们直接组合数奇偶性逆用，由\([n⊆m]\)变成\(\binom{n}{m}\),\(mod2\)，然后就没了

loj3067，发现有个简单dp，dpi表示匹配了前i个的最小花费，然后弄个正反trie，转移n方。然后考虑，其实一个trie上的节点的祖先顶多有根号个不同的代价（显然代价递减）然后分块，填表刷表一起弄

曼哈顿距离与切比雪夫距离互换

p7561，曼哈顿\((x,y)\)可以化成切比雪夫\((x-y,x+y)\)，这样算两点间距离就是\(max(|x_i-x_j|,|y_i-y_j|)\)，切比雪夫\((x,y)\)可以化成曼哈顿\((\frac{x+y}{2},\frac{x-y}{2})\)

trick

平面图，如果判断矩形或者圆形是相交或者包含，有个关于半径线性对数的做法，半径从小到大加入，如果超过当前块的两倍，暴力重构，这个肯定是nlogn的，每次搜当前周围25个块，块内暴力，如果是包含直接删除

p7323，某些有传递性，反转性的东西可以划为一个集合，此集合内两两可达

agc002_e，画成图，发现好做

倍增跳

p5465，其实就是倍增，第一步要特判就没了，有点反悔贪心的意思

dij（题）

CF843D，dis较小可以桶优化dij，然后考虑再增量图上跑dij，只能说很牛逼

最小割思想

比如n个任务m个时间，每个时间做一个任务之类的，考虑最小割，左边n个点代表任务，右边m个点代表时间，如果有别的附加条件另说，然后就是在哪里割的，就代表采用了这个元素

线段树合并+树上差分

P5327，没什么好说的

析合树思想

CF1089i，先容斥，连续段可以考虑析合树，但是也可以不用，考虑极长连续段为最长的连续段不等于n的，那么有两种情况是算入不合法的，一种是只有两个最长连续段，可能相交，另一种是四个及以上彼此不相交的连续段。进行dp就行了，

组合数推式子

CF1264D2，首先想到n方的，枚举位置，枚举答案，为什么不重不漏，因为ai递增，bi递减，每移动一次必然有一个边，ai=bi的时候算答案是恰好一次，然后考虑如何线性，发现式子是这样的，\(\sum{j}* \binom{s2}{j-s1}*\binom{s4}{j-s3}\)考虑把j换成j-s1这样就不用枚举j了，然后范德蒙德卷积就完事了

构造

CF1510J，发现一次最左一次最右边，取每一段的交，不是每一个，然后发现偏移量最多不超3做完了

轮廓线dp

p2435，qwaszx写的很好，字面理解就是按层dp时，按照轮廓一个一个凹进去转移

广义串并联图

精髓在于，删一度点，缩二度点，叠合重边

p6790，定义f，g分别表示这条边在生成树与不在生成树的方案

p8426，如果1和n不在一个点双内，加一条边连接一下1和n，权值为最短路，问题变为1和n都在的点双内的问题了，如果这张图同胚与\(K_4\)那么肯定有解，因为边权为正整数，否则就是个广义串并联图，直接做就行

串串

p4156，首先发现能接上的话得是用一个border来接，然后其实就成同余最短路了，n方的。考虑优化，有个性质，一个串的border长度可以被划分成log条序列。考虑如何在同余最短路上跑等差数列，如果模数等于首项，那么很好做，单调队列优化即可。不是的话，考虑换模数

CF1909G，首先考虑枚举xy与z的分界点，然后目标是求出最小周期，但是周期不能大于\(LCS(xy,y^{k-1})\)，发现指针向后移的时候这个LCS要么+1，要么清零，那hash判一下就做完了

ACAM

CF1483F，首先考虑固定每个r，只有一个l，怎么判断某两个串的中间是否夹了一个呢，对于i串，如果j串的出现次数=被计算次数，那么ans++

trick

要求多个区间的某些东西的并，可以考虑bitset，比如并的不同ai的数量，这种东西不是很好合并，让我现在来做，可能考虑线段树合并，但是其实考虑bitset合并是很好的

CF838D，考虑没有人会出去，多开一个状态记录寄掉的，就做完了

DP

CF778E，本来应该会的，之前见过进位套路的题，其实进位集合不是散的，而按后i位排序大小排序好后，是一个前缀

arc163_d，竞赛图缩完点后很有性质，发现一个图的SCC个数=分成两个集合，A和B，连接这两个集合之间的边都是从A到B的，然后直接dp就做完了

CF1363F，简单dp，只要发现本质操作是让一个s里的char向前走若干步就行

arc150f，首先有个显而易见的dp，\(dp_i\)表示和为i的情况下最小的指针，s方的，然后考虑分治，发现dp有单调性考虑枚举加的值，sgt做完了

p4548，期望题，稍微推一下式子然后就是kmp上dp

cf1992f,典题

p4582，双重心好算，分开dp然后枚举两边x=y的个数，单重心考虑容斥，算一个子树大小超过一半的，维护前缀积，后缀积即可

p5369，典题，考虑枚举一个集合表示最大前缀和就是这个集合的和，后面的数保证最大前缀和<0，后者好dp，前者加一个数是加在最前面，因为最大前缀和要么是之前的数，要么是第一个数

cf513e2，通过给一些限制使得是最优解就是答案，比如这个题很多dp方程不是很符合道理，但是不符合道理的选了一定不是最优解，所以可以选

反射容斥（神秘双射）

CF348D，妈的，典题都不会了

arc068_d，首先容易发现序列是个单谷序列，取出的序列前k项是有两个单调递减的序列弄得，容易得出dp，\(dp(i,j)\)表示考虑到第i项，贪心的放的情况小，第一序列的最小值为j，转移系数发现都是1，然后进一步发现等价于走格子，dp第二维有个上界，不能超过，然后做完了

p3266，容易从dp式子发现是个走格子类型的题，不过有两条线不能走，我们考虑将翻转过的点再次翻转，容斥一下即可

cf1924d，印度人玩原神玩的，发现有m-k个右括号，n-k个左括号不匹配，也就是画成折线最低点是k-m，发现最终点确定了，那么就是让我们统计这样的折线数量呗，随便容斥就做完了

线段树分治

CF603E，首先得发现一个性质，不能存在大小为奇数的连通块，否则是-1，然后静态问题是krusakl，达到条件后break，一个边的存在有单调性，被淘汰了永远回不来了，线段树分治，怎么算影响范围？边分治边覆盖

费用流模型（模拟费用流）

CF802O，显然有个费用流做法，但恰好选k个，可以考虑wqs二分（好像是个很常见的套路），然后wqs二分里面是个反悔贪心，或者说里面也是个费用流

分治

CF1787I，一眼看出两部分答案独立，分别计算，区间前缀最大值好算的，不说了。然后第二问直接分治，然后发现要么是一段右区间子段最大值，要么是左区间子段最大值，要么是前缀后缀拼起来的，枚举l，容易发现f(p)-g(p)单调，两个指针分开三个区间，做完了

数学

LOJ3626，行列式+树形dp，行列式介绍https://www.cnblogs.com/hello-/articles/10354991.html

计数

CF1085G，显然的，算rank等于算小于的数量，然后计数是平凡的

agc022_f，操作可以看作树，最终答案是个多项式\(\sum2^{d_i}(-1)^{ci}\)只要有系数不同，方案数就不一样，di跟深度有关，考虑一层一层的dp，ci只看奇偶性，跟儿子个数和比这个点后插入的满足是他的兄弟的点的奇偶性有关，然后dp

agc013_e，考虑组合意义，一些隔板分成很多区间，每个区间里恰好有一个颜色a的球和一个颜色b的球，发现总方案数这就是原问题要求的考虑dp，矩阵转移

gym102538h，考虑向一个空图里加点，然后发现环一定是1010101的形式，所以得记录链的数量，就没了

AT_hitachi2020_f，考虑G和H的共同点，那就是rt（直径中点）的dis不变，发现如果dis确定了可以唯一还原出H图，发现H图直径唯一，然后就可以以rt为根dp，（u，v）的差值可能是0/1/-1，这是BFS的性质

CF1554E，其实就是给边定向，因为一条边要么给u贡献1，要么给v，那么总方案数好算，发现k=1不会，容斥，发现k>1简单

线段树

P6794 区间推平，区间赋值为到一个点的前缀极值/后缀极值

p3246，线段树历史操作

树状数组维护组合数

https://ac.nowcoder.com/acm/contest/147/H

负数组合数也满足规律

凸性在最优化问题的应用

CF1229F，首先破环为链，简单dp，\(dp(i,j)\) 表示第i个点向后流j（可以为负），方程 \(dp_{i,j}=min_{k}^{}dp_{i-1,k}+|j|\) 我们只需要顶住\(x0\)即可，然后发现\(dp_i\)是个下凸包，先不管\(|j|\)，发现就是凸包向左右平移，\(|j|\)其实就是让左边斜率-1，右边斜率+1，可以用堆维护，这个东西好像叫slope trick，就是维护每个折点，相邻三个折点组成的两个线段斜率差常数个1

贪心

CF1693E,非常好的贪心，主要是找性质，发现肯定是一段前缀用向前操作，一段后缀向后操作中间的一段怎样都行

P6631,想到如果连续大于等于两个非0一定直线，否则跳线。可如果要舍弃一些线呢？也无所谓，看看那个线更重要保留哪个