A. Strong Password
注意到最大效果是在两个相同字符之间插入一个不同的，贡献为 3。
否则在一开始插入一个和首位不同的，贡献为 2。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
string s; cin >> s;
bool ok = 0;
for(int i = 0; i < s.size() - 1; i ++)
{
if(s[i] == s[i + 1])
{
ok = 1;
cout << s.substr(0, i + 1) + (char)((s[i] - 'a' + 1) % 26 + 'a') + s.substr(i + 1) << "\n";
break;
}
}
if(!ok) cout << (char)((s[0] - 'a' + 1) % 26 + 'a') << s << "\n";
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
int t;cin >> t;while(t --) solve();
return 0;
}
B. Make Three Regions
注意到如果要分割成三部分，那么这一块的三面一定都要是 .。
设新堵上的块为 o，图应该长这样：
.o.
?.?
因为三块不连通，所以 ? 应该是 x。
所以
图应该长这样（两种）：
.o. | x.x
x.x | .o.
因为保证原图联通，所以直接判断有几个像这样的图形就行了。
C. Even Positions
直接考虑贪心填右括号，不用担心右括号填多了出现 (())))(( 的情况。
因为最差也可在每个右括号前补一个左括号（奇数位都可以自己选择）。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
void solve()
{
int n; string s; cin >> n >> s;
int ans = 0;
stack<int> stk;
for(int i = 0; i < s.size(); i ++)
if(stk.size() && s[i] != '(') ans += i - stk.top(), stk.pop();
else stk.push(i);
cout << ans << "\n";
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
int t;cin >> t;while(t --) solve();
return 0;
}
上面用栈维护左括号位置，还可以拆贡献，只要维护未配对左括号个数即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
void solve()
{
int n; string s; cin >> n >> s;
int ans = 0;
int c = 0;
for(int i = 0; i < s.size(); i ++)
{
if(c && s[i] != '(') c --;
else c ++;
ans += c;
}
cout << ans << "\n";
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
int t;cin >> t;while(t --) solve();
return 0;
}
D. Maximize the Root
因为节点 \(u\) 做操作不会影响父节点，所以可以 dp，设 \(f(u)\) 表示 \(u\) 子树内最小值最大是多少。
设 \(g(u)=\min_{v\in sons(u)}f(v)\)
有 \(f(u)=\min(a_u,g(u))\)。
注意到当 \(a_u<g(u)\) 时， \(a_u\) 成为 \(f(u)\) 的瓶颈，于是可以通过操作增大 \(a_u\)，减小 \(g(u)\) 做到平衡。
所以可以让 \(a_u\) 和 \(g_u\) 都变成 \(\dfrac{g(u)+a_u}{2}\) 即可。
注意下取整一下。
注意到如果 \(a_u>g(u)\)，那么答案不会变大，\(f(u)=g(u)\)，特判一下。
所以有
\(f(u)=\min\left(a_u,\dfrac{\min_{v\in sons(u)}f(v)+a_u}{2}\right)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
ll n, f[N], a[N];
vector<int> e[N];
void dfs(int x)
{
if(e[x].empty()) return f[x] = a[x], void();
f[x] = 0;
ll mn = 2e9;
for(int i : e[x])
{
dfs(i);
mn = min(mn, f[i]);
}
if(x == 1) cout << a[1] + mn << "\n";
if(a[x] >= mn) f[x] = mn;
else f[x] = (mn + a[x]) / 2;
}
void solve()
{
cin >> n;
for(int i = 1; i <= n; i ++) e[i].clear();
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 2; i <= n; i ++)
{
int x; cin >> x;
e[x].push_back(i);
}
dfs(1);
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
int t;cin >> t;while(t --) solve();
return 0;
}
E. Level Up
法一：考虑主席树
注意到 \(\sum_{i=1}^n \frac 1i=O(n\log n)\)。
所以离线下来，对于每个 \(k\) 枚举等级增加的位置，也就是 \(O(n\log n)\) 个。
于是问题变成：求最小的 \(r\) 使得 \(\sum_{i=l}^r[a_i\geq lev]=k\)，这可以在 \(a_i\) 的大小这一维上可持久化一下，以 \(i\) 为下标，线段树上二分一下就可以了，复杂度 \(O(n\log^2n)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5, V = 2e5;
int rt[N];
int fdp;
struct sgt
{
int a[N << 6], ls[N << 6], rs[N << 6], idx;
inline void pu(int x) {a[x] = a[ls[x]] + a[rs[x]];}
int upd(int q, int l, int r, int x, int v)
{
int u = ++idx; a[u] = a[x], ls[u] = ls[x], rs[u] = rs[x];
if(l == r) return a[u] += v, u;
int mid = l + r >> 1;
if(mid >= q) ls[u] = upd(q, l, mid, ls[x], v);
else rs[u] = upd(q, mid + 1, r, rs[x], v);
pu(u); return u;
}
void fnd(int l, int r, int x, int k)
{
if(l == r) return fdp = l, void();
int mid = l + r >> 1;
if(a[ls[x]] >= k) return fnd(l, mid, ls[x], k);
else return fnd(mid + 1, r, rs[x], k - a[ls[x]]);
}
int qry(int ql, int qr, int l, int r, int x, int k)
{
if(ql > qr) return 0;
if(ql <= l && r <= qr)
{
if(a[x] < k) return a[x];
return fnd(l, r, x, k), k;
}
int mid = l + r >> 1, ans = 0;
if(mid >= ql) ans += qry(ql, qr, l, mid, ls[x], k);
if(ans < k && mid < qr) ans += qry(ql, qr, mid + 1, r, rs[x], k - ans);
return ans;
}
}t;
vector<pair<int, int>> q[N];
int n, ans[N], Q, a[N];
vector<int> v[N];
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> Q;
for(int i = 1; i <= n; i ++) cin >> a[i], v[a[i]].push_back(i);
for(int i = V; i >= 1; i --)
{
rt[i] = rt[i + 1];
for(int j : v[i])
rt[i] = t.upd(j, 1, n, rt[i], 1);
}
for(int i = 1; i <= Q; i ++)
{
int x, y; cin >> x >> y;
q[y].push_back({x, i});
}
for(int i = 1; i <= n; i ++)
{
if(q[i].empty()) continue;
vector<int> pos;
int lst = 0;
for(int j = 1; j <= n / i; j ++)
{
if(t.qry(lst + 1, n, 1, n, rt[j], i) < i) break;
pos.push_back(fdp);
lst = fdp;
}
for(auto [j, id] : q[i])
{
int lev = lower_bound(pos.begin(), pos.end(), j) - pos.begin() + 1;
ans[id] = a[j] >= lev;
}
}
for(int i = 1; i <= Q; i ++)
cout << (ans[i] ? "YES" : "NO") << "\n";
return 0;
}
法二：
咕咕咕。
F. Chips on a Line
注意到这很像斐波那契数列，又注意到 \(i\to i-1,i-2\)，我们发现，一个位于 \(i\) 上的棋子等价于 \(fib_i\) 个位于 \(1\) 或 \(2\) 的棋子。（不断使用这个操作，反过来，可以使用逆操作）。
设 \(i\) 上有 \(c_i\) 个棋子，设状态 \(S=\sum_{i=1}^x c_i\times fib_i\)。
这个性质让我们发现，不同状态之间是不能转化的，相同状态之间是可以随便转化的，于是可以处理出每个 \(S\) 的代价。考虑 dp。
设 \(f(i)\) 为 \(S=i\) 时的代价。
于是有 \(f(i)=\min_{j=1}f(i-fib_j)+1\)。
然后考虑计数有多少个状态为 \(S\) 的方案，考虑背包，设 \(g(i,j,k)\) 表示 dp 到 \(fib_i\)，填了 \(j\) 个棋子，状态为 \(k\) 的方案数，有：
\(g(i,j,k) = \sum_{c=0}g(i-1,j-c,k-c\times fib_i)\)。
复杂度不太对。
注意到这是一个完全背包，于是改写成：
\(g(i,j,k)=g(i,j-1,k-fib_i)+g(i-1,j,k)\)。
空间开不下。
滚动数组优化一下就好了。
答案就是 \(ans=\sum_{i=0} [f(i)=m]g(x,n,i)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005, M = N * 60, p = 998244353;
int a[40];
int f[M], n, x, m;
int g[N][M];
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> x >> m;
a[1] = a[2] = 1;
for(int i = 3; i < 40; i ++) a[i] = a[i - 1] + a[i - 2];
memset(f, 0x3f, sizeof f);
f[0] = 0;
for(int i = 1; i < M; i ++)
for(int j = 0; j < 40; j ++)
if(i >= a[j]) f[i] = min(f[i], f[i - a[j]] + 1);
g[0][0] = 1;
for(int i = 1; i <= x; i ++)
{
for(int j = 1; j <= n; j ++)
for(int k = a[i]; k <= n * 55; k ++)
g[j][k] = (g[j][k] + g[j - 1][k - a[i]]) % p;
}
ll ans = 0;
for(int i = 1; i < M; i ++)
ans += (f[i] == m) * g[n][i];
cout << ans % p;
return 0;
}