专栏文章

251018cch模拟赛总结

wwendywu
个人记录参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minkqfly
此快照首次捕获于
2025/12/02 04:00
3 个月前
此快照最后确认于
2025/12/02 04:00
3 个月前
查看原文
100 + 100 + 0 + 20 = 220
挂了80pts80ptsqwq
我T2居然过了！！！！：）
但是写了94行：）wssb我太菜了

A - matrix

这次T1只写了28min28min：）我终于有救了一次
注意到，每个数字都互不相同，而且只会变大
我们可以把每一行和每一列的最大值记下来（因为只会变大，所以只要最大值），然后用mapmap统计每个最大值（在记录的最大值里面）的出现次数。因为所有数字互不相同，所以出现了22遍的就是题目要求的最大值
修改的时候，把它跟他所在的行和列的最大值比较一下，修改一下mapmap和ansans就好了
CPP
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 2e5 + 5;

int n, m, q, mx[N][2], ans;
unordered_map <int, int> mp;

int main () {
  // freopen("matrix.in", "r", stdin);
  // freopen("matrix.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m >> q;
  for (int i = 1; i <= n; i++) {
    for (int j = 1, x; j <= m; j++) {
      cin >> x;
      mx[i][0] = max(mx[i][0], x);
      mx[j][1] = max(mx[j][1], x);
    }
  }
  for (int i = 1; i <= n; i++) {
    mp[mx[i][0]]++;
  }
  for (int i = 1; i <= m; i++) {
    mp[mx[i][1]]++;
    if (mp[mx[i][1]] == 2) ans++;
  }
  for (int x, y, z; q--;) {
    cin >> x >> y >> z;
    if (mx[x][0] < z) {
      mp[mx[x][0]]--;
      mp[z]++;
      if (mp[mx[x][0]] == 1) ans--;
      if (mp[z] == 2) ans++;
      mx[x][0] = z;
    }
    if (mx[y][1] < z) {
      mp[mx[y][1]]--;
      mp[z]++;
      if (mp[mx[y][1]] == 1) ans--;
      if (mp[z] == 2) ans++;
      mx[y][1] = z;
    }
    cout << ans << '\n';
  }
  return 0;
}

B - virus

哇我居然A了！：）我就是T2最唐做法 + 最长代码，不接受反驳
首先发现当一个病毒被撞没了之后，它就不会再出现了。所以稳定的意思就是它不可能被覆盖，可行就是有办法不被覆盖
所以稳定的病毒就是那些在它初始的位置上最优先的病毒
可行的话，就是有任意一个细胞，比这个病毒更优先的可以被其它的病毒都撞死
所以可以枚举病毒，然后枚举细胞，然后看它是不是满足上一句话的条件
然后我们发现暴力做是O(n4)O(n^4)，会炸，所以要预处理一些东西
我们发现，对于每个细胞，“比这个病毒更优先的可以被其它的病毒都撞死”是有单调性的，如果一个病毒可以，那么比它更优先的也可以，所以可以二分这个病毒
然而还是不知道怎么checkcheck，我们想到处理出每个点能直接撞死哪些，用bitsetbitset存，然后用bitsetbitset乱搞就能checkcheck了：）
CPP
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 505;

int n, a[N][N], p, f[N];
bitset <N> b[N], qwq;
vector <int> ans;

bool check (int x, int y) {
  if (y == 1) return 1;
  bitset <N> tmp, tmp1;
  for (int i = y; i <= n; i++) {
    tmp |= b[a[x][i]];
  }
  for (int i = 1; i < y; i++) {
    tmp1 |= qwq << a[x][i] - 1;
  }
  // cout << x << ' ' << y << '\n';
  // cout << tmp << ' ' << tmp1 << '\n';
  tmp &= tmp1;
  if (tmp == tmp1) return 1;
  return 0;
}

