2023 潮阳实验学校 OI 集训 D2

0822 复赛模拟

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

T1

洛谷 P8295

(资料图)

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

#include 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 using namespace std;typedef long long ll;ll n, s, m, c;priority_queue 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 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());// 在应对第一次询问之前先保证数列有序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 多行的模拟，然后还没写过去……写到一半把自己绕晕了，然后寄掉

参考 题解 思路

不难写出代码：

#include 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 using namespace std;const int N = 2e5 + 50;const int MOD = 12;int n, ans;int c[N], t[N];vector 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;}

关键词：