$A$

正常的签到？

~~然而我写了多长一大坨屎山代码~~

暴力字符串匹配，然后将每个密码子能匹配上的位置起止位置作为线段的左右端点，则问题转化为选择尽量多的互不重叠的线段，贪心即可。

#include <cstdio>
#include <algorithm>
#include <cstring>

int fa[1000005], l[1000005], r[1000005];
char s[10005], p[100][5];
bool removed[1000005];
struct Line {
	int l, r;
	inline bool operator < (const Line X) const {return l < X.l;}
} li[10005];
int find(const int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}

int main() {
	int n, m(0), t(0), MaxR(0), ans(0);
	scanf("%s", s + 1);
	n = strlen(s + 1);
	while (scanf("%s", p[m + 1] + 1) != EOF) ++ m;
	for (int i(1); i <= m; ++ i)
	for (int j(1); j + 2 <= n; ++ j)
		if (s[j] == p[i][1] && s[j + 1] == p[i][2] && s[j + 2] == p[i][3])
			li[++ t].l = j, li[t].r = j + 2;
	std::sort(li + 1, li + t + 1);
	for (int i(1); i <= t; ++ i) fa[i] = i;
	for (int i(t); i; -- i)
		if (li[i - 1].r > li[find(i)].r) removed[i - 1] = true, fa[i - 1] = find(i);
	m = 0;
	for (int i(1); i <= t; ++ i)
		if (!removed[i]) l[++ m] = li[i].l, r[m] = li[i].r;
	for (int i(1); i <= m; ++ i)
		if (!removed[i] && MaxR < l[i]) MaxR = r[i], ++ ans;
	printf("%d", ans);
	return 0;
}

$B$

贪心。考虑按照罪犯指控关系建图，则将目前所有入度为 $0$ 的点设定为罪犯，删掉从这个点出发的边，从这个点开始dfs。

因为图有环，最后再扫一遍，从所有入度为 $1$ 的点开始 dfs 一遍。

感性理解一下这个贪心应该是正确的。严格证明不会，老师也没讲。

#include <cstdio>

int A[500005], In[500005], n, ans;
bool vis[500005];

void dfs(const int u, const int mark) {
	if (vis[u]) return;
	vis[u] = true;
	ans += mark;
	if (-- In[A[u]] == 0 || mark) dfs(A[u], mark ^ 1);
}

int main() {
	scanf("%d", &n);
	for (int i(1); i <= n; ++ i)
		scanf("%d", A + i), ++ In[A[i]];
	for (int i(1); i <= n; ++ i)
		if (In[i] == 0) dfs(i, 1);
	for (int i(1); i <= n; ++ i)
		if (In[i] == 1) dfs(i, 0);
	printf("%d", ans);
	return 0;
}

$C$

你既可以状压也可以贪心，考试时觉得状压代码也很短，贪心反而不好严格证明（虽然我找不出hack）就写了状压。

状压做的话就是板子题了。$dp_S$ 表示打完 $S$ 集合中的英雄最小所需HP。转移方程不再赘述。

#include <cstdio>
#include <algorithm>
#include <cstring>

inline int min(const int x, const int y) {return x < y ? x : y;}
int dp[1 << 20], h[20], d[20], sum[1 << 20];

int main() {
	memset(dp, 0x3f, sizeof dp);
	dp[0] = 0;
	int n;
	scanf("%d", &n);
	for (int i(0); i < n; ++ i) scanf("%d%d", d + i, h + i);
	for (int i(1); i < 1 << n; ++ i) {
		for (int j(0); j < n; ++ j)
			if (i & 1 << j) sum[i] += d[j];
	}
	for (int i(1); i < 1 << n; ++ i) {
		for (int j(0); j < n; ++ j)
			if (i & 1 << j) dp[i] = min(dp[i], dp[i ^ 1 << j] + sum[i] * h[j]);
	}
	printf("%d", dp[(1 << n) - 1]);
	return 0;
}

$D$

妙啊（蒟蒻听完评讲后的感言）！

题目：给你一颗树，求这些树上的节点权值两两异或和（所有点对路径上的异或和）。注意 $(x,x)$ 也是点对。

