似乎全是水题，但我还是没有做出来......

A

求将 $n$ 分解为 $k$ 个不同质数的和的方案数

考虑 dp, $f[i][j]$ 表示将 $i$ 分解为 $j$ 个的方案，但因为要求不同，所以没有办法确定枚举范围，开始时我傻乎乎的以为只要枚举的质数 $pr$ 大于 $i-pr$ 就可以了，但这样显然是错的。反例是 15 3。

于是加一个维度 $f[i][j][k]$ 表示用 $k$ 个质数，最后一个是 $j$, 拼出 $i$ 的方案数，转移的时候再枚举上个最后一个就好了，这样子要三维状态加一维转移，实在太慢，无法忍受。观察发现转移时需要的都是从头开始的一段的和，答案是所有 $f[n][j][K]$ 的和，所以直接把这玩意儿做成前缀和就好了。

代码。(把 $j$ 放到了最后一个维度，为了方便。)

Seive(n);
for(int i = 1; i <= nump; i++) 
	for(int j = i; j <= nump; j++) f[pr[i]][1][j] = 1;
for(int i = 1; i <= n; i++)
	for(int j = 2; j <= k; j++)
		for(int k = 1; k <= nump; k++) {
			f[i][j][k] = f[i][j][k-1];
			if(i - pr[k] >= 0) f[i][j][k] += f[i-pr[k]][j-1][k-1];
		}
printf("%lld\n", f[n][k][nump]); 

B

bfs 基础题，没有技术含量。

C

给定一个矩阵，只能向下和向右走，求路径上数的乘积最后的 $0$ 的最少数量。

最少的 $0$ 就是经过的 $2$ 因子个数和 和 $5$ 因子个数和中最小的那个，所以题目要求就是最小的最小，最小的最小不就是最小吗！直接分开跑一遍取最小就可以了。

可是我比赛的时候很呆的没想到，只想着若确定了一个最小，则另一个数字最小的状态是最优的，于是还记了经过的具体 $2$ 和 $5$ 的数量，写出来的代码复杂得多， 浪费了一些时间来调试。

代码也放着留作纪念吧。

#include <cstdio>
#include <algorithm> 
const int N = 1005, INF = 100000000;
int n, x, num2[N][N], num5[N][N];
struct twt2 {
	int sum2, sum5;
	bool operator < (twt2 b) const {
		return sum2 < b.sum2 ||
			  (sum2 == b.sum2 && sum5 < b.sum5);
	}
} f2[N][N];
struct twt5 {
	int sum2, sum5;
	bool operator < (twt5 b) const {
		return sum5 < b.sum5 ||
			  (sum5 == b.sum5 && sum2 < b.sum2);
	}
} f5[N][N];
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) 
		for(int j = 1; j <= n; j++) {
			scanf("%d", &x);
			if(x == 0) { num2[i][j] = -1; continue; }
			while(x % 2 == 0) num2[i][j] ++, x /= 2;
			while(x % 5 == 0) num5[i][j] ++, x /= 5;
		}
	for(int i = 1; i <= n; i++) 
		f2[0][i].sum2 = INF, f5[0][i].sum5 = INF,
		f2[i][0].sum2 = INF, f5[i][0].sum5 = INF;
	f2[1][1].sum2 = num2[1][1], f2[1][1].sum5 = num5[1][1];
	f5[1][1].sum2 = num2[1][1], f5[1][1].sum5 = num5[1][1];	
	for(int i = 1; i <= n; i++)	
		for(int j = 1; j <= n; j++) {
			if(i == 1 && j == 1) continue; 
			if(num2[i][j] == -1) {
				f2[i][j].sum2 = INF;
				continue;
			}
			f2[i][j] = std::min(f2[i-1][j], f2[i][j-1]);
			f2[i][j].sum2 += num2[i][j], f2[i][j].sum5 += num5[i][j];
		}
	for(int i = 1; i <= n; i++)	
		for(int j = 1; j <= n; j++) {
			if(i == 1 && j == 1) continue; 
			if(num2[i][j] == -1) {
				f5[i][j].sum5 = INF;
				continue;
			}
			f5[i][j] = std::min(f5[i-1][j], f5[i][j-1]);
			f5[i][j].sum2 += num2[i][j], f5[i][j].sum5 += num5[i][j];
		} 
	return 0;
} 

D

题目未修改全文如下。

恭喜你，成为了牛牛航空公司的老板。
公司中有N个飞行员，有N/2架飞机。每架飞机需要配置两个飞行员，一个是机长，一个是助手。

现在你了解到了一些信息，比如每个飞行员当机长时希望获得的工资，和当助手时希望获得的工资。且每个飞行员都只愿意为比自己年纪大的人当助手。

现在需要你安排着N个人，到指定的飞机工作。如何做才能使得你需要支付的工资总数最小呢？

刚看到这个题目的时候就很奇怪这是什么年代的题目，为什么不是副驾驶 (co-polit/first officer) 而是助手？难道和 "Berd and his man" 是同一个年代的？

那么有没有具体规定应该怎么叫呢？

找了行情资料汇编并没有找到，看了民航法也没有规定具体的称呼，不过 ICAO 有一个 Q&A 中提到了

What is the MPL?

The MPL allows a pilot to exercise the privileges of a co-pilot in a commercial air transportation on multi-crew aeroplanes. It provides the aviation community with an opportunity to train pilots directly for co-pilot duties.

其中说了一个是机长，另一个是 co-polit 或 first officer。

在 CAAC 的网站能搜索到很多关于副驾驶的资料，如 这个

好了，接下来才是正经事。

其实这题就是要每组两个数选一个，只不过有一些限制。

如果没有限制，直接 dp 很简单，但有限制后有后效性。一般解决后效性的办法是改变转移顺序，对于这题，从后往前就好了。

#include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
const int N = 1e4 + 10;
int n, f[2][N], a[N], b[N];
signed main() {
    memset(f, 0x7f, sizeof(f));
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) scanf("%lld%lld", &a[i], &b[i]);
    f[0][0] = a[n];
    for (int i = n - 1; i >= 1; i--) {
        f[i & 1][0] = f[i & 1 ^ 1][0] + a[i];
        for (int j = 1; j <= (n - i + 1) / 2; j++)
            f[i & 1][j] = std::min(f[i & 1 ^ 1][j] + a[i], f[i & 1 ^ 1][j - 1] + b[i]);
    }
    printf("%lld", f[1][n / 2]);
}

比赛时一直在想着匹配的问题，没有想到 dp, 一直纠结于匹配了，最后搞了一个显然错的贪心，用 FTT（Fast Tanweitan Transform,快速谭炜谭变换）后获得 $0$ 分。