Solution - Educational Codeforces Round 174 (Rated for Div. 2)

Posted on 2025-02-24 Edited on 2026-03-23

Educational Codeforces Round 174 (Rated for Div. 2)

A Was there an Array?

Solution

观察发现不存在 $101$ ，排除 $101$ 即可。

时间复杂度 $O(n)$ 。

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 1;
int n, B[N];
signed main(){
    int t; cin >> t;
    while (t--){
        cin >> n;
        for (int i = 2; i < n; ++i) cin >> B[i];
        int flag = 1;
        for (int i = 3; i < n - 1; ++i){
            if (B[i] == 0 && B[i - 1] && B[i + 1]){
                puts("NO");
                flag = 0;
                break;
            }
        }
        if (flag) puts("YES");
    }
    return 0;
}

B Set of Strangers

Solution

首先发现给全图的一种颜色染色最多只需要两步。如果同种颜色存在相邻的，则起码需要两步，故需要恰好两步；否则可以一步染色。

然后最后要染成同一种颜色，故将所有颜色都直接染成这种颜色即是最优解。

注意到有一种颜色本身就是目标颜色，那么我们尽量找染色步数多的一种当作目标颜色。

时间复杂度 $O(nm)$ 。

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 701;
int n, m, A[N][N], col[N * N];
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
signed main(){
    int t; cin >> t;
    while (t--){
        cin >> n >> m;
        for (int i = 1; i <= n * m; ++i) col[i] = 0;
        for (int i = 1; i <= n; ++i){
            for (int j = 1; j <= m; ++j){
                cin >> A[i][j];
                col[A[i][j]] = 1;
            }
        }
        for (int i = 1; i <= n; ++i){
            for (int j = 1; j <= m; ++j){
                for (int k = 0; k < 4; ++k){
                    int nx = i + dx[k], ny = j + dy[k];
                    if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && A[nx][ny] == A[i][j]){
                        col[A[i][j]] = 2;
                    }
                }
            }
        }
        int ans = 0, maxn = 0;
        for (int i = 1; i <= n * m; ++i){
            ans += col[i];
            maxn = max(maxn, col[i]);
        }
        ans -= maxn;
        cout << ans << endl;
    }
    return 0;
}

C Beautiful Sequence

Solution

注意到长度最少为 $3$ ，所以最左边数一定是 $1$ 且最右边一定是 $3$ ，那么也确定了中间一定全部是 $2$ 。题目转化为找形如 $122\cdots 23$ 子序列数量。

枚举所有 $1$ ，再枚举所有这个数后面的 $3$ ，假设中间夹了 $x$ 个 $2$ ，则贡献为 $2^x - 1$ 。中间有多少 $2$ 可以前缀和 $O(1)$ 得到，故复杂度 $O(n^2)$ ，不能通过此题。

考虑优化。设 $S_i$ 为 $[1, i]$ 内 $2$ 的个数，假设枚举到 $i$ 下标的 $1$ 和 $j$ 下标的 $3$ ，则答案贡献为 $2^{S_j - S_i} - 1$ ，故 $i$ 下标的 $1$ 的贡献为

\begin{aligned} &\sum_{j > i, a_j = 3} (2^{S_j - S_i} - 1)\\ =&\sum_{j > i, a_j = 3} \frac{2^{S_j}}{2^{S_i}} - \sum_{j > i, a_j = 3} 1\\ =&\frac{1}{2^{S_i}}\sum_{j > i, a_j = 3} 2^{S_j} - \sum_{j > i, a_j = 3} 1 \end{aligned}

而 $\sum_{j > i, a_j = 3} 2^{S_j}$ 和 $\sum_{j > i, a_j = 3} 1$ 都可以用前缀和维护， $\frac{1}{2^{S_i}}$ 和 $j$ 无关，故可以快速获得每个 $i$ 的贡献。

