CF1976

https://codeforces.com/contest/1976/problems

A

直接 sort 即可。

B

前 $n$ 个直接做差即可，加上最后一个的答案。

C

考虑前缀和，二分出来分界点。

D

考虑合法条件是什么。

  • 首先让 ‘(‘ 为 1，’)’ 为 -1，括号序列合法仅当所有前缀和大于等于0。

  • 注意到翻转的这个区间一定是一个区间和为0的区间。

然后根据上面的条件判断即可，只需要做一个二分rmq即可。

E

忘了。

F

注意到要让桥边最少，肯定每次拉出来的都是最长链，删除一条最长链等这条路径的边权都设成0。

  • 第一次操作只能删除 $(1,x)$
  • 之后的操作都可以删除 $(x,y)$，等价删两次从 1 开始的最长链。

CF1980

https://codeforces.com/contest/1980/problems

G

分奇环和偶环考虑。

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
88
89
const int N = 2e5 + 5;
struct trie {
  int ch[N * 40][2], cnt, sz[N * 40];
  void init() {
    for (int i = 1; i <= cnt; i++) {
      ch[i][0] = ch[i][1] = 0;
      sz[i] = 0;
    }
    cnt = 1;
  }
 
  void add(int x, int v) {
    int p = 1;
    for (int i = 30; i >= 0; i--) {
      int c = x >> i & 1;
      if (!ch[p][c]) {
        ch[p][c] = ++cnt;
      }
      p = ch[p][c];
      sz[p] += v;
    }
  }
 
  int query(int x) {
    int p = 1;
    int res = 0;
    for (int i = 30; i >= 0; i--) {
      int c = (x >> i & 1) ^ 1;
      if (sz[ch[p][c]]) {
        res |= 1 << i;
      } else {
        c ^= 1;
      }
      p = ch[p][c];
    }
    return res;
  }
} a[2];
 
void solve() {
  int n, m;
  cin >> n >> m;
  vector<vc<pii>> e(n);
  int A = 0;
  rep(i, n - 1) {
    int a, b, c;
    cin >> a >> b >> c;
    --a, --b;
    e[a].pb(b, c);
    e[b].pb(a, c);
  }
  a[0].init();
  a[1].init();
 
  vi d(n);
  vi X(n);
  auto dfs = [&](auto &dfs, int u, int p) -> void {
    a[d[u]].add(X[u], 1);
    for (auto [v, w] : e[u]) {
      if (v != p) {
        d[v] = d[u] ^ 1;
        X[v] = X[u] ^ w;
        dfs(dfs, v, u);
      }
    }
  };
 
  dfs(dfs, 0, -1);
 
  rep(i, m) {
    char c;
    cin >> c;
    if (c == '^') {
      int y;
      cin >> y;
      A ^= y;
    } else {
      int v, x;
      cin >> v >> x;
      --v;
      int ans = 0;
      a[d[v]].add(X[v], -1);
      cmax(ans, a[d[v]].query(X[v] ^ x));
      cmax(ans, a[d[v] ^ 1].query(X[v] ^ x ^ A));
      a[d[v]].add(X[v], 1);
      cout << ans << " \n"[i + 1 == m];
    }
  }
}

CF1979

https://codeforces.com/contest/1979/problems

A

选择长度为 2 的区间，模拟即可。

1
2
3
4
5
6
7
8
9
10
void solve() {
  int n;
  cin >> n;
  vi a(n);
  rep(i, n) cin >> a[i];
  int ans = 1e9;
  rep(i, n - 1) cmin(ans, max(a[i], a[i + 1]));

  cout << ans - 1 << "\n";
}

B

结论

1
2
3
4
5
6
7
8
9
void solve() {
  int x, y;
  cin >> x >> y;
  int p = (x ^ y);

  int ans = p & (-p);

  cout << ans << "\n";
}

C

结论

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
void solve() {
  int n;
  cin >> n;
  vl a(n);
  rep(i, n) cin >> a[i];
  ll l = 1;
  rep(i, n) l = lcm(l, a[i]);
 
  vl b(n);
  rep(i, n) b[i] = l / a[i];
 
  ll s = 0;
  rep(i, n) s += b[i];
  if (s >= l) {
    cout << "-1\n";
    return;
  } else {
    ll g = 0;
    rep(i, n) g = gcd(g, b[i]);
    rep(i, n) b[i] /= g;
    rep(i, n) if (b[i] > INF) {
      cout << "-1\n";
      return;
    }
    rep(i, n) {
      cout << b[i] << " \n"[i + 1 == n];
    }
  }
}

D

