专栏文章

251028cch模拟赛总结

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

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@minh4l05
此快照首次捕获于
2025/12/02 02:19
3 个月前
此快照最后确认于
2025/12/02 02:19
3 个月前
查看原文
100 + 100 + 20 + 100 = 320
md差点就能AK了qwq
T3居然是人类智慧，我写了一个双loglog结果T了
我再也不用mapmap了，用了我是sb
T4第一次测的时候只有40pts40pts：）事实证明，cch所有的spjspj都会炸：）

A - queue

首先想到暴力做法：
枚举VV，然后枚举首项，然后算有几个不同
然后优化一下：先假设首项是00，然后算出每个人要变多少才能到他应该的身高。然后找到出现最多的这个变化量，把首项变成这个。
然后我们突然发现，这样复杂度其实是对的：）
因为VV的个数只有wn\frac{w}{n}，然后其他的是O(n)O(n)的，所以复杂度就是：O(wnn)=O(w)O(\frac{wn}{n}) = O(w)
CPP
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 3e5 + 5;

int n, w, a[N], c[N * 2], ans;

int main () {
  // freopen("queue.in", "r", stdin);
  // freopen("queue.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> w;
  ans = n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i * (n - 1) <= w; i++) {
    int mx = 0;
    for (int j = 1; j <= n; j++) {
      c[a[j] - j * i + w]++;
      if (a[j] - j * i + i < 1 || a[j] - j * i + i * n > w) continue;
      mx = max(mx, c[a[j] - j * i + w]);
    }
    ans = min(ans, n - mx);
    for (int j = 1; j <= n; j++) {
      c[a[j] - j * i + w]--;
    }
  }
  cout << ans;
  return 0;
}

B - compare

20min20min切掉了T1，心态直接飞起来了：）
去了趟厕所庆祝一下，回来之后又想出了T2：）
首先发现，当一个点相邻的都是比它小的，它就不可能被删掉
所以就开个数组统计一下每个点相邻的比它大的数量，同时算答案就行了：）
CPP
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 1e5 + 5;

int n, m, ans, q, s[N];

bool check (int x) {
  return !s[x];
}

void add (int x, int y) {
  if (x < y) swap(x, y);
  if (check(y)) ans--;
  s[y]++;
}

void D (int x, int y) {
  if (x < y) swap(x, y);
  s[y]--;
  if (check(y)) ans++;
}

int main () {
  // freopen("compare.in", "r", stdin);
  // freopen("compare.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  ans = n;
  for (int i = 1, x, y; i <= m; i++) {
    cin >> x >> y;
    add(x, y);
  }
  cin >> q;
  for (int t, x, y; q--;) {
    cin >> t;
    if (t == 3) {
      cout << ans << '\n';
    } else if (t == 1) {
      cin >> x >> y;
      add(x, y);
    } else {
      cin >> x >> y;
      D(x, y);
    }
  }
  return 0;
}

C - xor

md炸掉了qwq
用异或前缀和和异或后缀和，然后按位考虑。
先是把一堆并起来比后面大的情况：枚举后面那个数的每一位，对于一个是00的位，把它变成1，后面的不考虑。然后异或一下它前面那个数的前缀异或和，取前面的前几位符合要求的异或和的位置的最大值。算一下是合并多少次再跟ansans取minmin就好了
然后因为细节太多调了将近1h1h，本来应该2h2h切完T1-3的，结果写了3h3hqwq
*，怎么能合并很多个啊。。。。炸成2020了qwq
结果别人写的人类智慧居然是可以证的qwq
CPP
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 2e5 + 5;

int t, n, a[N], s[N], ans;
map <int, int> mp[35];

void add (int x, int y) {
  int sum = 0;
  for (int i = 30; i >= 0; i--) {
    if (x & (1 << i)) {
      sum += 1 << i;
    }
    mp[i][sum] = y;
  }
}

