做题流程

• 仔细看题，不要看漏看错看反
• 注意条件与数据，思考时间复杂度与猜测算法
• 尝试转化问题为相似已知问题
• 尝试多手玩/打表，找性质与规律
• 没思路时，多想什么题目条件没用上
• 尝试构造一些常见的性质，比如单调性
• 也从暴力枚举开始思考优化
• 或者正难则反
• 或者从简化版的题目开始思考
• 或者思考贡献

CF1993B

题目

想要构造出奇偶同样，可以看出若奇数转偶数只能奇+奇，必然最后还是会有一个奇数转不了

所以除本身本就一样外，只能都转为奇数

所以我们贪心的将所有偶数转为奇数（对偶数加上一个奇数），我们怎么贪心呢？

不难看出可以我们每次选最小的偶数加上最大的奇数变奇数是最优的，可以直接从贡献的角度证明这个贪心

所以排序然后贪心即可

其实可以进一步推出更简单的结论

ABC249D

题目

先维护频次数组cnt，然后排序原数组

此时不难想到暴力做法：

枚举下标$x,y$,此时答案即为$cn{t}_{a_x}\ast cn{t}_{a_y}\ast cn{t}_{a_x\ast a_y}$

这样减枝其实就是正解

为什么呢？

显然$a_y$满足$a_x\ast a_y<=a_{max}$,所以就算最坏情况下$a$为从$1$到$2e5$等差为1的数列，$a_y$加上这个约束减枝之后就是个调和级数罢了

所以复杂度为 $O(nlogn)$

ABC359D

题目

仔细观察题目数据范围：

$$n<1000,k<=10$$

k很小，可以直接$O(k)$判断是否回文

同时字符串实际只有A和B两种状态，不难想到这里可以状压表示子串

我们定义状压信息，二进制左边表示字符串左边状态

对于一个新的问号，当我们加入时，何时会贡献出长度为k的回文子字符串？

只需要考虑前k-1个字符构成的子串即可

令 $d{p}_{i,j}$ 表示第i个字符且前k-1字符状态为j时的合法串数量，c表示当前字符是0或1

当 j<<1|c 不为回文时有转移方程：

$$d{p}_{i,t}=d{p}_{i,t}+d{p}_{i-1,j}$$

其中：

$$mask=(1<<(k-1))-1$$$$t=(j<<1|c)\mathrm{\&}mask$$

这里mask用于清除多余前k-1个多余状态

CF1037C

题目

第一种操作可以一次变两个

所以我们贪心的尽可能做第一种操作

因为是01串，所以我们统计要转变的的0和1的个数，取其中小的做成对操作1，然后剩下的做操作2即可

CF1905C

题目

最大字典序子序列

要注意最大字典序子序列的定义

比如对于字符串"aebd",最大字典序子序列是ed而不是ebd

经典单调栈维护最大字典序子序列

该子序列显然是单调递减的，反转次数即为长度-字符串中最大字符的个数

然后再检验一下反转之后是否的字符串是否合法即可

LC1665

题目

从贡献角度考虑：

对于数组中两个元素(a1,m1)与(a2,m2)

怎么样计算最优？

顺序计算贡献s1为max(m1,m2+a1)，逆序s2为max(m2,m1+a2)

若s1>s2:

1. m1>m2+a1 && m2>m1+a2 && m1>m2

   因为a与m均大于等于0，该情况不成立

2. m1>m2+a1 && m1+a2>m2 && m1>m1+a2

   因为a与m均大于等于0，该情况不成立

3. m2+a1>m1 && m2>m1+a2 && m2+a1>m2

   此时成立

4. m2+a1>m1 && m1+a2>m2 && m2+a1>m1+a2

   此时成立

所以若s1>s2，则有：

m2+a1>m1 && ( (m2+a1>m1+a2 && m1+a2>m2) || m2>m1+a2)

化简则有： m2+a1>m1+a2时s1>s2

若s1<s2则与之相反

所以我们按照m2+a1>m1+a2排序然后贪心的去补即可

LC2602

题目

如果数组元素需要的操作都是增大或者都是减小时：

我们可以直接用数组元素和s减去q*n，就是需要操作的个数

但是若数组操作有增有减则不行，因为求和会抵消一部分本来应该操作的个数

所以可以想到我们把数组分为大于等于q和小于q的两部分，分别贡献计算即可

对原数组排序,并维护一个前缀和，然后对于每个q二分找划分点，然后按照贡献分两半计算即可

LC2608

题目

最小环板子

以任意一个点为起点，显然bfs重复入队节点的时候就找到了环

我们对每个结点都尝试作为起点跑一遍bfs即可

最大环

最大环会在最坏情况下变为哈密顿回路

所以是一个NP问题

LC3122

题目

我们可以先预处理一下每一列变成每个数字的花费cost

对于列两两不相同的要求，我们很难构造出决策单一的贪心思路，因为每次的选择都会相互影响

所以定义DP转移：

$$d{p}_{i,t}=\underset{k}{min}(d{p}_{i-1,k}|k\ne t)+cos{t}_{i,t}$$

复杂度为$O(n\ast k^2)$,因为$k$很小，所以可以AC

注意到实际上我们可以只维护上一个的最优$t$和次优$t$，每次转移从左到右必为两个之一

所以可以优化到$O(n\ast k)$

LC3081

题目

当增加一个问号转换为某个字母的时候，产生的贡献为该字符串的该字母次数

并且替换之间互不干扰，所以决策独立，我们可以直接贪心

所以统计字符个数，然后堆维护最小，贪心的每次将问号转为出现次数最小的字母即可

LC834

题目

求每个节点到树上其他节点的距离和，这种提示太明显了，一眼：

两次扫描，换根dp

对于固定一个节点到树上其他节点求距离和，我们可以直接DFS

然后我们思考转移根对整体的贡献：

手玩一下，可以看出子树的距离都减1，非子树的距离都加1

所以第一次先预处理每个子树大小并计算节点0到其它点的距离和

然后第二次从0节点开始换根转移：

$$d{p}_{son}=d{p}_{mom}+n-2\ast tre{e}_{son}$$

LC2581

题目

我们很容易验证一个点作为根的时候是否满足条件

思考换根的时候对整体贡献变化是什么？

假设由根节点由u转移到v，显然这只会影响到u与v父子关系

则有转移方程：

$$d{p}_v=d{p}_u+{mom}_{v,u}-{mom}_{u,v}$$