Solution - Codeforces Round 1003 (Div. 4)

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

Codeforces Round 1003 (Div. 4)

A Skibidus and Amog’u

题意

把单数变复数

思路

Replace all "us"s with "s"s, and print them.

把所有结尾的"us"替换为"i"即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 101;
signed main(){
    int T; cin >> T;
    while (T--){
        string x; cin >> x;
        string y = x.substr(0, x.length() - 2) + "i";
        cout << y << endl;
    }
    return 0;
}

B Skibidus and Ohio

题意

给定一个小写字母字串，每次可以选两个相邻相同的字母，消去并以任意字母替代。求最后剩余最短字串长度。

思路

观察到每次消去都可以选一个和相邻字母相同的字母，所以只要有两个相邻字母相同，答案就是 $1$ ，否则答案是 $length$ 。

代码

#include<bits/stdc++.h>
using namespace std;
signed main(){
    int T; cin >> T;
    while (T--){
        string x; cin >> x;
        bool flag = false;
        for (int i = 0; i < x.length() - 1; ++i){
            if (x[i] == x[i + 1]){
                cout << 1 << endl;
                flag = true;
                break;
            }
        }
        if (!flag) cout << x.length() << endl;
    }
    return 0;
}

C1 & C2 Skibidus and Fanum Tax

题意

给定 $a$ ， $b$ 两个数列，每个 $a_i$ 可以不变，也可以变成 $b_j-a_i$ （只能变一次， $j$ 任取）。问能否保证 $a$ 单调不降。

思路

从 $1$ 到 $n$ 遍历所有 $a_i$ ，我们当然希望每个 $a_i$ 在进行操作后尽可能小。每个 $a_i$ 有两种操作方式：

不变，需满足条件 $a_i \geq a_{i - 1}$ ；
找到一个 $j$ ，把 $a_i$ 变成 $b_j - a_i$ ，需要满足条件 $b_j - a_i \geq a_{i - 1}$ 。

其中 $2$ 操作 $b_j$ 越小越好，也就是说找到最小的 $b_j$ 使 $b_j - a_i \geq a_{i - 1}$ ，即最小的满足 $b_j\geq a_i + a_{i - 1}$ 的 $b_j$ 。这个可以通过把所有 $b_j$ 丢到一个set里面，然后用lower_bound查找即可。

复杂度 $O(n\log m + m)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1;
int n, m, A[N];
std::set<int> st;
signed main(){
    int T; scanf("%d", &T);
    A[0] = -1e9 - 1;
    while (T--){
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i){
            scanf("%d", &A[i]);
        }
        for (int i = 1; i <= m; ++i){
            int x; scanf("%d", &x);
            st.insert(x);
        }
        bool fflag = true;
        for (int i = 1; i <= n; ++i){
            bool flag = false;
            if (A[i] >= A[i - 1]){
                flag = true;
            }
            auto it = st.lower_bound(A[i] + A[i - 1]);
            int bb = (flag ? A[i] : 1e9 + 1);
            if (it != st.end()){
                flag = true;
                A[i] = min(bb, (*it) - A[i]);
                // printf("\nT = %d, i = %d, Found = %d, A[i] = %d\n", T, i, (*it), A[i]);
            }
            if (!flag){
                puts("NO");
                fflag = false;
                break;
            }
        }
        if (fflag){
            puts("YES");
        }
        st.clear();
    }
}

D Skibidus and Sigma

题意

给定一些长度相同的数列，请规定一种连接顺序，使最后的 $\sum_{i = 1}^{nm}\sum_{j = 1}^i b_j$ 最大。

思路

假设先按 $a_1, a_2, \dots, a_n$ 排好。

