Codeforces Round 925 (Div. 3)

发表于 2024-02-14 更新于 2024-07-19 分类于题解阅读次数：本文字数： 1.2k 阅读时长 ≈ 4 分钟

No cross, no crown.

A. Recovering a Small String

思路：

直接暴力枚举

时间复杂度：\(O(26^3)\)

void solve() {
    int n;
    std::cin >> n;

    for (char i = 'a'; i <= 'z'; i++) {
        for (char j = 'a'; j <= 'z'; j++) {
            for (char k = 'a'; k <= 'z'; k++) {
                int a = i - 'a' + 1;
                int b = j - 'a' + 1;
                int c = k - 'a' + 1;
                if (a + b + c == n) {
                    std::cout << i << j << k << "\n";
                    return ;
                }
            }
        }
    }
}

B. Make Equal

思路：

判断在过程中是否会出现差值累加小于0的情况

时间复杂度：\(O(n)\)

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    i64 dif = 0;
    i64 avg = std::accumulate(a.begin(), a.end(), 0LL) / n;
    for (int i = 0; i < n; i++) {
        if (a[i] < avg) {
            dif += a[i] - avg;
            if (dif < 0) {
                std::cout << "NO\n";
                return ;
            }    
        } else if (a[i] > avg) {
            dif += a[i] - avg;
        }
    }
    std::cout << "YES\n";
}

C. Make Equal Again

思路：

由于最多只能修改一次，那么最终的序列每个元素的值一定只可能等于a[0]或者a[n-1]，只需取最小数

时间复杂度：\(O(1)\)

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    int B = 0;
    for (int j = 0, i = n - 1; j < i ;) {
        while (a[j] == a[0] && j < n) {
            j++;
        }
        while (a[i] == a[0] && i >= 0) {
            i--;
        }
        B += i - j + 1;
        break;
    }

    int A = 0;
    for (int j = 0, i = n - 1; j < i ;) {
        while (a[j] == a[n - 1] && j < n) {
            j++;
        }
        while (a[i] == a[n - 1] && i >= 0) {
            i--;
        }
        A += i - j + 1;
        break;
    }

    std::cout << std::max(0, std::min(A, B)) << "\n";
}

D. Divisible Pairs

思路：

用 \(map\) 维护这个两个式子 \(B= \begin{cases} (a_i+a_j) \% x \\ (a_i-a_j) \% y \end{cases}\) 的值

时间复杂度：\(O(n)\)

void solve() {
    int n, x, y;
    std::cin >> n >> x >> y;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    i64 ans = 0;
    std::map<std::pair<int, int>, int> mp;
    for (int i = 0; i < n; i++) {
        ans += mp[{(x - a[i] % x) % x, a[i] % y}]; // (a_i - a_j) % x
        mp[{a[i] % x, a[i] % y}]++; // (a_i + a_j) % y
    }
    
    std::cout << ans << "\n";
}

E. Anna and the Valentine's Day Gift

思路：

Anna可以让一个数的0数量变少，如1580 => 851，相反，Sasha需要保护0尽可能多
所以我们可以开一个数组用来存每个数的末尾0的个数，然后将其从大到小排序，这样可以保证二人是按最优的方案进行游戏的
然后只需判断最后的所有数的位数是否大于等于m即可

时间复杂度：\(O(nlogn)\)

void solve() {
    int n, m;
    std::cin >> n >> m;

    int sum = 0;
    std::vector<int> b(n);
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        while (x % 10 == 0) {
            sum++;
            b[i]++;
            x /= 10;
        }
        while (x) {
            sum++;
            x /= 10;
        }
    }

    std::sort(b.rbegin(), b.rend());

    for (int i = 0; i < n; i += 2) {
        sum -= b[i];
    }

    std::cout << (sum > m ? "Sasha\n" : "Anna\n");
}

F. Chat Screenshots

思路：

用拓扑排序找出是否存在环即可
如果cnt为n就说明这个拓扑序是确定的，否则就说明有环，那么一定小于n

时间复杂度：\(O(n+m)\)

void solve() {
    int n, k;
    std::cin >> n >> k;

    std::vector<int> deg(n);
    std::vector<std::vector<int>> adj(n);
    for (int i = 0; i < k; i++) {
        std::vector<int> a(n);
        for (int j = 0; j < n; j++) {
            std::cin >> a[j];
            a[j]--;
            if (j > 1) {
                deg[a[j]]++;
                adj[a[j - 1]].push_back(a[j]);
            }
        }
    }

    auto topo = [&]() {
        std::queue<int> q;
        for (int i = 0; i < n; i++) {
            if (!deg[i]) q.push(i);
        }    

        int cnt = 0;
        while (q.size()) {
            auto cur = q.front();
            cnt++;
            q.pop();

            for (auto x : adj[cur]) {
                if (--deg[x] == 0) {
                    q.push(x);
                }
            }
        }
        return cnt == n;
    };

    std::cout << (topo() ? "YES\n" : "NO\n");
}

G. One-Dimensional Puzzle

思路：

\(1\) 和 \(2\) 是可以一直拼接的，\(3\) 和 \(4\) 是作为 \(1\) 和 \(2\) 的辅助，如果出现 \(1\) 和 \(2\) 的差值超过 \(2\)，那么一定不存在可行方案
所以我们可以用隔板法，来得到方案数，
- 当二者不相等时：\(C_{c+mx-1}^{mx-1} + C_{d+mx-1}^{mx-1}\)
- 当二者相等且不为 \(0\) 时：\(C_{c+a-1}^{a-1} + C_{d+a-1}^{a-1} + C_{c+a}^{a} + C_{d+a}^{a}\)
- 当二者相等且为 \(0\) 时：由于 \(3\) 和 \(4\) 并不可兼容，所以只存在 \(1\) 种情况
线性逆元：\(i^{-1}=-\lfloor \frac{mod}{i} \rfloor \times (mod \% i)^{-1} \Rightarrow inv[i]=(P - P / i) \times inv[P \% i] \space \% \space P\)

时间复杂度：\(O(n)\)

constexpr int P = 998244353;
constexpr int N = 2000010;
struct Comb {
    i64 Ca[N], Cb[N], inv[N];

    Comb() {}

    void init() {
        Ca[0] = Cb[0] = 1;
        for (int i = 1; i < N; i++) {
            inv[i] = i == 1 ? 1 : (P - P / i) * inv[P % i] % P; // 线性逆元
            Ca[i] = Ca[i - 1] * i % P;
            Cb[i] = Cb[i - 1] * inv[i] % P; 
        }
    }
    
    i64 get(int a, int b) {
        if (a < b || b < 0) return 0;
        return Ca[a] * Cb[b] % P * Cb[a - b] % P;
    }
}D;

void solve() {
    int a, b, c, d;
    std::cin >> a >> b >> c >> d;

    if (abs(a - b) > 1) {
        std::cout << "0\n";
        return ;
    }   

    i64 ans = 0;
    if (a == 0 && b == 0) {
        ans = c == 0 || d == 0;
    } else if (a == b) {
        ans += D.get(a + c - 1, a - 1) * D.get(a + d, a) % P;
        ans += D.get(a + c, a) * D.get(a + d - 1, a - 1) % P;
        ans %= P;
    } else {
        int mx = std::max(a, b);
        ans = D.get(c + mx - 1, mx - 1) * D.get(d + mx - 1, mx - 1) % P;
        ans %= P;
    }
    std::cout << ans % P << "\n";
}