省选联考 2021 B 卷

• D1T1｜数对｜100
• D1T2｜卡牌游戏｜100
  • 20pts
  • 40pts
  • 100pts
• D1T3｜图函数｜0
• D2T1｜取模｜60
• D2T2｜宝石｜25
• D2T3｜滚榜｜0
• 总结

15:30打到18:30，中间忘了，后面忘了。

D1T1｜数对｜100

易验丁真，鉴定为桶。

考虑枚举 $a_i$。

• $a_i$ 与 $a_j$ 配对，$i \neq j$ 且 $a_i = a_j$，贡献为 $cnt[a_i] \times (cnt[a_j] - 1)$；
• $a_i$ 与 $a_j$ 配对，$i \neq j$ 且 $k \cdot a_i = a_j$，贡献为 $cnt[a_i] \times cnt[a_j]$。

第一种情况本来写成除以2了，然而实际上并不用，但是样例能过。

把除以2删了反而样例不过。

发现当存在 $a_i = a_j$ 时会重复计数，特判一下。

掉坑里了。

官方数据能过，但是 hack 不行。

复杂度好像是什么调和极数，不过我不会。

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

typedef long long lxl;
typedef std::vector<int> vic;
typedef std::map<int, int> mii;

const int maxN = 2e5;
const int maxA = 5e5;

int n;
int a[maxN + 10];
int c[maxA + 10];
int ans;

int main() {
	std::cin >> n;
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	for (int i = 1; i <= n; i++) c[a[i]]++;
	for (int i = 1; i <= maxA; i++) {
		for (int j = 2; i * j <= maxA; j++) {
			ans += c[i] * c[i * j];
		}
		ans += c[i] * (c[i] - 1);
	}
	std::cout << ans;
	return 0;
}

D1T2｜卡牌游戏｜100

20pts

$n \le 10$。

考虑暴搜。

#include <iostream>
#include <algorithm>

const int maxN = 1e6;
const int inf = 1e9;

int n, m;
int a[maxN + 10];
int b[maxN + 10];
int ans = inf;

void DFS(int now, int cnt, int max, int min) {
	if (cnt > m) return;
	if ((n - now + 1) < (m - cnt)) return;
	if (max - min > ans) return;
	if (now > n) {
		ans = std::min(ans, max - min);
		return;
	}
	//printf("DFS %d, %d, %d, %d\n", now, cnt, max, min);
	DFS(now + 1, cnt, std::max(max, a[now]), std::min(min, a[now]));
	DFS(now + 1, cnt + 1, std::max(max, b[now]), std::min(min, b[now]));
	return;
}

int main() {
	std::cin >> n >> m;
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	for (int i = 1; i <= n; i++) std::cin >> b[i];
	DFS(1, 0, 0, inf);
	std::cout << ans << '\n';
	return 0;
}

40pts

极差即差的最大值。

求差的最大值最小。

考虑二分答案。

当前检查的答案为 $x$，值域左端点为 $l$，值域右端点为 $r = l + x$。

那么 $a_i \in [l, r]$ 内的卡牌 $i$ 是不需要翻面的。

并且 $a_i \notin [l, r]$ 内的卡牌 $i$ 是必须要翻面的。

由于 $a_i$ 单调，可以再次使用二分求得不需要反面的卡牌下标区间 $[l, r]$。

对于区间 $[1, l), (r, n]$，则需要保证 $b_i \in [l, r], i \in [1, l) \cup (r, n]$ 才合法。

于是转化为关于 $b$ 的 RMQ 问题。

这个算法应该是还可以优化到正解的但是我没做到。

#include <iostream>
#include <algorithm>

const int maxN = 1e6;
const int inf = 1e9;

int n, m;
int a[maxN + 10];
int b[maxN + 10];

struct SegmentTree {
	struct Node {
		int max;
		int min;
	} node[maxN * 4 + 10];

	void PushUp(int u) {
		node[u].max = std::max(node[u * 2].max, node[u * 2 + 1].max);
		node[u].min = std::min(node[u * 2].min, node[u * 2 + 1].min);
		return;
	}

	void Build(int u, int l, int r) {
		if (l == r) {
			node[u].max = b[l];
			node[u].min = b[l];
			return;
		}
		int mid = (l + r) / 2;
		Build(u * 2, l, mid);
		Build(u * 2 + 1, mid + 1, r);
		PushUp(u);
		return;
	}

	int QueryMax(int u, int l, int r, int s, int t) {
		if (s > t) return 0;
		if (s <= l && r <= t) {
			return node[u].max;
		}
		int mid = (l + r) / 2;
		if (t <= mid) return QueryMax(u * 2, l, mid, s, t);
		if (s >= mid + 1) return QueryMax(u * 2 + 1, mid + 1, r, s, t);
		return std::max(QueryMax(u * 2, l, mid, s, t), QueryMax(u * 2 + 1, mid + 1, r, s, t));
	}