int main () {
  freopen("xor.in", "r", stdin);
  freopen("xor.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  for (cin >> t; t--;) {
    cin >> n;
    ans = n;
    for (int i = 0; i <= 30; i++) {
      mp[i].clear();
      mp[i][0] = 1;
    }
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
      s[i] = s[i - 1] ^ a[i];
      if (i == 1) continue;
      int sum = 0;
      for (int j = 30; j >= 0; j--) {
        if (a[i] & (1 << j)) {
          sum += 1 << j;
        } else {
          if (!mp[j][(s[i - 1] ^ (sum + (1 << j))) - (s[i - 1] & (1 << j) - 1)]) continue;
          ans = min(ans, i - 1 - mp[j][(s[i - 1] ^ (sum + (1 << j))) - (s[i - 1] & (1 << j) - 1)]);
          // cout << i << ' ' << ans << ' ' << j << '\n';
        }
      }
      add(s[i - 1], i);
    }
    for (int i = 0; i <= 30; i++) {
      mp[i].clear();
      mp[i][0] = n;
    }
    s[n + 1] = 0;
    s[n] = a[n];
    for (int i = n - 1; i >= 1; i--) {
      s[i] = s[i + 1] ^ a[i];
      int sum = 0;
      for (int j = 30; j >= 0; j--) {
        if (a[i] & (1 << j)) {
          if (mp[j][(s[i + 1] ^ sum) - (s[i + 1] & (1 << j) - 1)])
            ans = min(ans, mp[j][(s[i + 1] ^ sum) - (s[i + 1] & (1 << j) - 1)] - i - 1);
          sum += 1 << j;
        }
      }
      add(s[i + 1], i);
    }
    if (ans == n) {
      cout << "-1\n";
      continue;
    }
    cout << ans << '\n';
  }
  return 0;
}
补题的代码：
CPP
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 1e5 + 5;

int t, n, a[N], s[N];

int main () {
  for (cin >> t; t--;) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
      s[i] = s[i - 1] ^ a[i];
    }
    int ans = n;
    for (int i = 3; i <= n; i++) {
      for (int j = i - 2; j >= max(1, i - 800); j--) {
        if ((s[i - 1] ^ s[j - 1]) > a[i]) {
          ans = min(ans, i - 1 - j);
        }
      }
    }
    for (int i = 1; i + 2 <= n; i++) {
      for (int j = i + 2; j <= min(n, i + 800); j++) {
        if (a[i] > (s[i] ^ s[j])) {
          ans = min(ans, j - i - 1);
        }
      }
    }
    if (ans == n) {
      cout << "-1\n";
    } else {
      cout << ans << '\n';
    }
  }
  return 0;
}

D - yugo

刚看完题的20min20min完全没有思路
突然想到会不会是图论，于是把样例的图画了出来（每个ll和rr之间连一条边）
然后发现是给边定向，然后让每个点的出度都是偶数
所以可以先假设每条边都指向ll，然后把是奇数的点之间的路径上的边都反过来
然后不知道怎么反，又烧烤了10min10min没思路，这时只剩下40min40min了，决定到11:3011:30就打暴力
然后就到了11:3011:30，开始打暴力。
暴力刚开始打，突然又想到了dfsdfs树。然后发现它其实就是在树上，如果一条边下面的子树里面的奇数点的个数为奇数，这个边就要反过来。
无解就是一个连通块里面的奇数点个数是奇数
感觉正解比暴力好打，赶紧把打一半的暴力删了，然后在还剩10min10min的时候打完了正解：）
CPP
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 1e6 + 5;

int T, n, m, c[N], s[N], vis[N], cc[N];
struct edge {
  int x, i;
};
vector <edge> v[N];
struct aa {
  int l, r, ans;
} a[N];

void dfs (int x) {
  vis[x] = 1;
  s[x] = c[x] & 1;
  for (edge i : v[x]) {
    if (vis[i.x]) continue;
    dfs(i.x);
    if (s[i.x]) {
      s[x] ^= 1;
      a[i.i].ans ^= 1;
      c[a[i.i].l]--;
      c[a[i.i].r]++;
    }
  }
}

int main () {
  // freopen("yugo.in", "r", stdin);
  // freopen("yugo.out", "w", stdout);
  cin >> T >> n >> m;
  for (int i = 1; i <= m; i++) {
    cin >> a[i].l >> a[i].r;
    a[i].ans = 0;
    c[a[i].l]++;
    v[a[i].l].emplace_back((edge){a[i].r, i});
    v[a[i].r].emplace_back((edge){a[i].l, i});
  }
  for (int i = 1; i <= n; i++) {
    if (vis[i]) continue;
    dfs(i);
    if (s[i]) {
      cout << "Yugoslavia is unstable!";
      return 0;
    }
  }
  for (int i = 1; i <= m; i++) {
    if (a[i].ans) {
      cc[a[i].r]++;
      if (cc[a[i].r] * 2 <= c[a[i].r]) {
        cout << "2 ";
      } else {
        cout << "4 ";
      }
    } else {
      cc[a[i].l]++;
      if (cc[a[i].l] * 2 <= c[a[i].l]) {
        cout << "1 ";
      } else {
        cout << "3 ";
      }
    }
  }
  return 0;
}

T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
T3人类智慧怎么证
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！
我再也不用mapmap了！！

评论

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

正在加载评论...