https://ac.nowcoder.com/acm/contest/52244
A - A Xor B Problem
给定序列 \(a_i\)，求有多少数对 \((i, j)\) 满足 \(a_i\oplus a_j = 0\)，其中 \(\oplus\) 表示按位异或
\(a_i\oplus a_j = 0\) 等价于 \(a_i = a_j\)，对 \(a_i\) 排序，直接计算即可
点击查看代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#include <functional>
#define i64 long long
inline int read() {
bool sym = 0; int res = 0; char ch = getchar();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return sym ? -res : res;
}
int main() {
int n = read(), a[n + 1];
for (int i = 1; i <= n; i++) a[i] = read();
std::sort(a + 1, a + n + 1);
i64 res = 0, ans = 0;
for (int i = 1; i <= n; i++) {
res = 1;
while (a[i] == a[i + 1] && i <= n) i++, res++;
ans += res * (res - 1);
}
printf("%lld", ans + n);
return 0;
}
B - 吃苹果
给定 \(a_i, b_i\) 两个序列，对于每个 \(i\)，只能选择 \(a_i, b_i\) 中的一个数提供贡献，求刚好选择 \(k\) 个 \(b_i\) 中的数最大的贡献
如果全选 \(a_i\)，每把一个 \(a_i\) 换成 \(b_i\) 的贡献为 \(b_i - a_i\)，以 \(b_i - a_i\) 为关键字排序，取前 \(k\) 个转化即可
点击查看代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#include <functional>
#define i64 long long
inline int read() {
bool sym = 0; int res = 0; char ch = getchar();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return sym ? -res : res;
}
class DAT {
public:
int a, b;
};
int main() {
int n = read(), k = read(); DAT dat[n + 1];
for (int i = 1; i <= n; i++) dat[i] = (DAT){read(), read()};
auto cmp = [](DAT A, DAT B) -> bool {
return A.a - A.b < B.a - B.b;
};
std::sort(dat + 1, dat + n + 1, cmp);
int ans = 0;
for (int i = 1; i <= k; i++) ans += dat[i].b;
for (int i = k + 1; i <= n; i++) ans += dat[i].a;
printf("%d", ans);
return 0;
}
C - n皇后问题
\(n\) 次询问 \((x, y)\) 位置放置一个皇后是否会被其它皇后攻击，并放置此皇后
两条斜线即一次函数 \(x + y = A\) 和 \(x - y = B\)，维护每个函数是否已经被占领即可
点击查看代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#include <functional>
#define i64 long long
inline int read() {
bool sym = 0; int res = 0; char ch = getchar();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return sym ? -res : res;
}
const int N = 1e6;
bool vis_1[N + 1], vis_2[N + 1], vis_3[2 * N + 1], vis_4[2 * N + 1];
int main() {
int n = read(), m = read();
for (int i = 1; i <= m; i++) {
int x = read(), y = read();
if (vis_1[x]) {printf("No\n"); continue;}
if (vis_2[y]) {printf("No\n"); continue;}
if (vis_3[x + y]) {printf("No\n"); continue;}
if (vis_4[x - y + n]) {printf("No\n"); continue;}
vis_1[x] = vis_2[y] = vis_3[x + y] = vis_4[x - y + n] = 1;
printf("Yes\n");
}
return 0;
}
D - 分苹果
给定两条直线，求将 \(n\) 个苹果分成的四个区域各有多少苹果
判断每个点在每条线的下面还是上面即可
点击查看代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#include <functional>
#define i64 long long
inline i64 read() {
bool sym = 0; i64 res = 0; char ch = getchar();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return sym ? -res : res;
}
int main() {
i64 n = read(), a1, a2, b1, b2, c1, c2, a[4];
memset(a, 0, sizeof(a));
a1 = read(); b1 = read(); c1 = read();
a2 = read(); b2 = read(); c2 = read();
for (i64 i = 1; i <= n; i++) {
i64 x = read(), y = read();
if (a1 * x + b1 * y + c1 < 0) {
if (a2 * x + b2 * y + c2 < 0) a[0]++;
if (a2 * x + b2 * y + c2 > 0) a[1]++;
}
if (a1 * x + b1 * y + c1 > 0) {
if (a2 * x + b2 * y + c2 < 0) a[2]++;
if (a2 * x + b2 * y + c2 > 0) a[3]++;
}
}
std::sort(a, a + 4);
for (int i = 0; i < 4; i++) printf("%lld ", a[i]);
return 0;
}
E - 完形填空
每个题有四个选项，一共 \(4n\) 个题，给定每个题每个选项正确的概率，求当每个选项正好选择 \(n\) 次期望正确的题目个数
因为每个题的收益都是 \(1\)，则期望即概率
dp[i][A][B][C][D] 表示前 \(i\) 个题四个选项选择了一定次数的最高期望，转移枚举一下选择哪个选项即可
点击查看代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#include <functional>
#define i64 long long
inline int read() {
bool sym = 0; int res = 0; char ch = getchar();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return sym ? -res : res;
}
int main() {
int n = read(), a[n + 1][4];
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 4; j++) a[i][j] = read();
}
int f[2][26][26][26][26];
int m = n / 4;
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i++) {
for (int A = 0; A <= m; A++) {
for (int B = 0; B <= m; B++) {
for (int C = 0; C <= m; C++) {
for (int D = 0; D <= m; D++) {
if (A + B + C + D == i) {
if (A) f[i & 1][A][B][C][D] = std::max(f[i & 1][A][B][C][D], f[(i & 1) ^ 1][A - 1][B][C][D] + a[i][0]);
if (B) f[i & 1][A][B][C][D] = std::max(f[i & 1][A][B][C][D], f[(i & 1) ^ 1][A][B - 1][C][D] + a[i][1]);
if (C) f[i & 1][A][B][C][D] = std::max(f[i & 1][A][B][C][D], f[(i & 1) ^ 1][A][B][C - 1][D] + a[i][2]);
if (D) f[i & 1][A][B][C][D] = std::max(f[i & 1][A][B][C][D], f[(i & 1) ^ 1][A][B][C][D - 1] + a[i][3]);
}
}
}
}
}
}
printf("%d", f[0][m][m][m][m]);
return 0;
}
F - 坐火车
求经历点数量最小的情况下 \(1\) 到 \(n\) 的最短路
由于边权大于 \(1\)，所以直接跑最短路，第一关键字为边数，第二关键字为边权即可
也可以边权全设为 \(1\) 找出所有在 \(1\) 到 \(n\) 最短路上的边再次跑最短路
点击查看代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
#include <functional>
#define i64 long long
inline int read() {
bool sym = 0; int res = 0; char ch = getchar();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return sym ? -res : res;
}
const int inf = 2e9 + 7;
class EDGE {
public:
int u, v, nxt, dis; bool vis;
};
class NODE {
public:
int id, dis;
NODE(int a, int b) {id = a; dis = b;}
bool operator < (const NODE& a) const {return dis > a.dis;}
};
int main() {
int n = read(), m = read();
int head[n + 1], w[m + 1], cnt = 0; EDGE edge[m * 2 + 1];
memset(head, 0, sizeof(head));
for (int i = 1; i <= m; i++) {
int u = read(), v = read(); w[i] = read();
edge[++cnt] = (EDGE){u, v, head[u], 1, 1}; head[u] = cnt;
edge[++cnt] = (EDGE){v, u, head[v], 1, 1}; head[v] = cnt;
}
std::vector<int> dis1, disn, dis2;
auto dijkstra = [&](int s) -> std::vector<int> {
std::vector<int> dis(n + 1, inf);
bool done[n + 1]; memset(done, 0, sizeof(done));
std::priority_queue<NODE> q;
q.push(NODE(s, 0)); dis[s] = 0;
while (!q.empty()) {
int u = q.top().id; q.pop();
if (done[u]) continue; done[u] = 1;
for (int e = head[u]; e; e = edge[e].nxt) {
if (!edge[e].vis) continue;
int v = edge[e].v, t = edge[e].dis;
if (done[v]) continue;
if (dis[u] + t < dis[v]) {
dis[v] = dis[u] + t;
q.push(NODE(v, dis[v]));
}
}
}
return dis;
};
dis1 = dijkstra(1);
disn = dijkstra(n);
int D = dis1[n]; printf("%d ", D + 1);
// for (int i = 1; i <= n; i++) printf("%d ", dis1[i]); puts("");
// for (int i = 1; i <= n; i++) printf("%d ", disn[i]); puts("");
for (int u = 1; u <= n; u++) {
for (int e = head[u]; e; e = edge[e].nxt) {
int v = edge[e].v, t = edge[e].dis;
if (dis1[u] + t + disn[v] != D && disn[u] + t + dis1[v] != D) {
// printf("%d %d\n", u, v);
edge[e].vis = 0;
}
}
}
for (int i = 1; i <= m; i++) {
edge[i * 2].dis = w[i];
edge[i * 2 - 1].dis = w[i];
}
dis2 = dijkstra(1); printf("%d", dis2[n]);
return 0;
}
G - A Xor B Problem again
给定序列 \(a_i\)，求有多少数对 \((i, j)\) 满足 \(a_i\oplus a_j = a_i + b_j\)，其中 \(\oplus\) 表示按位异或
对于每个 \(a_i\)，存在贡献的数即为自己补集的子集，于是使用高维前缀和计算出来每个集合的贡献，直接计算即可
点击查看代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#include <functional>
#define i64 long long
inline int read() {
bool sym = 0; int res = 0; char ch = getchar();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return sym ? -res : res;
}
int main() {
int n = read(), m = 0, a[n + 1];
for (int i = 1; i <= n; i++) {
a[i] = read(); m = std::max(m, a[i]);
}
int vis[1 << 18];
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n; i++) vis[a[i]]++;
for (int j = 0; j < 17; j++) {
for (int i = 0; i < 1 << 17; i++) {
if (i >> j & 1) vis[i] += vis[i ^ 1 << j];
}
}
i64 ans = 0;
for (int i = 1; i <= n; i++) {
ans += vis[(1 << 17) - 1 ^ a[i]];
}
printf("%lld", ans);
return 0;
}
H - 摘苹果
对序列支持 \(3\) 种操作，区间对所有大于等于 \(10\) 的数乘 \(2/3\)，查询区间小于 \(100\) 的数的个数，查询区间和
经典线段树，维护一个区间最大值，一个区间和，区间小于 \(100\) 的数的个数，修改时查询当前区间最大值若小于 \(10\) 直接返回，这样每个位置只会被修改 \(log\) 次，总体复杂度 \(O(m\log n)\)
点击查看代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#include <functional>
#define i64 long long
inline int read() {
bool sym = 0; int res = 0; char ch = getchar();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return sym ? -res : res;
}
class SEG_TREE {
#define ls x << 1
#define rs x << 1 | 1
public:
std::vector<int> cnt, max, a;
std::vector<i64> sum;
void init(int n) {
a.resize(n + 1);
max.resize(n * 4 + 1);
cnt.resize(n * 4 + 1);
sum.resize(n * 4 + 1);
}
void pushup(int x) {
max[x] = std::max(max[ls], max[rs]);
sum[x] = sum[ls] + sum[rs];
cnt[x] = cnt[ls] + cnt[rs];
}
void build(int x, int l, int r) {
if (l == r) {
max[x] = a[l];
sum[x] = a[l];
cnt[x] = a[l] < 100;
return;
}
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(x);
}
void modify(int x, int l, int r, int L, int R) {
if (max[x] < 10) return;
if (l == r) {
max[x] -= (max[x] + 2) / 3;
sum[x] -= (sum[x] + 2) / 3;
cnt[x] = max[x] < 100;
return;
}
int mid = l + r >> 1;
if (mid >= L) modify(ls, l, mid, L, R);
if (mid + 1 <= R) modify(rs, mid + 1, r, L, R);
pushup(x);
}
int query2(int x, int l, int r, int L, int R) {
if (L <= l && r <= R) return cnt[x];
int mid = l + r >> 1, res = 0;
if (mid >= L) res += query2(ls, l, mid, L, R);
if (mid + 1 <= R) res += query2(rs, mid + 1, r, L, R);
return res;
}
i64 query3(int x, int l, int r, int L, int R) {
if (L <= l && r <= R) return sum[x];
int mid = l + r >> 1; i64 res = 0;
if (mid >= L) res += query3(ls, l, mid, L, R);
if (mid + 1 <= R) res += query3(rs, mid + 1, r, L, R);
return res;
}
};
int main() {
int n = read(), m = read();
SEG_TREE seg; seg.init(n);
for (int i = 1; i <= n; i++) seg.a[i] = read();
seg.build(1, 1, n);
for (int i = 1; i <= m; i++) {
int opt = read(), l = read(), r = read();
if (opt == 1) seg.modify(1, 1, n, l, r);
if (opt == 2) printf("%d\n", seg.query2(1, 1, n, l, r));
if (opt == 3) printf("%lld\n", seg.query3(1, 1, n, l, r));
}
return 0;
}