• 致歉

因为出题人的疏忽，T6 造了 n 不是 4 的倍数的数据。同时 T8 因为多次重造数据，被暴力碾过去了。真抱歉 qaq 。

T1 回文括号序列计数

记串为 ，由于回文所以 ，由于括号序列所以 。

因此不存在长度 的串。当 时存在一个空串。

T2 系数

做法一

，求的即为 。

这个就是个简单的组合数，易知是 。

做法二

赛时也有部分人打表来观察解出此题，这里给出一种比较简洁的打表观察做法：

将前一些数打印出来：

int dp[105][105];
int main() {
  dp[0][0] = 1;
  for (int i = 1; i <= 30; i++) {
    for (int j = 0; j <= 2 * i; j++) {
      dp[i][j] = (dp[i - 1][j] + (j >= 1 ? dp[i - 1][j - 1] : 0) + (j >= 2 ? dp[i - 1][j - 2] : 0)) % 3;
      if (!dp[i][j]) printf("   ");
      else printf(" %d ", dp[i][j]);
    }
    puts("");
  }
}

发现它满足分形规律，不难联想到组合数也是满足分形规律的。

将组合数也打印出来，发现 有值当且仅当 不为 （模 3 意义下），进而发现 1 和 2 的取值与 m 的奇偶性相关。

归纳可知 ，前者可以用 Lucas 定理 计算。

总时间复杂度 。

T3 末三位

枚举一下：1 5 25 125 625 125 625 ... 可以发现 125, 625 二个一循环。

注意需要特判 的情况，需要输出前导零。

T4 划数

由于题目保证 ，所以答案一定是唯一的。因为新加入的数一定 ，所以 一定是原来序列中的某个数。

可以发现，无论怎么操作，这些数的和模 11 的值不会变。

所以答案即为 。

注意特判 的情况。

时间复杂度 。

T5 grid

显然每个点在上下中选一个，左右中选一个。所以对于竖直的情况和水平的情况是相互独立的。

下面只考虑水平的情况：对于每一行，用 表示当前第 个数向左/右能得到的最大答案。

则不难有转移：

答案即为 ，每一行的答案相加即为水平方向上的贡献。

竖直方向同理。预处理一个数的 （二进制位 1 的个数）即可做到 。

T6 组合数问题

所以原式 ，用复数快速幂即可。

时间复杂度 。

T7 机器人

暴力是 的，直接全排列枚举即可。可通过 random_shuffle 乱搞，但应该被卡掉了。

首先，局部最优可以推得全局最优，所以 dp 正确性可以保证。

正解是状压dp，用 表示当前状态 st 可得到的最大值，答案即为 。

注意一些常数优化的技巧，时间复杂度 。

还有一种贪心的做法，设两个相邻的机器人为 ，一开始的数是 。

则满足 ，即

按此排序即可。

T8 动态最小生成树

这道题好像被暴力碾过去了...

如果每次暴力重构生成树，每次跑 ，复杂度是 的，预处理排序，则复杂度降为 。

考虑将上述流程放到线段树上，对于线段树的每个节点，开一个大小为 的数组，表示区间构成的生成树的边的集合。每次线段树上传，则是一个归并排序做生成树的过程。

时间复杂度 。

另外一种做法是带修莫队，用 动态维护最小生成树。由于其难度较大且代码不易实现，而且常数极大，所以这里不细讲了，时间复杂度 。

T9 贪吃蛇

从 为起点 ，到 的最短路乘以 （进制转换）即为答案。

由于贪吃蛇不能吃自己，所以不会走走过的格子。而每个点显然是越早到越好，所以直接广搜是正确的。

时间复杂度 。

T10 天空之城

显然题目要求的是最小生成树。对于每个串，可以通过 std::map<string, int> 映射到一个数上，然后就转化成了 个点 条边求最小生成树的板子题。

时间复杂度 。