脑子笨，写了一个哈希拼接。

实际上可以不用哈希拼接，因为最开始看错题了。

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
const int base = 131;
using ull = unsigned long long;
void solve() {
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  int c0 = 0, c1 = 0;
  rep(i, n) {
    if (s[i] == '0')
      c0++;
    else
      c1++;
  }
  int part = n / k;
  if (part % 2 == 0) {
    if (c0 != c1) {
      cout << -1 << "\n";
      return;
    }
  }
 
  vi pref(n);
  vi suf(n + 1);
  
  suf[n] = 1;
  for (int i = 0; i < k; i++) {
    pref[i] = 1;
    suf[n - 1 - i] = 1;
  }
 
  for (int i = k; i < n; i++) {
    pref[i] = pref[i - 1] & (s[i] != s[i - k]);
  }
 
  for (int i = n - 1 - k; i >= 0; i--) {
    suf[i] = suf[i + 1] & (s[i] != s[i + k]);
  }
 
  vector<int> cand;
  for (int i = 0; i < n; i++) {
    if (pref[i] && suf[i + 1]) {
      cand.push_back(i + 1);
    }
  }
 
  vc<ull> pw(n + 1);
  pw[0] = 1;
  for (int i = 0; i < n; i++) {
    pw[i + 1] = pw[i] * base;
  }
 
  ull tar0 = 0;
  ull tar1 = 0;
  rep(i, k) tar0 = tar0 * base + 48;
  rep(i, k) tar1 = tar1 * base + 49;
 
  vc<ull> f(n + 1);
  f[0] = 0;
  rep(i, n) f[i + 1] = f[i] * base + s[i];
  vc<ull> rf(n + 1);
  rf[0] = 0;
  rep(i, n) rf[i + 1] = rf[i] * base + (s[i] ^ 1);
  vc<ull> g(n + 1);
  vc<ull> rg(n + 1);
  g[n] = 0;
  rg[n] = 0;
  for (int i = n - 1; i >= 0; i--) {
    g[i] = g[i + 1] * base + s[i];
    rg[i] = rg[i + 1] * base + (s[i] ^ 1);
  }
 
  // debug(s, cand);
 
  auto rangef = [&](vc<ull> &F, int l, int r) {
    return F[r] - F[l] * pw[r - l];
  };
  auto rangeg = [&](vc<ull> &G, int l, int r) {
    return G[l] - G[r] * pw[r - l];
  };
 
  auto check = [&](int i) {
    // [i, n) + (i, 0]
    int cut = n - i;
    int x = cut / k;
    int len = cut % k;
    ull cur = rangef((x % 2 == 1) ? rf : f, i + x * k, n) * pw[k - len] + rangeg((x % 2 == 1) ? rg : g, i - (k - len), i);
 
    ull cur0 = 0;
    if (i + k <= n) {
      cur0 = rangef(f, i, i + k);
    } else {
      cur0 = rangef(f, i, n) * pw[k - (n - i)] + rangeg(g, i - (k - (n - i)), i);
      // debug(s, i, cur0);
    }
 
    ull curn = 0;
    int y = (n - 1) / k;
    if (i >= k) {
      curn = rangeg((y % 2 == 1) ? rg : g, 0, k);
    } else {
      curn = rangef((y % 2 == 1) ? rf : f, n + i - k, n) * pw[i] + rangeg((y % 2 == 1) ? rg : g, 0, i);
    }
 
    // debug(s, i);
    // debug(cur0, cur, curn);
    if (cur0 == tar0 || cur0 == tar1) 
      return cur == cur0 && cur == curn;
    else
      return false;
  };
 
  for (int i : cand) {
    if (check(i)) {
      cout << i << "\n";
      return;
    }
  }
 
  cout << -1 << "\n";
}

E