	int QueryMin(int u, int l, int r, int s, int t) {
		if (s > t) return inf;
		if (s <= l && r <= t) {
			return node[u].min;
		}
		int mid = (l + r) / 2;
		if (t <= mid) return QueryMin(u * 2, l, mid, s, t);
		if (s >= mid + 1) return QueryMin(u * 2 + 1, mid + 1, r, s, t);
		return std::min(QueryMin(u * 2, l, mid, s, t), QueryMin(u * 2 + 1, mid + 1, r, s, t));
	}
} SGT;

bool check(int x) {
	//printf("checking dif = %d\n", x);
	for (int l = 1; l <= a[m + 1]; l++) {
		int r = l + x;
		int i = std::lower_bound(a + 1, a + n + 1, l) - a;
		int j = std::upper_bound(a + 1, a + n + 1, r) - a - 1;
		int need = (i - 1) + (n  - j);
		//printf("pos: [%d, %d], val: [%d, %d]\n", i, j, l, r);
		if (need > m) continue;
		if (1 != i) {
			int max1i = SGT.QueryMax(1, 1, n, 1, i - 1);
			int min1i = SGT.QueryMin(1, 1, n, 1, i - 1);
			//printf("[%d, %d]: min = %d, max = %d\n", 1, i - 1, min1i, max1i);
			if (max1i > r) continue;
			if (min1i < l) continue;
		}
		if (j != n) {	
			int maxjn = SGT.QueryMax(1, 1, n, j + 1, n);
			int minjn = SGT.QueryMin(1, 1, n, j + 1, n);
			//printf("[%d, %d]: min = %d, max = %d\n", j + 1, n, minjn, maxjn);
			if (maxjn > r) continue;
			if (minjn < l) continue;
		}
		/*
		int maxij = SGT.QueryMax(1, 1, n, i, j);
		int minij = SGT.QueryMin(1, 1, n, i, j);
		printf("[%d, %d]: min = %d, max = %d\n", i, j, minij, maxij);
		if (maxij > r) continue;
		if (minij < l) continue;
		*/
		return true;
		//printf("\n");
	}
	return false;
}

int main() {
	std::cin >> n >> m;
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	for (int i = 1; i <= n; i++) std::cin >> b[i];
	SGT.Build(1, 1, n);
	int l = 0;
	int r = inf;
	while (l < r) {
		int mid = (l + r) / 2;
		if (check(mid)) r = mid;
		else l = mid + 1;
		//printf("\n\n");
	}
	std::cout << l << '\n';
	return 0;
}

100pts

这个套路半个月前刷 CF 题 的时候见过。

把所有可能出现在最后序列中的取值都拉出来排序并记录其来源然后跑弱化版莫队（双指针）。

#include <iostream>
#include <algorithm>

const int maxN = 1e6;
const int inf = 1e9;

int n, m;
int a[maxN + 10];
int b[maxN + 10];
int ans = inf;

struct Node {
	int type;
	int pos;
	int val;

	bool operator<(const Node &other) const {
		return val < other.val;
	}
} node[maxN * 2 + 10];

int vis[maxN + 10];
int l = 1;
int r = 0;
int cntA = 0;
int tot = 0;

void Add(int x) {
	if (vis[node[x].pos] == 0) tot++;
	vis[node[x].pos] += node[x].type;
	if (node[x].type == 1) cntA++;
	return;
}

void Del(int x) {
	vis[node[x].pos] -= node[x].type;
	if (vis[node[x].pos] == 0) tot--;
	if (node[x].type == 1) cntA--;
	return;
}

bool check() {
	int cntB = tot - cntA;
	if (cntB > m) return false;
	if (tot < n) return false;
	return true;
}

int main() {
	std::cin >> n >> m;
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	for (int i = 1; i <= n; i++) std::cin >> b[i];
	for (int i = 1; i <= n; i++) node[i] = (Node) {1, i, a[i]};
	for (int i = 1; i <= n; i++) node[i + n] = (Node) {2, i, b[i]};
	std::sort(node + 1, node + 2 * n + 1);
	while (r <= 2 * n) {
		//printf("[%d, %d]\n", l, r);
		while (r <= 2 * n && !check()) Add(++r);
		if (r <= 2 * n && check()) ans = std::min(ans, node[r].val - node[l].val);
		//printf("ans = %d\n", ans);
		//while (l <= r && check()) 
		Del(l++);
	}
	std::cout << ans << '\n';
	return 0;
}

D1T3｜图函数｜0

题还是比较复杂的。

看上去需要 Floyd 维护连通性。

大体框架写出来就润了。

前 4 个点的 16 分是可以拿的。

#include <iostream>
#include <vector>
#include <deque>

typedef std::vector<int> vic;
typedef std::deque<int> dic;

const int maxN = 1e3;
const int maxM = 2e5;

int n, m;
int x[maxM + 10], y[maxM + 10];
int f[maxN + 10][maxN + 10];
int g[maxN + 10][maxN + 10];
vic e[maxN + 10];
dic ans;

void floyd(int k) {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == k) continue;
			if (j == k) continue;
			if (i == j) continue;
			f[i][j] += f[i][k] * f[k][j];
		}
	}
	return;
}

