T1

最开始是爱丽丝尽量远离绿，绿去追爱丽丝，如果爱丽丝和绿初始位置距离小于等于 $5$ （不是 $6$ 是因为爱丽丝先手，等绿出手会远离一格），那么等绿刷出来技能可以直接干掉爱丽丝，否则爱丽丝会干掉绿。

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
const int N = 1, inf = 2147483647;
int a, b, c, d;
int main() {
	scanf("%d%d%d%d", &a, &b, &c, &d);
	if (abs(c - a) + abs(d - b) <= 5) printf("Midori\n");
	else printf("Arisu\n");
	return 0;
}

T2

一个区间如果纳入新的数，那么这个数有可能会成为这个区间最大值或最小值，那么肯定是不优的，所以只需要枚举每相邻的两个的差就可以了。
时间复杂度 $O(n)$

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
const int N = 1e5 + 55, inf = 2147483647;
int n;
int a[N];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	int ans = 2e9;
	for (int i = 2; i <= n; i++) ans = min(ans, abs(a[i] - a[i - 1]));
	printf("%d\n", ans);
	return 0;
}

T3

分块，每个点如果块有标记则颜色为块的标记，没有则是原数组颜色，更新完整块直接给块打标记，非完整先下放标记，再暴力更新。
时间复杂度 $O(q \sqrt{n})$ 。

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
const int N = 2e5 + 55, M = 800, inf = 2147483647;
int n, q, len, tot;
int a[N], b[M], bl[N], l[M], r[M]; 
void init() {
	len = sqrt(n);
	tot = (n - 1) / len + 1;
	for (int i = 1; i <= tot; i++) {
		l[i] = r[i - 1] + 1;
		r[i] = i * len;
	}
	r[tot] = n;
	for (int i = 1; i <= tot; i++)
		for (int j = l[i]; j <= r[i]; j++)
			bl[j] = i;
}
void update(int ll, int rr, int c) {
	int p = bl[ll], q = bl[rr];
	if (p == q) {
		if (b[p]) for (int i = l[p]; i <= r[q]; i++) a[i] = b[p]; 
		for (int i = ll; i <= rr; i++) a[i] = c;	
		b[p] = 0;		
	}
	else {
		if (b[p]) for (int i = l[p]; i < ll; i++) a[i] = b[p];
		for (int i = ll; i <= r[p]; i++) a[i] = c;
		b[p] = 0;
		for (int i = p + 1; i <= q - 1; i++) b[i] = c;
		for (int i = l[q]; i <= rr; i++) a[i] = c;
		if (b[q]) for (int i = rr + 1; i <= r[q]; i++) a[i] = b[q];
		b[q] = 0;
	}
}
int main() {
	scanf("%d%d", &n, &q);
	init(); 
	while (q--) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		update(x, y, z);
	} 
	for (int i = 1; i <= n; i++) printf("%d ", b[bl[i]] ? b[bl[i]] : a[i]);
	return 0;
}

T4

定义状态 $dp_i$ 为走到 $i$ 所需最小的步数，每一位可以从上一位走过来，即

$$dp_i=dp_{i-1} + 1$$

也可以从之前的位置跳跃而来，设 $j$ 为蓄力的时间

$$dp_i=\min(dp_{i-j^2}+j+1)$$

初始在 $1$ 点

$$dp_1=0$$

时间复杂度 $O(n \sqrt{n})$

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
const int N = 2e5 + 55, inf = 2147483647;
int n;
int a[N];
int main() {
	scanf("%d", &n);
	for (int i = 2; i <= n; i++) a[i] = N;
	for (int i = 2; i <= n; i++) {
		a[i] = a[i - 1] + 1;
		for (int j = 2; i - j * j >= 1; j++) {
			a[i] = min(a[i], a[i - j * j] + j + 1);
		}
	}
	printf("%d\n", a[n]);
	return 0;
}

T5

