A. 匹配

$Hash$直接搞。

如果使用$KMP$，注意B字符串与A完全匹配，这是原本的$KMP$无法处理的问题。

B. 回家

刚开始以为是割点，打完后仔细一想发现不对。

于是打了圆方树，没有什么技巧。

另一种简单的做法：

只判断割点，但修改判断割点的方法。

 1 void tarjan(int x)
 2 {
 3     int son=0;
 4     dfn[x]=low[x]=++num;
 5     for(register int i=fr[x];i;i=mo[i].pr)
 6     {
 7         register int y=mo[i].to;
 8         if(!dfn[y])
 9         {
10             tarjan(y);
11             low[x]=min(low[x],low[y]);
12             if(low[y]>=dfn[x]&&dfn[y]<=dfn[n])
13             {
14                 son++;
15                 if(x!=1||son>1) cut[x]=1;
16             }
17         }
18         else low[x]=min(low[x],dfn[y]);
19     }
20 }

来自starsing

C. 寿司

断环成链，即把1～n-1补充在长度为n的字符串后。

将问题中的R和B转化为0和1，

问题转化为取一个长度为n的区间，移动1，使全部1分布在区间的左右两侧。

不难发现1每次都应与0交换，才能保证结果最优。

如果1向左移，移动的距离 等于 与左端点的距离 减去 两者中间1的个数。

利用前缀和优化，于是能推出$O(1)$计算的式子。

可以$O(n^2)$枚举区间和1左移右移的分界线，取最小值。

关于优化枚举的过程：

不难想到对于每个区间，函数值对于分界线是单谷的。（证明略去，可以参考O(n)正解的证明）

使用三分法求单峰函数极值即可。

注意在整数域上，三分法只能将极值收缩到长度不超过3的区间，都应尝试更新。

复杂度$O(nlogn)$ 常数稍大。

又发现随着区间的右移，最优决策点是单调不左移的。

而且最优决策点是一个定值，设区间内0的个数为t，

如果t为奇数，最优决策点在中位0的左右。

如果t为偶数，最优决策点在中位两个0左右。

证明：（大神yxs）

每个1的 向两侧移动的距离 等同于 1与左右端点之间 0的个数。

对于每一个1，当它在中位0左侧，去左端点更优，

反之则去右端点更优。

因为区间中0的总个数不变。

当区间右移，

如果原左端点为1，中位0不变。

如果原左端点为0，中位0右移。

故中位0单调变化，以一个指针记录中位0的位置，用$while$判断是否右移即可。

不断更新答案，总复杂度$O(n)$