假设 $i < j$ ，注意到 $a_i$ 和 $a_j$ 如果交换的话， $\Delta ans = sum(a_j) - sum(a_i)$ ，所以当任意 $i < j$ 都满足 $sum(a_i) \geq sum(a_i)$ 的话就是最优的。按照 $sum(a_i)$ 排序即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 1;
vector<int> A[N];
int idx[N], n, m;
LL sum[N];
inline bool cmp(const int& x, const int& y){
    return sum[x] > sum[y];
}
signed main(){
    int T; scanf("%d", &T);
    while (T--){
        scanf("%d%d", &n, &m);
        memset(sum, 0, sizeof(sum));
        for (int i = 1; i <= n; ++i){
            for (int j = 0; j < m; ++j){
                int x; scanf("%d", &x);
                A[i].push_back(x);
                sum[i] += A[i][j];
            }
            idx[i] = i;
        }
        sort(idx + 1, idx + 1 + n, cmp);
        LL ans = 0;
        for (int i = 1; i <= n ; ++i){
            for (int j = 0; j < m; ++j){
                ans += (LL)A[idx[i]][j] * (n * m - (i - 1) * m - j);
            }
            A[idx[i]].clear();
        }
        printf("%lld\n", ans);
    }
}

E Skibidus and Rizz

题意

给定 $n$ 个 $0$ 和 $m$ 个 $1$ ，询问是否能够用这 $n+m$ 个数构造一个01序列，使其所有子串01数量差的最大值恰好为 $k$ ，并构造解。

思路

我们只考虑 $0$ 比 $1$ 多或相等的情况：

$n - m > k$ ，则不管怎么摆这个串本身的01数量差大于 $k$ ，不可能；
$n < k$ ，则不管怎么摆都小于 $k$ ，不可能；
如果不是以上两种情况，我们先摆 $k$ 个 $0$ ，然后在后面跟上尽可能多的 $10$ 交替序列，最后再把多余的 $1$ 摆上。由于最后剩 $1$ 的个数为 $m-(n-k) \leq m - (m-k) = k$ ，所以最大值刚好是 $k$ 。

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

代码

#include<bits/stdc++.h>
using namespace std;
string construct(int n, int m, int k, bool flag){
    if (n - m > k || k > n){
        return "-1";
    }
    string s;
    for (int i = 1; i <= k; ++i){
        s += '0' + flag;
    }
    for (int i = 1; i <= n - k; ++i){
        s += '0' + !flag;
        s += '0' + flag;
    }
    for (int i = 1; i <= m - n + k; ++ i){
        s += '0' + !flag;
    }
    return s;
}
signed main(){
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    int T; cin >> T;
    while (T--){
        int n, m, k;
        cin >> n >> m >> k;
        bool flag = false;
        if (n < m) flag = true, n ^= m ^= n ^= m;
        cout << construct(n, m, k, flag) << endl;
    }
}

F Skibidus and Slay

题意

给定一棵树，树上每个点有一个颜色，对于每个颜色，求是否存在一条起码有两个节点的简单路径，使得这个路径上有超过一半的节点颜色是这个颜色。

思路

如果一条合法路径上任意相邻节点都不同时是当前颜色，则当且仅当这个路径有奇数个节点且刚好有一半多一个节点都是这个颜色（交替）那么我们可以找到一个长度为 $3$ 的子路径来替代这条路径；
如果一条合法路径上存在相邻节点同时是当前颜色，则可以用这两个节点替代这条路径。

综上，检测长度为 $2$ 或 $3$ 的路径即可。

长度为 $2$ 的路径数量就是边数， $O(m)$ 解决。
长度为 $3$ 的路径，可以每个节点枚举相邻节点，看看有没有相同颜色，同样 $O(m)$ 解决。

复杂度 $O(n + m)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 1;
// 🤔原来还可以打表情😂
int A[N], n;
bool vis[N], ans[N], flag[N];
vector<int> G[N];
void Dfs(int u){
    if (vis[u]) return;
    vis[u] = 1;
    for (int i = 0; i < G[u].size(); ++i){
        int v = G[u][i];
        if (A[u] == A[v]) ans[A[u]] = 1;
        if (flag[A[v]]) ans[A[v]] = 1;
        else flag[A[v]] = 1;
    }
    for (int i = 0; i < G[u].size(); ++i){
        int v = G[u][i];
        flag[A[v]] = 0;
    }
    for (int i = 0; i < G[u].size(); ++i){
        int v = G[u][i];
        Dfs(v);
    }
}
signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while (t--){
        cin >> n;
        for (int i = 1; i <= n; ++i){
            cin >> A[i];
            G[i].clear();
            ans[i] = 0, vis[i] = 0;
        }
        for (int i = 1; i < n; ++i){
            int a, b; cin >> a >> b;
            G[a].push_back(b);
            G[b].push_back(a);
        }
        Dfs(1);
        for (int i = 1; i <= n; ++i) cout << ans[i];
        cout << endl;
    }
    return 0;
}