感觉 T5 有问题啊，感觉我做法没啥问题，大家都 20 分，是都忽略啥了吗。
设 $dp_{i,j,k}$ 为在第 $k$ 秒走到点 $(i,j)$ 的方案数，你可以从上一秒相邻安全的点转移。其中起点在第 $0$ 秒为 $1$ ，答案是第 $t$ 秒的终点。
时间复杂度 $O(nmt)$
非AC代码：

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#define int long long
using namespace std;
const int N = 205, MOD = 998244353;
int n, m, t;
int a, b, c, d;
char str[N][N];
int f[N][N][N];
int nt[5][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
signed main() {
	scanf("%lld%lld%lld", &n, &m, &t);
	for (int i = 1; i <= n; i++) scanf("%s", str[i] + 1);
	scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
	f[a][b][0] = 1;
	for (int k = 1; k <= t; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if ((i != c || j != d) && str[i][j] == '*') continue;
				for (int p = 0; p < 4; p++) {
					int xx = i + nt[p][0];
					int yy = j + nt[p][1];
					f[i][j][k] = (f[i][j][k] + f[xx][yy][k - 1]) % MOD; 
				}
			}
		}
	}
	printf("%lld\n", f[c][d][t]);
	return 0;
}

T6

设 $f_i$ 为以 $i$ 为根的子树魔法值之和，$s_{i,j}$ 为以 $i$ 为根的子树颜色为 $j$ 结点总数，$d_{i,j}$ 为如果 $i$ 的父亲结点颜色为 $j$，子树中所有颜色为 $j$ 的结点与他相连能产生的除去这个父亲节点外能产生的魔法值。
对于每个结点：
$s$ 直接累加所有子树的每种颜色，最后在自己的颜色 $+1$。
$d$ 也是直接累加，但对于自己的颜色，要额外加上那个子树的 $s$，因为上面的点连接下面的点都会穿过他。
$f$ 先直接累加，对于与自己相连产生的贡献，就是那个子树与自己颜色相同的 $d + s$ ，原因：累加 $d$ 请看他的定义， $s$ 是因为还要算上当前结点产生的贡献。
然后考虑跨过当前结点产生的贡献，在每个子树内，其他子树所有颜色相同的节点都可以和自己的所有结点连接，设当前节点为 $u$，当前子树根结点为 $v$ 贡献就是 $d_v(s_u-s_v)$ ，对于每种颜色都要统计。还要额外颜色与当前结点相同时跨过当前结点产生的贡献。
时间复杂度 $O(nc)$

#include <iostream>
#include <cmath>
#include <cstdio>
#define int long long 
using namespace std;
const int N = 1e5 + 55, C = 105, inf = 2147483647;
int n, tot;
int f[N], d[N][C], s[N][C], h[N], a[N];
struct edge {
	int v, nxt;
} e[N << 2];
void add(int x, int y) {
	e[++tot] = {y, h[x]};
	h[x] = tot;
}
void dfs(int u, int fa) {
	int cnt = 0; 
	for (int i = h[u]; i; i = e[i].nxt) {
		if (e[i].v == fa) continue;
		dfs(e[i].v, u);
		f[u] += f[e[i].v];
		f[u] += d[e[i].v][a[u]] + s[e[i].v][a[u]];
		d[u][a[u]] += s[e[i].v][a[u]];
		for (int j = 1; j <= 100; j++) {
			d[u][j] += d[e[i].v][j];
			s[u][j] += s[e[i].v][j];
		} 
	}
	int ct = 0;
	for (int i = h[u]; i; i = e[i].nxt) {
		if (e[i].v == fa) continue;
		ct += (s[u][a[u]] - s[e[i].v][a[u]]) * s[e[i].v][a[u]];
		for (int j = 1; j <= 100; j++) {
			f[u] += (d[e[i].v][j]) * (s[u][j] - s[e[i].v][j]);
		}
	}
	ct /= 2;
	f[u] += ct;
	s[u][a[u]]++;
	d[u][a[u]]++;
}
signed main() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	for (int i = 1; i < n; i++) {
		int x, y;
		scanf("%lld%lld", &x, &y);
		add(x, y);
		add(y, x); 	
	}
	dfs(1, 0);
	printf("%lld\n", f[1]);

	return 0;
}