这个题没法像之前的套路性找最短路径和问题一样，因为异或没有分配律。

既然异或是二进制运算，那么对于每一位都进行一次求解，则原来的节点权值只有 $0$ 和 $1$ 两种。考虑树形dp。

$dp_{u,0/1}$ 表示在以 $u$ 为根节点的子树中，经过根节点 $u$，且不同时经过 $u$ 的两个以上的儿子的路径，异或和为 $0/1$ 的数量。

$dp_{u,0}=\sum\limits_{v\in sons(u)}dp_{v,val_u}$ $dp_{u,1}=\sum\limits_{v\in sons(u)}dp_{v,!val_u}$

注意边算 $dp_{u,0/1}$ 边统计答案。乘法原理将两个子树路径条数乘起来即可。

#include <cstdio>
#include <vector>
#define int long long

int dp[100005][23][2], val[100005], ans;
std::vector<int> sons[100005];

void dfs(const int u, const int fa) {
	for (int i(0); i <= 22; ++ i)
		if (val[u] & 1LL << i) dp[u][i][1] = 1;
		else dp[u][i][0] = 1;
	for (int v : sons[u]) if (v != fa) {
		dfs(v, u);
		for (int i(0); i <= 22; ++ i) {
			bool f(val[u] & 1 << i);
			ans += (dp[u][i][0] * dp[v][i][1] + dp[u][i][1] * dp[v][i][0]) << i;
			dp[u][i][0] += dp[v][i][f];
			dp[u][i][1] += dp[v][i][!f];
		}
	}
}

signed main() {
	int n;
	scanf("%lld", &n);
	for (int i(1); i <= n; ++ i) scanf("%lld", val + i), ans += val[i];
	for (int i(1); i < n; ++ i) {
		int u, v;
		scanf("%lld%lld", &u, &v);
		sons[u].push_back(v), sons[v].push_back(u);
	}
	dfs(1, -1);
	printf("%lld\n", ans);
	return 0;
}

$E$

之前做过和这道题有那么一点点相似的题，~~但是那题太难了（所以这就是你做不出这题的理由？）。~~

首先 $1\le a_i\le 50$ 显然有鬼对吧，正常情况直接给到1e9。也就是题目自动帮你离散化了亿下。

然后仍然没有头绪。挖掘一下区间反转的本质。其实就是两两交换了若干个数（当然数的位置有要求）。

想到这一步这题就和之前那题有一点相似了（想到这一步了这题甚至还简单一些）。

$dp_{l,r,d,u}$ 表示 $[l,r]$ 区间的数，经过若干次合法的交换，构成一个最大值大于 $u$，最小值小于 $d$ 的最长不下降子序列长度。

转移非常套路。$dp_{l,r,d,u}=max(dp_{l,r,d+1,u},dp_{l,r,d,u-1},dp_{l+1,r,d,u}+(A_l=d),dp_{l,r-1,d,u}+(A_r=u),dp_{l+1,r-1,d,u}+(A_l=u)+(A_r=d))$

#include <cstdio>

inline void max(int &x, const int y) {if (x < y) x = y;}
int A[51], dp[51][51][51][51];
bool vis[51][51][51][51];

int dfs(const int l, const int r, const int d, const int u) {
	if (l > r) return 0;
	if (l == r) return d <= A[l] && A[l] <= u;
	if (d > u) return 0;
	if (vis[l][r][d][u]) return dp[l][r][d][u];
	vis[l][r][d][u] = true;
	int &ans(dp[l][r][d][u]);
	max(ans, dfs(l, r, d + 1, u));
	max(ans, dfs(l, r, d, u - 1));
	max(ans, dfs(l + 1, r, d, u) + (A[l] == d));
	max(ans, dfs(l, r - 1, d, u) + (A[r] == u));
	max(ans, dfs(l + 1, r - 1, d, u) + (A[l] == u) + (A[r] == d));
	return ans;
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i(1); i <= n; ++ i) scanf("%d", A + i);
	printf("%d", dfs(1, n, 1, 50));
	return 0;
}

zqs`s blog

3/21 练习赛总结

$A$

$B$

$C$

$D$

$E$