考虑枚举哪个作为右上方的点 $(x3,y3)$，知道 $x1+y1=x2+y2=x3+y3-d$，当然可能实际上不在右上方，也就是说需要翻转坐标轴。

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
void solve() {
  int n;
  cin >> n;
  int d;
  cin >> d;
  vector<int> X(n);
  vector<int> Y(n);
  for (int i = 0; i < n; i++) {
    cin >> X[i] >> Y[i];
  }
 
  rep(ox, 2) {
    rep(oy, 2) {
      vc<array<int, 4>> p(n);
      rep(i, n) {
        int x = ox ? X[i] : -X[i];
        int y = oy ? Y[i] : -Y[i];
        p[i] = array<int, 4>{x + y, x, y, i};
      }
      sort(all(p));
      map<int, vc<pii>> ok;
      for (int i = 0, j = 0; i < n; i = j) {
        while (j < n && p[i][0] == p[j][0]) {
          j++;
        }
        auto &v = ok[p[i][0] - d];
        // debug(p[i][0] - d, v, p[i][0], p[i][3]);
        for (int k = i; k < j; k++) {
          int x = p[k][1];
          int y = p[k][2];
          int l = -1, r = (int)v.size();
          while (r - l > 1) {
            int m = (l + r) / 2;
            auto [b, c] = v[m];
            // debug(b, c);
            int xb = ox ? X[b] : -X[b];
            int yb = oy ? Y[b] : -Y[b];
            int xc = ox ? X[c] : -X[c];
            int yc = oy ? Y[c] : -Y[c];
 
            // debug(xb, yb, xc, yc, x, y);
            // xb < xc
            // yb > yc
 
            // assert(xb < xc && yb > yc);
            if (xc > x) {
              r = m;
            }
            if (yb > y) {
              l = m;
            }
 
            
            if (xc <= x && yb <= y) {
              cout << p[k][3] + 1 << " " << b + 1 << " " << c + 1 << "\n";
              return;
            }
          }
        }
 
        int l = i;
        for (int k = i; k < j; k++) {
          // debug(i, j, k, p[k][1]);
          while (l < j && p[l][1] - p[k][1] < d / 2) {
            l++;
          }
          if (l < j && p[l][1] - p[k][1] == d / 2) {
            ok[p[i][0]].pb(p[k][3], p[l][3]);
          }
        }
      }
    }
  }
  cout << 0 << " " << 0 << " " << 0 << "\n";
}

F

经过题解 的数学证明。

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
using p = array<int, 2>;
 
p query(int a) {
  a = max(a, 0);
  cout << "? " << a << endl;
  int x, y;
  cin >> x >> y;
  return p{x, y};
}
 
void solve() {
  deque<int> ans;
  auto calc = [&](auto &calc, int N) -> void {
    if (N == 0) {
      return;
    }
    p cur = query(N-2);
    if (N == 1) {
      ans.pb(cur[0]);
    } else {
      if (cur[1]) {
        calc(calc, N - 1);
        if (ans.back() != cur[1]) {
          ans.pb(cur[0]);
        } else {
          ans.push_front(cur[0]);
        }
      } else {
        p q = query(0);
        calc(calc, N-2);
        ans.pb(cur[0]);
        ans.pb(q[0]);
      }
    }
  };
  int N;
  cin >> N;
  calc(calc, N);
  cout << "! ";
  for (auto i : ans) {
    cout << i << " ";
  }
  cout << endl;
}

CF1984

待补。

CF1985

H1

题意：可以改变一行/一列

注意可以枚举使哪一行哪一列变成 ‘#’，然后直接算即可。

H2

题意：可以改变一行&一列

CF1978

A

max+back.

https://codeforces.com/contest/1978/submission/266078595

B

Easy math.

https://codeforces.com/contest/1978/submission/266078580

C

奇数无解。

否则贪心，如果还有多的没贪完，那么无解。

https://codeforces.com/contest/1978/submission/266078561

D

前缀和，前缀后缀max判断一下。

https://codeforces.com/contest/1978/submission/266078542

E

只会影响相邻几个，直接暴力改即可。

https://codeforces.com/contest/1978/submission/266078517

F

按照斜线 $j-i$ 分类，每个斜线必定在一个并查集里面

然后按照因数和距离限制合并。

按照斜线统计答案，最后要特判一下 1。

https://codeforces.com/contest/1978/submission/266078466

CF1986

A

$max-min$

https://codeforces.com/contest/1986/submission/267080919

B

周围 max。

https://codeforces.com/contest/1986/submission/267080953

C

implement。

https://codeforces.com/contest/1986/submission/267080991

D

implement。

https://codeforces.com/contest/1986/submission/267081008

E

%K 分组，贪心。

https://codeforces.com/contest/1986/submission/267081026

F

求割边，可以不用 lca。

https://codeforces.com/contest/1986/submission/267125590

G

注意卡空间。

https://codeforces.com/contest/1986/submission/267081076

CF1982

A

判断是否包含。

https://codeforces.com/contest/1982/submission/267474133

B

次数不会太多，并且可能有循环节。

https://codeforces.com/contest/1982/submission/267474151

C

rmq+dp，或者这个其实是后缀和。

https://codeforces.com/contest/1982/submission/267474169

D

二维前缀和。

https://codeforces.com/contest/1982/submission/267474194

E

区间 tag 合并。

https://codeforces.com/contest/1982/submission/267474229

F

待填坑

