省选联考 2020 B 卷

• D1T1｜卡牌游戏｜100
• D1T2｜信号传递｜30
• D1T3｜冰火战士｜0
• D2T1｜幸运数字｜85
• D2T2｜消息传递｜30
• D2T3｜丁香之路
• 总结

D1T1｜卡牌游戏｜100

简单的贪心。

#include <iostream>
#include <algorithm>
#include <queue>

typedef long long lxl;
typedef std::priority_queue<int> pri;

const int maxN = 1e5;

int n;
lxl a[maxN + 10];
lxl sum;
lxl ans;

int main() {
	std::cin >> n;
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	for (int i = 1; i <= n; i++) {
		sum += a[i];
		if (sum > 0 && i > 1) ans += sum;
	}
	std::cout << ans << '\n';
	return 0;
}

D1T2｜信号传递｜30

$\mathcal O(m!)$ 暴搜。

#include <iostream>

const int maxN = 1e5;
const int maxM = 23;
const int inf = 1e9 + 10;

int n, m, k;
int s[maxN + 10];
int v[maxM + 10];
int p[maxM + 10];
int ans = inf;

void update() {
	int res = 0;
	for (int i = 1; i < n; i++) {
		int u = s[i];
		int v = s[i + 1];
		if (p[u] <= p[v]) {
			res += p[v] - p[u];
		} else {
			res += k * (p[u] + p[v]);
		}
	}
	ans = std::min(ans, res);
	return;
}

void DFS(int now) {
	if (now > m) {
		update();
		return;
	}
	for (int i = 1; i <= m; i++) {
		if (v[i]) continue;
		v[i] = true;
		p[i] = now;
		DFS(now + 1);
		v[i] = false;
	}
	return;
}

int main() {
	std::cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) std::cin >> s[i];
	DFS(1);
	std::cout << ans;
	return 0;
}

D1T3｜冰火战士｜0

不会。

D2T1｜幸运数字｜85

发现奖励条件可以转化为区间修改，考虑线段树。

尝试了模块化调试。

其实没有多次询问的话可以用差分的。

不知道哪挂了 15 分。

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

typedef std::vector<int> vic;

const int maxN = 1e5;

int n;
struct Node {
	int t;
	int L, R;
	int A, B;
	int w;
} node[maxN + 10];

vic raw;

int a[6 * maxN + 10];
int ans;

struct SegmentTree {
	struct Node {
		int val;
		int tag;
	} node[4 * 6 * maxN + 10];

	void MakeTag(int u, int w) {
		node[u].tag ^= w;
		return;
	}

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

	void PushDown(int u) {
		if (!node[u].tag) return;
		MakeTag(u * 2, node[u].tag);
		MakeTag(u * 2 + 1, node[u].tag);
		node[u].tag = 0;
		return;
	}

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

	//int a[6 * maxN + 10];

	/*
	void Build(int u, int l, int r) {
		//for (int i = l; i <= r; i++) a[i] = raw[i];
		return;
	}
	*/

	///*
	void Modify(int u, int l, int r, int s, int t, int w) {
		if (s > t) return;
		if (s <= l && r <= t) {
			MakeTag(u, w);
			return;
		}
		PushDown(u);
		int mid = (l + r) / 2;
		if (s <= mid) Modify(u * 2, l, mid, s, t, w);
		if (t >= mid + 1) Modify(u * 2 + 1, mid + 1, r, s, t, w);
		return;
	}
	//*/

	/*
	void Modify(int u, int l, int r, int s, int t, int w) {
		for (int i = s; i <= t; i++) a[i] ^= w;
		return;
	}
	*/

	///*
	void Query(int u, int l, int r) {
		if (l == r) {
			a[l] = node[u].val ^ node[u].tag;
			//printf("a[%d] = %d\n", l, a[l]);
			if (a[l] > a[ans]) ans = l;
			return;
		}
		PushDown(u);
		int mid = (l + r) / 2;
		//return std::max(Query(u * 2, l, mid), Query(u * 2 + 1, mid + 1, r));
		Query(u * 2, l, mid);
		Query(u * 2 + 1, mid + 1, r);
		return;
	}
	//*/

	/*
	int Query(int u, int l, int r) {
		int ret = 0;
		for (int i = l; i <= r; i++) ret = std::max(ret, a[i]);
		return ret;
	}
	*/
} SGT;

