solution

T1 降雨

题意

有 $N$ 座山，按顺时针编号依次为 $1$号山,$2$ 号山,以此类推。保证 $N$是奇数。在这些山脉之间，有 $N$ 座大坝，称为 $1$ 号大坝，$2$ 号大坝，以此类推。

第 $i$ 号大坝位于山脉 $i$ 和 $i+1$ 之间，由于山脉是环形分布的，所以山脉 $N$ 的下一座山是山脉 $1$，

当山脉 $i$ 接收 $2x$ 升雨水，大坝 $i-1$ 号大坝和 $i$ 号大坝分别接到 $x$升水即将它收集到的水均分给两边大坝。

每天，每座山都接收到偶数升且水量不为负数的雨水，累计 $a[i]$ 升水。

现在给出 大坝数量 $N$ 和 第 $i$ 个大坝收集的水量 $a[i]$ ,请你出计算每座山的降水量。

思路

根据题意，设答案为 $b_1,b_2,⋯,b_n$ ，则可以列出方程:

$$a_1 = \frac{b_1}{2} + \frac{b_2}{2} \\ a_2 = \frac{b_2}{2} + \frac{b_2}{2} \\ ... \\ a_n = \frac{b_n}{2} + \frac{b_1}{2} $$

用 $a_i$ 和 $b_{i+1}$ 表示 $b_i$ ：

$$b_1 = 2a_1 - b_2 \\ b_2 = 2a_2 - b_3 \\ b_3 = 2a_3 - b_4 \\ ... \\ b_n = 2a_n - b_1 $$

消去 $b_2$ 到 $b_n$ ：

$$b_1 = 2a_1 - 2a_2 + 2a_3 - 2a_4 + ... + 2a_n - b_1 \\ b_1 = a_1 - a_2 + a_3 - a_4 + ... + a_n $$

所以我们可以用数据直接算出 $b_1$ ，然后在原方程组的基础上，用 $a_i$ 和 $b_i$ 表示 $b_{i+1}$ ：

$$b_2 = 2a_1 - b_1 \\ b_3 = 2a_2 - b_2 \\ b_4 = 2a_3 - b_3 \\ ... \\ b_n = 2a_{n-1} - b_{n-1} $$

将 $b_1$ 代入，直接递推就可以算出所有答案，时间复杂度 $O(n)$ 。

T2 传送门

题意

一个国家有 $n$ 个小镇，小镇从 $1$ 到 $n$ 编号，每一个小镇有一个传送门，第 $i$ 个小镇的传送门可以把人传送到第 $a_i$ 个小镇。现在有一个旅行者从小镇 $1$ 开始旅游，问经过 $k$ 次传送之后，他去到了第几个小镇。

思路

题目的 $K$ 比较大，如果直接模拟 $K$ 次循环会超时，但我们可以发现无论怎么传送，只要 $K$ 大到一定程度，一定会成环，而且环的最大长度是 $N$ 。

我们将所有路径存储，然后从 $1$ 开始遍历，把经过的结点入栈，找出路径中的环路。判断环路的方式只需要在结点入栈之前判断它是否曾经入过栈，如果有，那么该结点首次出现的位置到栈顶位置之间的长度就是环路 $S$ 。

接着判断传送次数 $k$ 是否大于起点 $Q_0$ 到环路起点 $W_0$ 的距离 $length=Q_0-W_0$ 。

若 $k \gt length$ ，则输出栈中从 $0$ 开始计数的第 $Q_0+(K-W_0)\%S$ 个元素。

若 $k \le length$ ，则输出栈中从 $0$ 开始计数的第 $K$ 个元素。

T3 循环节

题意

如题所示

思路

模拟除法的过程，每一次将上次的余数乘以 10 后，再做除法就可以得到下一次的商和余数。余数为 0 表示除尽，余数重复则代表出现了循环节。使用数组记录小数部分商的同时，记录一个余数对应下商的位置，即可判断余数是否重复以及确定循环节的位置。

T4 老鼠

题意

最近小h家闹鼠灾，弄得小h十分恼火。为了解决老鼠的问题，小h根据老鼠的特点想出了一个方法。