https://codeforces.com/contest/1982/submission/267541737

CF1989

A

y>=-1

https://codeforces.com/contest/1989/submission/267764461

B

枚举公共部分。

https://codeforces.com/contest/1989/submission/267764472

C

分类讨论

https://codeforces.com/contest/1989/submission/267764497

D

发现数值大的肯定直接先选最小的，定一个阈值然后 dp。

https://codeforces.com/contest/1989/submission/267842529

E

待填坑

https://codeforces.com/contest/1989/submission/267764417

F

待填坑

CF1987

烂了。

CF1983

A

$a_i = i$

B

做差，每行每列的和%3=0

C

分类讨论。

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
void solve() {
  int N;
  cin >> N;
  vl A(N), B(N), C(N);
  rep(i, N) cin >> A[i];
  rep(i, N) cin >> B[i];
  rep(i, N) cin >> C[i];
 
  vl SA(N + 1), SB(N + 1), SC(N + 1);
  rep(i, N) {
    SA[i + 1] = SA[i] + A[i];
    SB[i + 1] = SB[i] + B[i];
    SC[i + 1] = SC[i] + C[i];
  }
 
  ll tot = 0;
  rep(N) tot += A[i];
  ll tar = (tot + 2) / 3;
 
  // debug(tot, tar);
  int j = 0;
  rep(i, N) {
    while (SA[i + 1] - SA[j + 1] >= tar) {
      j++;
    }
    if (SA[i + 1] - SA[j] >= tar && SB[j] >= tar && SC[N] - SC[i + 1] >= tar) {
      cout << j + 1 << " " << i + 1 << " " << 1 << " " << j << " " << i + 2 << " "
           << N << "\n";
      return;
    }
    if (SA[i + 1] - SA[j] >= tar && SC[j] >= tar && SB[N] - SB[i + 1] >= tar) {
      cout << j + 1 << " " << i + 1 << " " << i + 2 << " " << N << " " << 1 << " "
           << j << "\n";
      return;
    }
  }
 
  j = 0;
 
  rep(i, N) {
    while (SB[i + 1] - SB[j + 1] >= tar) {
      j++;
    }
 
    // debug(j, i, SB[i + 1] - SB[j]);
    if (SB[i + 1] - SB[j] >= tar && SA[j] >= tar && SC[N] - SC[i + 1] >= tar) {
      cout << 1 << " " << j << " " << j + 1 << " " << i + 1 << " " << i + 2 << " "
           << N << "\n";
      return;
    }
    if (SB[i + 1] - SB[j] >= tar && SC[j] >= tar && SA[N] - SA[i + 1] >= tar) {
      cout << i + 2 << " " << N << " " << j + 1 << " " << i + 1 << " " << 1 << " "
           << j << "\n";
      return;
    }
  }
 
  j = 0;
  rep(i, N) {
    while (SC[i + 1] - SC[j + 1] >= tar) {
      j++;
    }
    if (SC[i + 1] - SC[j] >= tar && SB[j] >= tar && SA[N] - SA[i + 1] >= tar) {
 
      cout << i + 2 << " " << N << " " << 1 << " " << j << " " << j + 1 << " "
           << i + 1 << "\n";
      return;
    }
    if (SC[i + 1] - SC[j] >= tar && SA[j] >= tar && SB[N] - SB[i + 1] >= tar) {
      cout << 1 << " " << j << " " << i + 2 << " " << N << " " << j + 1 << " "
           << i + 1 << "\n";
      return;
    }
  }
  cout << -1 << "\n";
}

D

逆序对奇偶性相等。

考虑 $r-l=q-p=1$ 的情况即可。

E

平均值计算。

F

前缀和，然后高位到低位贪心即可。

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
void solve() {
  int n;
  ll k;
  cin >> n >> k;
  vi a(n);
  rep(n) { cin >> a[i]; }
  int ans = 0;
  vi f(n, n);
 
  for (int d = 29; d >= 0; d--) {
    map<int, int> p;
    auto nf = f;
    for (int i = 0; i < n; i++) {
      if (p.count((a[i] ^ ans) >> d)) {
        int j = p[(a[i] ^ ans) >> d];
        nf[j] = min(nf[j], i);
      }
      p[a[i] >> d] = i;
    }
    for (int i = n - 2; i >= 0; i--) {
      nf[i] = min(nf[i], nf[i + 1]);
    }
    ll sum = 0;
    for (int i = 0; i < n; i++) {
      sum += n - nf[i];
    }
    if (sum < k) {
      ans |= 1 << d;
      f = nf;
    }
  }
  cout << ans << "\n";
}