void dyolf(int k) {
	
}

int F(int u) {
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			g[i][j] = f[i][j];
		}
	}
	for (int v = 1; v <= u; v++) {
		if (g[u][v] && g[v][u]) {
			cnt++;
			
		}
	}
}

int h(int ban) {
	if (ban <= m) {
		f[x[ban]][y[ban]] = true;
		floyd(x[ban]);
		floyd(y[ban]);
	}
	int ret = 0;
	for (int u = 1; u <= n; u++) {
		ret += F(u);
	}
	return ret;
}

int main() {
	std::cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		std::cin >> x[i] >> y[i];
		e[x[i]].push_back(i);
	}
	for (int i = 1; i <= n; i++) f[i][i] = 1;
	for (int i = m + 1; i >= 1; i--) ans.push_front(h(i));
	return 0;
}

D2T1｜取模｜60

直觉告诉我们先排序。

枚举 $k$。

记 $b_i = a_i \bmod a_k$。

然后枚举 $i, j$。

很无脑吧。

当 $a_k - 1$（即模 $a_k$ 下的最大值）$\lt ans$ 时，答案无论如何都不能再更新的，停止枚举。

#include <iostream>
#include <algorithm>

const int maxN = 2e5;

int n;
int a[maxN + 10];
int b[maxN + 10];
int ans;

int main() {
	std::cin >> n;
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	std::sort(a + 1, a + n + 1);
	for (int k = n; k >= 1; k--) {
		if (a[k] - 1 <= ans) break;
		for (int i = 1; i <= n; i++) {
			b[i] = a[i] % a[k];
		}
		for (int i = 1; i <= n; i++) {
			if (i == k) continue;
			for (int j = 1; j <= n; j++) {
				if (j == k) continue;
				if (i == j) continue;
				ans = std::max(ans, (b[i] + b[j]) % a[k]);
			}
		}
	}
	std::cout << ans;
}

D2T2｜宝石｜25

树上路径我只会倍增 LCA。

先写个 $\mathcal O(qn)$ 的暴逆，能拿 25pts。

#include <iostream>
#include <set>

typedef std::set<int> sit;

const int maxN = 2e5;
const int maxQ = 2e5;
const int maxM = 5e4;
const int maxC = 5e4;

int n, m, c;
int P[maxC + 10];
int w[maxN + 10];
int u, v;
int q;
int s, t;

namespace graph {
	struct Vertex {
		int head;
	} vertex[maxN + 10];

	struct Edge {
		int head;
		int next;
	} edge[2 * maxN + 10];

	int ecnt;

	void addEdge(int tail, int head) {
		ecnt++;
		edge[ecnt].head = head;
		edge[ecnt].next = vertex[tail].head;
		vertex[tail].head = ecnt;
		return;
	}

	void DFS(int u, int t, int from, int cur) {
		if (w[u] == P[cur + 1]) cur++;
		if (u == t) {
			std::cout << cur << '\n';
			return;
		}
		for (int e = vertex[u].head; e; e = edge[e].next) {
			int v = edge[e].head;
			if (v == from) continue;
			DFS(v, t, u, cur);
		}
		return;
	}
}

int main() {
	std::cin >> n >> m >> c;
	for (int i = 1; i <= c; i++) std::cin >> P[i];
	for (int i = 1; i <= n; i++) std::cin >> w[i];
	for (int i = 1; i < n; i++) {
		std::cin >> u >> v;
		graph::addEdge(u, v);
		graph::addEdge(v, u);
	}
	std::cin >> q;
	for (int i = 1; i <= q; i++) {
		std::cin >> s >> t;
		graph::DFS(s, t, 0, 0);
	}
	return 0;
}

$m \le 300$ 的部分是可做的。

记 $f[u][p][x]$ 为以 $u$ 结点开始，路径长度为 $2$ 的 $p$ 次，从 $P_x$ 颗宝石开始取的答案。

把 $f$ 拆分为 $up$ 和 $dw$，然后在倍增求 LCA 的过程中不断更新左右两侧的 $x$ 即可。

先求一侧上行的结果，再求下行以该结果颗宝石开始取的答案。

树上倍增之前写吐了又累又吵又没时间就没写放了 25 分。

然后是链的情况，由于 $m$ 没有限制不能保证复杂度，没想出来。

D2T3｜滚榜｜0

这题一看就是退役选手出的。

读完题感觉不是很擅长统计方案数的题还是省选难度就没写。

赛后才注意到数据范围 $n \le 13$。

总结

• D1 通过了两题只能说是题简单+碰上了近似原题的运气，希望以后的正式考试都能有这样的好运。
• D1T3 写到一半发现自己根本就没想明白，写题之前还是要想清楚再写，不然会很耽误时间。
• D2 前两题暴力拿的还算中规中矩。
• D2T3 一看数据范围就应该想到状压，这告诉我们应该完整地通读题面。
• 发现了吗？T1T2拿到 30~70 分算是比较正常的，而到了 T3 的暴力就有些抓瞎了。至于其对策目前还没想好。