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

Posted on 2025-10-10 Edited on 2026-03-23

Educational Codeforces Round 183 (Rated for Div. 2)

A. Candies for Nephews

Solution

模3。

Code

Show Code

signed main() {
    int t; io >> t;
    while (t--) {
        int n; io >> n;
        if (n % 3 == 0) {
            io << 0 << '\n';
        }else io << (3 - (n % 3)) << '\n';
    }
    return 0;
}

B. Deck of Cards

Solution

如果 $k=n$ ，则全部输出-，如果 $k<n$ ：

假设一开始全是+。

如果遇到0，则把从左往右第一个?变成-，第一个+变成?；
如果遇到1，则把从右往左第一个?变成-，第一个+变成?；
如果遇到2，则把从左往右第一个+变成?，从右往左第一个+也变成?。

模拟即可。

Code

Show Code

const int N = 2e5 + 1;
int n, k;
signed main() {
    int t; io >> t;
    while (t--) {
        io >> n >> k;
        int min1 = 1, max1 = n;
        int min2 = 1, max2 = n;
        for (int i = 1; i <= k; ++i) {
            char op; io >> op;
            if (op == '0') {
                ++min2;
                ++min1;
            } else if (op == '1') {
                --max2;
                --max1;
            } else if (op == '2') {
                ++min2;
                --max2;
            }
        }
        // printf("max1 = %d, min1 = %d, max2 = %d, min2 = %d\n",max1,min1,max2,min2);
        for (int i = 1; i <= n; ++i) {
            if (k >= n) {
                io << '-';
            } else if (i >= min2 && i <= max2) {
                io << '+';
            } else if (i >= min1 && i <= max1) {
                io << '?';
            } else {
                io << '-';
            }
        }
        io << '\n';

    }
    return 0;
}

C. Monocarp’s String

Solution

设a为 $-1$ ，b为 $1$ ，则问题转化为找到最短的区间，使得该区间的和等于整个序列的和。

如果序列和为 $0$ ，输出 $-1$ 。否则我们可以从左往右枚举区间的右端点。

设 $sum_i$ 表示 $[1,i]$ 的和，则每次对于 $sum_r$ 我们只需要找到 $sum_r - sum_{l - 1} = sum_n$ 即 $sum_{l-1} = sum_r - sum_n$ 就行了，并且是最大的 $l$ 。从左往右将 $sum_{l-1}$ 加入表，每次取下标最大值即可。复杂度 $O(n)$ 。

Code

Show Code

const int N = 2e5 + 1;
int n, sum[N], maxn[N * 2];
char A[N];
signed main() {
    int t; io >> t;
    while (t--) {
        io >> n;
        int ans = n;
        for (int i = 1; i <= n; ++i) {
            io >> A[i];
            sum[i] = sum[i - 1] + (A[i] == 'b' ? 1 : -1);
        }
        for (int i = 0; i <= 2 * n; ++i) {
            maxn[i] = -1;
        }
        for (int i = 1; i <= n; ++i) {
            maxn[sum[i - 1] + n] = i - 1;
            int now = maxn[n - (sum[n] - sum[i - 1])];
            if (now != -1) {
                ans = min(ans, i - now - 1);
            }
        }
        maxn[sum[n] + n] = n;
        if (maxn[n] != -1) {
            ans = min(ans, n - maxn[n]);
        }
        if (ans == n) {
            io << -1 << '\n';
        } else {
            io << ans << '\n';
        }
    }
    return 0;
}

D. Inversion Value of a Permutation

Solution

这是一道dp求方案。

首先，由于统计的是有逆序对的字串数量，只有 $a_i>a_{i+1}$ 时才有实际的贡献，其他逆序对都可以用这个代替。

假设我们前 $i$ 个数已经摆好，则 $i+1$ 个数加入时多出来的 $i$ 个区间，要不继承第 $i$ 个数产生的逆序字串数量，即 $a_{i+1}>a_i$ ，要不产生新的逆序子串，即 $a_{i+1}<a_i$ 。

