A.

显然。

cpp
1
2
3
4
5
6
7
8
9
10
11
12
void solve() {
  int x, y, k;
  cin >> x >> y >> k;
 
  if (y <= x) {
    cout << x << "\n";
  } else {
    int t = min(x + k, y);
    cout << y + y - t << "\n";
  }
  
}

B.

选择两个子集，极差之和最小。

显然是排序之后分两半。

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve() {
  int n;
  cin >> n;
  vi a(n * 2);
  rep(i, n * 2) cin >> a[i];
  sort(all(a));
  vi x, y;
  rep(i, n) {
    x.pb(a[i]);
  }
  rep(i, n) {
    y.pb(a[i + n]);
  }
  int ans = a.back() - a[n] + a[n - 1] - a[0];
  cout << ans << "\n";
  rep(i, n) {
    cout << x[i] << " " << y[i] << "\n";
  }
}

C.

枚举偶数长度 l，然后选择可能的方案。

非常好写。

cpp
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
int coef[10][50];
void solve() {
  int n;
  cin >> n;
  vc<string> s(n);
  rep(i, n) cin >> s[i];
  ll ans = 0;
  for (int l = 2; l <= 10; l += 2) {
    memset(coef, 0, sizeof coef);
    rep(i, n) {
      if (sz(s[i]) < l) {
        int sum = 0;
        int c = 0;
        for (int j = sz(s[i]) - 1; j >= 0; j--) {
          c += 1;
          if (c > l / 2) {
            sum -= s[i][j] - '0';
          } else {
            sum += s[i][j] - '0';
          }
        }
        if (sum >= 0) coef[sz(s[i])][sum] += 1;
        sum = 0;
        c = 0;
        rep(j, sz(s[i])) {
          c += 1;
          if (c > l / 2) {
            sum -= s[i][j] - '0';
          } else {
            sum += s[i][j] - '0';
          }
        }
        if (sum >= 0) coef[sz(s[i])][sum] += 1;
      }
    }
    rep(i, 1, l) {
      rep(j, 50) {
        ans += 1ll * coef[i][j] * coef[l - i][j];
      }
    }
  }
 
  cout << ans / 4 << "\n";
}

D.

简单讲讲我的做法。

考虑所有数字一定互不相同。（异或性质）

那么只需要满足 max≤n−1，即 di≤n−1，就可以满足这个序列是 0…n−1

我们假设 x xor yi=di，使得 di 为 0…n−1

那么 x=yi xor di，由于 yi 互不相同，那么 di 肯定也互不相同。

那只需要 x∈\andyi xor 0,yi xor 1…yi xor n−1 即可。

考虑对于一个数字 y，y xor i，i∈[0,n−1] 会产生 log 个区间。

综上，可以用前缀和维护，交集的话相当于出现了 n−1 次，复杂度 O(nlog)。

感觉别的做法都比我的简单啊。/ll

cpp
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
void solve() {
  int n;
  cin >> n;
  vi a(n);
  rep(i, 1, n) {
    cin >> a[i];
    a[i] ^= a[i - 1];
  }
  debug(a);
  vi s(n * 4);
  int t = n - 1;
  // x ^ a[i] <= n - 1, x < n
  rep(i, 1, n) {
    // debug(a[i]);
    int x = a[i];
    for (int j = 20; j >= 0; j--) {
      if (t >> j & 1) {
        // debug(x);
        int k = 1 << j;
        int l = x & ~(k - 1);
        int r = l + k;
        // [l, r)
        s[l] += 1; 
        s[r] -= 1;
        x ^= k;
        // debug(l, r);
      }
    }
    // debug(x);
    s[x] += 1;
    s[x + 1] -= 1;
  }
  rep(i, 1, n) {
    s[i] += s[i - 1];
  }
  rep(i, n) {
    if (s[i] == n - 1) {
      rep(j, n) {
        cout << (a[j] ^ i) << " \n"[j + 1 == n];
      }
      return;
    }
  }
}

