F题题解： 大致思路： 先看操作成功的规律： 对于一个  和 ，按二进制来看  的  最低位（即 lowbit）加进  中，会变为  ，并进位，而更低位的值不会变化。下一次  的  最低位 将会变高，而当  的  最低位比  的  最高位还高时， 的值将不会发生变化。 举个例子： 如果  （二进制表示）   第一次操作：     第二次操作：     第三次操作：     之后 ， 的值将不再变化。  二进制最高  位，故  最多变化  次。 我们只需求出小于等于  次变化的概率； 然后用  减掉前面的概率，算出大于等于  次变化的概率（对应的  都相等）。 用概率乘上对应的  即可算出总期望...

D题题解： 方法： 数学解法 思路： 查询保证了有且仅有两个数只出现1次，其他都是2次 设这两个数分别为 、，不妨让  我们可以想办法，搞一种前缀和，两个一样的数会消掉，正常人会想到异或，求区间异或和我们就能得到  ，以为需要求其中一个值，比较麻烦，我们不考虑这个做法。（我不会求其中一个值） 换一种思路，如果我把 第偶数次出现的数 改为它的负数，那么前缀和求值，得到  的值 ；同理，如果对原数组的平方数组（每个数为原数的平方）同样做，能够得到  的的值 。为了方便取个绝对值。 因为  与  同号， 与  同号，故  与  只有两种情况：  ，这个好求，，然后直接得到 。  被hack了：  ，...

D题的妙妙解法: 时间复杂度 思路： 我这里的点是从 到 。 因为 走两次及以上没有意义（走回来了），将 分两种： 若 答案为从 走到 （等价于从 到 ）。 若 =1&preview=true"> 答案取 上面的值 与 从  走到  （等价于从  到 ）加上一 最小的那个。   我们记录用  能走到的点的最小次数，线性推  次就好，同样记录 。 因为 、 走的顺序不重要，所以枚举 ， 代表从  按  走到 ，再从  按  走到终点，然后取最小的一个走法。 最终代码： #include<bits/stdc++.h> #define ll long lo...

E题题解 题目大意： 题目挺短好理解，这里就不解释了 前置知识： 树形dp、线段树合并、树上启发式合并 解题思路： 对于任意的  ， 能到达  的状态数量为，， 到达  也是这个值，因此总值为 。 题目转化为  这种树上求值问题，首先就要往树形dp上想。 不妨让  节点为整棵树的根 首先来看到根节点为  的子树  ，思考如何求出  能到达  的状态数量，其中 。 对于每个  的儿子 （子树中直接相连的点），根节点为  的子树我们已经统计好了 只需要求  到  的值，将其拆成两部分来看         先来看第一部分，考虑把上面的式子绝对值拆掉，如果我们能知道  ，那么总值为两部分: 一部分是 ...

E题题解： 时间复杂度O(n)哦！ 题目大意： 给数组切 2 刀，每份总和相等，都要包含正数 思路： 首先定义一个前缀和数组 sum，sum[i]=a[1]+a[2]+...+a[i]。 如果 sum[n] 不是三的倍数，怎么切，都不行。 直接考虑第一刀砍在 i，i+1 之间，求右边能切的位置数量，需要满足下面几点：  sum[i] == sum[n]/3  定义一个前缀和数组 ne，ne[j]=(a[1]>0)+(a[2]>0)+...+(a[j]>0)，表示从 1~j 有几个正数。  ne[i] > 0  那右边能切的位置数量如何求？ 我们从后往前推，记录切在 i~...

F题题解： 题目说求字符串 s 中的子序列red的数目 减去 字符串 t 中的子序列red的数目。 因为有修改，往维护方面想，考虑线段树，维护区间red6个非空子串（r、e、d、re、ed、red）的个数。 众所周知，red=re+d或r+ed，而re=r+e，ed=e+d。 区间 [l,r] 的r的个数 = [l,mid] 的r的个数 + [mid+1,r] 的r的个数。e和d 同理。 区间 [l,r] 的re的个数 = [l,mid] 的re的个数 + [mid+1,r] 的re的个数 + [l,mid] 的r的个数 * [mid+1,r] 的e的个数。ed 同理。 区间 [l,r] 的r...

E题题解 （最简方法，运行最快，不需要特判，不需要算法，只有一个for循环!） 首先  与  取数发现可以遍历 ++ 所有数， 令 +、+，问题转化为在  取一个数。 举例一个 、 ：   贪心考虑从高位往低位看，如果 、 对应数位值相等，没有办法，只能取这个值，现在 。   一直到不等的地方，例子中百位 、，如果我们的  百位为  ，那么最后三位数最大位数和为 ++；但如果退一步选 ，那么最后三位数最大位数和为 ++。观察琢磨发现，在 、 不等的地方，将  数位降  ，后面的数位全选 。   发现  和  这样的临界值我们取不到，之前我们的  总会小于  ，那么不妨让 加上一个  完美解决问...

H题纯诈骗，题面一本正经地解释合法串，避开了回文串。 众所周知，回味串是首尾依次相等。 也就是说abba、((这样的都是回文串； 而()自然不是回文串，因为(不等于)。 最后会发现，合法串都不是回文串。 因此直接输出 0 即可。