枚举所有 $i$ ，预处理 $2$ 的幂次及其逆元，时间复杂度 $O(n)$ 。代码展示的方法是 $O(n\log n)$ 的。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 1, MOD = 998244353;
int n, A[N], sum2[N], one[N], idx1, three[N], idx3, sum3[N], num3[N];
int jc[N], inv2;
inline int fpow(int a, int b){
    int x = 1;
    while (b){
        if (b & 1) x = (LL) x * a % MOD;
        a = (LL) a * a % MOD;
        b >>= 1;
    }
    return x;
}
signed main(){//printf("%d\n", (LL)inv2 * fpow(2, 1) % MOD);
    int t; cin >> t;
    inv2 = fpow(2, MOD - 2);
    
    jc[0] = 1;
    for (int i = 1; i < N; ++i) jc[i] = (LL)jc[i - 1] * 2 % MOD;
    while (t--){
        cin >> n;
        idx1 = idx3 = 0;
        for (int i = 1; i <= n; ++i){
            cin >> A[i];
            sum2[i] = sum2[i - 1] + (A[i] == 2);
            if (A[i] == 1) one[++idx1] = i;
            if (A[i] == 3) three[++idx3] = i;
        }
        for (int i = 1; i <= n; ++i){
            sum3[i] = (sum3[i - 1] + (A[i] == 3 ? jc[sum2[i]] : 0)) % MOD;
            num3[i] = num3[i - 1] + (A[i] == 3);
            // printf("sum3 %d = %d\n", i, sum3[i]);
        }
        int ans = 0;
        for (int i = 1; i <= idx1; ++i){
            int now = one[i];
            int sum23 = (sum3[n] - sum3[now] + MOD) % MOD;
            // printf("sum23 = %d\n", sum23);
            sum23 = (LL)sum23 * fpow(inv2, sum2[now]) % MOD;
            // printf("inv2 = %d, sum2[now] = %d",inv2, sum2[now]);
            // printf("sum2333 = %d\n", sum23);
            int del = (sum23 - (num3[n] - num3[now]) + MOD) % MOD;
            // printf("del = %d\n",del);
            ans = (ans + del) % MOD;
            // ans = (ans + ((LL)jc[sum2[n] - sum2[now]] - sum2[n] + sum2[now] - 1 + MOD) % MOD) % MOD; // 1 2
        }
        // for (int i = 1; i <= idx3; ++i){
        //     int now = three[i];
        //     ans = (ans + ((LL)jc[sum2[now]] - sum2[now] - 1 + MOD) % MOD) % MOD; // 2 3
        // }
        // ans = ((LL)ans + jc[sum2[n]] - sum2[n] - 1 - ((LL) sum2[n] * (sum2[n] - 1) % MOD * inv2) % MOD + MOD + MOD) % MOD; // 2
        // ans = (ans - 1 + MOD) % MOD;
        // cout << "G: ";
        cout << ans << endl;
    }
    return 0;
}

D Palindrome Shuffle

Solution

首先，头尾对称的部分一定不会被选中翻转，可以忽略。现在研究去掉头尾对称部分的字符串。

如果左右各个字母总数相同，则一定不会挑越过中线的字母，也就是挑当前的前若干个，使剩下中间部分对称。

如果总数不相同，则一定要挑越过中线的字母。从左边第一个不对称的开始挑，然后把左半部分全部纳入，再从右半部分第一个开始往右，直到包含部分的每个字母都比右边剩余部分多。从右边开始同理，最后答案取一个 $\min$ 。

