A - League Preparation

双循环需要打 $n(n-1)$ 场，单循环需要打 $\dfrac{n(n-1)}{2}$ 场。

$m$ 场比赛中间有 $m-1$ 个 $3$ 天间隔，因此一共 $4m-3$ 天。

记得特判 $n=1$。

#include <bits/stdc++.h>
using namespace std;
int main()
{
	freopen("league.in", "r", stdin);
	freopen("league.out", "w", stdout);
	int T;
	cin >> T;
	while (T--)
	{
		long long n;
		cin >> n;
		if (n == 1) cout << 0 << endl;
		if (n >= 2 && n <= 15) cout << n * (n - 1) * 4 - 3 << endl;
		if (n >= 16) cout << n * (n - 1) / 2 * 4 - 3 << endl;
	}
	return 0;
}

B - Rice Cake Consumption

对于任意两块相距不超过 $k$ 的年糕，无论先吃哪块，都会在另一块年糕上蹭下 $1$ 单位辣椒酱。

也就是说，最终蹭下辣椒酱的量与吃法无关，恒等于相距不超过 $k$ 的年糕对数。

直接前缀和统计相距不超过 $k$ 的年糕对数即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 12;
char s[N];
int pre[N];
int n;
int k;
int main()
{
	freopen("ricecake.in", "r", stdin);
	freopen("ricecake.out", "w", stdout);
	int T;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d %d %s", &n, &k, s + 1);
		for (int i = 1; i <= n; i++)
			pre[i] = pre[i - 1] + s[i] - '0';
		long long ans = 0;
		for (int i = 1; i <= n; i++)
			if (s[i] == '1')
			{
				int i1 = min(i + k, n);
				int i2 = max(i - k - 1, 0);
				ans += pre[i1] - pre[i2] - 1;
			}
		cout << ans / 2 << endl;
	}
	return 0;
}

C - Garbage Collection

显然最短的操作序列不包含 $1$，因为 $c_i=1$ 的操作什么用也没有，可以直接删去。

当已经确定操作序列时，去掉操作序列中的重复元素（假设取出后还剩 $m$ 个元素，它们本身构成集合 $S=\{c_i\ |\ i=1,2,\ldots,k\}$，加上元素 $1$ 后构成集合 $T=S\cup\{1\}$），考察 $1$ 号垃圾站和操作序列中涉及到的其他垃圾站：

• 这 $m+1$ 个垃圾站中最开始有 $\displaystyle \sum _{x \in T}a_x$ 袋垃圾。
• 设原操作序列中使得员工们并没有什么都不做的最靠后的出现 $x$ 的位置是 $c_{d_x}=x$，考察 $S$ 中的某个垃圾站 $x$：
  • 如果 $d_x$ 不存在，那么可以直接从原操作序列中删掉所有元素 $x$（以及 $x$ 号垃圾站的所有下级垃圾站、$x$ 号垃圾站的所有下级垃圾站的所有下级垃圾站、……所对应的元素，因为这些垃圾站不可能跨过 $x$ 号垃圾站把垃圾运送到 $1$ 号垃圾站，下同），显然不影响清理垃圾的袋数且可以使得操作序列更短。
  • 同理，如果原操作序列中的某一项使得员工们什么都不做，那么也可以把它删去。
  • 否则，$x$ 号垃圾站中最后：
    • 要么剩下恰好 $d_x$ 袋垃圾。
    • 要么剩下多于 $d_x$ 袋垃圾，但这意味着「它的下级垃圾站后来向它运了垃圾，但这些垃圾最终滞留在了 $x$ 号垃圾站中，没能运到 $1$ 号垃圾站，也没能增加清理垃圾的袋数」，此时显然可以直接选择不进行这些无用的运输，从原操作序列中删掉相关元素。（当然了，在剩下恰好 $d_x$ 袋垃圾的情况中，我们也可以这么做，于是操作序列中在 $c_{d_x}$ 后一定不会再出现任何有关 $x$ 号垃圾站机器下级垃圾站的操作。）