E.

贪心建边建立所有的关系，然后跑拓扑。

cpp
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
void solve() {
  int n;
  cin >> n;
  vc<pii> a(n);
  rep(i, n) cin >> a[i].fi; // atk
  rep(i, n) cin >> a[i].se; // def
 
  int m;
  cin >> m;
  vc<pii> b(m);
  rep(i, m) cin >> b[i].fi;
  rep(i, m) cin >> b[i].se;
 
  sort(all(a));
  sort(all(b));
 
  vc<pii> sa(n);
  vc<pii> sb(m);
 
  for (int i = n - 1; i >= 0; i--) {
    sa[i] = {a[i].se, i};
    if (i + 1 < n && sa[i + 1] > sa[i]) {
      sa[i] = sa[i + 1];
    }
  }
 
  for (int i = m - 1; i >= 0; i--) {
    sb[i] = {b[i].se, i};
    if (i + 1 < m && sb[i + 1] > sb[i]) {
      sb[i] = sb[i + 1];
    }
  }
 
  // debug(a, b);
  // debug(sa, sb);
 
  vc<vi> g(n + m);
  vi d(n + m);
  vi ans(n + m, -1);
 
  rep(i, n) {
    int j = lower_bound(all(b), pii(a[i].se + 1, 0)) - begin(b);
    if (j == m) {
      continue;
    } else {
      int x = n + sb[j].se;
      int y = i;
      g[x].pb(y);
      d[y] += 1;
    }
  }
 
  rep(i, m) {
    int j = lower_bound(all(a), pii(b[i].se + 1, 0)) - begin(a);
    if (j == n) {
      continue;
    } else {
      int x = sa[j].se;
      int y = n + i;
      g[x].pb(y);
      d[y] += 1;
    }
  }
 
  queue<int> q;
  rep(i, n + m) {
    if (!d[i]) {
      ans[i] = i < n;
      q.emplace(i);
    }
  }
 
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (auto v : g[u]) {
      ans[v] = ans[u];
      if (--d[v] == 0) {
        q.emplace(v);
      }
    }
  }
 
  ans.resize(n);
  cout << count(all(ans), 1) << " " << count(all(ans), -1) << " "
       << count(all(ans), 0) << "\n";
}

F.

假设 x=0，那么我们知道答案是 k(2k+1)n−1。

可以让 ci−1=ai−ai−1∈[−k,k]，那么我们只需确定 c1…n−1 就可以确定下来 ai，再确定最小值 t∈[0,k−1]，就可以唯一确定一个序列 a。

现在 x 不为 0，考虑容斥。

首先假设同样假设最小值为 t∈[0,x+k−1]，能算出来总方案数。

多算的部分就是所有的 ai∈[0,x)，并且满足整个序列为非负整数的方案数。可以建立一个矩阵 M，$[M^{n-1}]{i,j}就表示首为i，尾为j的方案数量。显然这部分是\sum{i,j} [M^{n-1}]_{i,j}$。

后者可以用矩阵快速幂，感觉难的部分在想到枚举最小值，然后容斥。

cpp
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
void solve() {
  int n, x, k;
  cin >> n >> x >> k;
  int ans = 1ll * (x + k) * power(2 * k + 1, n - 1) % P;
  if (x == 0) {
    cout << ans << "\n";
    return;
  }
  vector<vector<int>> base(x, vi(x));
  rep(i, x) {
    rep(j, x) {
      if (abs(i - j) <= k) {
        base[i][j] = 1;
      }
    }
  }
 
  // debug(base);
  auto mat = power(base, n - 1);
 
  rep(i, x) {
    rep(j, x) {
      ans += P - mat[i][j];
      if (ans >= P) {
        ans -= P;
      }
    }
  }
 
  cout << ans << "\n";
}

G.

wa53…