设 $f[i][j][p]$ 表示前 $i$ 个数，从左往右数第 $j$ 和 $j+1$ 个数产生了最右端的逆序对，逆序子区间数为 $p$ 能否达到。转移时，分为两种情况：

$a_{i+1}>a_i$ ， $f[i+1][j][p+j]|=f[i][j][p]$ ；
$a_{i+1}<a_i$ ， $f[i+1][i][p+i]|=f[i][j][p]$ ；

这个dp是 $O(n^4)$ 的。最后再倒过来dp出答案即可。

E. Predicting Popularity

Solution

每次询问完，实际上我们都知道每个人需要有几个人看才会看这个电影，而且每次相当于只修改一个人的状态。

设第 $i$ 个人会看这个电影需要最少他人为 $p_i$ ，则只有所有 $p_j<p_i$ 的人都看电影，并且这些人的数量 $\geq p_i$ ，第 $i$ 个人才会看。

不妨设 $p_i = x$ 的人的数量为 $c_x$ ，令 $d_x = \sum_{y=0}^{x - 1}c_x - x$ ，则问题转化为求最小的 $x$ 使得 $d_x<0$ 。

在 $d_x$ 的基础上开一个最小值线段树，每次需要区间 $-1$ 和区间 $+1$ ，以及查询最小的小于 $0$ 的下标（递归每次优先往左即可）。

时间复杂度 $O(m\log{1000000})$ 。

Code

Show Code

int n, ac, dr;
const int N = 2e6 + 2;
int T[N << 2], lz[N << 2];
inline void add(int k, int v) {
    T[k] += v;
    lz[k] += v;
}
inline void pushup(int k) {
    T[k] = std::min(T[k << 1], T[k << 1 | 1]);
}
inline void pushdown(int k) {
    if (lz[k]) {
        add(k << 1, lz[k]);
        add(k << 1 | 1, lz[k]);
        lz[k] = 0;
    }
}
void Add(int k, int l, int r, int le, int ri, int v) {
    if (l >= le && r <= ri) return add(k, v);
    pushdown(k);
    int mid = (l + r) >> 1;
    if (mid >= le) Add(k << 1, l, mid, le, ri, v);
    if (mid < ri) Add(k << 1 | 1, mid + 1, r, le, ri, v);
    pushup(k);
}
int QueryMin(int k, int l, int r) {
    // printf("k = %d, l = %d, r = %d, T[k] = %d\n",k,l,r,T[k]);
    if (T[k] > 0) return -1;
    if (l == r) return l;
    pushdown(k);
    int mid = (l + r) >> 1;
    if (T[k << 1] <= 0) return QueryMin(k << 1, l ,mid);
    else return QueryMin(k << 1 | 1, mid + 1, r);
}
void Build(int k, int l, int r) {
    if (l == r) return T[k] = -l, void();
    int mid = (l + r) >> 1;
    Build(k << 1, l, mid);
    Build(k << 1 | 1, mid + 1, r);
    pushup(k);
}
signed main() {
    io >> ac >> dr >> n;
    std::vector<int> A(n + 1);
    std::vector<int> B(n + 1);
    std::vector<int> p(n + 1);
    const int maxn = 2000000;
    for (int i = 1; i <= n; ++i) {
        io >> A[i];
    }
    Build(1, 0, maxn);
    for (int i = 1; i <= n; ++i) {
        io >> B[i];
        p[i] = std::max(A[i] - ac, 0) + std::max(B[i] - dr, 0);
        Add(1, 0, maxn, p[i], maxn, 1);
    }
    int m; io >> m;
    for (int i = 1; i <= m; ++i) {
        int a, b, c;
        io >> a >> b >> c;
        int np = std::max(b - ac, 0) + std::max(c - dr, 0);
        if (np > p[a]) Add(1, 0, maxn, p[a], np - 1, -1);
        else if (np < p[a]) Add(1, 0, maxn, np, p[a] - 1, 1);
        p[a] = np;
        // printf("%d\n", QueryMin(1, 0, maxn));
        io << QueryMin(1, 0, maxn) << '\n';
    }
    return 0;
}

