A M形字符串

解法一

对于每个字符i,算出两个值len1,len2.

len1表示以当前字符结尾的最长回文串的长度.

len2表示以当前字符开头的,满足以下性质的最长字符串的长度:
0->len2这一个区间的字符串和i->i+len2这一个区间的字符串相等.

以上的len1,可以用回文树算出.

以上的len2,可以用扩展kmp(又称z函数)算出.

如果知道这两个值,对于每个i,直接判断len1[i]==i+1并且len2[i]>=i+1.
为什么:
如果以i结尾前面都是回文串,那么len1[i]=i+1
如果以i开头后面有一个一模一样的回文串,那么len2[i]>=i+1

但是还有123321+123321这样的串,所以第二个回文串可能从i+1开始.
无所谓,多判断一下(len1[i] == i+1 && len2[i+1] >= i+1)即可.

解法二

我原本以为要像上面那样解,然而年轻人不讲武德,直接字符串hash就搞过去了.

B 找山坡

解法一

单调栈

对比单调栈/单调队列的性质:能求滑动区间的最小值;

还有单调栈经典例题:求最大矩形面积;

就知道,这个也许可以用单调栈乱搞。

接着,因为这个序列两端是整个序列的最小值,所以考虑用单调递增的栈(栈内元素单调递增)。
难点在于,如何处理相同的值。做法:在遍历数组过程中,对于当前的元素:

  1. 如果栈不为空且小于栈顶元素,就把栈顶元素弹出,然后继续执行1
  2. 如果栈不为空且等于栈顶元素,那么这时答案贡献为:当前元素下标 - 栈顶元素下标
  3. 否则,就把当前元素加入到栈中
  4. 最后,对答案贡献取最大值,就可以得到答案了

注意栈存放的是元素对应的下标,这样才能方便统计答案。

简略证明:

  1. 不把相同元素的下标塞入单调栈中,可以保留这个元素最左边的下标
  2. 单调递增的栈,可以保证中间所有值大于等于左右两端。这里可以用反证法:
    假设中间出现了小于左端点的值,那么在单调栈中,这个中间元素的下标会把左端点的下标弹出去,这时左端点就不能贡献答案了。

解法二

桶+RMQ(区间最值查询)

从两个端点值相等可以想到,可以考虑维护这样的桶(key, value):
桶的key为数组的值,value为key值对应的所有数组下标(从小到大排好序)

这时,只要我们遍历每一个key对应的value,从value中找到两个符合条件的端点,然后就可以统计答案了。所以现在问题是:如何快速找到两个符合条件的端点。

首先,我们需要有快速判定两个端点是否符合题目条件的方法,即快速判定:连续序列的两端是否为序列的最小值。对于这个问题,可以用与RMQ有关的算法(ST表,线段树等),查询区间最小值,然后判断这个最小值是否为两个端点的值来解决。

接着,因为我们对value中的端点进行了排序,所以,对于两个相邻的端点value[i], value[i+1],如果不满足题目限制条件,那么答案端点构成的区间肯定不包含这两个端点。形象地说,就是答案会在这里“断开”。根据这个性质,我们可以在O(size * k)(size为value的大小,k为RMQ复杂度)找到答案。

C 涂墙

解法一

其实就是问一个数字能不能表示成5个正平方数的和.

首先要知道拉格朗日四平方数和定理:

任意一个非负整数可以表示为四个平方数(0也是平方数)的和.

比如这样:
$[0,4]0$.

有一个特殊的数字169,他分别可以表示成1,2,3,4个正平方数的和.
$169nm=n-169$.

这个不小于,分解成四个平方数,可能会含有.

  • 如果分解出来的四个平方数中有四个正数,那么

  • 如果分解出来的四个平方数中有三个正数,那么

  • 如果分解出来的四个平方数中有两个正数,那么

  • 如果分解出来的四个平方数中有一个正数,那么

  • 如果分解出来的四个平方数中有没有正数,那么

所以任何不小于的整数,都符合条件.

对于小于的整数,暴力打表发现以下几个数字不符合

0,1,2,3,4,6,7,9,10,12,15,18,33

所以如果输入是以上数字,直接NO

否则YES.

D 动态序列

解法一

