CF-CodeTon-3解题报告

发表于 更新于 分类于

比赛传送门

A. Indirect Sort

题意：有一个排列 aa，每次可以选三个不同的位置，从左到右依次为 i,j,ki,j,k。如果 ai>aka_i>a_k，将 aia_i 加上 aja_j，否则交换 aj,aka_j,a_k。问是否能将其排成非降序列。

贪心。如果第一个元素是 11，则一定可以：每次用 11 来当 ii，即可任意交换 j,kj,k。如果不是，则一定不可以：因为对于 11 所在的位置，要么将它移到左边，要么将它增加，要么让前面的减少。容易证明这三种都是不可行的。

By tourist

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    bool ok = true;
    for (int i = 0; i < n; i++) {
      ok &= (a[0] <= a[i]);
    }
    cout << (ok ? "Yes" : "No") << '\n';
  }
  return 0;
}

B. Maximum Substring

题意：定义一个 01 字符串的权值为：如果只有 0 或只有 1，则为 0/1 个数的平方，否则为 0 的个数乘 1 的个数。给定一个字符串，找出所有子串的最大权值。

分类讨论。有 0 有 1 时，全选一定最优，否则为最长的连续 0/1 子串长度的平方。三种情况取最大值即可。

By tourist

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int mx = 1;
    int t = 1;
    for (int i = 1; i < n; i++) {
      if (s[i] == s[i - 1]) {
        t += 1;
        mx = max(mx, t);
      } else {
        t = 1;
      }
    }
    int x = 0;
    for (int i = 0; i < n; i++) {
      x += (s[i] == '0');
    }
    int y = n - x;
    long long ans = (long long) x * y;
    ans = max(ans, (long long) mx * mx);
    cout << ans << '\n';
  }
  return 0;
}

C. Complementary XOR

题意：有两个 01 串 a,ba,b，每次操作可以选一个区间，将 aa 这段区间内的元素取反， bb 这段元素外的区间取反。构造一种方案，在 n+5n+5 次操作内将两个串归零，或判断无解。

容易发现，进行操作后 a,ba,b 的异或值将会完全取反，所以只有当 a=ba=b 或 a=inv(b)a=inv(b) 时才可能有解。如果 a=inv(b)a=inv(b)，我们可以先选整个串，将 aa 取反，转化为 a=ba=b 的情况。此后，当奇数次操作后 a=inv(b)a=inv(b)，偶数次操作后 a=ba=b。问题转化为：每次可以选 aa 的一段区间取反，恰好偶数次操作内将 aa 归零。

于是，我们先对每个 1 的位单独选中取反，最多 O(n)O(n) 次。如果此时用了奇数次操作，我们考虑如何再“浪费”奇数次操作将其变成偶数。一种方法是将第一位取反，再将剩下的取反，最后将全部取反。使用三次操作，结果不变。

By jiangly

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>

using i64 = long long;

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

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

    for (int i = 0; i < n; i++) {
        if (a[i] ^ b[i] ^ a[0] ^ b[0]) {
            std::cout << "NO\n";
            return;
        }
    }

    std::cout << "YES\n";

    std::vector<std::array<int, 2>> ans;
    for (int i = 0; i < n; i++) {
        if (a[i] == '1') {
            ans.push_back({i, i + 1});
        }
    }
    if (a[0] ^ b[0] ^ (ans.size() & 1)) {
        ans.push_back({0, 1});
        ans.push_back({1, n});
        ans.push_back({0, n});
    }

    std::cout << ans.size() << "\n";
    for (auto [l, r] : ans) {
        std::cout << l + 1 << " " << r << "\n";
    }
}

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

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

D. Count GCD

题意：给你一个数组 aa，求数组 bb 的方案数，满足 bb 的值域在 [1,m][1,m]，且 aa 为 bb 的前缀 gcd⁡\gcd。

由于 bb 的每一位独立，问题转化为求 bib_i 的方案数，满足 gcd⁡(ai−1,bi)=ai\gcd(a_{i-1},b_i)=a_i。式子两边同时除以 aia_i，则要求 gcd⁡(ai−1ai,biai)=1\gcd(\frac{a_{i-1}}{a_i},\frac{b_i}{a_i})=1 的方案数。我们可以枚举每个 ai−1a_{i-1} 的质因数，然后容斥。由于 10910^9 内的数不同的质因数个数不超过 1010 个，2102^10 枚举每一种方案即可。

By tourist

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    Mint ans = 1;
    for (int i = 0; i < n - 1; i++) {
      int x = a[i];
      int y = a[i + 1];
      if (x % y != 0) {
        ans = 0;
        break;
      }
      if (x == y) {
        ans *= m / x;
        continue;
      }
      int bound = m / y;
      int num = x / y;
      vector<int> fs;
      for (int j = 2; j * j <= num; j++) {
        if (num % j == 0) {
          fs.push_back(j);
          while (num % j == 0) {
            num /= j;
          }
        }
      }
      if (num > 1) {
        fs.push_back(num);
      }
      int sz = (int) fs.size();
      int cnt = 0;
      for (int mask = 0; mask < (1 << sz); mask++) {
        int sign = 1;
        int u = 1;
        for (int j = 0; j < sz; j++) {
          if (mask & (1 << j)) {
            sign *= -1;
            u *= fs[j];
          }
        }
        cnt += sign * (bound / u);
      }
      ans *= cnt;
    }
    cout << ans << '\n';
  }
  return 0;
}