时间复杂度 $O(n\times26)$ 。

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1;
int num1[26], num2[26];
inline bool judge(){
    for (int i = 0; i < 26; ++i){
        if (num1[i] < num2[i]) return false;
    }
    return true;
}
signed main(){
    int t; cin >> t;
    while (t--){
        string s; cin >> s;
        memset(num1, 0, sizeof(num1));
        memset(num2, 0, sizeof(num2));
        for (int i = 0; (i + 1) * 2 <= s.length(); ++i){
            ++num1[s[i] - 'a'];
            ++num2[s[s.length() - 1 - i] - 'a'];
        }
        bool flag = true;
        for (int i = 0; i < 26; ++i){
            if (num1[i] != num2[i]){
                flag = false;
                break;
            }
        }
        int ans = s.length();
        // printf("flag = %d\n",flag);
        if (flag){
            int l = -1, r = s.length() / 2;
            while (l < r - 1){
                if (s[l + 1] == s[s.length() - l - 2]){
                    l++;
                }else if (s[r - 1] == s[s.length() - r]){
                    r--;
                }else{
                    break;
                }
            }
            // printf("l = %d, r = %d\n",l, r);
            ans = r - l - 1;
        }
        int l = -1, lm = s.length() / 2 - 1;
        while (l < lm && s[l + 1] == s[s.length() - l - 2]) l++;
        int i;
        for (i = 0; i <= l; ++i){
            num1[s[i] - 'a']--;
            num2[s[i] - 'a']--;
        }
        i = lm + 1;
        while (i < s.length() && !judge()){
            num1[s[i] - 'a']++;
            num2[s[i] - 'a']--;
            ++i;
        }
        ans = min(ans, i - l - 1);
        
        reverse(s.begin(), s.end());
        l = -1, lm = s.length() / 2 - 1;
        while (l < lm && s[l + 1] == s[s.length() - l - 2]) l++;
        memset(num1, 0, sizeof(num1)), memset(num2, 0, sizeof(num2));
        for (int i = l + 1; (i + 1) * 2 <= s.length(); ++i){
            ++num1[s[i] - 'a'];
            ++num2[s[s.length() - 1 - i] - 'a'];
        }
        i = lm + 1;
        while (i < s.length() && !judge()){
            num1[s[i] - 'a']++;
            num2[s[i] - 'a']--;
            ++i;
        }
        ans = min(ans, i - l - 1);
        cout << ans << endl;
    }
    return 0;
}

/*
1
eteffeteefekfektetee

*/

E A, B, AB and BA

Solution

发现 $\textrm{A}$ 和 $\textrm{B}$ 比 $\textrm{AB}$ 和 $\textrm{BA}$ 好用，所以要优先填入 $\textrm{AB}$ 和 $\textrm{BA}$ ，剩下用 $\textrm{A}$ 和 $\textrm{B}$ 填充。

假设最后需要 $p$ 个 $\textrm{A}$ 和 $q$ 个 $\textrm{B}$ ，则需要 $\textrm{AB}$ 和 $\textrm{BA}$ 的总数是 $w = \max\{p - a, q - b, 0\}$ 。如果 $w$ 比 $p$ 或者 $q$ 还要大，那么就是不可能的。否则，我们尝试填入 $\textrm{AB}$ 和 $\textrm{BA}$ ：

$\textrm{AB}$ 和 $\textrm{BA}$ 只能填在 $\textrm{AB}$ 交替的时候，我们可以记录所有 $\textrm{AB}$ 连续交替的区间；
对于 $\textrm{ABA}\cdots \textrm{AB}$ ，如果只填 $\textrm{AB}$ ，可以比混着填 $\textrm{AB}$ 和 $\textrm{BA}$ 多填一个，这种称为 $A$ 型；对于 $\textrm{ABA}\cdots \textrm{BA}$ 和 $\textrm{BAB}\cdots \textrm{AB}$ ，任意混着填都一样多，这种称为 $AB$ 型；对于 $\textrm{BAB}\cdots \textrm{BA}$ ，如果填 $\textrm{BA}$ ，可以比混着填 $\textrm{AB}$ 和 $\textrm{BA}$ 多填一个，这种称为 $B$ 型；
我们显然更想要让 $A$ 型用来填 $\textrm{A}$ ， $B$ 型用来填 $\textrm{B}$ ，剩下用 $AB$ 型填充。为了使损失最小，我们可以按长度从小往大填 $A$ 型和 $B$ 型，溢出再减 $1$ 化为 $AB$ 型。

