「题解」Educational Codeforces Round 170 (Rated for Div. 2)

before

我不想写作业呜呜。

A. Two Screens

Problem

A. Two Screens

Sol&Code

理解题意后发现使用复制的方法完成最长公共前缀即可。

#include <bits/stdc++.h>

typedef long long ll;
typedef std::pair<int, int> pii;

int T;
std::string s1, s2;

int main() {
  scanf("%d", &T);
  while (T--) {
    std::cin >> s1 >> s2;
    int l1 = s1.length(), l2 = s2.length();
    int now = 0;
    while (now < l1 && now < l2 && s1[now] == s2[now]) ++now;
    if (now) printf("%d\n", now + 1 + l1 - now + l2 - now);
    else printf("%d\n", l1 + l2);
  }
  return 0;
}

B. Binomial Coefficients, Kind Of

Problem

B. Binomial Coefficients, Kind Of

Sol&Code

手推一部分数据不难发现答案是 \(2\) 的幂次。

#include <bits/stdc++.h>
#define N 100001

typedef long long ll;
typedef std::pair<int, int> pii;

int T, n[N], k[N];
const int mod = 1000000007;

int qpow(int a, int b) {
  int ans = 1, base = a;
  while (b) {
    if (b & 1) ans = 1ll * ans * base % mod;
    base = 1ll * base * base % mod;
    b >>= 1;
  }
  return ans % mod;
}

int main() {
  scanf("%d", &T);
  for (int i = 1; i <= T; ++i) scanf("%d", &n[i]);
  for (int i = 1; i <= T; ++i) scanf("%d", &k[i]);
  for (int i = 1; i <= T; ++i) {
    if (k[i] == 0 || k[i] == n[i]) puts("1");
    else printf("%d\n", qpow(2, k[i]));
  }
  return 0;
}

C. New Game

Problem

C. New Game

Sol&Code

双指针维护一下从某个数字开始最多能到哪，注意之间有多少不同的数即可。

#include <bits/stdc++.h>
#define N 200001

typedef long long ll;
typedef std::pair<int, int> pii;

int T, n, k, a[N];

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    std::sort(a + 1, a + n + 1);
    int l = 1, r = 1, ans = 1, cnt_ = 1;
    while (r < n) {
      while (r < n && (a[r + 1] == a[r] || (a[r + 1] == a[r] + 1 && cnt_ < k)) ) {
        if (a[r + 1] == a[r]) ++r;
        else ++r, ++cnt_;
      }
      ans = std::max(ans, r - l + 1);
      if (r < n && a[r + 1] - a[r] > 1) ++r, l = r, cnt_ = 1;
      else {
        int gl = l;
        while (gl < n && a[gl] == a[l]) ++gl;
        l = gl, --cnt_;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

D. Attribute Checks

Problem

D. Attribute Checks

Sol&Code

设 \(f_{i,j}\) 前 \(i\) 个技能点，智力用了 \(j\) 个，最多能通过到 \(i + 1\) 个技能点之前的几个测试。

转移，f[i][j] = max(f[i][j], max(f[i - 1][j], f[i - 1][j - 1]) + ad)，其中 ad 是 \(j\) 点智力， \(i - j\) 点力量能通过的第 \(i\) 个技能点和第 \(i + 1\) 个技能点之间的测试的数量。

#include <bits/stdc++.h>

#define N 5001
#define M 2000002
#define lowbit(x) ((x) & (-x))

typedef long long ll;
typedef std::pair<int, int> pii;

int n, m, a[M], f[N][N];
struct BIT {
  int a[5001];
  void add(int x, int k) {
    while (x <= m) a[x] += k, x += lowbit(x);
  }
  int query(int x, int res = 0) {
    if (x < 0) return res;
    while (x > 0) res += a[x], x -= lowbit(x);
    return res;
  }
}b1, b2;

int main() {
  f[0][0] = 0;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  int lst = 0, now = 0, cnt = 1, ans = 0;
  while (a[now + 1] != 0) ++now;
  ++now, lst = now;
  while (now <= n) {
    while (now <= n && a[now + 1] != 0) ++now;
    if (a[now + 1] == 0) {
      // std::cout << lst << " " << now << '\n';
      for (int i = lst + 1; i <= now; ++i) {
        if (a[i] > 0) b1.add(a[i], 1);
        else b2.add(-a[i], 1);
      }
      for (int i = 0; i <= cnt; ++i) {
        int a1 = b1.query(i), a2 = b2.query(cnt - i);
        f[cnt][i] = std::max(f[cnt][i], std::max(f[cnt - 1][i - 1], f[cnt - 1][i]) + a1 + a2);
        // std::cout <<a1 << " " << a2 << " " << cnt << " " << i << " " << f[cnt][i] << '\n';
      }
      for (int i = lst + 1; i <= now; ++i) {
        if (a[i] > 0) b1.add(a[i], -1);
        else b2.add(-a[i], -1);
      }
      ++now, lst = now, ++cnt;
    }
  }
  for (int i = 0; i <= m; ++i) ans = std::max(ans, f[m][i]);
  printf("%d\n", ans);
  return 0;
}

/*
9 3
0 0 1 0 2 -3 -2 -2 1
*/

After

唉唉。。

好多作业。

不想上课。。

好久没打 cf 了，好多笨蛋错误，初始值错了两发，数组开小了一发。我是笨蛋。

C 和 D 写了好久，感觉不会写代码了。