也就是说，设 $S$ 中所有元素 $x$ 对应的 $d_x$ 构成集合 $Q=\{d_i\ |\ i \in S\}$，那么最后留下的垃圾数量要想最少就尽量要让 $Q$ 集合中的所有元素之和 $\displaystyle \sum _{x \in Q} x$ 最小。

然而，在所有 $S$ 集合（或 $T$ 集合）相同的所有操作序列中，既没有相同元素也没有上文提到的这些无用元素的（或者说「最简洁的」）那个操作序列不仅可以实现 $Q=\{1,2,\ldots,m\}$（显然不可能再小了），而且项数显然最少。这样的操作序列一定存在：

• 对于任何一个垃圾站 $x$，考虑删去（如果有）操作序列中除 $c_{d_x}$ 外另一个等于 $x$ 的元素 $c_y=x$：
  • 对于任何一个垃圾站 $z$，只要 $c_{d_z}$ 依然不会使得员工什么都不做（或者说「$c_{d_z}$ 没有失效」），删去 $c_y$ 要么（$d_z<y$ 时，删去 $c_y$ 不影响 $c_{d_z}$ 在操作序列中的位置）不影响 $d_z$，要么（$d_z \ge y$ 时，删去 $c_y$ 使得 $c_{d_z}$ 从操作序列中前移了一位），把 $d_z$ 减小了 $1$：
    • 若 $z$ 没有下级垃圾站，则原来的 $c_{d_z}$ 显然不受对其他垃圾站进行的操作的影响，$c_{d_z}$ 依然不会使得员工什么都不做。
    • 当操作到 $c_{d_z}$ 时，所有应该运给 $z$ 号垃圾站的垃圾已经运送完毕（因为后面不会再运了）。若 $z$ 的下级垃圾站构成的集合 $P_z$ 中的每个下级垃圾站 $f \in P_z$ 都被证明「$c_{d_f}$ 没有失效」，则它们最开始存放了 $\displaystyle \sum _{x \in P_z}a_x$ 袋垃圾，最后滞留了 $\displaystyle \sum _{x \in P_z}d_x$ 袋垃圾，二者之差 $\displaystyle \sum _{x \in P_z}a_x - \displaystyle \sum _{x \in P_z}d_x$ 就是它们运给 $z$ 号垃圾站的垃圾袋数。由上面的分析，$\displaystyle \sum _{x \in P_z}a_x$ 不变，$\displaystyle \sum _{x \in P_z}d_x$ 只会变小或不变，因此二者之差 $\displaystyle \sum _{x \in P_z}a_x - \displaystyle \sum _{x \in P_z}d_x$ 只会变大或不变。由于执行 $c_{d_z}$ 时 $z$ 号垃圾站本就拥有多于 $d_z$ 袋垃圾（$\displaystyle \sum _{x \in P_z}a_x - \displaystyle \sum _{x \in P_z}d_x$ 袋），删除后 $\displaystyle \sum _{x \in P_z}a_x - \displaystyle \sum _{x \in P_z}d_x$ 只会变大或不变，$d_z$ 又只会变小或不变，因此仍然有 $\displaystyle \sum _{x \in P_z}a_x - \displaystyle \sum _{x \in P_z}d_x > d_z$，因此可以断言「$c_{d_z}$ 没有失效」。
    • 综上，对于任何一个垃圾站 $z$，可以断言「$c_{d_z}$ 没有失效」。
  • 删去 $c_y$ 后，考察 $1$ 号垃圾站和操作序列中涉及到的其他垃圾站，它们最开始存放的垃圾袋数之和 $\displaystyle \sum _{x \in T}a_x$ 保持不变（事实上，$a_1,a_2,a_3,\ldots,a_n$ 各自不变）。
  • 综上，删去 $c_y$ 一定是（并非严格地）更优的决策。
