记录了博主平时考试 (爆零 + 划水) 时碰到的一些非常棒 (毒瘤) 的一些思想以及方法.
- (因为我太菜了总是会忘 QAQ)
- $ Begin ?from ?2019.7.19 $
- 1.
对于两个点之间与 下标 有关的 (一次项) 贡献, 可以转换为 已经放了的数与还没放的数之间 都有 1 的贡献
ps: 高次似乎并不行
例题
- CometOJ_#7_C https://www.luogu.org/blog/Ameiyo/cometoj7c
- CodechiefSCDP-H https://www.luogu.org/blog/Ameiyo/codechiefscdp
- 2.
注意 两两不等 的量可以引发出的许多关系
例题
计蒜客四月普及模拟 $ D $ 题: 苹果树 https://nanti.jisuanke.com/t/37250
博客还没打, 就是由权值两两不等得到最多只能选 500 个苹果, 然后树形 $ DP $ 直接搞.
3.
区间 <-> 前缀和
ps: 选一些数可能可以转变为一个区间
例题
数学题 https://www.luogu.org/blog/Ameiyo/shuo-xue-ti
这题真的是.... 没见过想不到
51Nod 第 k 大区间 2
二分之后的 check 里把区间转换成了前缀和来用树状数组进行计算
4.
注意把每个数的 贡献 独立出来, 尤其是在碰到 绝对值 等奇怪的东西时.
例题
ABC134_F Permutation Oddness
对于每个数来说有两种贡献, 一种是下标, 一种是数本身.
一个数放的位置会影响绝对值拆开来后的符号, 枚举前中后转移即可.
5.
注意 离线算法 的应用.
离线算法的应用非常的多, 做题时更重要的是对 题目给出条件 的认识或是对 题目性质 的挖掘
### 例题
题目 https://cn.vjudge.net/contest/292301#problem/D
见 这篇博客 的 $ D $ 题, 标记打上后不会抹去是离线的关键.
AHOI2005 航线规划
题目保证了图一定联通, 而且删掉的边不会再连上, 所以可以离线.
6.
对于与异或值有关的题目, 可以先随便来一个, 在对他进行 更改 .
例题
[Wc2011] Xor
见 这篇博客 , 非常巧妙的利用了异或.
7.
一条链唯一的对应着一个序列.
8.
与异或有关的题往往都和贪心或者是异或的自反性有关.
9.
最短路有负边时不能用 dij
10.
所有的回文串都是从相邻或间隔为 1 的子串开始的
11.
把二维的东西压到一维上面
- (时隔三个多月的更新. 咕咕咕)
- $ End ?in ?2019.12.06 $
零碎笔记
来源: http://www.bubuko.com/infodetail-3319406.html