Tricks

zhqwq · 2019-07-30 15:09:03 · 个人记录

• 如果动归的状态过多可以通过容斥的方法

  好像说了和没说一样……

  给个例题好了：ZJOI2016 小星星计数

  2020.5.3update:又来一道！

• 考虑每个元素对答案贡献

  经常见，但是并不能每道题都马上想到诶

  比如两道考试题它和它

• 树上如果是一次性给你若干条链，为啥不考虑树上差分呢hhh

  比如天天爱跑步和雨天的尾巴是吧hhh

• 最大化两个东西的和，直接搞不方便，考虑枚举其中的一个。

  如这个题BZOJ3145 最大化LCS+LCP，考虑枚举LCP，最大化LCS

  更推广一些（也不算推广吧），要最大化某个东西，也可以考虑把难算的枚举一下

  比如4510 [CTSC2015]性别改造计划 ，最大化⌊10ln(1+A)⌋×S−C 考虑枚举ln的取值。

• 子树问题转dfs序
  链上问题转欧拉序列（啊应该是括号序列吧……）。。

• "序列同时加上某个数相同"

转化为做差分

2463 [SDOI2008]Sandy的卡片

• 关于括号序列的套路是，左括号视作1，有括号视作-1

• 很多对于区间的问题，如果区间之间没有包含关系，那是好做的。

考虑有没有什么方法去掉包含关系。

看这里

• 据说也是对于构造一棵树比较常见的思路，是你考虑当前这棵树最靠右的那条链是啥，拿个栈维护一下。

看这里

• 只有删除操作考虑倒叙插入；只有插入操作考虑倒序删除。

• 通过考虑“第一个不合法的是谁”把2^k的容斥优化成Poly(k)

看这里

• 额。。你发现，点数很少，如果我们能快速地判断一条边通往的是不是一个已经走过的点，那判断一次的复杂度就从和m相关，变成和n相关。

  那，如果用一个bitset记录哪些点还没走过，然后再和表示邻接矩阵的bitsetand一下不就能快速找到了嘛！！

  bitset里有俩函数可以帮助我萌找到所有为1的位置！见代码。

还是看这里

• 枚举右端点，数据结构维护所有左端点的答案（的和?）

2020SDSC Day2T2

套路！

树上联通块数=点数-边数

仙人掌上联通块数=点数-边数+环数

算所有区间的某个值的和，考虑枚举右端点，数据结构维护所有左端点的答案（的和）

线段树维护平方的和

啊

• 不断给你某些条件，判断加入哪个条件时开始不合法

可以考虑一个一个条件加入，也可以考虑二分。

而二分的好处之一是——可以离线了。

• 那些覆盖的问题，我们从后往前考虑，这样后操作的点可以看做被“删掉了”

啊

• 我也说不太出来这是啥套路，但感觉很妙：

使用字符串Hash，O(n)求最长回文串？

就要求最大值，我们就枚举的过程中让它尽量变大。复杂度就O(n)啦

2021.3.3update:又见到了一个例子：区间众数的一个做法。

这里

• 元素A对应若干元素B。要求对某个元素A，求它对应的元素B的最小值。

从大到小考虑元素B，对于和它对应的所有A的答案打上一个覆盖标记——因为之前考虑的都比它小，不可能成为答案了。

说的很概括而笼统，是从这里（“讲题”的第一题（钟神出的题！））来的，感觉很强！

这个题是在树上，所以并非单纯从大到小考虑，而是dfs的过程中考虑。主席树维护覆盖和撤销覆盖（回溯时）操作。

• qbxt 11月Day9T4正解做法&区间mex问题

思路都是：求某些元素中，符合条件的最小权值；二分后转为判断，是否权值<=mid的所有元素都不符合条件。

这里和这里

• 把“每个点的存活时间”转化成“每个时间有多少个点存活”加起来

• “轮数可能很多，注意到每轮的贡献是关于“第几轮”的多项式

  预处理这个多项式的系数，用自然数幂和即知前缀和。”

上两个都是noip的这个题：这里！

• 对抗型的Dp，往往是外面取max里面取min这种，分别对应两个人的决策

ZROI2021省选Day1T1

