牛客练习赛122

• 写在前面
• A
• B
• C
• D
• E
• 写在最后

写在前面

比赛地址：https://ac.nowcoder.com/acm/contest/75768。

因为 suzt 大神在打所以也来凑一凑热闹。

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 n, m;
  std::cin >> n >> m;
  while (n --) {
    int c = 0;
    for (int i = 1; i <= m; ++ i) {
      int x; std::cin >> x;
      c += (x == 1 ? 1 : -1);
    }
    std::cout << abs(c) << "\n";
  }
  return 0;
}

B

签到。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, a[kN], b[kN], p[kN];
//=============================================================
//=============================================================
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;
    for (int i = 1; i <= n; ++ i) std::cin >> a[i];
    for (int i = 1; i <= n; ++ i) p[i] = 0;
    int flag = 1;
    for (int i = 1; i <= n; ++ i) {
      std::cin >> b[i];
      if (p[a[i]] == 0) p[a[i]] = b[i];
      else if (p[a[i]] != b[i]) flag = 0;
    }
    std::cout << (flag ? "Yes\n" : "No\n");
  }
  return 0;
}

C

设 \(n\le m\)，手玩下发现 \(n= 1\) 无解，\(n=2\) 只可以往一个方向跳，\(m \ge 4\) 时所有位置均可遍历到，于是给小范围打个表即可。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
int ans[5][5] = {
  0, 0, 0, 0, 0,
  0, 0, 0, 0, 0,
  0, 0, 0, 1, 1,
  0, 0, 1, 8, 12,
  0, 0, 1, 12, 16
};
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    int n, m; std::cin >> n >> m;
    if (n <= 1 || m <= 1) {
      std::cout << 1 << "\n";
      continue;
    }
    if (n == 2 || m == 2) {
      if (n != 2) std::swap(n, m);
      std::cout << 1 + (m - 1) / 2 << "\n";
      continue;
    }
    if (n <= 4 && m <= 4) {
      std::cout << ans[n][m] << "\n";
      continue;
    }
    std::cout << 1ll * n * m << "\n";

  }
  return 0;
}

D

区间 DP

发现将圆直接断开没有影响，问题变为给定 \(m\) 条线段，要求这些线段之间要么相互包含要么没有任何交点，求少能删多少。

可能有重复线段，先预处理 \(g_{l, r}\) 表示端点为 \(l, r\) 的线段中权值最大的。

考虑求最多能保留多少，考虑区间 DP，设 \(f_{l, r}\) 表示完全位于区间 \([l, r]\) 的线段最多能保留多大的价值，初始化 \(\forall 1\le i\le n, f_{i, i}=0\)。枚举分界点的区间 DP 转移显然只能是 \(O(n^3)\) 的，绝对跑不过去，但对于此题发现转移时仅需考虑线段的端点即可覆盖所有有贡献的分界点，于是考虑按长度枚举区间，有如下三种转移：

• \(\max(f_{l + 1, r}, f_{l, r - 1}) \rightarrow f_{l, r}\)，表示不新增区间的贡献，继承更小区间的答案即可。
• \(f_{l + 1, r - 1} + g_{l, r} \rightarrow f{l, r}\)，新增一条最外层的线段。
• 维护集合 \(s_r\) 表示右端点为 \(r\) 的左端点的数量，则 \(\forall p\in s_r,\ f_{l, p - 1} + f_{l, r}\) 表示新增没有交点的线段的贡献。

发现第三种转移总共只会进行 \(O(nm)\) 次，其他转移每轮只会进行常数次，则总时间复杂度 \(O(n^2 + nm)\) 级别。

//区间 DP
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define pii std::pair<int,int>
#define mp std::make_pair
const int kN = 2e3 + 10;
const LL kInf = 1e18 + 2077;
//=============================================================
int n, m;
LL s, f[kN][kN];
std::map <pii, pii> maxw;
std::vector <int> v[kN];
//=============================================================
//=============================================================
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 <= m; ++ i) {
    int l, r, w; std::cin >> l >> r >> w;
    if (l > r) std::swap(l, r);
    s += 1ll * w;
    if (maxw.count(mp(l, r))) {
      if (maxw[mp(l, r)].first < w) maxw[mp(l, r)] = mp(w, l);
    } else {
      maxw[mp(l, r)] = mp(w, l);
    }
  }

  for (int i = 1; i <= n; ++ i) {
    for (int j = 1; j < n; ++ j) {
      if (!maxw.count(mp(j, i))) continue;
      v[i].push_back(j);
    }
  }
  
  for (int len = 2; len <= n; ++ len) {
    for (int l = 1, r = l + len - 1; r <= n; ++ l, ++ r) {
      f[l][r] = f[l + 1][r - 1];
      f[l][r] = std::max(f[l][r], std::max(f[l + 1][r], f[l][r - 1]));
      if (maxw.count(mp(l, r))) {
        f[l][r] = std::max(f[l][r], f[l - 1][r + 1] + maxw[mp(l, r)].first);
      }
      for (auto x: v[r]) {
        if (x < l) continue;
        f[l][r] = std::max(f[l][r], f[l][x - 1] + f[x][r]);
        f[l][r] = std::max(f[l][r], f[l][x - 1] + f[x + 1][r - 1] + maxw[mp(x, r)].first);
      }
    }
  }
  std::cout << s - f[1][n];
  return 0;
}
/*
6 6
1 4 1
2 5 1
3 6 1
4 1 1
5 2 1
6 3 1

6 6
1 2 1
2 4 5
2 3 1
3 4 1
4 5 1
5 6 1
*/

E

上课再写吸吸

写在最后

学到了什么

• D：我草区间 DP 有 \(O(n^2)\) 的太牛逼了，考虑区间合并时根据性质仅考虑有贡献的区间分界点。
• E