A. Escalator Conversations
Problem
Sol & Code
签到
#include <bits/stdc++.h>
typedef long long ll;
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int T, n, m, k, h;
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d %d %d %d", &n, &m, &k, &h);
int ans = 0;
for (int i = 1, x; i <= n; ++i) {
scanf("%d", &x);
if (x == h) continue;
int d = std::abs(x - h);
if (d % k == 0 && d / k < m) ++ans;
}
printf("%d\n", ans);
}
return 0;
}
B. Parity Sort
Problem
Sol & Code
只能奇数之间交换，偶数之间交换，就看奇偶数分别排序后在插回去是否有序。
#include <bits/stdc++.h>
#define N 200001
typedef long long ll;
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int T, n, a[N], b[N], c[N];
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
int cnt1 = 0, cnt2 = 0;
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
if (a[i] & 1) b[++cnt1] = a[i];
else c[++cnt2] = a[i];
}
std::sort(b + 1, b + cnt1 + 1);
std::sort(c + 1, c + cnt2 + 1);
bool okay = true;
int cnt1_ = 1, cnt2_ = 1;
for (int i = 1; i <= n; ++i) {
if (a[i] & 1) a[i] = b[cnt1_++];
else a[i] = c[cnt2_++];
if (a[i] < a[i - 1]) { okay = false; break; }
}
puts(okay ? "YES" : "NO");
}
return 0;
}
C. Tiles Comeback
Problem
Sol & Code
贪心，看首尾两个数是否出现了足够多次且不相交（抽象）。
#include <bits/stdc++.h>
#define N 200001
typedef long long ll;
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int T, n, k, a[N];
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
int p1 = 0, p2 = 0;
for (int i = 1, cnt = 0; i <= n; ++i) {
if (a[i] == a[1]) ++cnt;
if (cnt == k) { p1 = i; break; }
}
for (int i = n, cnt = 0; i >= 1; --i) {
if (a[i] == a[n]) ++cnt;
if (cnt == k) { p2 = i; break; }
}
if (a[1] == a[n]) {
if (!p1) puts("NO");
else puts("YES");
} else {
if (!p1 || !p2 || p1 >= p2) puts("NO");
else puts("YES");
}
}
return 0;
}
D. Prefix Permutation Sums
Problem
Sol & Code
看相邻两个数之间的差值，以及最大值是否是 \(1+2+\dots+n\)。
差值要求 \(1\sim n\) 每个数都出现一次。判断是否满足即可。
#include <bits/stdc++.h>
#define N 200001
typedef long long ll;
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
ll a[N], d[N];
int T, n, vis[N];
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) vis[i] = 0;
int cnt1 = 0, cnt2 = 0, ret = 0;
bool okay = true;
for (int i = 1; i < n; ++i) scanf("%lld", &a[i]);
for (int i = 1; i < n; ++i) {
d[i] = a[i] - a[i - 1];
if (d[i] > 2 * n - 1) { okay = false; break; }
if (d[i] > n) {
if (cnt1 || cnt2) { okay = false; break; }
++cnt1, ret = d[i];
} else {
if (vis[d[i]]) {
if (cnt2 || cnt1) { okay = false; break; }
++cnt2;
}
++vis[d[i]];
}
}
if (!okay) { puts("NO"); continue; }
else {
int res = 0, cnt = 0;
for (int i = 1; i <= n; ++i) {
if (!vis[i]) res += i, ++cnt;
}
if (cnt == 1 || vis[res] == 2 || res == ret) puts("YES");
else puts("NO");
}
}
return 0;
}
E. Nastya and Potions
Problem
Sol & Code
若 \(a\) 能和其他的混合成 \(b\) 就由 \(a\) 向 \(b\) 连线。
拓扑序 dp
#include <bits/stdc++.h>
#define N 200001
typedef long long ll;
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int cnt, head[N];
std::queue<int> q;
int T, n, k, f[N], du[N], res[N];
struct Edge {
int v, nxt;
}e[N << 1];
void add(int u, int v) {
e[++cnt].v = v, e[cnt].nxt = head[u], head[u] = cnt;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; ++i) scanf("%d", &f[i]), res[i] = 0, head[i] = 0;
for (int i = 1, x; i <= k; ++i) {
scanf("%d", &x);
f[x] = 0;
}
cnt = 0;
for (int i = 1, x; i <= n; ++i) {
scanf("%d", &x);
for (int j = 1, u; j <= x; ++j) {
scanf("%d", &u);
add(u, i);
++du[i];
}
}
for (int i = 1; i <= n; ++i) {
if (du[i] == 0) q.push(i);
}
while (!q.empty()) {
int u = q.front();
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
res[v] += f[u];
if (res[v] >= f[v]) res[v] = f[v];
--du[v];
if (du[v] == 0) {
f[v] = min(f[v], res[v]);
q.push(v);
}
}
q.pop();
}
for (int i = 1; i <= n; ++i) printf("%d ", f[i]);
puts("");
}
return 0;
}
F. Lisa and the Martians
Problem
Sol & Code
使 \((a_i\oplus x)\&(a_j \oplus x)\) 最大。
找两两之间不同的位的最高位最低的两个数。然后构造 \(x\) 使相同的位都为 \(1\) 即可。
#include <bits/stdc++.h>
#define N 200001
typedef long long ll;
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int T, n, k;
struct qwq {
int x, id;
friend bool operator < (qwq q1, qwq q2) {
return q1.x < q2.x;
}
}a[N];
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i].x);
a[i].id = i;
}
std::sort(a + 1, a + n + 1);
int ans, minn = 2147483647;
for (int i = 1; i < n; ++i) {
int flag = a[i].x ^ a[i + 1].x;
if (flag < minn) {
minn = flag;
ans = i;
}
}
printf("%d %d ", a[ans].id, a[ans + 1].id);
int x = 0;
for (int i = 0; i < k; ++i) {
if (minn & (1 << i)) continue;
else {
if (a[ans].x & (1 << i)) x += 0;
else x += (1 << i);
}
}
printf("%d\n", x);
}
return 0;
}