• 对于某个垃圾站 $x$，对所有满足上述条件的 $c_y$ 的逐个考虑删去，操作序列中便只会剩下唯一一个（$c_{d_x}$）等于 $x$ 的元素。
• 对 $x=1,2,3,\ldots,n$ 都像上面那样考虑一遍，操作序列中便不会再留下任何两个相同的元素，于是我们成功得到了「最简洁的」操作序列。

因此，我们只需要对每个 $T$ 集合求出一个「最简洁的」操作序列（如果存在的话），然后对这些操作序列进行（清理垃圾袋数和项数的）比较和计数即可。

进一步地，让我们把垃圾站的关系抽象成一棵树，那么 $T$ 集合一定构成一个包含 $1$ 号结点的连通块，于是我们考虑树形 DP，设三元组 $dp_{x,y}$ 表示：

• 只考虑 $T$ 集合在 $x$ 号结点（及其子树）的部分（且这一部分恰好包含 $y$ 个结点）。
• 此时的最多垃圾清理袋数（这里认为运送到 $x$ 号结点就算清理成功）。
• 此时对应的操作序列（这里指完整操作序列的子序列）最小项数。
• 此时最优操作序列的个数。

接下来，我们惊喜地发现：

• 除非不存在「最简洁的」操作序列，否则最优操作序列一定等价于「最简洁的」操作序列。
• 除非不存在「最简洁的」操作序列，否则最优操作序列的操作次数一定是 $y-1$。
• 除非不存在「最简洁的」操作序列，否则最多垃圾清理袋数一定是选定部分的初始垃圾袋数减去 $\displaystyle \sum _{i=1} ^{y-1} i = 1+2+\ldots+(y-1)=\dfrac{y(y-1)}{2}$ 的结果。
• 当不存在「最简洁的」操作序列时，如果将目前的最优操作序列中的无用操作去掉，得到一个「最简洁的」操作序列，那么这个操作序列：
  • 项数一定少于目前的最优操作序列。
  • 垃圾清理袋数一定不少于目前的最优操作序列。
  • 所对应的「$T$ 集合在 $x$ 号结点（及其子树）的部分」的结点数一定不大于（实际上是严格小于，因为我们已经假设了「不存在「最简洁的」操作序列」）目前的最优操作序列。
  • 一定在某个 $dp_{x,z}$ 中（$z<y$）被统计过了，于是从 $dp_{x,y}$ 向上转移出来的答案都不是最优解（都比从 $dp_{x,z}$ 向上转移出来的答案更劣），我们不会在最终的答案计算中采纳任何涉及 $dp_{x,y}$ 的答案。
• 当不存在「最简洁的」操作序列时，我们会把（本就不是全局最优解的）目前的最优操作序列的垃圾清理袋数算少（因为无用操作的本质是剩余垃圾太少运不上去，如果无用操作对应的那些垃圾站最终剩下的垃圾袋数的总和多余对应的 $d$ 序列中的预测值的总和，那么由前面的分析可知我们一定可以多运一些垃圾上去，这与它们是无用操作的试试矛盾，于是我们只会把最终剩下的垃圾袋数算多，而不会算少，这导致我们把目前的最优操作序列的垃圾清理袋数算少），于是我们更不会在最终的答案计算中采纳任何涉及 $dp_{x,y}$ 的答案。

也就是说，根据树形 DP 的流程，我们可以放心大胆地假设「最简洁的」操作序列有一定存在，因为我们不会在最终的答案计算中采纳任何涉及并非「最简洁的」操作序列的答案。

最后，当两个方案数分别为 $w_1,w_2$，项数分别为 $l_1,l_2$ 的子序列合并时，大序列的方案数为 $\displaystyle w_1w_2\binom{l_1+l_2}{l_1}=w_1w_2C_{l_1+l_2}^{l_1}=w_1 \cdot w_2 \cdot \dfrac{(l_1+l_2)!}{l_1! \cdot l_2!}$，其中组合数可以 $O(n^2)$ 预处理。

最终的时间复杂度为 $O(Tn^2)$，空间复杂度为 $O(n^2)$。