维护两个变量mul、add,假设序列中原来的数为ai,设最终结果为mul * ai + add,则可以:

  • 进行操作1时,(mul * ai + add) * b => mul * b * ai + add * b,所以mul *= b,add *= b
  • 进行操作2时,mul * ai + add + b => mul * ai + (add + b),所以add += b
  • 当添加一个数b时,为了保持询问时计算结果的方法是统一的,则需要计算一个x,使得:mul * x + add = b,用这个x来代替b,加入序列里面。改变方程形式:x = (b - add) * mul ^ (-1),就可以转化为计算逆元的问题

在上述做法基础上,我们可以偏移序列在数组中的位置,维护头尾下标(low,high),来实现操作3和操作4。进行操作5的时候,数的真实下标就可以根据头下标和p计算出来.

特别注意:数组要开足够大

E 捡贝壳

解法一

朴素做法.

对于每个询问遍历区间求得是x的倍数的个数。复杂度最坏为,显然超时。

考虑分块做法.

将数组分为块,统计每个块内x的答案,复杂度为

对于每个询问区间,不属于整块的暴力统计答案,属于的直接加上。复杂度

F 钓卡游戏

解法一

题目需要用线性时间求 Alice 能获得的最大分数是否大于

先对牌堆进行处理,把 Alice 的牌序用数组存起来, Bob 的牌序用数组存起来。

不妨假设两张卡的数值为.

我们可以认为 Alice 无论是选择盖下这张牌还是选择打出这张牌,这张牌的值都已经加进答案里了。

接下来就是使得从数组里钓得的值求和最大。

对于一个回合内, Alice 与 Bob 存在四种情况。

Alice Bob
2 2
1 2
2 1
1 1

钓卡的动作视作在当前数组的数对当前及往后数组中相同的数连线,记作

假设现在有 ,那么下一次连线的限制是不能跨过

即只有时连线成立。

那么对于的情况,应该当前回合就直接把对手的牌钓走, 不会对答案产生后效性。

全部去掉以后,就只剩下的情况了.

而对于的情况则存在决策。可以想到,这个位置可以被前面的某个位置连接,但这个 位置也可以选择向后面某一个位置进行连接,而这两个动作不能同时发生。

为了方便继续思考,可以先简化数组,因为只有的情况,我们可以把两个数组看成一个,因 为知道一个数组就可以得出另一个数组。

这里我们只看数组,那么原来两个数组间相同数字的连线,区间不能交叉的问题,则变成在数组上 找出最大权值的连线,连线之间不能相交的问题。

连线的最大数量取决于中较少的那一个。

的权值为的权值为,也就是说我们只需要在最大连线的情况下尽可能贪心最多的连线即可。

要维护连线之间不相交并且数量尽可能多,我们可以去连接左边离最近的且没有被用过的,这样就能保证连线之间的项都已经对答案做出过贡献。

这个过程可以用栈去去维护的位置,每次遇到时就入栈,每次遇到时就尝试取出栈顶的数来获得 一个连线。

然后标记一下连线已经用过的位置,去掉这些位置以后,再对连线作出同样的贪心即可得到最大分数。

那么对于任意不相等的(这里指卡牌的数值),按照上述思路优先贪心中较大的数,去掉已标记位置后再贪心另一个数,即可得到答案。

G 分割

解法一

首先我们讲分别从小到大排序.

我们可以有一个暴力的解法就是枚举每一个可能的矩形,时间复杂度.
$$
只需要各自算出每一段相邻段差值的贡献次数累加起来,再相乘即可.

H 有多短?

解法一

  • 先说结论:答案是 2*k/(度数为1的节点个数)
  • 感性认识:
    • 直径肯定是从一个度数1的点到另一个度数1的点
    • 所以我们只给所有度数为1相连的边分配权值,其他边全置为0(之后不再考虑)
    • 均摊下来,每条边的权值Wi = k/(度数为1的节点个数)
    • 所以直径为2*Wi

I 母牛哥与子序列

解法一

易知规律为:

稍微证明一下,构造函数:

展开,在未合并同类项之前,每个项的系数都是一个子序列乘积。

例如 的时候有:

所以,我们要求所有子序列乘积的和的时候,只需要求 就行。但注意到其实上面多了一个 ,这个 是空序列的贡献,只需要减去这个 即可。

也就是求:

J 最长连续相同数字的长度

解法一

维护一棵平衡树或treap,除了普通平衡树要维护的东西外,再维护这个区间的答案,最左/右边是0还是1以及连续相同的个数,还有3个懒惰标记分别表示区间异或,区间取反和区间赋值。