CCF GESP 2025年3月认证 C++ 7级
题目描述
小 A 有一张包含 $n$ 个结点与 $m$ 条边的无向图，结点以 $1, 2, \dots, n$ 标号。小 A 会从图上选择一个结点作为起点，每一步移动到某个与当前小 A 所在结点相邻的结点。对于每个结点 $i$ （$1 \leq i \leq n$），小 A 想知道从结点 $i$ 出发恰好移动 $1, 2, \dots, k$ 步之后，小 A 可能会位于哪些结点。由于满足条件的结点可能有很多，你只需要求出这些结点的数量。
输入格式
第一行，三个正整数 $n, m, k$，分别表示无向图的结点数与边数，最多移动的步数。
接下来 $m$ 行，每行两个正整数 $u_i, v_i$，表示图中的一条连接结点 $u_i$ 与 $v_i$ 的无向边。
输出格式
共 $n$ 行，第 $i$ 行 ($1 \leq i \leq n$) 包含 $k$ 个整数，第 $j$ 个整数 ($1 \leq j \leq k$) 表示从结点 $i$ 出发恰好移动 $j$ 步之后可能位置的结点数量。
样例说明
样例 1
4 4 3
1 2
1 3
2 3
3 42 4 4
2 4 4
3 3 4
1 3 3数据范围
对于 $20\%$ 的测试点，保证 $k = 1$。
对于另外 $20\%$ 的测试点，保证 $1 \leq n \leq 50, 1 \leq m \leq 50$。
对于所有测试点，保证 $1 \leq n \leq 500, 1 \leq m \leq 500, 1 \leq k \leq 20, 1 \leq u_i, v_i \leq n$。
题目描述
小 A 有一个仅包含小写英文字母的字符串 $S$。
对于一个字符串，如果能通过每次删去其中两个相同字符的方式，将这个字符串变为空串，那么称这个字符串是可以被等价消除的。
小 A 想知道 $S$ 有多少子串是可以被等价消除的。
一个字符串 $S'$ 是 $S$ 的子串，当且仅当删去 $S$ 的某个可以为空的前缀和某个可以为空的后缀之后，可以得到 $S'$。
输入格式
第一行，一个正整数 $|S|$，表示字符串 $S$ 的长度。
第二行，一个仅包含小写英文字母的字符串 $S$。
输出格式
一行，一个整数，表示答案。
样例说明
样例 1
7
aaaaabb9样例 2
9
babacabab2数据范围
对于 $20\%$ 的测试点，保证 $S$ 中仅包含 $a$ 和 $b$ 两种字符。
对于另外 $20\%$ 的测试点，保证 $1 \leq |S| \leq 2000$。
对于所有测试点，保证 $1 \leq |S| \leq 2 \times 10^5$。