一

T1：小奇挖矿2

因为只能走4步或7步，可以发现，当步数差\(\ge18\)时，一定能到达。而当步数差\(<18\)时，枚举出所有能到达的情况即可。

#include<bits/stdc++.h>
#define rg register
#define qwq 0
#define int long long
using namespace std;
const int N = 1e5 + 3;
int n, m;
struct node {
	int a, b;
} c[N];
inline bool cmp(node x, node y) {
	return x.b < y.b;
}
int dp[N], f[N];
bool vis[N];
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m;
	for (rg int i = 1; i <= n; i++) {
		cin >> c[i].a >> c[i].b;
	}
	sort(c + 1, c + n + 1, cmp);
	vis[0] = true;
	rg int ans = 0;
	for (rg int i = 1; i <= n; i++) {
		for (rg int j = i; j >= 0; j--) {
			if (c[i].b - c[j].b >= 18) {
				dp[i] = max(dp[i], f[j] + c[i].a);
				break;
			}
			if (vis[j]) {
				if (c[i].b - c[j].b == 0) dp[i] = max(dp[i], dp[j] + c[i].a);
				if (c[i].b - c[j].b == 4) dp[i] = max(dp[i], dp[j] + c[i].a);
				if (c[i].b - c[j].b == 7) dp[i] = max(dp[i], dp[j] + c[i].a);
				if (c[i].b - c[j].b == 8) dp[i] = max(dp[i], dp[j] + c[i].a);
				if (c[i].b - c[j].b == 11) dp[i] = max(dp[i], dp[j] + c[i].a);
				if (c[i].b - c[j].b == 12) dp[i] = max(dp[i], dp[j] + c[i].a);
				if (c[i].b - c[j].b == 14) dp[i] = max(dp[i], dp[j] + c[i].a);
				if (c[i].b - c[j].b == 15) dp[i] = max(dp[i], dp[j] + c[i].a);
				if (c[i].b - c[j].b == 16) dp[i] = max(dp[i], dp[j] + c[i].a);
			}
		}
		if (dp[i] != 0) vis[i] = true;
		f[i] = max(f[i - 1], dp[i]);
	}
	cout << f[n] << "\n";
	return qwq;
}

T2：小奇的矩阵(matrix)

容易推出，\(V = (n+m-1)\times pfh-sum^2\)，其中pfh为选的数的平方的和，sum为选的数的和。
令\(f[i][j][k]\)表示当前坐标\((i,j)\)，总值为k的最小值。

#include<bits/stdc++.h>
#define rg register
#define qwq 0
using namespace std;
const int N = 33;
int T, n, m;
int a[N][N];
int f[N][N][2005];
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> T;
	while (T--) {
		memset(f, -1, sizeof(f));
		cin >> n >> m;
		rg int len = n + m - 1;
		for (rg int i = 1; i <= n; i++) {
			for (rg int j = 1; j <= m; j++) {
				cin >> a[i][j];
			}
		}
		f[1][1][a[1][1]] = a[1][1] * a[1][1];
		for (rg int i = 1; i <= n; i++) {
			for (rg int j = 1; j <= m; j++) {
				for (rg int k = a[i][j]; k <= 1500; k++) {
					if (i == 1 && j == 1) continue ;
					if (f[i - 1][j][k - a[i][j]] != -1) {
						f[i][j][k] = f[i - 1][j][k - a[i][j]] + a[i][j] * a[i][j];
					}
					if (f[i][j - 1][k - a[i][j]] != -1) {
						if (f[i][j][k] == -1) f[i][j][k] = f[i][j - 1][k - a[i][j]] + a[i][j] * a[i][j];
						else f[i][j][k] = min(f[i][j][k], f[i][j - 1][k - a[i][j]] + a[i][j] * a[i][j]);
					}
				}
			}
		}
		rg int ans = 2e9;
		for (rg int i = 0; i <= 1500; i++) {
			if (f[n][m][i] == -1) continue ;
			ans = min(ans, f[n][m][i] * len - i * i);
		}
		cout << ans << "\n";
	}
	return qwq;
}

T3：小奇的仓库(warehouse)

换根DP。
若\(M=0\)很简单，但异或M不好处理。观察到M最大为15，最多只会对一个数的最后四位造成影响，于是将最后四位单独处理。
令\(f[i]\)表示以i为根的子树内的节点到i的距离之和（减去后四位），\(siz[i]\)表示此时距离以j为后缀的共有几个。
每一次向根节点方向转移时会加上一条边的长度，此时不同距离的后缀会发生相应的改变，然后更新父亲相应后缀的siz值。
f中统计的距离总和是抹掉所有后缀后的总和，等到最后根节点统计答案时再考虑每个后缀的贡献。
还有一点，因为\(0 xor M\)值为M，因此最后答案要减去M。

#include<bits/stdc++.h>
#define rg register
#define qwq 0
using namespace std;
const int N = 1e5 + 3;
int siz[N][17], fn[N], f[N];
int n, m;
struct edge {
	int to, val;
};
vector<edge> e[N];
inline void dfs1(int u, int fath) {
	siz[u][0] = 1;
	for (rg int i = 0; i < e[u].size(); i++) {
		rg int v = e[u][i].to, w = e[u][i].val;
		if (v == fath) continue ;
		dfs1(v, u);
		f[u] += f[v];
		for (rg int j = 0; j <= 15; j++) {
			rg int ret = j + w;
			rg int res = ret & 15;
			siz[u][res] += siz[v][j];
			f[u] += siz[v][j] * (ret - res);  //剔除后缀 
		}
	}
}
int sizn[N][17];
inline void dfs2(int u, int fath) {
	fn[u] = f[u];
	for (rg int i = 0; i <= 15; i++) {
		fn[u] += (i ^ m) * siz[u][i];
	}
	for (rg int i = 0; i <= 15; i++) {
		sizn[u][i] = siz[u][i];
	}
	rg int bf = f[u];
	for (rg int i = 0; i < e[u].size(); i++) {
		rg int v = e[u][i].to, w = e[u][i].val;
		if (v == fath) continue ;
		rg int ret, res;
		for (rg int j = 0; j <= 15; j++) {
			ret = j + w;
			res = ret & 15;
			siz[u][res] -= siz[v][j];
			f[u] -= siz[v][j] * (ret - res);
		}
		f[v] = f[u];
		for (rg int j = 0; j <= 15; j++) {
			ret = j + w;
			res = ret & 15;
			siz[v][res] += siz[u][j];
			f[v] += siz[u][j] * (ret - res);
		}
		dfs2(v, u);
		f[u] = bf;
		for (rg int j = 0; j <= 15; j++) {
			siz[u][j] = sizn[u][j];
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m;
	for (rg int i = 1; i < n; i++) {
		rg int x, y, z;
		cin >> x >> y >> z;
		e[x].push_back({y, z});
		e[y].push_back({x, z});
	}
	dfs1(1, 0);
	dfs2(1, 0);
	for (rg int i = 1; i <= n; i++) {
		cout << fn[i] - m << "\n";
	}
	return qwq;
}

T4：[COCI2014-2015#1] Kamp

令\(siz[i]\)表示i子树内关键点数量，\(f[i]\)表示i子树内完成任务并回到i的花费，\(g[i]\)表示i子树外完成任务并回到i的花费，\(dis[i][0]\)表示i子树内的最长链，\(dis[i][1]\)表示i子树内的次长链，\(up[i]\)表示i子树内的最长链。