vickyの做题总结

· · 个人记录

记录一些结论和技巧，省省脑子QwQ

复习的时候可以配合学会清单食用噢QwQ

正难则反

做题的时候不要怀疑自己！！！尽管冲暴力！！！QwQ

确定博弈中的必胜态

例题：ARC137C

网格图中有一线段，两端点均在整点上，两端点横纵坐标差值分别为 a , b ，求线段上的整点数。

例题：方格计数（组合计数）

看到题目条件记得第一时间将其转化为数学语言

例题：（同下）区间平均值

当题目推导式子得到含两个不同下标的不等式时

例题：区间平均值

当重生要打FJOI时考前记得去CF看traveller的代码。

例题：2022 FJOI省选

复习：THUPC2022想象

看到题目式子有固定系数时可考虑杨辉三角（组合数）

例题：交替

DP实质：不能漏情况&&状态转移间不能有情况重叠的分类讨论

例题：变换

前缀和可以用滚动数组（在线）

例题：P2671 [NOIP2015 普及组] 求和

遇到有固定求解式子的题目，首先考虑将其式子拆分成多个部分，分开来求解。对于每个部分我们可以考虑通过前缀和等手段进行优化。

这是一个很重要的计数技巧！！！！

例题：

\text{差分数组维护} 区间等差修改 \text{时使用二次差分}

说得有点抽象.....

就是当我们要对区间 (l,r) 进行一次区间加的操作时：

也就是对于区间 (l,r) ，我们要在原数组的每一项上加的数附合以下性质：

此时我们称我们操作时要加的值构成一个等差数列时。

此时我们考虑对原数组的差分数组再进行一次差分。

易发现等差数列中每一项与前一项的关系是保持绝对不变的。

这正是差分的关键所在。

详细讲解见这篇日报

总之，见到区间加值且加值相等操作时用一次差分即可；见到区间加值且加值间等差操作时用二次差分。

具体操作为：

1.我们在二次差分数组中的 l 位置加上等差数列的首项，在二次差分数组中的 r+1 位置减去等差数列的末项。

2.然后我们分别在 l+1,r 这两个位置加上和减去数列公差-数列首项的值就好了。

需要特别注意的是，我们二次查分数组中加上和减去的是数列公差-数列首项的值，不是数列的公差！！！！

因为我们在二次差分数组最前面加上的数列首项对它后面的项也是有影响的！所以如果我们直接加数列公差的话那么该操作的效果就是在原数组上加一个公差为首项+公差的等差数列！！！

具体为什么自己手玩一遍就知道了。

例题：P4231 三步必杀

当遇到题目要求区间操作为对其加一段有规律数列时

例题：

当发现自己的复杂差分跑不过样例时，第一时间查看是否有需要修改的位置没有修改到位！（用枚举+推式子看一下修改区间两端周围的位置是否有遗漏的需要修改的位置）

b_i=a_i-a_{i-1}

例题：

看到二项式的时候敏感一点，看看拆成二项式定理能不能得到什么信息。

例题：- P6308 「Wdsr-1」笨蛋结构

根号分治

更像是一种乱搞思想呢。

当一道题目具有以下特点：

那么就可以考虑使用根号分治了。

感觉就是不同做法的大乱炖&&有套路的瞎搞。

例题：P3396 哈希冲突

看到类似“K个互不相等的B的整次幂之和”之类的话要第一时间联想到转化B进制

例题：【CSND】数位DP入门——例题1

对于一个等差数列，我们仅需知道项数/公差/首项/末项中的两/三（首项末项+随便一个）个信息即可求出该数列。

例题：[SCOI2009] windy 数

关于最长上升子序列长度的 O(n log n) 解法

  1. 对于求解序列 a 的最长上升子序列长度，我们定义一个数组 A ， A_i 的意义为长度为 i 的最长上升子序列的最后一位最小可以为多少。

  2. 我们从 1~n 枚举 a 的每一位，然后在 A 数组中找到第一个大于等于 a_i 的数（下文称为 A_j ），然后用 a_i 替换掉 A_j ，此处用 lower_bound 即可实现。

  3. 那么最终 A 的长度就是 a 的最长上升子序列的长度。

例题：

当题目对于一个序列只关心序列中的元素的相对大小关系时（也就是可以忽视数值时）

  1. 若原序列中的数字很大，考虑离散化。

例题：普通平衡树【权值线段树做法】

  1. 若题目中可直接忽视数值而只注意大小关系，针对每一个数原序列中存在的 n 中相对关系，我们可以将序列转化为 n 个如下序列：

例题：排列（DP）

比如在例题中很显然只存在两种关系：大于/小于。

且我们容易观察得到序列的操作实际上之关系元素与元素间的大小关系而并不关系元素具体的值。

故我们考虑对于原序列 a 中的每个元素 a_i ，我们将比它大的数转化为 1 ,将比它小的数以及它自己转化为 0 ，我们解题就可以找到突破口了。

位运算trick

当见到题目说两个序列有对应元素互斥时第一时间想到状压DP/找互斥性质

可将对应元素替换为0/1，然后运用位运算进行判断两序列是否互斥。

例题： P2150 [NOI2015]寿司晚宴

（博弈论）当有多个石子堆，且博弈者每次取石子的数量一定时

你取了a个，对方紧跟着你在同一堆取了b个，一轮减少（a+b）个 ，其实无论经过多少轮结果都是一样的。

该输的照样输，该赢的照样赢

那么就把每个堆的个数 \mod (a+b) 不就好了？

如果有多堆的话，一人突然对另外一堆来操作，这时，另一人会紧跟前一人去同样的堆操作，且在前一人重新对原来的堆操作之前，也不对前一堆操作。

这样，其实第一人只是将操作推后了而已，他还是要操作的。

那么，为啥另一人会跟着呢？

因为前一人换堆肯定是因为他不换就会输、后一人就会赢，所以后一人这样就可以将前一人锁定在必输的情形，这是出于最佳策略。

所以当我们遇到这类情形时，我们可以直接将每个堆的个数 \mod (a+b) ，然后将其分成四类：

我们假设两位博弈者 A 、 B 每次分别取 a 、 b 个石子，有多堆石子，且第 i 堆石子的个数为 x_i ，保证有 a<b 。

看到顺序相关类的题目时记得试试从相对顺序这一角度进行思考。

SG 找不出规律怎么办？

遇到一些特殊操作如翻转的时候

看一下这个操作是否进行多次相同操作之后等于没操作，如果是的话，考虑数据范围是否支持直接暴力枚举每种情况。

实在不行加个剪枝&相信自己一定能过的。

例题：

遇到下标相同的两项数字的乘积求和时

也就是求 \sum\limits_{i=1}^{n}a_ib_i 时。

我们可以考虑将a或b序列进行翻转，然后求 \sum\limits_{i=1}^{n}a_ib_{n-i}。此时我们就可以用fft来进行多种匹配的求解。（即a_ib_{n-i}、a_ib_{n-i+1}之类的匹配的求解）

例题：

看到数据范围带个 \sum \leq \text{能过} 的题目

第一时间考虑是否是虚树，即题目的是否动规可做、动规的关键点是否可组织为树状结构。

组合计数问题看到求非严格单调性序列个数，果断在可选择个数后面加上重复数字个数。

例题：

遇到类似蜂窝网络之类的位置可转为二维坐标，但是其相对的相邻关系并不只是一对四的题目时。

直接转多维，用切比雪夫距离、曼哈顿距离、欧氏距离之类的奇怪求距离方式进行二维转多维之后的距离求值，得到可判断的相邻关系。

例题：