0822 复赛模拟
今天题挺符合胃口，打得挺舒服
T1
一眼爆搜 其实是道数学题，可以观察余数来写下代码，运用到的无非就是用 \(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
一眼堆
这道题如果每次询问就 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
考场上写了 100 多行的模拟，然后还没写过去……写到一半把自己绕晕了，然后寄掉
参考 题解 思路
不难写出代码：
#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
爆搜只能拿 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;
}