A/B
较为简单，略去。
C
预处理一下，然后前缀和就好了。
时间复杂度 \(O(n)\)。
D
用链表来记录字符串。
注意到每次能够消去意味着链表上连续三个节点拼起来是 ABC，然后从左到右一个个算就行了。
匹配到的话把三个节点一起删掉。
时间复杂度 \(O(n)\)。
E
注意到 \(N\le 8, M\le 28\)，树边为 \(N-1\le 7\) 条
所以直接 dfs，计算次数不超过 \(C_{28}^7=1184040\) 次。
F
发现两个变量之间的关系是确定的，启发我们使用带权并查集，然后每次尝试合并，如果可以就加入到集合里面。
具体的，如果 \(x\xrightarrow{+w} y,x\xrightarrow{+d_x}r_x,y\xrightarrow{+d_y}r_y\)，那么 \(r_x\xrightarrow{w+d_y-d_x}r_y\)。
G
乍一看 \(N\le 22\)，以为只能 \(O(2^N)\)，但是仔细一想，发现并不一定。
先稍微分析一下，显然有：
Split A...操作一次性全部做完就行了。因为先后操作没有关系。Choose ...操作，对于每一个 \(a_i\) 只要做一遍就行了。
所以相当于把 \(a\) 分成 \(i\) 段，每段和 \(b\) 中的某个连续段配对。
于是先想到 \(f_i\) 表示 \(a\) 的前 \(popcount(i)\) 个数和 \(b\) 中 \(i\) 二进制下为 1 的每一位 \(j\) 对应的 \(b_j\) 配对（例：\(5=(101)_2,j=\{0,2\}\)）。
然后考虑枚举这一连续段的长度。
所以有 \(f_i=\min_{j\subsetneq i}f_j+c\)，并且 \(j\) 还需要满足 \(j\text{ xor }i\) 的二进制表示下的 1 是连续的。
为了方便实现，可以枚举 1 连续段的长度和 \(b\) 中的起始位置。
最后输出一下计算次数，发现只要 \(2\times 10^8\) 次计算。
代码
A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10;
int a[N], n, s;
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> s;
int ans = 0;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
if(a[i] <= s) ans += a[i];
}
cout << ans;
return 0;
}
B
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool all(int x)
{
if(x < 10) return true;
int y = x % 10;
while(x)
{
if(x % 10 != y) return false;
x /= 10;
}
return true;
}
const int N = 105;
int a[N], n;
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n;
int ans = 0;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
for(int j = 1; j <= a[i]; j ++)
{
if(all(i) && all(j))
{
if(i % 10 == j % 10) ans ++;
}
}
}
cout << ans;
return 0;
}
C
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
int n, q, ans[N];
string s;
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> q >> s;
s = ' ' + s;
for(int i = 1; i < n; i ++)
{
ans[i] = ans[i - 1] + (s[i] == s[i + 1]);
}
while(q --)
{
int l, r;cin >> l >> r;
cout << ans[r - 1] - ans[l - 1] << "\n";
}
return 0;
}
D
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int pre[N], nxt[N];
string s;
int n;
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> s;
n = s.size();
s = ' ' + s;
for(int i = 1; i <= n; i ++)
pre[i] = i - 1, nxt[i] = i + 1;
nxt[n] = 0;nxt[0] = 1;
for(int i = 3; i <= n; i ++)
{
if(s[i] == 'C')
{
if(s[pre[i]] == 'B' && s[pre[pre[i]]] == 'A')
{
// cerr << i << endl;
pre[i + 1] = pre[pre[pre[i]]];
nxt[pre[pre[pre[i]]]] = i + 1;
}
}
}
// cerr << nxt[0];
if(!nxt[0] || nxt[0] > n) return 0;
int i = nxt[0];
string ans;
while(i && i <= n)
{
ans += s[i];
i = nxt[i];
}
cout << ans;
return 0;
}
E
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 10, M = 100;
int u[M], v[M], w[M];
int g[N], n, m, k, ans = 1e18;
int fa[N] = {};
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
void chk()
{
for(int i = 1; i <= n; i ++) fa[i] = i;
int s = 0;
for(int i = 1; i < n; i ++)
{
int uf = find(u[g[i]]), vf = find(v[g[i]]);
fa[uf] = vf;
(s += w[g[i]]) %= k;
}
for(int i = 1; i <= n; i ++)
if(find(i) != find(1)) return;
ans = min(ans, s);
}
void dfs(int l, int lv)
{
if(lv == n) return chk();
for(int i = l; i <= m; i ++)
{
g[lv] = i;
dfs(i + 1, lv + 1);
}
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> m >> k;
for(int i = 1; i <= m; i ++)
cin >> u[i] >> v[i] >> w[i];
dfs(1, 1);
cout << ans;
return 0;
}
F
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 2e5 + 5;
int fa[N], d[N];
int find(int x)
{
if(x == fa[x]) return x;
int u = fa[x];
fa[x] = find(fa[x]);
d[x] += d[u];
return fa[x];
}
bool merge(int x, int y, int w)
{
int fx = find(x), fy = find(y);
if(fx == fy)
{
if(d[x] != d[y] + w) return false;
return true;
}
fa[fx] = fy;
d[fx] = w + d[y] - d[x];
return true;
}
int n, q;
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> q;
for(int i = 1; i <= n; i ++) fa[i] = i;
for(int i = 1; i <= q; i ++)
{
int x, y, w;cin >> x >> y >> w;
if(merge(y, x, w))
cout << i << " " ;
}
return 0;
}
G
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 22;
int f[1 << N], n, c, a[N + 1], b[N + 1];
inline int aabs(int x){return x < 0 ? -x : x;}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
memset(f, 0x20, sizeof f);
// ll cnt = 0;
// for(int i = 1; i < (1 << 22); i ++)
// {
// int p = __builtin_popcount(i);
// for(int j = 1; j <= p; j ++)
// {
// for(int k = 0; k + j <= 22; k ++)
// {
// if(((i >> k) & ((1 << j) - 1)) == ((1 << j) - 1))
// cnt ++;
// }
// }
// }
// cout << cnt;
cin >> n >> c;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++) cin >> b[i];
f[0] = 0;
int cnt = 0;
for(int i = 1; i < (1 << n); i ++)
{
int p = __builtin_popcount(i);
for(int j = 1; j <= p; j ++)
{
for(int k = 0; k + j <= n; k ++)
{
if(((i >> k) & ((1 << j) - 1)) == ((1 << j) - 1))
{
int l = i ^ (((1 << j) - 1) << k);
int w = 0;
for(int o = 1; o <= j; o ++)
w += aabs(a[o + p - j] - b[o + k]), cnt ++;
f[i] = min(f[i], f[l] + c + w);
}
}
}
}
cout << f[(1 << n) - 1] - c;
cerr << cnt;
return 0;
}
后记：第一次 AK，激动。
标签：return,int,题解,ll,cin,long,fa,ABC328 From： https://www.cnblogs.com/adam01/p/17826421.html