int main() {
	std::cin >> n;
	for (int i = 1; i <= n; i++) {
		std::cin >> node[i].t;
		if (node[i].t == 1) {
			std::cin >> node[i].L >> node[i].R >> node[i].w;
			raw.push_back(node[i].L - 1);
			raw.push_back(node[i].L);
			raw.push_back(node[i].L + 1);
			raw.push_back(node[i].R - 1);
			raw.push_back(node[i].R);
			raw.push_back(node[i].R + 1);
		} else if (node[i].t == 2) {
			std::cin >> node[i].A >> node[i].w;
			raw.push_back(node[i].A - 1);
			raw.push_back(node[i].A);
			raw.push_back(node[i].A + 1);
		} else if (node[i].t == 3) {
			std::cin >> node[i].B >> node[i].w;
			raw.push_back(node[i].B - 1);
			raw.push_back(node[i].B);
			raw.push_back(node[i].B + 1);
		}
	}
	std::sort(raw.begin(), raw.end());
	raw.erase(std::unique(raw.begin(), raw.end()), raw.end());
	//for (int i = 0; i < raw.size(); i++) printf("%5d", i); printf("\n");
	//for (int i = 0; i < raw.size(); i++) printf("%5d", raw[i]); printf("\n");
	for (int i = 1; i <= n; i++) {
		if (node[i].t == 1) {
			node[i].L = std::lower_bound(raw.begin(), raw.end(), node[i].L) - raw.begin();
			node[i].R = std::lower_bound(raw.begin(), raw.end(), node[i].R) - raw.begin();
		} else if (node[i].t == 2) {
			node[i].A = std::lower_bound(raw.begin(), raw.end(), node[i].A) - raw.begin();
		} else if (node[i].t == 3) {
			node[i].B = std::lower_bound(raw.begin(), raw.end(), node[i].B) - raw.begin();
		}
	}
	//SGT.Build(1, 0, raw.size() - 1);
	for (int i = 1; i <= n; i++) {
		if (node[i].t == 1) {
			SGT.Modify(1, 0, raw.size() - 1, node[i].L, node[i].R, node[i].w);
			//printf("modify [%d, %d], %d\n", node[i].L, node[i].R, node[i].w);
		} else if (node[i].t == 2) {
			SGT.Modify(1, 0, raw.size() - 1, node[i].A, node[i].A, node[i].w);
			//printf("modify [%d, %d], %d\n", node[i].A, node[i].A, node[i].w);
		} else if (node[i].t == 3) {
			SGT.Modify(1, 0, raw.size() - 1, 0, node[i].B - 1, node[i].w);
			SGT.Modify(1, 0, raw.size() - 1, node[i].B + 1, raw.size() - 1, node[i].w);
			//printf("modify [%d, %d], %d\n", 0, node[i].B - 1, node[i].w);
			//printf("modify [%d, %d], %d\n", node[i].B + 1, raw.size() - 1, node[i].w);
		}
	}
	//std::cout << SGT.Query(1, 0, raw.size() - 1);
	SGT.Query(1, 0, raw.size() - 1);
	std::cout << a[ans] << ' ' << raw[ans] << '\n';
	return 0;
}

D2T2｜消息传递｜30

$\mathcal O(qn)$ 搜索。

#include <iostream>

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

int T;
int n, m;
int a, b;
int x, k;

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

	struct Edge {
		int head;
		int next;
	} edge[maxN * 2 + 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;
	}

	int DFS(int u, int from, int k) {
		if (k == 0) return 1;
		int ret = 0;
		for (int e = vertex[u].head; e; e = edge[e].next) {
			int v = edge[e].head;
			if (v == from) continue;
			ret += DFS(v, u, k - 1);
		}
		return ret;
	}

	void clear() {
		for (int i = 1; i <= n; i++) vertex[i].head = 0;
		ecnt = 0;
		return;
	}
}

void mian() {
	std::cin >> n >> m;
	graph::clear();
	for (int i = 1; i < n; i++) {
		std::cin >> a >> b;
		graph::addEdge(a, b);
		graph::addEdge(b, a);
	}
	for (int i = 1; i <= m; i++) {
		std::cin >> x >> k;
		std::cout << graph::DFS(x, 0, k) << '\n';
	}
	return;
}

int main() {
	std::cin >> T;
	while (T--) mian();
	return 0;
}

D2T3｜丁香之路

没打暴力，但是有部分分。

#include <iostream>
#include <algorithm>

const int maxN = 2500;
const int maxM = 3123750;
const int inf = 1e9 + 10;

int abs(int x) {
	if (x < 0) x = - x;
	return x;
}

int n, m, s;
int u, v;

namespace M0 {
	void mian() {
		for (int i = 1; i <= n; i++) std::cout << abs(i - s) << ' ';
		return;
	}
}

namespace M1 {
	void mian() {
		for (int i = 1; i <= n; i++) {
			int ans = inf;
			int uv = abs(u - v);
			int su = abs(u - s);
			int sv = abs(v - s);
			int ui = abs(u - i);
			int vi = abs(v - i);
			ans = std::min(ans, su + uv + vi);
			ans = std::min(ans, sv + uv + ui);
			ans = std::min(ans, su + uv + uv + ui);
			ans = std::min(ans, sv + uv + uv + vi);
			std::cout << ans << ' ';
		}
	}
}

int main() {
	std::cin >> n >> m >> s;
	for (int i = 1; i <= m; i++) std::cin >> u >> v;
	if (m == 0) M0::mian();
	if (m == 1) M1::mian();
	return 0;
}

总结

• 模块化调试真的好用。
• 暴力与部分分还是值得多思考。