神禾必思维题解题方法
PP__
·
2023-08-13 20:17:15
·
个人记录
划分段数
比较讨厌的题目之一。题意大概是将 a 数组划分成 k 段，使得每一段满足某种条件。
这时考虑动规或贪心，或者推出前缀和等性质。同理，我们可以化简题目要求的式子，容易发现性质。
1、神秘科技+暴力+性质
Aulvwc
易得，如果要使整个划分出来的数列的平均数相等，那么这些段内的平均数就等于整个数列的平均数。然后我们将所有数减去平均数，问题转变为将数列划分成两个子序列使得每个子序列的和为零。因为很明显如果不能划分为两个子序列的话，那么也划分不出更多的子序列。那么最后再加上一个随机化科技或者马学长的同余科技就可以脏过去。
2、前（后）缀和+性质
oiclass:Array Splitting
luogu:Array Splitting
黄的，但差点不会（乐）。
化简式子，将式子转化为（sum 为前缀和，p_i 为分割点，从小到大排列）
\sum_{i=1}^{n}a_i \times n - sum_{p_k}-sum_{p_{k-1}}-\dots-sum_{p_1}
我们要使得答案最大，就使式子最小。前面的和显然固定，使后面的前缀和最小就行了。最后注意处理边界问题。
中位数性质题
还是可以接受的。遇到这种题一眼显然，但重点在于用一些数据结构来维护中位数，例如STL的set，权值线段树，对顶堆等等。
环形分金币（？）
oiclass:分金币
luogu:分金币
很典，所以很明显最后要使得每个人的金币数等于整个数列的平均数。所以最后转变为一个前缀和问题。详细解释过程可以参考题解。
区间等值
oiclass:砖块Klo
luogu:KLO-Building blocks
很典，目标是每次能够使一个数加一或减一，最后整个区间之内的数都相等。设 t 为最终变为的数，s1 为区间中所有大于 t 的数的和，cnt1 为这些数的数量，s2 为区间所有小于等于 t 的数的和，cnt2 为这些数的数量，证明显然如下：
ans=\sum_{i=1}^{n}|a_i-t|=s1-t*cnt1+t*cnt2-s2
显然当 t 取区间中位数时，ans 最小。所以我们要求的就是区间的中位数。那么因为题目给了我们区间长度，我们不用可持久化，我们就每次加一个数、扔一个数，做一个类似“滑动窗口”的东西就可以了。具体维护可以用权值线段树、set、对顶堆等等，做法较多。
暴力出奇迹题
这种题一般给出的限制比较严格，所以一般只有几个状态，直接手玩出来，暴力枚举即可——但如果没有想到这种暴力就比较难做。
只有几个状态的**题
oiclass:Say no to Palindrome
luogu:Say no to Palindrome
给出一个纸糊串，每次询问一次 l 和 r ，回答使区间 l 到 r 中不存在长度大于1的回文子串最少需要改变多少个字符。数据较水，字符只有a,b,c三种。
我们想到一个动规，但怎么动规呢？显然不行。我们手玩一下，发现一个重要的性质：如果要使区间中没有大于1的回文子串，那么三个字符应该交替出现！为什么？如果两个字符交替，就会形成长度为3的回文子串；如果相邻两个字符相等，那么显然也不行。排除掉这两种东西，我们就只剩下了三字符交替的情况。那么我们暴力枚举一遍三个字符交替的顺序，然后最后看一下区间内跟我们目标的串相差最小的答案，用前缀和乱搞一下，最后取一个 min 就行了。
括号序列
这种题一般是判断合法括号序列，这时只要思考性质或推动规方程即可。
括号序列
oiclass:Bracket Walk
luogu:Bracket Walk
#### 括号树
[括号树](https://www.luogu.com.cn/problem/P5658)
推出一个重要性质：如果当前右括号可以匹配一个左括号，那么如果左括号前是一个右括号，那么当前右括号的贡献等于这个右括号的贡献加一。这也是很显然的，因为以当前右括号为区间右端点的情况，就只有在这个右括号匹配的左括号的左边已经被匹配的左括号数量，再加上这个区间本身。所以用手写栈模拟就行了。
#### 区间DP+性质题
[括号序列](https://www.luogu.com.cn/problem/P7914)
比较离谱的一题。设几个不同的动规数组，然后暴力进行区间DP，然后考虑好细节就行了。遇到这种题应该合理考虑DP，同时推性质。
## 异或
对于这种东西一般考虑异或前缀和。因为异或有着跟加法相似的性质。同理，对于树上异或问题，我们只需要将前缀和改成树上从根到节点 $i$ 的异或和，求 $x$ 到 $y$ 的路径上的异或和，即为 $sum_x xor sum_y$。
#### 异或和翻转（诈骗）
[区间翻转区间异或和](https://www.luogu.com.cn/problem/P9533)
重点在于推性质。先考虑不翻转的情况。那很显然，我们只用考虑原序列的区间异或和为零的区间的数量。那么答案显然就是异或前缀和相等的情况。那么我们再考虑翻转的情况。
我们翻转的目的显然就是要使右边的区间异或翻转区间的原左边异或和为零。那么我们设右边区间异或和为 $c$，翻转区间原左边为 $a$，翻转区间原右边为 $b$，那么显然，我们翻转目的是使 $a xor c = 0$。那么显然要翻转区间，则 $a xor b = 0$。那么得到这两个柿子，我们易得 $b xor c = 0$。那么区间翻转跟不翻转，都有两个区间。同理，再次翻转翻转后的区间 $a$ 和 $c$，都是一样的。所以翻转跟不翻转的贡献一样。直接统计答案就行了。
## 构造
没什么好说的，主要是找到性质，然后手玩一下样例就可以了。
未完待续