题目链接：Educational Codeforces Round 168 (Rated for Div. 2)
总结：题目较简单，但是发挥很一般。A，B题一直读假题，卡了半个小时；C题用char存int，难绷了。
A. Strong Password
tag：模拟
void solve() {
string s;
cin >> s;
for (int i = 1; i < s.size(); i ++) {
if (s[i] == s[i - 1]) {
cout << s.substr(0, i) << (s[i] == 'a' ? 'b' : 'a') << s.substr(i) << "\n";
return;
}
}
s += s.back() == 'a' ? 'b' : 'a';
cout << s << "\n";
}
B. Make Three Regions
tag：模拟
void solve() {
int n;
cin >> n;
string s[2];
cin >> s[0] >> s[1];
int ans = 0;
for (int i = 1; i < n - 1; i ++) {
for (int j = 0; j < 2; j ++) {
if (s[j][i] == '.' && s[j][i - 1] == '.' && s[j][i + 1] == '.' && s[j ^ 1][i] == '.' && s[j ^ 1][i - 1] == 'x' && s[j ^ 1][i + 1] == 'x') {
ans ++;
}
}
}
cout << ans << "\n";
}
C. Even Positions
tag：思维
Description：给定一个括号序列，奇数位用\(\_\)表示，对于一个括号序列的花费为\((xxxx)\)：\(r - l\)，你需要将其还原为花费最少的合法序列。
Solution：先考虑如何还原，我们定义\(x\)为当前\((\)的数量，\(y\)为\()\)的数量，当\(x <= y\)时，我们填\((\)，否则填\()\)。
- 考虑如何计算答案，使用\(stack\)，存储\((\)的下标，遇到\()\)时，弹出栈顶比计算答案。
void solve(){
cin >> n;
string s;
cin >> s;
int x = 0, y = 0;
s = "$" + s;
for (int i = 1; i <= n; i ++){
if (s[i] == '(')
x ++;
else if (s[i] == ')')
y ++;
else{
if (x <= y)
s[i] = '(', x ++;
else
s[i] = ')', y ++;
}
}
int ans = 0;
stack<int> st;
for (int i = 1; i <= n; i ++){
if (s[i] == '('){
st.ep(i);
continue;
}
else{
int t = st.top();
st.pop();
ans += (i - t);
}
}
cout << ans << endl;
}
D. Maximize the Root
tag：dfs
Description：给定一个由\(n\)个节点组成的树，每个点的权值为\(a_i\)。可以执行任意次一下操作：
- 选择一个有子节点的节点\(v\)，将\(v\)加\(1\)，其余所有子节点\(-1\)。但是所有值必须大于等于零。
- 求根节点的最大可能值。
Solution：模拟操作发现，对于非根节点的最大值
-
如果其值大于所有子节点，那么该值的贡献为子节点中的最小值。
-
如果该值小于子节点中的最小值，那么该值最大贡献为\((a_i + mi) / 2\)。
-
对于根节点，只需要加上其子节点的最小值即可。
void solve(){
cin >> n;
vector g(n + 1, vector<int>());
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++)
cin >> a[i];
for (int i = 2; i <= n; i ++){
int x;
cin >> x;
g[x].eb(i);
g[i].eb(x);
}
auto dfs = [&](auto dfs, int v, int u) -> int{
int res = a[v];
int t = -1;
for (auto i : g[v]){
if (i == u)
continue;
if (t == -1)
t = dfs(dfs, i, v);
else
t = min(t, dfs(dfs, i, v));
}
if (v == 1){
return a[1] += t;
}
if (t == -1)
return res;
if (t <= res)
return a[v] = t;
else{
return a[v] = (res + t) / 2;
}
};
cout << dfs(dfs, 1, -1) << endl;
}
E. Level Up
tag：二分 + 树状数组
Description：有一个长度为\(n\)的序列\(a\)，和整数\(x, k\)，初始时\(x == 1\)。
-
一次操作为：从\(1 -> n\)一次判断，每\(k\)次满足\(a_i >= x\)，\(x ++\)。
-
现在有\(q\)次询问，每次询问给定\(i, t\)，求当\(k == t\)，操作执行到\(i\)时，\(a_i\)是否大于等于\(x\)。
-
\(1 <= n, q <= 2*10^5, 1 <= a_i <= 2*10^5\)
Solution：没有修改操作，首先考虑预处理。
- 我们先考虑\(k\)与\(x\)的关系，显然\(k\)越小\(x\)越大，那么对于每一个\(a_i\)，我们可以二分得到一个最小的\(b_i\)，使得\(k == b_i\)时，\(a_i >= x\)。但是对每个数处理的时间复杂度为\(O(nlogn)\)，总的时间复杂度为\(O(n^2logn)\)
- 考虑如果优化check函数，对于每一个\(mid\)，我们需要知道前面\(i - 1\)个数执行的操作次数。并且我们已经得到\(b_1到b_{i - 1}\)，如果\(mid >= b_j\)，那么在第\(j\)个数就需要执行操作。因此我们使用树状数组维护前\(i - 1\)个怪物的\(b_i\)值。
- 对于每一个\(mid\)，我们只需要知道前面有多少个\(b_i\)小于等于\(mid\)即可。
int tr[N];
int lowbit(int x){
return x & -x;
}
void add(int x, int c){
for (int i = x; i <= n; i += lowbit(i))
tr[i] += c;
}
LL sum(int x){
LL res = 0;
for (int i = x; i > 0; i -= lowbit(i))
res += tr[i];
return res;
}
LL aks(int l, int r){
return sum(r) - sum(l - 1);
}
void solve(){
int q;
cin >> n >> q;
vector<int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i ++){
cin >> a[i];
}
for (int i = 1; i <= n; i ++){ // 初始化
int l = 0, r = i + 1;
while (l + 1 < r){
int mid = l + r >> 1;
if (sum(mid) / mid + 1 > a[i])
l = mid;
else
r = mid;
}
b[i] = r;
add(b[i], 1);
}
while (q --){
int i, x;
cin >> i >> x;
if (x < b[i])
cout << "NO\n";
else
cout << "YES\n";
}
}