Educational Codeforces Round 170 (Rated for Div. 2)

标签：std Educational Rated int LL Codeforces long cin cnt

写在前面
A 签到
B 结论
C 双指针
D 模拟，差分，DP，结论
E 计数，DP，
F
写在最后

写在前面

比赛地址：https://codeforces.com/contest/2025。

妈的不想上学省赛回来昏了一天了。

A 签到

发现最优的操作是先在一个屏幕操作得到最长公共前缀，然后复制到另一方上，再分别操作两方。

特判若无公共前缀时，独立操作两方更优。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    std::string s, t;
    std::cin >> s >> t;
    int n = s.length(), m = t.length(), nm = 0;
    for (int i = 0; i < std::min(n, m); ++ i) {
      if (s[i] == t[i]) ++ nm;
      else break;
    }
    if (nm) std::cout << (n + m - nm + 1) << "\n"; 
    else std::cout << n + m << "\n";
  }
  return 0;
}

B 结论

手推几层这个倒塌的杨辉三角很容易发现：

\[C(n, k) = \begin{cases} 2^k &(k<n)\\ 1 &\operatorname{k=n} \end{cases}\]

然后做完了。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
const LL p = 1e9 + 7;
//=============================================================
LL n[kN], k[kN], pw2[kN];
//=============================================================
LL solve (LL n_, LL k_) {
  if (k_ == 0 || k_ == n_) return 1;
  return pw2[k_];
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  pw2[0] = 1;
  for (int i = 1; i < kN; ++ i) pw2[i] = pw2[i - 1] * 2ll % p;
  
  int T; std::cin >> T;
  for (int i = 1; i <= T; ++ i) std::cin >> n[i];
  for (int i = 1; i <= T; ++ i) std::cin >> k[i];
  for (int i = 1; i <= T; ++ i) {
    std::cout << solve(n[i], k[i]) << "\n";
  }
  return 0;
}

C 双指针

考虑记录每种权值出现次数，并将所有权值排序，问题即求所有连续的极差不超过 \(k\) 的权值区间出现次数之和的最大值。

套路地双指针即可。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, k, a[kN], cnt[kN];
std::map<int, int> b;
//=============================================================
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    std::cin >> n >> k;
    b.clear();
    for (int i = 1; i <= n; ++ i) std::cin >> a[i], ++ b[a[i]];
    n = 0;
    for (auto [x, y]: b) a[++ n] = x, cnt[n] = y; 

    LL ans = 0, sum = 0;
    for (int l = 1, r = 0; l <= n; ) {
      if (l > r) r = l - 1, sum = 0;
      while (r + 1 <= n && (r - l + 1) < k) {
        if (sum == 0) sum += cnt[r + 1], ++ r;
        else if (a[r + 1] == a[r] + 1) sum += cnt[r + 1], ++ r;
        else break;
      }
      ans = std::max(ans, sum);
      sum -= cnt[l], ++ l;
    }
    std::cout << ans << "\n";
  }
  return 0;
}

D 模拟，差分，DP，结论

首先有限制 \(m\le 5000\)，那么若已有了 \(2\times m\) 个 0，之后的 check 一定都有贡献。

然后考虑一个显然的暴力，设 \(f_{i, j}\) 表示进行到某一回合，当前智力为 \(i\)，力量为 \(j\) 时可以得到的最大价值，转移时 \(r=0\) 即新增一条合法的对角线，\(r \not= 0\) 则枚举所有合法状态并全部加 1，可以发现这些合法状态构成一个以 \((m, m)\) 为右下角的矩形。

然后发现在暴力里，每回合的合法状态实际上只有一条对角线上的 \(O(m)\) 个，所以只需要维护对角线的状态即可。记 \(f_{i}\) 表示在某一回合智力为 \(i\) 时可以得到的最大价值，\(r=0\) 直接根据当前 \(f\) 构造新的 \(f\)，\(r\not= 0\) 时发现受影响的状态在对角线上是连续的前缀或后缀，于是考虑用差分维护 \(f\) 进行区间加即可。

上述 \(r=0\) 的转移复杂度 \(O(m)\) 级别，\(r\not= 0\) 转移复杂度 \(O(1)\)，至多进行 \(2\times m\) 次 \(r=0\) 的转移，则转移总数是 \(O(m^2 + n)\) 级别的。

最后还原数组并求最大值即可。总时间复杂度 \(O(n + m^2)\) 级别。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kM = 5010;
//=============================================================
int n, m, cnt, f[kM], temp[kM];
//=============================================================
void modify(int l_, int r_) {
  ++ f[l_], -- f[r_ + 1];
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  std::cin >> n >> m;

  for (int i = 1; i <= n; ++ i) {
    int a; std::cin >> a;
    if (cnt >= 2 * m) {
      if (a != 0) ++ f[m];
      continue;
    }

    if (a == 0) {
      for (int i = 1; i <= std::min(m, cnt); ++ i) f[i] += f[i - 1];

      ++ cnt;
      for (int i = 0; i <= std::min(m, cnt); ++ i) temp[i] = 0;
      for (int i = std::max(0, cnt - m); i <= std::min(m, cnt); ++ i) {
        temp[i] = f[i];
        if (i > 0) temp[i] = std::max(temp[i], f[i - 1]);
      }
      for (int i = 0; i <= std::min(m, cnt); ++ i) f[i] = 0;
      for (int i = std::max(0, cnt - m); i <= std::min(m, cnt); ++ i) {
        if (i == 0) f[i] = temp[i];
        if (i > 0) f[i] = temp[i] - temp[i - 1];
      }
    } else if (a > 0) {
      if (a > cnt) continue;
      modify(std::max(a, cnt - m), std::min(m, cnt));
    } else {
      a = -a;
      if (a > cnt) continue;
      modify(cnt - std::min(m, cnt), cnt - std::max(a, cnt - m));
    }
  }

  int ans = 0;
  for (int i = 1; i <= m; ++ i) f[i] += f[i - 1];
  if (cnt >= 2 * m) {
    ans = f[m];
  } else {
    for (int i = std::max(0, cnt - m); i <= std::min(m, cnt); ++ i) {
      ans = std::max(ans, f[i]);
    }
  }
  std::cout << ans << "\n";
  return 0;
}

E 计数，DP，

稍等。

F

写在最后

感觉这辈子没这么厌学过。

高中好歹还有“上了大学我要干…”这种美好的幻想现在上学又学不到东西又浪费时间而且为了有学上还不得不去卷卷也学不到东西只会更痛苦受不了了呃呃呃呃

标签：std,Educational,Rated,int,LL,Codeforces,long,cin,cnt
From： https://www.cnblogs.com/luckyblock/p/18466960