F. Long Journey

Solution

设 $l=\operatorname{lcm}(a_1, a_2, \cdots, a_n)$ ，则 $l\leq 2520$ 。

首先，最优方案是固定的：

如果下一格不会被炸死，那就走，因为待会走过去不如现在走过去（不可能存在相邻两格同时都是炸弹）；
如果下一格会被炸死，就不动（你也干不了啥了）。

其次，走不动的话就会在一个格子呆了 $n$ 个回合还动不了，并且在 $2l$ 步内这个情况就会出现，否则就没有这个情况。

然后，我们可以发现，如果存在两个状态 $(move_1, pos_1)$ 和 $(move_2, pos_2)$ 满足 $move_1\%10 = move_2\%10$ 且 $pos_1\%l = pos_2\%l$ ，则这两个状态之后的任何行为都将相同，所以我们可以开一个map记录 $(move\% 10, pos\% l)$ 状态，最多有 $10\times 2520$ 个，也就是说最多走 $25200$ 次后就会产生循环。

所以我们暴力往前走，如果发现走不动则报告无解，发现走到相同状态则跳出循环，利用后面的重复步数快速计算出答案。

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

Code

Show Code

using LL = long long;

signed main() {
    int t; io >> t;
    while (t--) {
        int n; LL m; io >> n >> m;
        std::vector<int> a(n);
        std::vector<int> b(n);
        int mul = 1;
        for (int i = 1; i <= n; ++i) {
            io >> a[i % n];
            mul = lcm(mul, a[i % n]);
        }
        for (int i = 1; i <= n; ++i) io >> b[i % n];
        // mul = 2420;
        // io << "mul = " << mul << '\n';
        std::vector<bool> steps(1, 0);
        int move = 0, pos = 0, move_n = 0, zeros = 0;
        std::map<int, int> mp;
        // io << "gogogo " << n << ' ' << m << '\n';
        while (pos < m) {
            ++move;
            ++move_n;
            if (move_n == n) move_n = 0;
            if ((pos + 1) % a[move_n] == b[move_n]) {
                steps.push_back(0);
                ++zeros;
            } else {
                steps.push_back(1);
                ++pos;
                zeros = 0;
            }
            // if (move < 100) io << "move = " << move << ", steps[-1] = " << steps.back() << ", pos = " << pos << '\n';
            if (mp[(pos % mul) * 10 + move_n]) {
                // io << "move=" << move << ",premove=" << mp[(pos % mul) * 10 + move_n] << ",pos=" << pos << '\n';
                break;
            }
            mp[(pos % mul) * 10 + move_n] = move;
            if (zeros >= n) {
                break;
            }
        }
        // io << "DONe" << '\n';
        if (pos == m) {
            io << move << '\n';
        } else if (zeros >= n) {
            io << "-1\n";
        } else {
            int res = 0;
            int premove = mp[(pos % mul) * 10 + move_n];
            for (size_t i = premove + 1; i < steps.size(); ++i) {
                // assert(move + 1 == steps.size());
                res += steps[i];
            }
            int res2 = 0;
            for (auto x : steps) {
                res2 += x;
            }
            assert(res2 == pos);
            LL ans = (m - 1 - pos + res) / res * (move - premove) + premove;
            size_t now = (m - 1 - pos + res) % res;
            size_t i, j;
            for (i = 0, j = premove + 1; i <= now && j < steps.size(); ++j) {
                assert(j < steps.size());
                i += steps[j];
                ++ans;
            }
            if (i <= now) {
                for (j = premove + 1;;++j) {
                    ++ans;
                    if (steps[j]) break;
                }
            }
            io << ans << '\n';
        } 
    }
    
    return 0;
}