暑假集训 杭电多校 Round 2

比赛链接

补题链接

---

「1009」 String Problem

签到题，求出连续段字符的数量，字符串长度减去该数量就是答案。

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

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

#include <iostream>

void solve() {
    std::string str;
    std::cin >> str;
    int dn = 1;
    for (int i = 1, len = str.size(); i < len; i++) {
        if (str[i] != str[i - 1]) dn++;
    }

    std::cout << str.size() - dn << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int numTest;
    std::cin >> numTest;
    while (numTest--) solve();

    return 0;
}

「1002」 Binary Number

签到题，简单分类讨论即可。但要注意细节，各种情况都需要考虑到。

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

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

#include <iostream>

using i64 = long long;

void solve() {
    int n;
    i64 k;
    std::string str;
    std::cin >> n >> k >> str;
    int p = 0;
    i64 k0 = k;
    while (k) {
        while (p < n && str[p] == '1') p++;
        if (p == n) {
            if (k & 1) {
                if ((n == 1 && str[0] == '1') || (k == k0 && k == 1)) {
                    str[n - 1] = '0';
                }
                break;
            }
            break;
        }
        else {
            int i;
            for (i = p; i < n && str[i] == '0'; i++) str[i] = '1';
            // str[i] == '0'
            p = i;
            k--;
        }
    }
    
    std::cout << str << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int numTest;
    std::cin >> numTest;
    while (numTest--) solve();

    return 0;
}

「1004」 Card Game

数学题，由题意可得 \(f(n) = 2 f(n - 1) + 1\) ，又因为 \(f(1) = 0\) ，所以有： \[ f(n) = 2 ^ {n - 1} - 1 \] 使用快速幂求出答案即可。

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

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

#include <iostream>

const int mod = 998244353;

int quickPow(int x, int n) {
    int res = 1;
    while (n) {
        if (n & 1) res = 1ll * res * x % mod;
        x = 1ll * x * x % mod;
        n >>= 1;
    }

    return res;
}

void solve() {
    int n;
    std::cin >> n;
    std::cout << quickPow(2, n - 1) - 1 << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int numTest;
    std::cin >> numTest;
    while (numTest--) solve();

    return 0;
}

「1007 」 foreverlasting and fried-chicken

有一说一，比赛的时候这题给我看饿了（正好碰上疯狂星期四）。

枚举全部不同的两个节点，一个作为炸鸡的头，一个作为炸鸡的尾，假设两个节点共同一步可达的节点数为 \(cnt\)，则炸鸡的躯干一共有 \(C_{cnt} ^ 4\) 种取法，对于炸鸡尾部的两个节点，将从与尾部节点相邻的其余节点中选取，一共 \(C_{x - 4} ^ 2\) 中取法（\(x\) 在这里表示与尾部节点相邻且不为头节点的节点数），最后枚举求和即可，时间复杂度为 \(O(n ^ 3)\) ，对于题目的数据量而言是会超时的，所以这里考虑 bitset 优化。

时间复杂度：\(O(\frac{n ^ 3}{w})\)

空间复杂度：\(O(n ^ 2)\)

bitset 讲解

#include <iostream>
#include <bitset>

#define MAX_N 1005

using i64 = long long;

const int mod = 1000000007;

inline int c2(int n) {
    if (n < 2) return 0;
    return (i64)n * (n - 1) / 2 % mod;
}

inline int c4(int n) {
    if (n < 4) return 0;
    return (i64)n * (n - 1) * (n - 2) * (n - 3) / 24 % mod;
}


std::bitset<MAX_N> g[MAX_N];