故我们模拟以上操作，时间复杂度 $O(n\log n)$ 。

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1;
int n, a, b, ab, ba, p, q, w;
int A[N], B[N], C, idxa, idxb;
signed main(){
    int t; cin >> t;
    while (t--){
        string s; cin >> s;
        n = s.length();
        cin >> a >> b >> ab >> ba;
        p = q = 0;
        for (int i = 0; i < n; ++i){
            if (s[i] == 'A') ++p;
            else ++q;
        }
        if (p <= a && q <= b){
            cout << "YES" << endl;
            continue;
        }
        w = max(p - a, q - b);
        // printf("p = %d, q = %d, w = %d\n", p, q, w);
        if (ab + ba < w || w > p || w > q){
            cout << "NO" << endl;
            continue;
        }
        idxa = idxb = C = 0;
        int len = 0, start = -1;
        for (int i = 1; i < n; ++i){
            if (s[i] == s[i - 1]){
                // printf("i = %d, len = %d, start = %d\n",i,len,start);
                if (start != -1){
                    if (len & 1){
                        C += len >> 1;
                    }else if (start == 0){
                        A[++idxa] = len >> 1;
                    }else{
                        B[++idxb] = len >> 1;
                    }
                    start = -1;
                }
            }else{
                if (start == -1){
                    len = 2;
                    start = (s[i - 1] == 'B');
                }else{
                    ++len;
                }
            }
        }
        if (start != -1){
            if (len & 1){
                C += len >> 1;
            }else if (start == 0){
                A[++idxa] = len >> 1;
            }else{
                B[++idxb] = len >> 1;
            }
        }
        sort(A + 1, A + 1 + idxa, [](int x, int y){return x > y;});
        sort(B + 1, B + 1 + idxb, [](int x, int y){return x > y;});
        // for (int i = 1; i <= idxa; ++i) printf("A %d = %d\n", i, A[i]);
        // for (int i = 1; i <= idxb; ++i) printf("B %d = %d\n", i, B[i]);
        // printf("C = %d\n", C);
        while (idxa){
            if (A[idxa] <= ab){
                ab -= A[idxa];
                w -= A[idxa];
                --idxa;
            }else{
                A[idxa] -= ab;
                w -= ab;
                ab = 0;
                break;
            }
        }
        while (idxb){
            if (B[idxb] <= ba){
                ba -= B[idxb];
                w -= B[idxb];
                --idxb;
            }else{
                B[idxb] -= ba;
                w -= ba;
                ba = 0;
                break;
            }
        }
        // printf("ab = %d, ba = %d, w = %d\n", ab, ba, w);
        for (int i = 1; i <= idxa; ++i) C += A[i] - 1;
        for (int i = 1; i <= idxb; ++i) C += B[i] - 1;
        w -= min(C, ab + ba);
        if (w <= 0){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }
    }
}/*
1
AABABBABABAAABAABBABBABABABAABAAB
5 2 4 9


*/

F Graph Inclusion

Solution

首先发现每次查询的答案就是 $(A\bigcup B)\text{的连通块个数}-A\text{的连通块个数}$ 。故我们尝试维护两个图，支持动态插入边、删除边、查询连通块个数。（然而我并不会qwq）

通过学习题解，我们得到了一个经典的离线做法：记录每条边的存在时间，按照时间轴建立线段树，将每个存在时间的区间分割成线段树上 $O(\log q)$ 个区间；然后我们遍历整个线段树，每次走到一个新节点或者回溯一步，对应的操作为将当前节点所有边关系加入并查集和将当前节点所有边关系移出并查集。虽然移出并查集这个操作是不能实现的（可能？），但由于是回溯操作，所以我们只需要撤销最后若干个操作，这个操作是可以通过非路径压缩的并查集实现的（甚至不用主席树，多么好的算法）。每次到根节点记录答案就好了。

