2025年信息竞赛复赛试题及答案.docxVIP

2025年信息竞赛复赛试题及答案

试题一：回文分割的最小代价

题目描述

给定一个由小写字母组成的字符串\(S\)（长度为\(n\)），以及一个\(n\timesn\)的整数矩阵\(C\)，其中\(C[i][j]\)（\(0\leqi\leqjn\)）表示将子串\(S[i..j]\)作为一个分割段的代价。要求将\(S\)分割成若干个不重叠的回文子串，求总代价的最小值。若无法分割，输出\(-1\)。

输入格式

第一行一个整数\(n\)（\(1\leqn\leq2000\)）。

第二行一个字符串\(S\)。

接下来\(n\)行，每行\(n\)个整数，表示矩阵\(C\)，其中第\(i\)行的第\(j\)个数为\(C[i][j]\)（仅当\(i\leqj\)时有意义，\(ij\)时的值可忽略）。

输出格式

一个整数，表示最小总代价；若无法分割，输出\(-1\)。

样例输入

```

5

ababa

01234

10567

25089

368010

479100

```

样例输出

```

0

```

样例解释

字符串\(S=\text{ababa}\)本身是回文，因此分割为自身，代价为\(C[0][4]=0\)。

试题二：彩色树的最远异色节点对

题目描述

给定一棵有根树（根节点为\(1\)），每个节点有一个颜色（颜色用\(1\)到\(m\)的整数表示），边有正权值。定义两个节点\(u\)和\(v\)的距离为路径上所有边权之和。求所有颜色不同的节点对中，距离的最大值。

输入格式

第一行两个整数\(n\)和\(m\)（\(1\leqn\leq10^5\)，\(1\leqm\leq10^5\)）。

第二行\(n\)个整数，表示每个节点的颜色\(c[1..n]\)。

接下来\(n-1\)行，每行三个整数\(u,v,w\)，表示\(u\)和\(v\)之间有一条权值为\(w\)的边（节点编号从\(1\)到\(n\)）。

输出格式

一个整数，表示最大距离。

样例输入

```

63

123213

125

233

242

154

561

```

样例输出

```

13

```

样例解释

节点\(3\)（颜色\(3\)）到节点\(6\)（颜色\(3\)）颜色相同，不满足条件。节点\(3\)（颜色\(3\)）到节点\(5\)（颜色\(1\)）的路径为\(3\rightarrow2\rightarrow1\rightarrow5\)，距离为\(3+5+4=12\)。节点\(6\)（颜色\(3\)）到节点\(4\)（颜色\(2\)）的路径为\(6\rightarrow5\rightarrow1\rightarrow2\rightarrow4\)，距离为\(1+4+5+2=12\)。节点\(6\)（颜色\(3\)）到节点\(5\)（颜色\(1\)）的路径为\(6\rightarrow5\)，距离为\(1\)，不满足。正确最大距离为节点\(3\)（颜色\(3\)）到节点\(6\)的路径中颜色不同的节点对？重新计算：节点\(6\)颜色\(3\)，节点\(4\)颜色\(2\)，路径\(6-5-1-2-4\)边权\(1+4+5+2=12\)。节点\(3\)颜色\(3\)，节点\(5\)颜色\(1\)，路径\(3-2-1-5\)边权\(3+5+4=12\)。节点\(3\)颜色\(3\)，节点\(2\)颜色\(2\)，路径\(3-2\)边权\(3\)。可能样例输出应为\(13\)，例如节点\(3\)（颜色\(3\)）到节点\(6\)（颜色\(3\)）颜色相同，不符合；节点\(6\)（颜色\(3\)）到节点\(5\)（颜色\(1\)）路径\(6-5\)边权\(1\)。可能我之前的