假设小h 的家是一个n*n的网格，每个格子都有一定的食物，数量在0到100之间，经过观察，老鼠的窝在（1，1）的位置，老鼠吃东西有个特点，到哪个地方，就把这个地方的食物都吃掉，而且每次都比上一次吃的食物要多，因此它们总会有个停止的地方，而且，这些老鼠一次最多可以跳k格，不过只能按x轴或y轴方向来跳。

现在，小h给出食物的分布，他想知道一只老鼠最多可以吃到多少食物。

思路

记忆化搜索

int dfs(int x, int y)
{
	if(dp[x][y] > 0) {
		return dp[x][y];
	}
	int tmp = 0;
	for(int i = -k; i <= k; i++) {
		if(x+i >= 1 && x+i <= n && mp[x+i][y] > mp[x][y]) {
			dp[x+i][y] = dfs(x+i, y);
			tmp = max(tmp, dp[x+i][y]);
		}
	}
	for(int i = -k; i <= k; i++) {
		if(y+i >= 1 && y+i <= n && mp[x][y+i] > mp[x][y]) {
			dp[x][y+i] = dfs(x, y+i);
			tmp = max(tmp, dp[x][y+i]);
		}
	}
	dp[x][y] = tmp + mp[x][y];
	return dp[x][y];
}

T5 付款

题意

一个国家只有 $10^{100}+1$ 种面值的纸币，分别是 $1,10,10^2,10^3,...$ 。现在需要支付 $n$ 元，你有可能刚好凑齐，也有可能是需要给一个更大的钱数，然后找钱。问这个过程中最少需要多少纸币。

思路

对于要支付的钱，用字符串存，从数字的低位到高位，假设第 $i$ 位的数字是 $x$ ，那么只有两种选择：

1. 支付 $x$ 张 $10^i$
2. 支付 $1$ 张 $10^{i+1}$ ，找回 $10-x$ 张 $10^i$ 的货币。

状态表示：$f[0][i]$ 表示第 $i$ 位用第一种方法的最小票数，$f[1][i]$ 表示第 $i$ 位用第二种方法的最小票数。（最小票数指的是第 i~len 位所用的票数之和最小）

情况划分：根据第 $i+1$ 位的状态为依据将第 $i$ 位的两种状态各自划分为两类：（字符串正着存，从低位到高位转移就是倒着转移） $f[0][i]$：

1. 当第 $i+1$ 位的选择是 $1$ 时，即 $f[0][i+1]$，第 i+1 位产生的票数是支付时的 x 张，对第 i 位无影响，此时的 $f[0][i]$ 就等于 $f[0][i+1]$ 加上第 $i$ 位的票数 $x$ ：即$f[0][i+1] + (s[i] - '0')$；
2. 当第 $i+1$ 位的选择是 $2$ 时，即 $f[1][i+1]$ ，第 $i+1$ 产生的票数时店员找回的 10-x 张，同时还需要第 $i$ 位的 $1$ 张，这时的 $f[1][i+1]$ 没有算上(因为它包含的仅是第 i+1~len 位的票数和)，需要将这一张算到第 $i$ 位 $f[0][i]$ 中：即 $f[1][i+1] + (s[i] - '0' + 1)$

$f[1][i]$:

1. 当第 $i+1$ 位的选择是 $1$ 时，同理，在继承 $f[0][i+1]$ 的基础上再算上第 i 位所需的票数 $10-x$ ：即$f[0][i+1] + 10 - (s[i] - '0')$；
2. 当第 $i+1$ 位的选择是 $2$ 时，同理，由于第 $i+1$ 位还产生了 $1$ 张第 $i$ 位的票，所以第 $i$ 位的票数为 $x+1$ ，用到的票数为 $10-(x+1)$ ：即 $f[1][i+1] + 10 - (s[i] - '0' + 1)$

最后得到的 $f[0][0], f[1][0]$ 分别表示对于第1位选择1和选择2时，第 1~len 位所有票数的最小值。只需取$min(f[0][0],f[1][0])$即可。

注意预处理 $f[0][len]=s[len] - '0' 和 f[1][len]=10 - (s[len] - '0')$。

之所以循环 $i$ 到 $0$ 结束，是因为最后一个数即第1位如果选择2，向第0位借位的话，所借的这一张票只能第0位那里补算上，所以最后需要的是 $f[0][0]$ 与 $f[1][0]$。