cf1996

A.

先用 4 填，填不了用 2.

被 codeforces better 骗了，过了样例，A wa2

void solve() {
  int N; cin >> N;
  int ANS = N / 4;
  if (N % 4 == 2) {
    ANS++;
  }
  cout << ANS << "\n";
}

B.

手动模拟.

void solve() {
  int N; cin >> N;
  int K; cin >> K;
  vc<vi> A(N, vi(N));
  rep(i, N) rep(j, N) {
    char c; cin >> c;
    A[i][j] = c - '0';
  }
  for (int i = 0; i < N; i += K) {
    for (int j = 0; j < N; j += K) {
      cout << A[i][j];
    }
    cout << "\n";
  }
}

C.

前缀和，$A_{i,j}$ 表示前 $i$ 个有多少个 $j$ 字符，$B_{i,j}$ 同理。

然后可以表示出区间 $[l,r]$ 各自含有多少个 $j$ 字符。

简单计算即可。

void solve() {
  int N, Q; cin >> N >> Q;
  vc<array<int, 26>> A(N+1);
  vc<array<int, 26>> B(N+1);
  string a, b;
  cin >> a >> b;
  rep(i, N) {
    A[i + 1] = A[i];
    A[i+1][a[i]-'a']++;
    B[i+1] = B[i];
    B[i+1][b[i]-'a']++;
  }

  rep(Q){
    int l, r; cin >> l >> r;
    --l;
    int ans = 0;
    rep(j, 26) {
      int aa = A[r][j] - A[l][j];
      int bb = B[r][j] - B[l][j];
      ans += abs(aa - bb);
    }
    cout << ans / 2 << "\n";
  }
}

D.

考虑到可以先放缩。

弱化条件，$ab \leq N, a \leq X$，这样我们可以确定，枚举 $(a,b)$ 的复杂度不会超过调和级数 $O(N \log N)$，然后 $c$ 必然是连续的一段，直接计算即可。

void solve() {
  int N, X;
  cin >> N >> X;

  ll ans = 0;
  for (int a = 1; a <= X; a++) {
    for (int b = 1; b <= N / a; b++) {
      if (a + b >= X) {
        break;
      }
      int rem = N - a * b;
      int c = min(X - a - b, rem / (a + b));
      ans += c;
    }
  }
  cout << ans << "\n";
}

E.

弱化问题，有多少个区间 $[x,y]$ 满足 $0,1$ 个数相等。

• 考虑把 ‘1’ 设成 1，’0’ 设成 -1，使用 map 扫一遍就可以做了。
• 具体的，枚举右端点，记录有多少个符合条件的左端点。

注意到包含 $[x,y]$ 的区间 $[l,r]$ 的个数有 $x \times (n+1-y)$ 个。

考虑枚举 $y$，将 $(n+1-y)$ 的这部分贡献丢给 $y$，也就是让右端点带权。

剩下的权重丢给左端点解决，也就是把 $x$ 丢给 map 里面处理贡献，原本弱化的问题是只加1，现在变成加 $x$。

void solve() {
  string s;
  cin >> s;
  int N = sz(s);

  vi S(N+1);
  rep(N) {
    S[i+1] = S[i] + (s[i] == '1' ? 1 : -1);
  }

  mint ans = 0;
  map<int, mint> mp;
  rep(N+1){
    ans += mp[S[i]]*(N+1-i);
    mp[S[i]]+=i+1;
  }
  cout<<ans.val()<< "\n";
}

F.

如果 $K$ 很小，考虑怎么贪心，肯定是每次都取最大的，然后重新丢回堆里，一直取到 $K$ 个为止。

正确性显然，因为丢回去的值不可能比原来的值更大。

可以观察到，选的数越多，那么取的值越小，二分这个值 $x$，使得我选取的 $K$ 个数都 $\geq x$。

但是注意到

• 可能 $\geq x$ 的数字可能会有 $C \geq K$ 个，此时应该减去多余的部分。
• 不足 $K$ 个，说明最后的部分都是 0，略去。

void solve() {
  ll N, K;
  cin >> N >> K;
  vl A(N), B(N);
  rep(N) cin >> A[i];
  rep(N) cin >> B[i];

  auto check = [&](int x) {
    ll cur = 0;
    rep(i, N) {
      if (A[i] >= x)
        cur += (A[i] - x) / B[i] + 1;
    }
    return cur;
  };

  ll l = 0, r = INF + 2;
  while (r - l > 1) {
    int m = (l + r) / 2;
    if (check(m) >= K) {
      l = m;
    } else {
      r = m;
    }
  }
  ll cur = check(l);

  ll ans = 0;
  rep(i, N) {
    if (A[i] < l) continue;
    int c = (A[i] - l) / B[i];
    int aa = A[i] - c * B[i];
    int bb = A[i];
    ll t = 1ll * (aa + bb) * (c + 1) / 2;
    ans += t;
  }
  if (cur >= K) {
    ans -= l * (cur - K);
  }

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

G.

题意简化：给定 $m$ 组 $(a,b)$，可以选择将 $[a+1,b]$ 整体加 $1$，也可以选择将 $[b+1,a+n]$ 整体加 $1$，使得 $0$ 个数最多。（$0$ 就是不需要建边的情况）

假设选择的所有区间是 $(l_1,r_1) \dots (l_m,r_m)$

注意到我可以枚举右端点 $R$，表示我选定的所有区间的 $r_i \leq R$。

此时我可以知道我右端点的右侧是一定不需要建边的，并且只需要关心左端点有多少边是不用建边（也就是值为 $0$）的，注意到所有边的值，一定都是 非负整数，可以采用线段树维护区间最小值并且同时维护次数来完成。剩余的部分就只有一个懒标记。

void solve() {
  int N, M;
  cin >> N >> M;
  vc<vc<pii>> g(N * 2);
  rep(i, M) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    g[b].pb(a, b);
    g[a + N].pb(b, a);
    g[a + N].pb(b, a + N);
    g[b + N].pb(a + N, b);
    g[b + N].pb(a + N, b + N);
  }
  build(0, N * 2, 1);
  int ans = N;
  rep(cur, N * 2) {
    for (auto [i, j] : g[cur]) {
      if (i < j) {
        upd(i + 1, j, 0, N * 2, 1, 1);
      } else {
        upd(j + 1, i, 0, N * 2, 1, -1);
      }
    }
    if (cur >= N - 1) {
      auto [x, y] = query(0, cur, 0, N * 2, 1);
      if (x > 0) {
        y = 0;
      }
      cmin(ans, cur + 1 - y);
    }
  }

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

• 学习了一下 jiangly 的随机化做法，大概思路是，我这题其实求的是最小并集，我可以通过转化：全集是n的大小，减掉最大补集的交集的大小即可。