Codeforces Round 943 (Div. 3)

A. Maximize?

思路：

• \(n\) 的范围比较小，直接暴力枚举即可

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

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

    int ans = 0, mx = 0;
    for (int i = 1; i < x; i++) {
        if (std::gcd(i, x) + i > mx) {
            ans = i;
            mx = std::gcd(i, x) + i;
        }
    }
    std::cout << ans << "\n";
}

B. Prefiquence

思路：

• 双指针，分别在两个字符串上按规则扫描即可

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

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

    std::string a, b;
    std::cin >> a >> b;

    int j = 0;
    for (int i = 0; i < m; ) {
        if (a[j] == b[i]) {
            i++, j++;
        } else {
            i++;
        }
    }
    std::cout << j << "\n";
}

C. Assembly via Remainders

思路：

• 我是直接取个最大值，然后减去两个之间的差值，不知道会不会被hack

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

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

    std::vector<int> x(n + 1);
    for (int i = 2; i <= n; i++) {
        std::cin >> x[i];
    }  
    int tot = 998244353;
    std::vector<int> ans;
    for (int i = n; i >= 2; i--) {
        if (ans.empty()) {
            ans.push_back(tot + x[i]);
            ans.push_back(tot);
        } else {
            ans.push_back(ans.back() - x[i]);
        }
    }
    std::reverse(ans.begin(), ans.end());
    for (int i = 0; i < ans.size(); i++) {
        std::cout << ans[i] << " \n"[i == ans.size() - 1];
    }
}

D. Permutation Game

思路：

• 这题直接遍历所有可能走过的点即可，然后我们剪枝一下就好了

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

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

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

    int mxa = *max_element(a.begin() + 1, a.end());

    i64 l = 0;
    int t = Ps, tot = 0;
    i64 A = 0, B = 0;
    std::vector<int> st(n + 1);
    while (true) {
        l += a[t];
        tot++;
        A = std::max(A, l + 1LL * (k - tot) * a[t]);
        if (tot == k || a[t] == mxa || t == p[t] || st[t]) break;
        st[t] = true;
        t = p[t];
    }

    i64 r = 0;
    t = Pb; tot = 0;
    st.assign(n + 1, 0);
    while (true) {
        r += a[t];
        tot++;
        B = std::max(B, r + 1LL * (k - tot) * a[t]);
        if (tot == k || a[t] == mxa || t == p[t] || st[t]) break;
        st[t] = true;
        t = p[t];
    }
    if (B > A) {
        std::cout << "Bodya\n";
    } else if (B == A) {
        std::cout << "Draw\n";
    } else {
        std::cout << "Sasha\n";
    }
}

E. Cells Arrangement

思路：

• 这题挺简单的，只要耐心推一下，就可以发现，只要我们将 \(n=2\) 的这个位置的坐标改为 \((2, 1)\) 就可以使得所有的组合方式的 \(dist\) 方案数最大

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

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

    std::cout << "1 1\n";
    std::cout << "2 1\n";
    for (int i = 3; i <= n; i++) {
        std::cout << i << " " << i << "\n";
    }
}

F. Equal XOR Segments

思路：

时间复杂度：

G1. Division + LCP (easy version)

思路：

• 二分加 kmp 或者字符串双模数 hash，来处理整个字符串中包含多少个当前长度的子串，根据这个数量和l的大小关系来

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

/*
双模数hash模板
...
*/

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

    std::string s;
    std::cin >> s;

    Shash S;
    S.init(s);

    int l = 0, r = n + 1;
       while (l + 1 < r) {
           int mid = l + r >> 1;
           auto check = [&](int x) {
            int cnt = 1;
               for (int i = x + 1; i <= n; i++) {
                if (i + x - 1 > n) break;
                if (S.same(1, x, i, i + x - 1)) {
                    cnt++;
                    i = i + x - 1;  
                }
            }
            return cnt >= l1;
           };
           if (check(mid)) {
               l = mid;
           } else {
               r = mid;
           }
       }
       std::cout << l << "\n";
}