时间复杂度 $O(n\log n\log q)$ 。

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 4e5 + 1;
int n, q, fa[N], sz[N], line[N], idx, num[N], ans, num2[N];
bool opt[N]; int px[N], py[N];
struct Edge{
    int x, y;
    Edge(int a, int b){
        x = a;
        y = b;
    }
    bool operator < (const Edge& other) const{
        return x == other.x ? y < other.y : x < other.x;
    }
};
vector<Edge> T[N << 2];
map<Edge, int> mp;
int find(int x){
    return (x == fa[x] ? x : find(fa[x]));
}
inline void merge(int x, int y){
    int fx = find(x), fy = find(y);
    if (fx == fy) return line[++idx] = 0, void();
    if (sz[fx] > sz[fy]) fx ^= fy ^= fx ^= fy, x ^= y ^= x ^= y;
    ans--;
    fa[fx] = fy;
    line[++idx] = fx;
    sz[fy] += fx;
}
inline void rollback(){
    int x = line[idx--];
    if (!x) return;
    ans ++;
    sz[fa[x]] -= sz[x];
    fa[x] = x;
}
void Add(int k, int l, int r, int le, int ri, Edge e){
    if (l >= le && r <= ri) return T[k].push_back(e);
    int mid = l + r >> 1;
    if (mid >= le) Add(k << 1, l, mid, le, ri, e);
    if (mid < ri) Add(k << 1 | 1, mid + 1, r, le, ri, e);
}
void Calc(int k, int l, int r){
    for (int i = 0; i < T[k].size(); ++i){
        Edge now = T[k][i];
        merge(now.x, now.y);
    }
    // printf("k = %d, l = %d, r = %d, ans = %d\n\n", k, l, r, ans);
    if (l == r) num[l] = ans;
    else{
        int mid = l + r >> 1;
        Calc(k << 1, l, mid);
        Calc(k << 1 | 1, mid + 1, r);    
    }
    for (int i = 0; i < T[k].size(); ++i){
        rollback();
    }
}
void clear(int k, int l, int r){
    if (l == r) T[k].clear();
    int mid = l + r >> 1;
    clear(k << 1, l, mid);
    clear(k << 1 | 1, mid + 1, r);
}
inline int read(){
    int x = 0; char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}
inline bool get(){
    char ch = getchar();
    while (ch != 'A' && ch != 'B') ch = getchar();
    return ch == 'A';
}
signed main(){
    n = read(), q = read();
    // printf("n, q = %d %d\n",n,q);
    for (int i = 1; i <= n; ++i) fa[i] = i, sz[i] = 1;
    for (int i = 1; i <= q; ++i){
        opt[i] = get(), px[i] = read(), py[i] = read();
        if (px[i] > py[i]) px[i] ^= py[i] ^= px[i] ^= py[i];
    }//exit(0);
    // A
    for (int i = 1; i <= q; ++i){
        if (opt[i]){
            Edge now = Edge(px[i], py[i]);
            int pre = mp[now];
            if (!pre) mp[now] = i;
            else{
                Add(1, 1, q, pre, i - 1, now);
                mp.erase(now);
            }
        }
    }
    for (auto it = mp.begin(); it != mp.end(); ++it){
        Edge now = (*it).first; int pre = (*it).second;
        Add(1, 1, q, pre, q, now);
    }
    // exit(0);
    mp.clear();
    ans = n;
    Calc(1, 1, q);
    for (int i = 1; i <= q; ++i) num2[i] = num[i];
    for (int i = 1; i <= q; ++i){
        if (!opt[i]){
            Edge now = Edge(px[i], py[i]);
            int pre = mp[now];
            if (!pre) mp[now] = i;
            else{
                Add(1, 1, q, pre, i - 1, now);
                mp.erase(now);
            }
        }
    }
    for (auto it = mp.begin(); it != mp.end(); ++it){
        Edge now = (*it).first; int pre = (*it).second;
        Add(1, 1, q, pre, q, now);
    }
    mp.clear();
    ans = n;
    Calc(1, 1, q);
    for (int i = 1; i <= q; ++i){
        printf("%d\n", num2[i] - num[i]);
    }
    return 0;s
}