Atcoder Beginner Contest 372
A
模拟即可。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
char ch;
while (cin >> ch) {
if (ch != '.') {
cout << ch;
}
}
}
int main() {
int T = 1;
// cin >> T;
while (T --) {
solve();
}
return 0;
}
B
三进制拆分即可。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int m;
void solve() {
cin >> m;
vector <int> v;
while (m) {
v.push_back(m % 3);
m /= 3;
}
vector <int> ans;
for (int i = 0; i < v.size(); i ++) {
for (int j = 0; j < v[i]; j ++) {
ans.push_back(i);
}
}
cout << ans.size() << "\n";
for (auto i : ans) cout << i << " ";
}
int main() {
int T = 1;
// cin >> T;
while (T --) {
solve();
}
return 0;
}
C
统计每个字符的贡献，每次增减。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5;
int n, q, ans;
string S;
void solve() {
cin >> n >> q >> S;
for (int i = 0; i < S.size() - 2; i ++) {
if (S[i] == 'A' && S[i + 1] == 'B' && S[i + 2] == 'C') {
ans ++;
}
}
while (q --) {
int i; char ch;
cin >> i >> ch, i --;
if (i < S.size() - 2) {
if (S[i] == 'A' && S[i + 1] == 'B' && S[i + 2] == 'C') {
ans --;
}
}
if (i < S.size() - 1 && i > 0) {
if (S[i - 1] == 'A' && S[i] == 'B' && S[i + 1] == 'C') {
ans --;
}
}
if (i < S.size() && i > 1) {
if (S[i - 2] == 'A' && S[i - 1] == 'B' && S[i] == 'C') {
ans --;
}
}
S[i] = ch;
if (i < S.size() - 2) {
if (S[i] == 'A' && S[i + 1] == 'B' && S[i + 2] == 'C') {
ans ++;
}
}
if (i < S.size() - 1 && i > 0) {
if (S[i - 1] == 'A' && S[i] == 'B' && S[i + 1] == 'C') {
ans ++;
}
}
if (i < S.size() && i > 1) {
if (S[i - 2] == 'A' && S[i - 1] == 'B' && S[i] == 'C') {
ans ++;
}
}
cout << ans << "\n";
}
}
int main() {
int T = 1;
// cin >> T;
while (T --) {
solve();
}
return 0;
}
D
单调栈模板。
从后往前扫描序列，维护单调递减栈。
当前答案即栈内元素个数。
如果当前数比栈顶大，栈顶就没有意义了，弹栈。
随后当前点入栈。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5;
int n, a[N];
int q[N], t;
void solve() {
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
}
vector <int> ans;
for (int i = n; i >= 1; i --) {
ans.push_back(t);
while (t && a[i] > a[q[t - 1]]) t --;
q[t ++] = i;
}
reverse(ans.begin(), ans.end());
for (auto i : ans) {
cout << i << " ";
}
}
int main() {
int T = 1;
// cin >> T;
while (T --) {
solve();
}
return 0;
}
E
原题：P3224 永无乡
用并查集维护连通性，平衡树维护权值。
合并时启发式合并。
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
const int N = 2e5 + 5;
__gnu_pbds::tree<int, __gnu_pbds::null_type, greater<int>,
__gnu_pbds::rb_tree_tag,
__gnu_pbds::tree_order_statistics_node_update> S[N];
int n;
int p[N], q[N], fa[N], Q;
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return ;
if (S[fx].size() > S[fy].size())
swap(fx, fy);
for (auto num : S[fx])
S[fy].insert(num);
S[fx].clear();
fa[fx] = fy;
}
int query(int x, int y) {
int id = find(x);
if (S[id].size() < y) return -1;
return q[*S[id].find_by_order(y - 1)];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> Q;
for (int i = 1; i <= n; i ++) {
p[i] = i;
q[p[i]] = i, fa[i] = i;
S[i].insert(p[i]);
}
int op; int x, y;
while (Q --) {
cin >> op >> x >> y;
if (op == 1) {
merge(x, y);
} else cout << query(x, y) << "\n";
}
return 0;
}
F
考虑把 \(2M\) 个连有附加边的点单独拎出来，称为特殊点。
把相邻特殊点之间通过普通点连接的路径缩成一条边，边权为走环的路径长度。
然后考虑动态规划。定义 \(dp_{i,j}\) 表示从 \(1\) 走到 \(i\) 用了 \(j\) 步的方案数。
\[dp_{v,j+w} \leftarrow dp_{v,j+w} + dp_{u,j} \]这样可求出以特殊点结尾的方案数。
考虑以普通点结尾的方案数。对于每个特殊点 \(u\)，只统计环上在 \(u\) 与 \(u\) 的下一个特殊点 \(v\) 间的普通点，这样可做到不重不漏。
对于普通点在 \(u,v\) 间的普通点 \(x\)，答案为 \(dp_{u,k-dis(u,x)}\)，
所以每个特殊点 \(u\) 对答案的贡献为：\(\sum_{i=0}^{dis(u,v)-1} dp_{u,k-i}\)。
时间复杂度：\(O(n+mk)\)。
实现时注意边界问题，边和特殊点需要去重。
为了实现方便，令 \(1\) 号点为特殊点。
#include <bits/stdc++.h>
#define int ll
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = tuple<int, int, int>;
const ll mod = 998244353;
const int N = 2e5 + 5;
const int M = 405;
vector <pii> E[N];
vector <int> t;
set <piii> e;
set <int> tt;
int n, m, k, id[N];
ll dp[M][N], ans;
int dis(int x, int y) {
return (y - x + n) % n;
}
void solve() {
cin >> n >> m >> k;
if (m == 0) {
cout << 1 << "\n";
return ;
}
for (int i = 1; i <= m; i ++) {
int u, v;
cin >> u >> v;
e.insert({u, v, 1});
tt.insert(u);
tt.insert(v); // 使用 set 去重
}
if (tt.find(1) == tt.end()) tt.insert(1);
for (auto i : tt) t.push_back(i);
for (int i = 0; i < t.size(); i ++) {
e.insert({t[i], t[(i + 1) % t.size()], dis(t[i], t[(i + 1) % t.size()])});
id[t[i]] = lower_bound(t.begin(), t.end(), t[i]) - t.begin();
// 离散化和相邻点连边
}
for (auto [u, v, w] : e) { // set 去重
E[u].push_back({v, w});
}
dp[id[1]][0] = 1;
for (int j = 0; j <= k; j ++) {
for (int i = 0; i < t.size(); i ++) {
for (auto [v, w] : E[t[i]]) {
if (j + w <= k) // dp 边界
(dp[id[v]][j + w] += dp[i][j]) %= mod;
}
}
}
for (int i = 0; i < t.size(); i ++) {
int d = dis(t[i], t[(i + 1) % t.size()]);
for (int j = 0; j < d && j <= k; j ++) { // 边界
(ans += dp[i][k - j]) %= mod;
}
}
cout << ans << "\n";
}
signed main() {
int T = 1;
// cin >> T;
while (T --) {
solve();
}
return 0;
}