Atcoder ABC 455
Info
2026.04.25 第八周 周六 链接
A 签到
B 枚举
void solve() {
int h, w;
cin >> h >> w;
vector<string> maze(h);
for (int i = 0; i < h; i ++) cin >> maze[i];
int h1, h2, w1, w2;
auto check = [&](int h1, int w1, int h2, int w2) {
for (int i = h1; i <= h2; i ++) {
for (int j = w1; j <= w2; j ++) {
if (maze[i][j] != maze[h1 + h2 - i][w1 + w2 - j]) return 0;
}
}
return 1;
};
i64 ans = 0;
for (h1 = 0; h1 < h; h1 ++) {
for (w1 = 0; w1 < w; w1 ++) {
for (h2 = h1; h2 < h; h2 ++) {
for (w2 = w1; w2 < w; w2 ++) {
if (check(h1, w1, h2, w2)) ans ++;
}
}
}
}
cout << ans << endl;
}
C
我也说不上来叫啥，把元素相同且和最大的按顺序删就好了，我写的有点丑
D 指针
原来abc还会考链表
也可以用没有路径压缩的并查集，只要每次合并时维护这个点下方是哪个点就好了
void solve() {
int n, q;
cin >> n >> q;
using pii = pair<int, int>;
int c, p;
struct node {
int next, prev;
int loc;
};
vector<node> arr(n + 1);
for (int i = 1; i <= n; i ++) {
arr[i].next = 0;
arr[i].prev = 0;
arr[i].loc = i;
}
while (q --) {
cin >> c >> p;
// c放到p上
// 指向的是在上面的
// p.next = c
arr[arr[c].prev].next = 0;
// 0.prev = ...
arr[p].next = c;
arr[c].prev = p;
arr[c].loc = arr[p].loc;
}
vector<int> ans(n + 1);
for (int i = 1; i <= n; i ++) {
if (arr[i].prev != 0) continue;
int cur_loc = arr[i].loc;
int cur_p = i;
ans[cur_loc] ++;
while (arr[cur_p].next != 0) {
ans[cur_loc] ++;
cur_p = arr[cur_p].next;
}
}
for (int i = 1; i <= n; i ++) cout << ans[i] << ' ';
cout << endl;
}
补题
E 容斥原理 前缀和
正难则反
统计不合法的情况AB相同、BC相同、CA相同，这其中包含ABC都相同，利用熔池原理删掉
\[res = Total - |S_{AB} \cup S_{BC} \cup S_{CA}|\]
其中
\[|S_{AB} \cup S_{BC} \cup S_{CA}| = |S_{AB}| + |S_{BC}| + |S{CA}| - 2*S_{ABC}\]
至于如何计算S，用到前缀和
void solve() {
int n;
string s;
cin >> n >> s;
auto count = [&](char x, char y) -> i64 {
vector<i64> freq(2 * n + 1); // 差值可能是负数，用n偏移
int diff = 0; // 当前x y 差值为0
i64 res = 0;
freq[n] = 1; //初始状态0
for (char c : s) {
if (c == x) diff ++;
if (c == y) diff --;
res += freq[diff + n]; // 之前出现过多少次【相同差值】，就新增多少个合法子串
//其实等价于加完了以后+=c(c - 1)/2
freq[diff + n] ++;
}
return res;
};
auto count_all = [&]() -> i64 {
map<pair<int, int>, i64> freq;
freq[{0, 0}] = 1;
int A = 0, B = 0, C = 0;
for (char c : s) {
if (c == 'A') A ++;
else if (c == 'B') B ++;
else C ++;
freq[{A - B, A - C}] ++;
}
i64 res = 0;
for (auto [_, c] : freq) {
res += c * (c - 1) / 2;
}
return res;
};
i64 total = (i64) n * (n + 1) / 2;
i64 ab = count('A', 'B');
i64 bc = count('B', 'C');
i64 ca = count('C', 'A');
i64 all = count_all();
cout << total - ab - bc - ca + 2 * all << '\n';
}