std 的 DP 实现与上文中的 DP 策略有两点不同：

• std 中 $y$ 指操作序列长度，比上文中的 $y$ 少 $1$。
• std 在 DP 过程中没有扣掉剩余的垃圾袋数，因此计算最终答案时需要在 std 中减去 $\dfrac{y(y+1)}{2}$。

#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 12;
const int M = 2000 + 12;
const int P = 1e9 + 7;
int C[N][N];
struct Bag
{
	int n;
	int maxsum[N];
	int count[N];
};
Bag b[N];
void init()
{
	for (int i = 0; i < N; i++)
		C[i][0] = C[i][i] = 1;
	for (int i = 2; i < N; i++)
		for (int j = 1; j < i; j++)
		{
			C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
			if (C[i][j] >= P) C[i][j] -= P;
		}
}
void operator+=(Bag& x, Bag y)
{
	Bag z = x;
	for (int i = 0; i <= x.n; i++)
		x.maxsum[i] = x.count[i] = 0;
	x.n = z.n + y.n;
	for (int i = 0; i <= z.n; i++)
		for (int j = 0; j <= y.n; j++)
		{
			if (z.maxsum[i] + y.maxsum[j] > x.maxsum[i + j])
			{
				x.maxsum[i + j] = z.maxsum[i] + y.maxsum[j];
				x.count[i + j] = 0;
			}
			if (z.maxsum[i] + y.maxsum[j] == x.maxsum[i + j])
			{
				x.count[i + j] += 1ll * z.count[i] * y.count[j] % P * C[i + j][i] % P;
				if (x.count[i + j] >= P) x.count[i + j] -= P;
			}
		}
}
void operator+=(Bag& x, int y)
{
	x.n++;
	for (int i = x.n; i >= 1; i--)
	{
		x.maxsum[i] = x.maxsum[i - 1] + y;
		x.count[i] = x.count[i - 1];
	}
}
struct Fk
{
	int to[M];
	int ns[M];
	int fs[N];
	int m = 0;
	void init(int n)
	{
		for (int i = 1; i <= m; i++)
			to[i] = ns[i] = 0;
		for (int i = 1; i <= n; i++)
			fs[i] = 0;
		m = 0;
	}
	void add(int f, int t)
	{
		m++;
		to[m] = t;
		ns[m] = fs[f];
		fs[f] = m;
	}
};
Fk fk;
int f[N];
int a[N];
void dfs(int x)
{
	int ii = fk.fs[x];
	while (ii)
	{
		if (fk.to[ii] != f[x])
		{
			dfs(fk.to[ii]);
			b[x] += b[fk.to[ii]];
		}
		ii = fk.ns[ii];
	}
	b[x] += a[x];
}
int main()
{
	freopen("garbage.in", "r", stdin);
	freopen("garbage.out", "w", stdout);
	init();
	int T;
	cin >> T;
	while (T--)
	{
		int n;
		cin >> n >> a[1];
		for (int i = 2; i <= n; i++)
			cin >> f[i] >> a[i];
		fk.init(n);
		memset(b, 0, sizeof b);
		for (int i = 1; i <= n; i++)
			b[i].count[0] = 1;
		for (int i = 2; i <= n; i++)
		{
			fk.add(i, f[i]);
			fk.add(f[i], i);
		}
		dfs(1);
		int bs = 0;
		for (int i = 0; i <= n - 1; i++)
			b[1].maxsum[i + 1] -= i * (i + 1) / 2;
		for (int i = 0; i <= n - 1; i++)
			if (b[1].maxsum[i + 1] > b[1].maxsum[bs + 1]) bs = i;
		cout << b[1].maxsum[bs + 1] << ' ' << bs << ' ' << b[1].count[bs + 1] << endl;
	}
	return 0;
}

D - Back Translation

有向环上 $a \to b$ 经过的最小边数被定义为单词 $a$ 和单词 $b$ 之间的语义偏差度 —— 由于翻译家并不像 OI 选手那样具备逆向思维，因此单词 $a$ 和单词 $b$ 之间的语义偏差度不一定等于单词 $b$ 和单词 $a$ 之间的语义偏差度。