void solve() {
    int n, m;
    std::cin >> n >> m;
    for (int i = 0; i < n; i++) g[i].reset();
    for (int i = 0, x, y; i < m; i++) {
        std::cin >> x >> y;
        x--, y--;
        g[x][y] = g[y][x] = 1;
    }
    int res = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            int cnt_i = g[i].count();
            int cnt_j = g[j].count();
            int cnt_and = (g[i] & g[j]).count();
            if (g[i][j]) {
                cnt_i--, cnt_j--;
            }
            res = (res + (i64)c4(cnt_and) * (c2(cnt_i - 4) + c2(cnt_j - 4))) % mod;
        }
    }

    std::cout << res << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int numTest;
    std::cin >> numTest;
    while (numTest--) solve();

    return 0;
}

「1011」SPY finding NPY

典中典结论，若前 \(k\) 个不选择，则选择到 IQ 最高的对象的概率为 \(\sum_{i = k + 1} ^ n \frac{1}{i - 1} \frac{k}{n}\) 。当 \(n\) 足够大的的时候，\(k\) 大概等于 \([\frac{n}{e}]\) ，考虑到可能会存在误差，所以还需要在此基础上将 \(k\) 左右微调。

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

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

在这里时间和空间的开销主要都在预处理上。

最优终止策略讲解

#include <iostream>
#include <cmath>

#define MAX_N 10005

double div_num[MAX_N];
const double e = exp(1);

void preProcess() {
    for (int i = 2; i < MAX_N; i++) {
        div_num[i] = 1.0 / (i - 1);
    }
    for (int i = 1; i < MAX_N - 1; i++) {
        div_num[i] += div_num[i - 1];
    }
}

inline double prob(int n, int k) {
    if (k == 0) {
        return 1.0 / n;
    }

    return (div_num[n] - div_num[k]) * k / n;
}

void solve() {
    int n;
    std::cin >> n;
    int k = (int)((n + 0.5) / e);
    
    while (k > 0 && prob(n, k - 1) > prob(n, k)) k--;
    while (k < n && prob(n, k + 1) > prob(n, k)) k++;

    std::cout << k << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    preProcess();
    int numTest;
    std::cin >> numTest;
    while (numTest--) solve();

    return 0;
}

「1001」Alice Game

我们假设一段长度为 \(x\) 的序列的 \(SG\) 值为 \(sg(x)\) ，若 \(x <= k\) ，则先手可以且只能一次将序列全部删除，此时，\(sg(x) = 1\) ，若 \(x > k\) ，删除长度为 \(k\) 的序列后还剩两段不相连的序列，且两段序列互不影响，这事实上就是一种 Nim 游戏，此时有 \(sg(x) = \underset{i > 0\ \land\ n - k - i > 0}{mex} \{ sg(i) \oplus sg(n - k - i) \}\) ，这里的 \(\oplus\) 表示异或。

这样我们就可以求出 \(sg(n)\) 的值来判断先手是必胜还是必败了，但对于每一个 \(k\) 和 \(n\) 都求一次 \(sg(n)\) 的话时间开销过大，所以我们考虑打表找规律：

k = 2:  0 3 13 23 33 43 ...
k = 3:  0 4 18 32 46 60 ...
k = 4:  0 5 23 41 59 77 ...

以上为不同的 \(k\) 满足 \(sg(n) = 0\) 的 \(n\) 的取值。

不难发现，必败点 \(n\) 在 \(n > 0\) 的时候构成首项为 \(k + 1\) ，公差为 \(4k + 2\) 的等差数列。

因此可以大胆估计，当且仅当 \(n = 0\) 或者 \(n \equiv k + 1\ (mod\ 4k + 2)\) 的时候先手必败，否则先手必胜。

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

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

#include <iostream>

void solve() {
    int k, n;
    std::cin >> k >> n;
    bool ans = (n != 0 ? n % (4 * k + 2) != k + 1 : false);

    std::cout << (ans ? "Alice" : "Bob") << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int numTest;
    std::cin >> numTest;
    while (numTest--) solve();

    return 0;
}

至于这个结论怎么证明，就不得而知了（ACM 要什么证明）。

如果读者感兴趣可以自己试试。