一、实操题
1、排水系统（water）
【题目描述】
对于一个城市来说，排水系统是极其重要的一个部分。有一天，小 C 拿到了某座城市排水系统的设计图。排水系统由 n 个排水结点（它们从 1 ∼ n 编号）和若干个单向排水管道构成。每一个排水结点有若干个管道用于汇集其他排水结点的污水（简称为该结点的汇集管道），也有若干个管道向其他的排水结点排出污水（简称为该结点的排出管道）。
排水系统的结点中有 m 个污水接收口，它们的编号分别为 1, 2, · · · , m，污水只能从这些接收口流入排水系统，并且这些结点没有汇集管道。排水系统中还有若干个最终排水口，它们将污水运送到污水处理厂，没有排出管道的结点便可视为一个最终排水口。
现在各个污水接收口分别都接收了 1 吨污水，污水进入每个结点后，会均等地从当前结点的每一个排出管道流向其他排水结点，而最终排水口将把污水排出系统。
现在小 C 想知道，在该城市的排水系统中，每个最终排水口会排出多少污水。该城市的排水系统设计科学，管道不会形成回路，即不会发生污水形成环流的情况。
【输入格式】
从文件 water.in 中读入数据。
第一个两个用单个空格分隔的整数 n，m。分别表示排水结点数与接收口数量。
接下来 n 行，第 i 行用于描述结点 i 的所有排出管道。其中每行第一个整数 di 表示其排出管道的数量，接下来 di 个用单个空格分隔的整数 a1, a2, · · · , adi 依次表示管道的目标排水结点。
保证不会出现两条起始结点与目标结点均相同的管道。
【输出格式】
输出到文件 water.out 中。
输出若干行，按照编号从小到大的顺序，给出每个最终排水口排出的污水体积。其中体积使用分数形式进行输出，即每行输出两个用单个空格分隔的整数 p，q，表示排出的污水体积为
要求 p 与 q 互素，q = 1 时也需要输出 q。
【样例 1 输入】
5 1
3 2 3 5
2 4 5
2 5 4
0
0
【样例 1 输出】
1 3
2 3
【样例 1 解释】
【数据范围】
对于所有测试点，保证
数据保证，污水在从一个接收口流向一个最终排水口的过程中，不会经过超过 10个中间排水结点（即接收口和最终排水口不算在内）。
参考答案：
本题可以使用洪水算法解决。首先，找到污水接收口，然后从接收口开始，沿着每个结点的排出管道进行遍历，直到找到最终排水口。在遍历的过程中，将经过的每个结点的汇集管道数加一，表示该结点汇集到的污水体积。最终，每个最终排水口的污水体积就是其汇集到的污水体积。
由于题目要求输出的污水体积为分数形式，我们可以使用扩展欧几里得算法求出两个互质的整数 p 和 q，使得 p/q = 污水体积。具体地，我们可以将污水体积乘以一个足够大的数，使得结果变成整数，然后求出该整数的分子和分母。
对于本题，我们可以使用洪水算法找到每个最终排水口的汇集管道数，然后求出每个最终排水口的污水体积。最后，使用扩展欧几里得算法求出每个最终排水口的污水体积的分子和分母，按照题目要求输出即可。
2、字符串匹配（string）
【题目描述】
小 C 学习完了字符串匹配的相关内容，现在他正在做一道习题。
对于一个字符串 S，题目要求他找到 S 的所有具有下列形式的拆分方案数：S = ABC，S = ABABC，S = ABAB · · · ABC，其中 A，B，C 均是非空字符串，且 A 中出现奇数次的字符数量不超过 C 中出现奇数次的字符数量。
更具体地，我们可以定义 AB 表示两个字符串 A, B 相连接，例如 A = aab，B = ab，则 AB = aabab。
并递归地定义
例如 A = abb，则
则小 C 的习题是求
的方案数，其中 F(A) ≤ F(C)，F(S ) 表示字符串 S中出现奇数次的字符的数量。两种方案不同当且仅当拆分出的 A、B、C 中有至少一个字符串不同。
小 C 并不会做这道题，只好向你求助，请你帮帮他。
【输入格式】
从文件 string.in 中读入数据。
本题有多组数据，输入文件第一行一个正整数 T 表示数据组数。
每组数据仅一行一个字符串 S，意义见题目描述。S 仅由英文小写字母构成。
【输出格式】
输出到文件 string.out 中。
对于每组数据输出一行一个整数表示答案。
【样例 1 输入】
3
nnrnnr
zzzaab
mmlmmlo
【样例 1 输出】
8
9
16
【样例 1 解释】
对于第一组数据，所有的方案为：
1. A=n，B=nr，C=nnr。
2. A=n，B=nrn，C=nr。
3. A=n，B=nrnn，C=r。
4. A=nn，B=r，C=nnr。
5. A=nn，B=rn，C=nr。
6. A=nn，B=rnn，C=r。
7. A=nnr，B=n，C=nr。
8. A=nnr，B=nn，C=r。
【样例 2 输入】
5
kkkkkkkkkkkkkkkkkkkk
lllllllllllllrrlllrr
cccccccccccccxcxxxcc
ccccccccccccccaababa
ggggggggggggggbaabab
【样例 2 输出】
156
138
138
147
194
【数据范围】
对于所有测试点，保证
参考答案：对于每组数据，首先统计字符串S中出现奇数次的字符的数量，记为odd_count。然后，遍历字符串S，对于每个位置i，以i为分割点将字符串S拆分为A和B，其中A为S的前i个字符，B为S的剩余部分。对于每个分割点，计算A和B中出现奇数次的字符的数量，分别记为odd_count_A和odd_count_B。如果odd_count_A <= odd_count_B，则满足题目要求，将方案数加1。具体的算法步骤如下：1. 统计字符串S中出现奇数次的字符的数量，记为odd_count。2. 遍历字符串S，对于每个位置i，执行以下操作：1. 计算A和B中出现奇数次的字符的数量，分别记为odd_count_A和odd_count_B。2. 如果odd_count_A <= odd_count_B，则将方案数加1。3. 返回方案数。
3、移球游戏（ball）
【题目描述】
小 C 正在玩一个移球游戏，他面前有 n + 1 根柱子，柱子从 1 ∼ n + 1 编号，其中1 号柱子、2 号柱子、· · ·、n 号柱子上各有 m 个球，它们自底向上放置在柱子上，n + 1号柱子上初始时没有球。这 n × m 个球共有 n 种颜色，每种颜色的球各 m 个。
初始时一根柱子上的球可能是五颜六色的，而小 C 的任务是将所有同种颜色的球移到同一根柱子上，这是唯一的目标，而每种颜色的球最后放置在哪根柱子则没有限制。
小 C 可以通过若干次操作完成这个目标，一次操作能将一个球从一根柱子移到另一根柱子上。更具体地，将 x 号柱子上的球移动到 y 号柱子上的要求为：
1. x 号柱子上至少有一个球；
2. y 号柱子上至多有 m − 1 个球；
3. 只能将 x 号柱子最上方的球移到 y 号柱子的最上方。
小 C 的目标并不难完成，因此他决定给自己加加难度：在完成目标的基础上，使用的操作次数不能超过 820000。换句话说，小 C 需要使用至多 820000 次操作完成目标。
小 C 被难住了，但他相信难不倒你，请你给出一个操作方案完成小 C 的目标。合法的方案可能有多种，你只需要给出任意一种，题目保证一定存在一个合法方案。
【输入格式】
从文件 ball.in 中读入数据。
第一行两个用空格分隔的整数 n，m。分别表示球的颜色数、每种颜色球的个数。
接下来 n 行每行 m 个用单个空格分隔的整数，第 i 行的整数按自底向上的顺序依次给出了 i 号柱子上的球的颜色。
【输出格式】
输出到文件 ball.out 中。
本题采用自定义校验器（special judge）评测。
你的输出的第一行应该仅包含单个整数 k，表示你的方案的操作次数。你应保证0 ≤ k ≤ 820000。
接下来 k 行每行你应输出两个用单个空格分隔的正整数 x, y，表示这次操作将 x 号柱子最上方的球移动到 y 号柱子最上方。你应保证 1 ≤ x, y ≤ n + 1 且 x , y。
【样例 1 输入】
2 3
1 1 2
2 1 2
【样例 1 输出】
6
1 3
2 3
2 3
3 1
3 2
3 2
柱子中的内容为：按自底向上的顺序依次给出柱子上每个球的颜色。
【样例 1 解释】
【数据范围】
对于所有测试点，保证 2 ≤ n ≤ 50，2 ≤ m ≤ 400。
参考答案：br />61 32 32 33 13 23 2
4、微信步数（walk）
【题目描述】
小 C 喜欢跑步，并且非常喜欢在微信步数排行榜上刷榜，为此他制定了一个刷微信步数的计划。
他来到了一处空旷的场地，处于该场地中的人可以用 k 维整数坐标 (a1, a2, · · · , ak)来表示其位置。场地有大小限制，第 i 维的大小为 wi，因此处于场地中的人其坐标应满足 1 ≤ ai ≤ wi（1 ≤ i ≤ k）。
小 C 打算在接下来的 P = w1 × w2 × · · · × wk 天中，每天从场地中一个新的位置出发，开始他的刷步数计划（话句话说，他将会从场地中每个位置都出发一次进行计划）。
他的计划非常简单，每天按照事先规定好的路线行进，每天的路线由 n 步移动构成，每一步可以用 ci 与 di 表示：若他当前位于 (a1, a2, · · · , aci, · · · , ak)，则这一步他将会走到 (a1, a2, · · · , aci + di, · · · , ak)，其中 1 ≤ ci ≤ k，di ∈ {−1, 1}。小 C 将会不断重复这个路线，直到他走出了场地的范围才结束一天的计划。（即走完第 n 步后，若小 C 还在场内，他将回到第 1 步从头再走一遍）。
小 C 对自己的速度非常有自信，所以他并不在意具体耗费的时间，他只想知道 P天之后，他一共刷出了多少步微信步数。请你帮他算一算。
【输入格式】
从文件 walk.in 中读入数据。
第一行两个用单个空格分隔的整数 n，k。分别表示路线步数与场地维数。
接下来一行 k 个用单个空格分隔的整数 wi，表示场地大小。
接下来 n 行每行两个用单个空格分隔的整数 ci，di，依次表示每一步的方向，具体意义见题目描述。
【输出格式】
输出到文件 walk.out 中。
仅一行一个整数表示答案。答案可能很大，你只需要输出其对 109 + 7 取模后的值。
若小 C 的计划会使得他在某一天在场地中永远走不出来，则输出一行一个整数 -1。
【样例 1 输入】
3 2
3 3
1 1
2 -1
1 1
【样例 1 输出】
21
【样例 1 解释】
从 (1, 1) 出发将走 2 步，从 (1, 2) 出发将走 4 步，从 (1, 3) 出发将走 4 步。
从 (2, 1) 出发将走 2 步，从 (2, 2) 出发将走 3 步，从 (2, 3) 出发将走 3 步。
从 (3, 1) 出发将走 1 步，从 (3, 2) 出发将走 1 步，从 (3, 3) 出发将走 1 步。
共计 21 步。
【样例 2 输入】
5 4
6 8 6 5
3 1
2 1
1 1
2 1
2 -1
【样例 2 输出】
10265
【数据范围】
对于所有测试点，保证 1 ≤ n ≤ 5 × 105，1 ≤ k ≤ 10，1 ≤ wi ≤ 109，di ∈ {−1, 1}。
参考答案：对于每个位置，我们需要计算小C从该位置出发，按照给定的路线，能走多少步。首先，我们需要判断小C是否会陷入循环。对于每个位置，我们可以计算小C从该位置出发，按照给定的路线，需要多少天才能走出场地。我们可以通过模拟的方式，计算出每个位置对应的步数，并将这些步数存储在数组中。最后，我们遍历所有的位置，并累加每个位置的步数，得到总的步数。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