考虑逆向思维，从单词 $i$ 沿着与题目描述相反的方向回译到单词 $i$。

（在下面的讨论中，我们默认单词 $i$ 可以翻译到单词 $i$ 本身，因为这显然不影响答案 —— 这只会增加翻译次数，而不能推进翻译进度，没人愿意这么做。）

于是我们惊喜地发现：

• 单词 $i$ 反向翻译一次能翻译到的单词恰好在环上构成一个半开半闭区间，其中闭区间的端点是单词 $i$ 本身，开区间的端点是距离单词 $i$ 反向距离最近的同语言单词 $j$。
• 在此基础上，如果我们再进行一次反向翻译，那么能翻译到的单词是所有「上一次能翻译到的单词」这次能翻译到的单词的并集。因为所有区间都是闭区间点为本身的半开半闭区间，所以这些区间的并集仍然是半开半闭区间，其中开区间的端点是所有「子区间内开区间的端点」中距离单词 $i$ 反向最远的单词。
• 随着翻译次数的增加，当这个反向最远的单词从单词 $i$ 开始绕着环反向跑了一圈又穿过单词 $i$ 来到它后面时，我们就求出了回译单词 $i$ 所需的最小翻译次数 —— 它就是使得这一事件发生所需的最小翻译次数。

直接二分每个答案并用 ST 表和（不属于 ST 表的）倍增实现对那个反向最远的单词的高效查询即可。

最终的时间复杂度为 $O(Tn \log^2 n)$，空间复杂度为 $O(n \log^2 n)$，瓶颈均在预处理部分。

（实际上，我们也可以套用 $O(n)-O(1)$ RMQ 把时间复杂度降到 $O(Tn \log n)$，空间复杂度降到 $O(n \log n)$，但是意义不大。）

#include <bits/stdc++.h>
using namespace std;
const int N = 2 * 1e5 + 12;
const int D = 17;
const int W = 18;
int a[N];
int b[N];
int logs[N];
int st[W][W][N];
void setst(int n, int x)
{
	for (int i = 1; i <= D; i++)
		for (int j = 1; j <= n - (1 << (i - 1)); j++)
			st[x][i][j] = min(st[x][i - 1][j + (1 << (i - 1))], st[x][i - 1][j]);
}
int getst(int l, int r, int x)
{
	int y = logs[r - l + 1];
	return min(st[x][y][l], st[x][y][r - (1 << y) + 1]);
}
int main()
{
	freopen("translation.in", "r", stdin);
	freopen("translation.out", "w", stdout);
	for (int i = 1; i <= D; i++)
		logs[1 << i] = i;
	for (int i = 3; i <= N - 1; i++)
		if (!logs[i]) logs[i] = logs[i - 1];
	int T;
	scanf("%d", &T);
	while (T--)
	{
		int n;
		scanf("%d", &n);
		int m = (n << 1);
		memset(st, 0x7f, sizeof st);
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
			a[i + n] = a[i];
			b[a[i]] = 0;
		}
		for (int i = 1; i <= m; i++)
		{
			st[0][0][i] = b[a[i]] + 1;
			b[a[i]] = i;
		}
		for (int i = 0; i <= D; i++)
			st[i][0][1] = 1;
		setst(m, 0);
		for (int i = 1; i <= D; i++)
		{
			for (int j = 2; j <= m; j++)
				st[i][0][j] = getst(st[i - 1][0][j], j, i - 1);
			setst(m, i);
		}
		for (int i = n + 1; i <= m; i++)
		{
			int ans = 1;
			int cur = i;
			for (int j = D; j >= 0; j--)
			{
				int to = getst(cur, i, j);
				if (to > i - n)
				{
					ans += (1 << j);
					cur = to;
				}
			}
			printf("%d", ans);
			if (i < m) putchar(' ');
		}
		puts("");
	}
	return 0;
}