由于出题人并不会评估普及组题目难度，这次的题目还是偏难了……

下面是题解。

祖玛

关键字：模拟

首先可以用循环语句，从字符串的第 $x$ 个字符开始往左找第一个不是 $c$ 的字符，假设它是第 $l$ 个字符（如果找不到则 $l=0$），然后从第 $x+1$ 个字符开始往右找第一个不是 $c$ 的字符，假设它是第 $r$ 个字符（如果找不到则 $r=n+1$）。

如果 $r-l < 3$，说明把珠子射入以后，射入的珠子所在的连续段不足 $3$ 个珠子，这时候，应该先输出前 $x$ 个字符，再输出字符 $c$，最后输出第 $x+1$ 到第 $n$ 个字符。

如果 $r-l\ge 3$，说明射入之后 $l+1$ 到 $r-1$ 这一段会消失。如果 $l,r$ 两个位置是不同字符，过程结束；如果是相同字符，设其为 $c'$，从 $l$ 往左找第一个不是 $c'$ 的位置 $l'$，从 $r$ 往右找第一个不是 $c'$ 的位置 $r'$，如果 $(l-l')+(r'-r)\ge 3$，那么 $l'+1$ 到 $l$、$r$ 到 $r'-1$ 会消除，否则不会消除；如果会消除，令 $l=l'$，$r=r'$ 重复此过程即可。可以用 while 循环来实现。最后应该先输出前 $l$ 个字符，再输出第 $r$ 到第 $n$ 个字符。

数列分割

关键字：枚举，减少枚举量

显然可以用两重循环枚举两个切割点 $p,q$ 的位置，再用一重循环计算三个段的最大值，求出最大和最小的答案。但是这样运算量是 $n^3$ 级别的，太慢了。

当然可以少枚举一些东西。比如我们可以开两个数组 L[i] 和 R[i] 分别存储前 $i$ 个数的最大值和第 $i$ 到第 $n$ 个数的最大值。

for(int i = 1; i <= n; i++) L[i] = L[i-1] > a[i] ? L[i-1] : a[i];
for(int i = n; i >= 1; i--) R[i] = R[i+1] > a[i] ? R[i+1] : a[i];

还可以一边枚举 $q$ 一边更新中间段的最大值：

for(int p = 1; p < n; p++){
    int m = 0;
    for(int q = p; q < n; q++){
        if(a[q] > m) m = a[q];
        // m 即为 [p,q] 段的最大值
    }
}

这样左段、中段、右段的最大值不需要额外计算了。这样的运算量还是 $n^2$ 级别的（只要枚举 $p,q$），尽管能得到很多分，但由于超时的缘故还是不能得到满分。

先考虑三段和的最大值怎么求，它就是数列中前三大的数的和。

• 比如数列 $3,5,1,4,3$ 前三大的数是 $5,4,3$，那么不管怎么切，三段加起来不会超过 $5+4+3$。让三段加起来等于 $5+4+3$ 只要一刀切在第2项和第4项之间，一刀切在第4项和第5项之间就好了，$[3,5],[1,4],[3]$ 之类的都行，答案就是 $5+4+3=12$。

再考虑三段和的最小值怎么求，我们只要枚举中段只有1个数或者左右两段都只有1个数的分割方法。因为如果整个数列的最大的数是 $a_k$（如果有几个数都是最大的，随便找一个），那么 $a_k$ 被分到的段肯定越长越好：

• 若 $a_k$ 在左段或右段，可以让中段只有1个数。比如[3,5],[4,1],[3]显然把左段加长更好：[3,5,4],[1],[3]。这种用一个 for 循环枚举中段包含哪一个数，用刚才处理出的 L[] 和 R[] 数组求答案。
• 若 $a_k$ 在中段，可以让左右两段都只有1个数。比如[3],[5,1],[4,3]显然把中段加长更好：[3],[5,1,4],[3]。这种直接按 $1,n-2,1$ 分割然后算答案就好了。

在这些情况中求最小的三段和即可，这样枚举量只有 $n$ 级别了，可以得到100分。

秋游

关键字：贪心，问题转化

如果 $m=0$，只要考虑学生的满意度。对每个 $k$，要让 $k$ 个学生秋游，一定是让 $a_i$ 最大的那 $k$ 个学生去。于是把 $a_i$ 排序以后，从大到小一边累加一边输出。（下面这个代码要 #include <algorithm>）

std::sort(a + 1, a + n + 1);
int s = 0; // 总满意度
for(int i = n; i; i--) printf("%d\n", s += a[i]);

如果 $m>0$，需要考虑朋友关系，看起来不是很好处理。

可以用搜索算法（如深度优先搜索）搜索所有可能的情况，对每种情况计算满意度。然而 $n$ 个学生一共有 $2^n$ 种选取方式，对于 $n=100000$ 的数据搜索是一定会超时的。我们需要一些更好的处理方法。

对于一对朋友关系 $j$，它对满意度的影响可以表示成 $(t-1)\cdot w_j = t\cdot w_j - w_j$，其中 $t$ 表示 $u_j,v_j$ 两人中，有几个人去了秋游。因此在计算总满意度的时候，可以先把总满意度减掉 $w_j$，然后 $u_j$ 和 $v_j$ 每有一个人去秋游，总满意度加 $w_j$。

所以只要对于每对朋友关系 $j$，把 $a_{u_j}$ 和 $a_{v_j}$ 加上 $w_j$，最后答案减掉 $w_j$，就可以不管这条边了。这样就把问题转化成了 $m=0$ 的情况。排序以后输出 $a$ 累加的结果减去所有 $w_j$ 的和就行了：

int s = 0; // 总满意度
for(int j = 1; j <= m; j++) a[u[j]] += w[j], a[v[j]] += w[j], s -= w[j];
std::sort(a + 1, a + n + 1);
for(int i = n; i; i--) printf("%d\n", s += a[i]);

这样就可以轻松得到满分了。

兔子繁殖

关键字：递推，前缀和

1. 80分算法

稍微有点常识就会发现，兔子的繁殖数量是指数级增长的，用简单的模拟法，记录每对兔子的年龄，计算机内存无法接受。

注意到所有兔子的年龄都在 $0$ 到 $n-1$ 之间，不妨换一种模拟方法：记录每个月，年龄为 $0$ 的兔子有多少对，年龄为 $1$ 的兔子有多少对，……，年龄为 $n-1$ 的兔子有多少对。开一个数组 f[i] 表示年龄为 $i$ 的兔子数量，那么每个月所有兔子的年龄增加 $1$ 就是这个操作：

for(int i = n - 1; i >= 0; i--) f[i + 1] = f[i];
f[0] = 0;

繁殖则是这样的操作：

for(int i = 0; i < m && k + i * t < n; i++) f[0] += f[k + i * t];

这样你会发现一个问题：使用32位整数 int 类型甚至64位整数 long long 类型都会溢出！这时候仔细看题目，题目只要输出答案除以 $10007$ 的余数，也就是如果答案为 $x$，输出的是 $x\bmod 10007$。并且我们知道模运算有很好的性质，那就是对任意整数 $a,b$ 和正整数 $p$，有：

$$(a+b)\bmod p=a\bmod p+b\bmod p$$

所以任何时候我们都只要记录当前的兔子数量除以10007的余数。只要把繁殖操作改一改：

const int mod = 10007;
for(int i = 0; i < m && k + i * t < n; i++) f[0] = (f[0] + f[k + i * t]) % mod;

这样就能求出第 $m$ 个月每种年龄的兔子有多少对，把未死亡的兔子数量加起来以后求出除以10007的余数输出就是答案了。

很好，这样的运算量是 $n^2$ 级别的，可以轻松通过 $n\le 2000$ 的测试数据了。当然我们注意到这题有一类特殊的测试数据：$k\le 4,t=1,m=n$。这意味着什么？每对兔子出生至多 $4$ 个月以后，每个月都会生出兔子，且 $n$ 个月以内不会死亡。那么年龄在 $4$ 以上的兔子都是一样的，只要记录年龄为 $0,1,2,3,4$ 的兔子数量这五个信息就行了，只要 $5n$ 级别的运算量。

把 $n\le 2000$ 和 $k\le 4,t=1,m=n$ 的两个程序用 if 语句拼起来，可以获得80分。

2. 100分算法

遗憾的是上面的算法并不能通过一般的 $n=10^7$ 的测试数据，毕竟用 for 循环从 $1$ 遍历到 $10^7$ 都需要不少的时间了。

其实我们只要考虑刚出生的兔子就行了。因为兔子的出生时间确定了，繁殖和死亡时间也就确定了。第 $n$ 个月未死亡的兔子就是出生在第 $n-k-(m-1)t+1$ 个月到第 $n$ 个月的兔子数量。

开一个数组 $f[i]$ 存第 $i$ 个月出生的兔子有多少对（注意还是只要存除以10007的余数），显然 $f[1] = 1$。当 $i>1$ 时怎么计算 $f[i]$ 呢？

对于第 $i$ 个月，可以发现，第 $i-k,i-k-t,i-k-2t,\cdots,i-k-(m-1)t$ 这些月份出生的每对兔子恰好生出一对第 $i$ 个月出生的兔子，而其余月份出生的兔子不会生成第 $i$ 个月出生的兔子。因此可以得到递推式：

$$f[i]=f[i-k]+f[i-k-t]+f[i-k-2t]+\cdots+f[i-k-(m-1)t]$$

如果下标是负的就当成 $0$。如果直接用这个式子递推，求和需要花费比较多的时间。不过等号右边的 $f$ 的下标除以 $t$ 的余数都相同。比如 $t=3$，如果我们把 $f$ 数组摆成这样：

f[1]        f[4]        f[7]        f[10]            ...
    f[2]        f[5]        f[8]        f[11]        ...
        f[3]        f[6]        f[9]        f[12]    ...

那么对某个 $f[i]$，它的值是上面这个数组某一行的某一个连续段的和。

这可以用前缀和技巧来加速计算，也就是我们开一个数组 $g[i]$ 存上面的 $f[i]$ 往左的所有数之和。

例如当 $t=3$ 时，$g[11]=f[11]+f[8]+f[5]+f[2]$。这样用前缀和相减就可以快速得到一段区间的和。还是假设 $t=3$，比如要算 $f[5]+f[8]+f[11]$，只需两端的 $g$ 相减，即 $g[11]-g[2]$。

处理这个 $g$ 数组非常简单，如果 $i\le t$，那么 $g[i]=f[i]$，否则 $g[i]=f[i]+g[i-t]$ 这样递推就好了。

于是按 $i$ 从小到大依次推出 $f[i],g[i]$，最后统计第 $n-k-(m-1)t+1$ 个月到第 $n$ 个月的兔子有多少对就做完了，注意负下标要当成 $0$。可以获得100分。