int main () {
  // freopen("virus.in", "r", stdin);
  // freopen("virus.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  qwq = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> a[i][j];
      if (a[i][j] == i) {
        for (int k = 1; k < j; k++) {
          b[a[i][k]] |= qwq << i - 1;
        }
      }
    }
  }
  cin >> p;
  if (p == 1) {
    for (int i = 1; i <= n; i++) {
      if (i == a[i][1]) {
        ans.emplace_back(i);
      }
    }
    cout << ans.size() << '\n';
    for (int i : ans) {
      cout << i << ' ';
    }
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    int l = 1, r = n;
    while (l <= r) {
      int mid = l + r >> 1;
      if (check(i, mid)) {
        f[i] = mid;
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    int cch = 0;
    for (int j = 1; j <= n; j++) {
      for (int k = 1; k <= f[j]; k++) {
        if (a[j][k] == i) {
          cch = 1;
          break;
        }
      }
      if (cch == 1) {
        break;
      }
    }
    if (cch) {
      ans.emplace_back(i);
    }
  }
  cout << ans.size() << '\n';
  for (int i : ans) {
    cout << i << ' ';
  }
  return 0;
}
/*
qi si wo le !! wo bu hui yong bitset !!!!!
*/

C - monster

没想到我的暴力调出来就有80pts80pts，再稍微改一改就有100pts100pts了qwq
放过没学过上下界优化的**吧qwq
直接dp，设f[i][j][0/1]f[i][j][0/1]表示以ii为根的子树中，只选jj个点，选/不选ii的最小值
然后背包，转移见补题代码
考场代码：
CPP
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const LL N = 2e3 + 5, inf = 1e18;

LL a[N], n, f[N][N][2], sz[N];
vector <int> v[N];

void dfs (int x, int fa) {
  if (v[x].size() == 1 && x != 1) {
    f[x][1][1] = a[x];
    f[x][0][0] = 0;
    sz[x] = 1;
    return;
  }
  sz[x] = 1;
  f[x][0][0] = 0;
  f[x][1][1] = a[x];
  for (int i : v[x]) {
    if (i == fa) continue;
    dfs(i, x);
    sz[x] += sz[i];
    for (LL j = sz[x]; j >= 0; j--) {
      for (LL k = min(j, sz[i]); k >= 0; k--) {
        if (j != sz[x]) {
          f[x][j][0] = min(f[x][j][0], min(f[i][k][0], f[i][k][1]) + f[x][j - k][0]);
        }
        if (j != k) {
          f[x][j][1] = min(f[x][j][1], min(f[i][k][0] + f[x][j - k][1], f[i][k][1] + f[x][j - k][1] + a[i])) + a[x];
        }
      }
    }
  }
}

int main () {
  freopen("monster.in", "r", stdin);
  freopen("monster.out", "w", stdout);
  cin >> n;
  fill(&f[0][0][0], &f[n + 1][0][0], inf);
  for (int i = 1, x, y; i < n; i++) {
    cin >> x >> y;
    v[x].emplace_back(y);
    v[y].emplace_back(x);
  }
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  dfs(1, 1);
  for (int i = 0; i <= n; i++) {
    cout << min(f[1][n - i][0], f[1][n - i][1]) << ' ';
  }
  return 0;
}
补题代码：
CPP
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const LL N = 2e3 + 5, inf = 1e18;

LL a[N], n, f[N][N][2], sz[N];
vector <int> v[N];

void dfs (int x, int fa) {
  if (v[x].size() == 1 && x != 1) {
    f[x][1][1] = a[x];
    f[x][0][0] = 0;
    sz[x] = 1;
    return;
  }
  sz[x] = 1;
  f[x][0][0] = 0;
  f[x][1][1] = a[x];
  for (int i : v[x]) {
    if (i == fa) continue;
    dfs(i, x);
    for (LL j = sz[x]; j >= 0; j--) {
      for (LL k = sz[i]; k >= 0; k--) {
        f[x][j + k][0] = min(f[x][j + k][0], min(f[i][k][0], f[i][k][1]) + f[x][j][0]);
        f[x][j + k][1] = min(f[x][j + k][1], min(f[i][k][0] + f[x][j][1], f[i][k][1] + f[x][j][1] + a[i]));
        // if (x == 4 && j == 2) {
        //   cout << k << ' ' << f[i][k][0] << ' ' << f[x][j - k][1] << ' ' << f[i][k][1] << ' ' << f[x][j - k][1] << ' ' << a[i] << '\n';
        // }
      }
    }
    sz[x] += sz[i];
  }
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  fill(&f[0][0][0], &f[n + 1][0][0], inf);
  for (int i = 1, x, y; i < n; i++) {
    cin >> x >> y;
    v[x].emplace_back(y);
    v[y].emplace_back(x);
  }
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  dfs(1, 1);
  for (int i = 0; i <= n; i++) {
    cout << min(f[1][n - i][0], f[1][n - i][1]) << ' ';
  }
  return 0;
}
qwqwqwqwqwq痛失8080分，要是没挂，或者早开始写10min10min就能上300300了qwqwqwqwqwq
aaaaaaaa要是学过上下界优化就能A了qwqwqwqwq

D - collect

直接大暴力20pts20pts，结果交到vjudgevjudge上面有70pts70pts
CPP
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 5e5 + 5;

LL n, m, ans, ans1, ans2, ans3, ans4;
vector <int> v[N * 2];
struct aa {
  LL a, x;
} a[N], b[N];

int main () {
  // freopen("collect.in", "r", stdin);
  // freopen("collect.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].a;
  }
  for (int i = 1; i <= n; i++) {
    cin >> a[i].x;
    a[i].x += a[i - 1].x;
  }
  for (int i = 1; i <= m; i++) {
    cin >> b[i].a;
    v[b[i].a].emplace_back(i);
  }
  for (int i = 1; i <= m; i++) {
    cin >> b[i].x;
    b[i].x += b[i - 1].x;
  }
  for (int i = 1; i <= n; i++) {
    set <int> s;
    s.insert(0); s.insert(m + 1);
    for (int j = i; j <= n; j++) {
      for (int k : v[a[j].a]) {
        s.insert(k);
      }
      int qwq = 0;
      for (int k : s) {
        if (k == 0) continue;
        ans = max(ans, b[k - 1].x - b[qwq].x + a[j].x - a[i - 1].x);
        if (ans == b[k - 1].x - b[qwq].x + a[j].x - a[i - 1].x) {
          ans1 = i, ans2 = j, ans3 = qwq + 1, ans4 = k - 1;
        }
        qwq = k;
      }
    }
  }
  if (b[m].x > ans) {
    ans = b[m].x;
    cout << ans << "\n0 0\n1 " << m << '\n';
    return 0;
  }
  cout << ans << '\n' << ans1 << ' ' << ans2 << '\n' << ans3 << ' ' << ans4;
  return 0;
}

T2想到了正解结果因为没用过bitsetbitset不敢写，拖了30min30min结果还是只能写bitsetbitset，要是有30min30min我就能调出T3了qwq

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...