G Skibidus and Capping

题意

给定数列，求数列中的所有数对中，满足两者的 $\operatorname{lcm}$ 可以表示为两个质数乘积的（半质数）个数。

思路

先记录每个数的质因子个数，逐次考虑每个数 $x$ ：

$x$ 是质数，则找到之前所有的质数（不等于 $x$ ），以及之前的包含 $x$ 的半质数；
$x$ 是半质数，则找到之前的 $x$ 的两个质数，或者 $x$ 。

所有都可以 $O(n)$ 维护，而判断是否为质数和分解质因数需要 $O(\sqrt n)$ ，复杂度 $O(n\sqrt n)$ 。也可以通过欧拉筛预处理达到 $O(n)$ 的复杂度。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e5 + 1;
int n, cnt1[N], cnt2[N], prnum;
LL ans;
inline bool isprime(int x){
    for (int i = 2; i * i <= x; ++i){
        if (x % i == 0){
            return false;
        }
    }
    return true;
}
inline PII divide(int x){
    PII y = {0, 0};
    for (int i = 2; i * i <= x;){
        if (x % i == 0){
            x /= i;
            if (y.first) return PII(0, 0);
            else y.first = i;
        }else ++i;
    }
    if (x != 1) y.second = x;
    return y;
}
signed main(){
    int t; cin >> t;
    while (t--){
        cin >> n;
        for (int i = 1; i <= n; ++i) cnt1[i] = cnt2[i] = 0;
        prnum = 0, ans = 0;
        for (int i = 1; i <= n; ++i){
            // printf("i = %d\n",i);
            int x; cin >> x;
            if (isprime(x)){
                cnt1[x] += 1, prnum += 1;
                ans += prnum - cnt1[x];
                ans += cnt2[x];
                // printf("anssss += %d\n", prnum - cnt1[x] + cnt2[x]);
            }else{
                PII y = divide(x);
                if (y.second == 0){
                    continue;
                }
                cnt2[y.first] += 1;
                if (y.second != y.first) cnt2[y.second] += 1;
                cnt1[x] += 1;
                ans += cnt1[y.first];
                // printf("first = %d, second = %d\n",y.first, y.second);
                if (y.second != y.first) ans += cnt1[y.second];
                ans += cnt1[x];
                // printf("ans += %d %d %d\n", cnt1[y.first], cnt1[y.second], cnt1[x]);
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

H Bro Thinks He’s Him

题意

给定一个01序列，现作 $q$ 次修改，每次把某一位数反转，求每次修改完该序列所有子序列的01交替次数之和。

思路

首先考虑对于总序列如何求解：

设 $f(i)$ 为为第 $i$ 位及以前子序列交替次数之和， $g(i)$ 为第 $i$ 位及以前结尾为 $0$ 的子序列交替次数之和， $h(i)$ 为第 $i$ 位及以前结尾为 $1$ 的子序列交替次数之和； $p(i)$ 为第 $i$ 位及以前结尾为 $0$ 的子序列数量， $q(i)$ 为第 $i$ 位及以前结尾为 $1$ 的子序列数量； $r(i)$ 为第 $i$ 位及以后开头为 $0$ 的子序列数量， $s(i)$ 为第 $i$ 位及以后开头为 $1$ 的子序列数量。

假设第 $i$ 位为 $0$ ，则：

\begin{aligned} g(i) &= 2g(i - 1) + h(i - 1) + q(i - 1)\\ h(i) &= h(i - 1)\\ \implies f(i) &= 2f(i - 1) + q(i - 1)\end{aligned}

故我们可以得到：

f(i) = \begin{cases} 2f(i - 1) + q(i - 1) & \text{if } x = 0\\ 2f(i - 1) + p(i - 1) & \text{if } x = 1 \end{cases}

这样可以算出原序列的 $f(n)$ 。

现在考虑将中间某个数从 $0$ 变成 $1$ ，则我们只需考虑包含这个数的子序列：

左边最后一个为 $0$ ，右边第一个为 $0$ ，则答案会加 $2p(i - 1)r(i + 1)$ ；左边最后一个为 $1$ ，右边第一个为 $0$ ，则答案会减少 $2q(i - 1)s(i + 1)$ ；只有左边或右边 $0$ 答案会增加 $p(i - 1)$ 或 $r(i + 1)$ ；只有左边或右边 $1$ 答案会减少 $q(i - 1)$ 或 $s(i + 1)$ 。其余情况答案没有变化。

而 $p,q,r,s$ 都可以用树状数组动态维护（单点修改，区间查询）。复杂度 $O(n\log n)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 1, MOD = 998244353;
class BIT{ // 树状数组
private:
    int n; vector<int> T;
public:
    inline void add(int x, int v){
        for (; x <= n; x += x & -x) T[x] = (T[x] + v) % MOD;
    }
    inline int query(int x){
        int res = 0;
        for (; x; x -= x & -x) res = (res + T[x]) % MOD;
        return res;
    }
    inline int sum(int x, bool flag){
        if (flag){
            return query(x);
        }else{
            return (query(n) - query(x - 1) + MOD) % MOD;
        }
    }
    BIT(int x){
        n = x;
        T = vector<int>(n + 1);
    }
}; 

int n, q, f[N], pow2[N];

signed main(){
    int t; cin >> t;
    pow2[0] = 1;
    for (int i = 1; i < N; ++i) pow2[i] = pow2[i - 1] * 2 % MOD;
    while (t--){
        string A; cin >> A;
        n = A.length();
        BIT g(n), h(n), r(n), s(n); // g, h对应p, q
        for (int i = 0; i < A.length(); ++i){
            if (A[i] == '0'){
                g.add(i + 1, pow2[i]);
                r.add(i + 1, pow2[n - i - 1]);
                f[i + 1] = (f[i] * 2 % MOD + h.sum(i, 1) + 1) % MOD;
            }else{
                h.add(i + 1, pow2[i]);
                s.add(i + 1, pow2[n - i - 1]);
                f[i + 1] = (f[i] * 2 % MOD + g.sum(i, 1) + 1) % MOD;
            }
            // printf("i = %d, fi = %d\n",i,f[i + 1]);
        }
        int ans = f[n];
        cin >> q;
        for (int i = 1; i <= q; ++i){
            int x; cin >> x;
            if (A[x - 1] == '0'){
                ans = (ans + (LL)g.sum(x - 1, 1) * r.sum(x + 1, 0) * 2 % MOD + MOD) % MOD;
                ans = (ans - (LL)h.sum(x - 1, 1) * s.sum(x + 1, 0) * 2 % MOD + MOD) % MOD;
                ans = ((LL)ans + g.sum(x - 1, 1) - h.sum(x - 1, 1) + r.sum(x + 1, 0) - s.sum(x + 1, 0) + MOD * 2) % MOD;
                g.add(x, MOD - pow2[x - 1]), r.add(x, MOD - pow2[n - x]);
                h.add(x, pow2[x - 1]), s.add(x, pow2[n - x]);
                A[x - 1] = '1';
            }else{
                ans = (ans - (LL)g.sum(x - 1, 1) * r.sum(x + 1, 0) * 2 % MOD + MOD) % MOD;
                ans = (ans + (LL)h.sum(x - 1, 1) * s.sum(x + 1, 0) * 2 % MOD + MOD) % MOD;
                ans = ((LL)ans - g.sum(x - 1, 1) + h.sum(x - 1, 1) - r.sum(x + 1, 0) + s.sum(x + 1, 0) + MOD * 2) % MOD;
                h.add(x, MOD - pow2[x - 1]), s.add(x, MOD - pow2[n - x]);
                g.add(x, pow2[x - 1]), r.add(x, pow2[n - x]);
                A[x - 1] = '0';
            }
            cout << ans << ' ';
        }
        cout << endl;
    }
    return 0;
}