0822 复赛模拟

今天题挺符合胃口，打得挺舒服

T1

洛谷 P8295

一眼爆搜 其实是道数学题，可以观察余数来写下代码，运用到的无非就是用 \(4 \times 5\) 转 \(5 \times 4\) 之类的，处理时注意代码细节

#include <bits/stdc++.h>

using namespace std;

int n, ans;
int x, y, m;

int main() {
	scanf("%d", &n);
	x = n / 4;
	y = n % 4;
	m = x - y;
	if (m < 0) {
		ans = 0;
	} else {
		ans = m / 5 + 1;
	}
	printf("%d\n", ans);
	return 0;
}

T2

洛谷 P9321

一眼堆

这道题如果每次询问就 sort 一遍的话只能拿 33 分，但是如果和我一样使用 priority_queue 的话，那么最终能拿到 77 分，T 掉两个大点

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll n, s, m, c;

priority_queue<ll> h, q;

inline ll read() {
    register ll x = 0, f = 1;
    register char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

inline void write(ll x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

int main() {
	n = read(), s = read();
	for (register ll i = 1, in; i <= n; i++) {
		in = read();
		h.push(in);
	}

	while (s--) {
		m = read(), c = read();
	
		for (register ll i = 1; i <= c; i++) {
			q.push(h.top() - m);
			h.pop();
		}
		
		for (register ll i = 1; i <= c; i++) {
			h.push(q.top());
			q.pop();
		}
	}

	for (register ll i = 1; i <= n; i++) {
		write(h.top());
		putchar(' ');
		h.pop();
	}
	puts("");

	return 0;
}

由于本人不会 STL 卡常，所以老老实实按照教练给的题解改打归并来减少常数

虽然没学过归并，但是 打打代码 后发现还是挺好懂的

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 50;

int n, s, m, c;
int a[N], t[N];

int main() {
	scanf("%d %d", &n, &s);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	
	sort(a + 1, a + n + 1, greater<int>());		// 在应对第一次询问之前先保证数列有序

	while (s--) {
		scanf("%d %d", &m, &c);
		for (int i = 1; i <= c; i++)	// 应对脚本
			a[i] -= m;

		int i = 1, j = c + 1, k = 0;
		while (i <= c && j <= n) {			// 移动双指针
			if (a[i] >= a[j]) t[++k] = a[i++];
			else t[++k] = a[j++];
		}
		while (i <= c) t[++k] = a[i++];
		while (j <= n) t[++k] = a[j++];
		
		for (int i = 1; i <= n; i++)		// 合并更改
			a[i] = t[i];
	}
	
	for (int i = 1; i <= n; i++)
		printf("%d ", a[i]);
	printf("\n");
}

T3

洛谷 P6359

考场上写了 100 多行的模拟，然后还没写过去……写到一半把自己绕晕了，然后寄掉

参考 题解 思路，易得：

• 可以用户需求和电脑店提供的代码存在一个结构体数组里
• 卖出电脑时，按照重要程度买进数量 \(\geq\) 订单需求的核心数和时钟频率 \(\geq\) 订单需求或价格来从大到小排序
• 排序时，买的电脑放前面
• 显然 01 背包

不难写出代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int intN = 2e5 + 50;

ll n, m, cnt, ans;
ll f[intN];

struct node {
	ll c, f, v;
} s[intN];

bool cmp(node a, node b) {
	if (a.f == b.f) return a.v < b.v;
	return a.f > b.f;
}

int main() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld %lld %lld", &s[i].c, &s[i].f, &s[i].v);
		s[i].v  = -s[i].v;
	}
	scanf("%lld", &m);
	for (int i = n + 1; i <= n + m; i++)
		scanf("%lld %lld %lld", &s[i].c, &s[i].f, &s[i].v);
	sort(s + 1, s + n + m + 1, cmp);
	
	memset(f, 128, sizeof(f));

	f[0] = 0;
	for (int i = 1; i <= n + m; i++) {
		if (s[i].v < 0) {
			for (int j = cnt; j >= 0; j--)
				f[j + s[i].c] = max(f[j + s[i].c], f[j] + s[i].v);
			cnt += s[i].c;
		} else {
			for (int j = 0; j <= cnt - s[i].c; j++)
				f[j] = max(f[j], f[j + s[i].c] + s[i].v);
		}
	}
	
	for (int j = 0; j <= cnt; j++)
		ans = max(ans, f[j]);
	printf("%lld\n", ans);
	return 0;
}

T4

洛谷 P6150

爆搜只能拿 30 分，所以需要 魔法

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 50;
const int MOD = 12;

int n, ans;
int c[N], t[N];

vector<int> f[N];

void dfs(int u, int x) {
	for (int i = 0; i < f[u].size(); i++) {
		int v = f[u][i];
		if (v == x) continue;
		dfs(v, u);
		t[u] = (t[u] - t[v] + 12) % MOD;
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &c[i]);
		c[i] %= MOD;
	}
	
	for (int i = 0, u, v; i < n - 1; i++) {
		scanf("%d %d", &u, &v);
		f[u].push_back(v);
		f[v].push_back(u);
	}
	
	for (int i = 1; i <= n; i++) {
		memcpy(t, c, sizeof(t));
		dfs(i, 0);
		if (t[i] == 0 || t[i] == 1)
			ans++;
	}
	
	printf("%d\n", ans);
	return 0;
}