• 每个元素(v)都会给其他元素(x)做贡献

两个自然的想法，一个是预处理每个元素对其他所有元素的贡献 一个是对于每个元素直接快速算其他元素对它的贡献和（于是顺着这个思路想了好久的换根DP）。

然鹅还可以分别考虑每对元素(v,u)的之间贡献（考虑v对u贡献了多少 ——既不是先一个一个枚举所有v，考虑它对u的贡献 ——也不是一个一个枚举所有u，考虑所有v对它的贡献 而是按照某个顺序，把每对(v,u)都考虑到了——只是为了能做。

在树上，这个“某个顺序”就很可以是点分治了！分治的过程中，每次只考虑路径经过分治重心Rt的(v,u) ，而最终一定会把每对都统计到

ZROI 2021省选十连Day1T2

• 数点问题，如果有一维每次修改询问的区间长度都为1（单点），直接把这一维的每个值分别开数据结构。

如单点带修求区间[l,r]中多少个数权值为x，当然不要憨憨地树套树，直接动态开点开n棵线段树就行了

• 兑换型问题：要么全换要么全留着。

4027 [NOI2007] 货币兑换

• 和不超过多少，我们考虑把前缀和状压（而非记录到底选了哪些元素）——这样写暴力也好写。。

这里

• 根号平衡优化转移和预处理。神乎其技

序列妙妙值

• 拼凑的思想：

最优化f[i][j]：f[i][j]=\max(f[i][j-1],f[i+1][j],a(i,j))

如SAM上，求一个状态所有子串的最大值，可以去掉开头（跳fa），去掉结尾（是go指向它的那些点）的串的值取max。再和自己本身的值取max。

计数f[i][j]：f[i][j]=f[i][j-1]+f[i+1][j]-f[i+1][j-1]+cst(i,j)

（分块时有用。。）

• “第k个”可以二分，计数变成<=x的有几个。

• 分治解决“挖去某个位置”的这种问题

here

• 3260 [JLOI2014]镜面通道：能透气就能透光，但是我估计这个结论再也不会遇到了。

• 优化空间的一个思路：发现是不是可以换换枚举顺序，当某一维度的位置固定时，是不是不需要这一维其他位置的信息。如果不需要，那就可以每个位置分别处理信息分别考虑，这个维度就去掉了。

一个题https://codeforces.ml/gym/102391/problem/K笔记

还有这个T2

• 对于给定的数组a_i，若存在一个x使得(a_1+x)xor(a_2+x)...xor(a_n+x)，那么x可以从低位到高位归纳证明是唯一的：

这里problem11

• BSGS的想法可能在好多题里出现。

HDU6331。好像是在走边类型的问题中经常出现

• Z变换：ab=C(a+b,2)-C(a,2)-C(b,2)。

这样就只和a+b,a,b有关了。组合意义可考虑两个点集之间的连边。用总的容斥掉内部的

• 树上距离的处理：

  • 点分治

  • dep[x]+dep[y]-2dep[lca]

• 移动左端点，考虑所有右端点的贡献，即使强制在线也可以通过可持久化来做。

• 二元关系看做边，更进一步地，两种选择看做给边定向。

• 枚举一个L，再枚举一个R，快速判断[L+1,R-1]是否全部合法，不好做。

  换个方式：维护哪个角度区间能让[L+1,R-1]是合法的，然后check一下<L,R>是否在这个区间里即可。

  看这里T2

• “区间内子段最值？”考虑扫描线（枚举右端点考虑左端点答案）再来个支持历史最值的吉老师线段树。比如GSS2

• 最小的K个？二分！见THUSC2021T1

• 当函数变化是连续的（比如+-1），可以维护区间最大值，最小值，利用类似零点存在定理的方法二分“最后一个为k的值”。

• 有的题可以通过在外面二分减小DP状态数。

一个例子是，，，NOIP2017普及组 跳房子

没 想 到 吧

还有这个T3

• 正着做没前途的时候，下意识想想反着做会怎么样。

• 构造方案，n个的可能就是n-1个的基础上加上一个元素。

背后的原理可能是费用流/阿狸桃子/调整法/blahblah