【施工中，已完成C】2021 CCPC 女生专场（TeamVP）

比赛相关信息

比赛信息

比赛名称： 2021年中国大学生程序设计竞赛女生专场
比赛地址： Gym补题

全部参赛队伍： （非官方）257队
金： （非官方）Rk 35，6题，710m
银： （非官方）Rk 105，5题，330m
铜： （非官方）Rk 210，4题，682m

其他参考：
8题尾： Rk 11
7题尾： Rk 19
6题尾： Rk 35
5题尾： Rk 184

以上数据参考自 \(\tt Gym\) 榜单，可能与官方榜单有所差别。

比赛过程回顾

共 5 题，132m，Rk 36（五题第一）。

✔：比赛时通过；⚪：比赛时提交过；补：已补题。

个人小评

纯手速场，五道签到题全部做出来最快就有银牌，兜底也有铜牌，但是再往上就比较困难了。VP时我们队伍发挥不错，47分钟搞定全部签到题之后就开始罚坐，杰神看了一圈题之后直接开了没人开的H，上网摘了个圆的面积并的板子之后光荣T62；我和 \(\mathcal Hamine\) 则一起开了C，但是搞了半天也没能搞出来，刚开始暴力实现T59，之后就一直在猜优化，可惜的是最终都猜错了……

赛程前半把全部题目都开了一遍，B没有思路；我手推了一下E感觉像是矩阵之类的神必题就没去碰了；F则是完全没有思路（然而最后好像过了挺多人的，好神必）；\(\mathcal Hamine\) 开了J之后跟我解释了下什么是”最大权边独立集“，我去找了下最小割的资料发现都是没涉及过的芝士，只能作罢。

快到三个小时的时候，杰神要去做核酸于是先行离开，我和 \(\mathcal Hamine\) 又各自推了一会儿C，一交流才发现我们两个思路是一样的，\(\mathcal Hamine\) 那边实现差一点所以一直WA2、3这种点，改过之后和我一起WA11，然后 \(\mathcal Hamine\) 找到了这个思路的缺陷，于是决定直接结束比赛，最终耗时三个半小时。

部分题目回顾

C - 连锁商店

小评

赛后补题。赛时很容易的想到了二分，但是尴尬的点在于我们想的是对时间进行二分，然后分类讨论两个人的位置关系，这就导致代码很长，而且一直存在错误没有找到。

总体来说这是一道偏简单的题目，想到了正解之后代码极其精炼，且没有多少细节，能够很轻易的解决。

题意

长度为 \(N\) 的数轴上有两个人分别位于 \(x、y\) ，两个人的步行速度分别为 \(v_x、v_y\) ，在任何时刻他们都能转换方向，求解他们走遍整根数轴需要的最短时间。

思路

先来分析暴力 \(\tt dfs\) 的复杂度：假设构成完全图，那么到第二家店有 \(1\) 种走法（从第一家店转移过来），到第三家店有 \(2\) 种走法（从第一家店转移过来 \(1\) 种，从第二家店转移过来 \(2\) 种），到第四家店有 \(4\) 种走法（从第一家店转移过来 \(1\) 种，从第二家店转移过来 \(1\) 种，从第三家店转移过来 \(2\) 种），……，到第 \(N\) 家店有 \(2^{N-2}\) 种走法。可以得到纯暴力的复杂度：\(\mathcal O(N*2^N)\) ，显然是超时的。

优化方法1：根据规律出发进行剪枝

我们发现，尽可能的多拿红包一定更优，所以，如果从 \(u\) 到 \(v\) 有直达和间接到达两种选择，则一定是间接到达更优。所以我们只需要对读入的边进行判断处理即可，具体而言，对于每一条读入的边 \(u,v\) ，暴力枚举所有的 \(k \in (u,v)\) ，判断是否同时存在 \(u,k\) 和 \(k,v\) 两条边，如果存在，则直接丢弃 \(u,v\) 这一条边。

再来分析剪枝之后 \(\tt dfs\) 的复杂度：假设构成完全图，那么到第 \(N\) 家店只有 \(1\) 种走法（从第 \(N-1\) 家店转移过来）。加上判边的复杂度，可以得到：\(\mathcal O(M*N)\) 。

这里还想要提一嘴网上题解所言的” \(\tt Flody\) 优化“，这个方法在本质上确实是利用了和 \(\tt Flody\) 类似的思想，但是我并不觉得这就可以粗暴的称之为” \(\tt Flody\) 优化“，事实上如果在这里硬套 \(\tt Flody\) 的代码的话反倒会造成不必要的麻烦，不如直接抽丝剥茧，直接用暴力枚举来形容这个剪枝的思想。

优化方法2：状态压缩 \(\tt DP\)

这个方法不是我的学习方向，这里指路我队友 \(\mathcal Hamine\) 的博客，他有详细的研究。

AC代码

const int N = 36 + 7;
int c[N], w[N];
map<pair<int, int>, int> edge;
namespace G {
	const int M = N * N;
	int tot, h[N], ver[M], ne[M];
	int v[N], ans[N];
	
	void add(int x, int y) {
	    ver[++ tot] = y, ne[tot] = h[x], h[x] = tot;
	}
	void dfs(int x, int sum) {
		if (v[c[x]] == 0) sum += w[c[x]];
		++ v[c[x]];
		ans[x] = max(ans[x], sum);
	    for (int i = h[x]; i; i = ne[i]) {
	        int y = ver[i];
	        dfs(y, sum);
	    }
	    -- v[c[x]];
	}
}
void check(int n) {
	for (auto [it, u] : edge) {
		auto [x, y] = it;
		int f = 0;
		for (int k = x + 1; k < y; ++ k) {
			if (edge.count({x, k}) && edge.count({k, y})) {
				f = 1;
			}
		}
		if (!f) G::add(x, y);
	}
}
signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; ++ i) cin >> c[i];
	for (int i = 1; i <= n; ++ i) cin >> w[i];
	for (int i = 1; i <= m; ++ i) {
		int x, y; cin >> x >> y;
		edge[{x, y}] = 1;
	}
	check(n);
	G::dfs(1, 0);
	for (int i = 1; i <= n; ++ i) cout << G::ans[i] << endl;
	
	return 0;
}

？