题目链接：
https://pintia.cn/problem-sets/1571150153619189760
A.01 Sequence
题意：
给定一个 01 字符环，可以选择一个 1 然后删除它及周围的两个数，如果通过若干次操作后可以删除整个字符环，那么这个字符环就是 \(good\) 的。
现在进行 \(q\) 次询问，每次告诉 \(l\) 和 \(r\)，问最少进行几次翻转操作（将 0 改为 1）可以使 \([l, r]\) 区间的字符环变成 \(good\) 的。
思路：
要删除 \([l, r]\) 区间的字符串，至少需要 \(\lceil \frac{r - l + 1}{3} \rceil\) 个有效 1。因为一个 1 可以删除周围两个字符，对于长度为 \(len\) 的连续 1，有效 1 就有 \(\lceil \frac{len}{2} \rceil\) 个。
当这个区间中有效 1 的数量不够时，说明 0 的数量太多了，且它们是连续的，那么每改变一个 1 就可以让有效 1 的数量加 1。
对于一个区间，因为是一个环，所以首尾的 1 是相连的，等价于将尾部的 1 放到开头，可以通过预处理求得某一位的前缀连续 1 和后缀连续 1，这样子就可以求出首尾的 1 的有效 1。
接着求去掉了首尾 1 的剩余区间中的有效 1 的个数，两个相连的 1，只有一个是有效 1，所以对于一个连续的 1，第一个 1 就是有效 1，第二个不是，第三个是...即前缀 1 为奇数个的时候，有效 1 的数量加一。
代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int n, q;
cin >> n >> q;
string s;
cin >> s;
s = '-' + s;
vector <int> sum(n + 2), pre(n + 2), suf(n + 2);
for (int i = 1; i <= n; i ++ )
if (s[i] == '1')
pre[i] = pre[i - 1] + 1;
for (int i = n; i >= 1; i -- )
if (s[i] == '1')
suf[i] = suf[i + 1] + 1;
for (int i = 1; i <= n; i ++ )
sum[i] += sum[i - 1] + (pre[i] & 1);
auto cal = [&](int L, int R){
int p = L + suf[L], q = R - pre[R];
if (p >= q) return R - L;
else return (suf[L] + pre[R] + 1) / 2 + sum[q] - sum[p - 1];
};
for (int i = 1; i <= q; i ++ ){
int L, R;
cin >> L >> R;
cout << max(0, (R - L + 1) / 3 - cal(L, R)) << "\n";
}
return 0;
}
C.Delete the Tree
题意：
给定一棵树，有两个操作：
1.删除一个点及所有连着它的边。
2.删除一个度为 2 的点，并将与它连接的两个点用新的一条边连接起来。
问最少执行多少次操作 1 能删除整棵树。
思路：
答案就是叶子节点的数量，记得特判 \(n == 1\) 的情况。
代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
void solve(){
int n;
cin >> n;
vector <int> deg(n + 1);
for (int i = 0; i < n - 1; i ++ ){
int u, v;
cin >> u >> v;
deg[u] ++ ;
deg[v] ++ ;
}
if (n == 1){
cout << "1\n";
return;
}
int ans = 0;
for (int i = 1; i <= n; i ++ )
ans += (deg[i] == 1);
cout << ans << "\n";
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int T = 1;
cin >> T;
while(T -- ){
solve();
}
return 0;
}
D Find the Number
题意：
一个数二进制状态下，1 的数量等于后导 0 的数量，那么它就是幸运数字，\(q\) 次询问，每次询问输出一个在 \([l, r]\) 中的幸运数字，若没有，输出 -1。
思路：
因为所有满足条件的数只有 5e5 个左右，所以暴力跑出所有答案然后二分查找即可。
代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int INF = 1e9;
vector<int> num;
void init(){
for (LL i = 1; i <= (INF >> 2); i += 2)
if ((i << __builtin_popcount(i)) <= INF)
num.push_back(i << __builtin_popcount(i));
sort(num.begin(), num.end());
}
void solve(){
int l, r;
cin >> l >> r;
auto it = lower_bound(num.begin(), num.end(), l);
if (it != num.end() and *it <= r) cout << *it << "\n";
else cout << "-1\n";
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
init();
int T;
cin >> T;
while(T -- ){
solve();
}
return 0;
}
G.Read the Documentation
题意：
有一个游戏持续 \(n\) 秒，第 \(i\) 秒阅读会获得 \(a_i\) 分，连续阅读的第 1，2，3，4 秒会导致裁判怒气值分别增加 \(x_1, x_2, x_3, x_4\) 点，当连续阅读 5 秒或者总的怒气值超过 \(T\) 时直接结束游戏，同时得分归 0，问最多能获得多少分。
思路：
因为读的情况只有四种，所以定义 \(dp[i][j1][j2][j3][j4]\) 表示第 \(i\) 秒，读了 \(j1\) 个 1 秒，\(j2\) 个 2 秒...最多能获得多少分。
容易转移，但是整个数组大小为 101 * 51 * 35 * 26 * 21 会超限，可以通过滚动数组压缩。
代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL n, T, x[5], a[102], dp[6][51][35][26][21], ans;
signed main(){
ios::sync_with_stdio(false);cin.tie(0);
cin >> n >> T;
for (int i = 1; i <= 4; i ++ ){
cin >> x[i];
x[i] += x[i - 1];
}
for (int i = 1; i <= n; i ++ ){
cin >> a[i];
a[i] += a[i - 1];
}
for (int i = 1; i <= n; i ++ ){
for (int j1 = 0; j1 <= (n + 1) / 2; j1 ++ ){
for (int j2 = 0; j2 <= (n + 2) / 3; j2 ++ ){
for (int j3 = 0; j3 <= (n + 3) / 4; j3 ++ ){
for (int j4 = 0; j4 <= (n + 4) / 5; j4 ++ ){
if (j1 * x[1] + j2 * x[2] + j3 * x[3] + j4 * x[4] > T) break;
LL res = dp[(i + 5) % 6][j1][j2][j3][j4];
if (j1 >= 1 && i >= 1) res = max(res, dp[(i + 4) % 6][j1 - 1][j2][j3][j4] + a[i] - a[i - 1]);
if (j2 >= 1 && i >= 2) res = max(res, dp[(i + 3) % 6][j1][j2 - 1][j3][j4] + a[i] - a[i - 2]);
if (j3 >= 1 && i >= 3) res = max(res, dp[(i + 2) % 6][j1][j2][j3 - 1][j4] + a[i] - a[i - 3]);
if (j4 >= 1 && i >= 4) res = max(res, dp[(i + 1) % 6][j1][j2][j3][j4 - 1] + a[i] - a[i - 4]);
dp[i % 6][j1][j2][j3][j4] = res;
ans = max(ans, dp[i % 6][j1][j2][j3][j4]);
}
}
}
}
}
cout << ans << "\n";
return 0;
}
H.Step Debugging
题意：
给定一个新的语法，求 "library" 执行的次数，答案对 20220911 取模，保证语法正确。
思路：
本质就是一个栈操作。
当出现 "library" 时，栈顶元素 + 1。
出现 "repeat" 时，要新压入一个元素 0。
出现数字时，栈顶元素要乘上这个数字。
出现 "times"，要将栈顶元素加到倒数第二个元素上。
代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mod = 20220911;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
string s;
getline(cin, s);
int n = s.size();
vector <string> a;
for (int i = 0; i < n; i ++ ){
if (s[i] == ' ') continue;
string t = "";
for (; i < n && s[i] != ' '; i ++ )
t = t + s[i];
a.push_back(t);
}
int m = a.size();
vector <LL> b;
b.push_back(0);
for (int i = 0; i < m; i ++ ){
if (a[i] == "library"){
b.back() = (b.back() + 1) % mod;
}
else if (a[i] == "repeat"){
b.push_back(0);
}
else if ('0' <= a[i][0] && a[i][0] <= '9'){
b.back() = b.back() * stoi(a[i]) % mod;
}
else if (a[i] == "times"){
LL t = b.back();
b.pop_back();
b.back() = (b.back() + t) % mod;
}
}
cout << b.back() << "\n";
return 0;
}
L.LCS-like Problem
题意：
给定两个字符串 \(s\) 和 \(t\)，找到 \(s\) 的一个最长子序列 \(s'\)，满足它和 \(t\) 的任意公共子序列长度小于等于 1，输出 \(s'\) 的长度即可。
思路：
首先长度要小于等于 1，那么如果在 \(t\) 中，某个字母 \(x_1\) 后面出现了字母 \(x_2\)，那么在 \(s'\) 中就不会出现这种情况。可以通过一个从右至左的预处理求出某个字母后面不能出现哪些字母，这个数组记为 \(ban\)，\(ban[i][j]\) 表示 \(i\) 后面不能出现 \(j\)。
假设当前枚举到 \(s\) 的第 \(i\) 位，已经求出来了一个符合条件的字符串 \(s'\)，显然，只有 \(s'\) 的最后一位可以决定 \(s_i\) 能不能出现接在 \(s'\) 后面。
设 \(s'\) 现在为 \(ab\)，第 \(i\) 位的字母是 \(c\)，如果 \(ban[b][c]\) 是 false 的，那么 \(c\) 就可以接在当前字符串后面，且 \(ban[a][c]\) 肯定是 false 的（因为刚开始处理的时候是从右至左的，如果 \(ban[b][c] = true\)，\(a\) 在 \(b\) 前面，所以 \(ban[a][c]\) 肯定也是 \(true\) 的）。
所以定义 \(dp[i][j]\) 表示枚举了 \(s\) 的前 \(i\) 位，最后一个字母是 \(j\) 时满足条件的字符串的最长长度。
如果第 \(i\) 位字母在 \(t\) 没出现过，那么答案直接 + 1。
如果出现过，记当前符合条件的字符串的最后一位是 \(u\)，\(s\) 的第 \(i\) 位的字母是 \(v\)，如果 \(ban[u][v]\) 是 \(false\) 的，说明 \(v\) 可以接在字符串后面，答案为 \(max(dp[i - 1][v], dp[i - 1][u] + 1)\)。
代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
string s, t;
cin >> s >> t;
int n = s.size(), m = t.size();
vector < vector<int> > ban(26, vector<int>(26));
vector <bool> vis(26);
for (int i = m - 1; i >= 0; i -- ){
for (int j = 0; j < 26; j ++ )
if (vis[j])
ban[t[i] - 'a'][j] = 1;
vis[t[i] - 'a'] = true;
}
s = '-' + s;
vector < vector<int> > dp(n + 1, vector<int>(26));
for (int i = 1; i <= n; i ++ ){
if (!vis[s[i] - 'a']){
for (int j = 0; j < 26; j ++ )
dp[i][j] = dp[i - 1][j] + 1;
}
else{
for (int j = 0; j < 26; j ++ ){
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
if (!ban[j][s[i] - 'a'])
dp[i][s[i] - 'a'] = max(dp[i][s[i] - 'a'], dp[i - 1][j] + 1);
}
}
}
int ans = 0;
for (int i = 0; i < 26; i ++ )
ans = max(ans, dp[n][i]);
cout << ans << "\n";
return 0;
}