专栏文章

251115noip模拟赛总结

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

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@min7op4j
此快照首次捕获于
2025/12/01 21:55
3 个月前
此快照最后确认于
2025/12/01 21:55
3 个月前
查看原文
80 + 100 + 20 + 24 = 224：）
没想到T2都过了，结果T1炸了qwqwqwqwqwq
wssb！！！

A - mexdnc

wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wszrr！！！
最初的序列的mexmex叫做mmmm
如果m=0m = 0就判一下有没有00
如果m<mmm < mm，就输出22
如果m=mmm = mm，就输出11
如果m>m >最大能搞出来的，就输出−1-1
然后就贪心地分出mexmex最大的，在mm里面减掉
但是这样会炸，所以要把每次选的最大的的mexmex值预处理出来，作前缀和，然后二分
然后我就通过了所有的样例，提交
CPP
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 1e5 + 5;

LL t, n, q, a[N], b[N][3];

int main () {
  // freopen("mexdnc2.in", "r", stdin);
  // freopen("mexdnc.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  for (cin >> t; t--;) {
    cin >> n >> q;
    fill(a, a + n + 1, 0);
    for (int i = 1, aa, bb; i <= n; i++) {
      cin >> aa >> bb;
      if (aa > n) continue;
      a[aa] = bb;
      if (aa != 0) {
        a[aa] = min(a[aa], a[aa - 1]);
      }
    }
    a[n + 1] = 0;
    int cnt = 0;
    for (LL i = n; i >= 0; i--) {
      if (a[i] > a[i + 1]) {
        cnt++;
        b[cnt][0] = b[cnt - 1][0] + (i + 1) * (a[i] - a[i + 1]);
        b[cnt][1] = b[cnt - 1][1] + a[i] - a[i + 1];
        b[cnt][2] = i + 1;
        // cout << b[cnt][0] << ' ' << b[cnt][1] << '\n';
      }
    }
    for (LL m; q--;) {
      cin >> m;
      if (m == 0) {
        if (a[0]) {
          cout << "-1\n";
        } else {
          cout << "1\n";
        }
        continue;
      }
      if (m < b[1][0] / b[1][1]) {
        cout << "2\n";
        continue;
      }
      if (m == b[1][0] / b[1][1]) {
        cout << "1\n";
        continue;
      }
      if (b[cnt][0] < m) {
        cout << "-1\n";
        continue;
      }
      if (b[cnt][0] == m) {
        cout << b[cnt][1] << '\n';
        continue;
      }
      int l = 1, r = cnt, qwq = cnt;
      while (l <= r) {
        int mid = l + r >> 1;
        if (b[mid][0] > m) {
          qwq = mid;
          r = mid - 1;
        } else {
          l = mid + 1;
        }
      }
      LL tmp = (m - b[qwq - 1][0]) / b[qwq][2] + ((m - b[qwq - 1][0]) % b[qwq][2] ? 1 : 0);
      tmp += b[qwq - 1][1];
      cout << tmp << '\n';
    }
  }
  return 0;
}
获得了高达80pts80pts的高分！！！（全班第5低qwq
然后发现是漏了一种情况，就是没有00但m>0m > 0
加了一个
CPP
if (!a[0]) {
  cout << "-1\n";
  continue;
}
就过了qwq
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wszrr！！
wszrr！！
wszrr！！
wszrr！！
wszrr！！

B - guess

死磕了2h2h终于写出来了：）
看完题之后有20min20min完全不知道出题人在说什么
终于看懂了题意之后完全没有烧烤的方向。然后突然想到了区间dpdp，但是看到数据范围就直接放弃了这个想法
但是区间dpdp是唯一的思路，直接放弃不太好，还是觉得像dpdp。于是就想到，每个区间有用的信息其实只有长度，和从哪一端进入区间
所以设计状态f[i][0/1]f[i][0/1]表示在一个长度为ii的区间内，从左端/右端进入，最少花多少代价找到最难找的点
转移就是：
CPP
f[i][0] = min(f[i][0], max(f[j][1], f[i - j][0]) + d[j]);
f[i][1] = min(f[i][1], max(f[j][0], f[i - j][1]) + d[j]);
jj是一步的距离
然后想到要是最短的一步都大于等于ii，但是有两步的差<i<i怎么办
考虑预处理所有移动的距离≤103\le 10^3的最小代价（≤103\le 10^3是因为如果有>>的就一定是什么≤103\le 10^3的东西加出来的，把那个东西减掉就好，实际用的时候分两步处理
想到了floyd，会炸
又想到了dj，好像不会炸欸！
于是把代码敲了出来，一遍过了所有的大样例，感觉最大的样例跑的还挺快的：）
然后就过了：）
CPP
#include <bits/stdc++.h>
#define LL long long

using namespace std;

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

LL t, n, m, a[M], d[M], f[N][2], vis[M], c;

void dj () {
  fill(vis + 1, vis + 1001, 0);
  priority_queue <pair <LL, int>> q;
  for (int i = 1; i <= 1000; i++) {
    if (d[i] != inf) q.push({-d[i], i});
  }
  while (q.size()) {
    int x = q.top().second;
    q.pop();
    if (vis[x]) continue;
    vis[x] = 1;
    for (int i = 1; i <= m; i++) {
      if (d[abs(a[i] - x)] > d[x] + d[a[i]]) {
        d[abs(a[i] - x)] = d[x] + d[a[i]];
        q.push({-d[abs(a[i] - x)], abs(a[i] - x)});
      }
    }
  }
}

int main () {
  // freopen("guess5.in", "r", stdin);
  // freopen("guess.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> c;
  for (cin >> t; t--;) {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
      cin >> a[i];
    }
    fill(d + 1, d + 1001, inf);
    for (LL i = 1, b; i <= m; i++) {
      cin >> b;
      d[a[i]] = min(d[a[i]], b);
    }
    dj();
    fill(&f[0][0], &f[n + 1][0], inf);
    f[1][0] = f[1][1] = 0;
    for (int i = 2; i <= n; i++) {
      for (int j = 1; j < min(1001, i); j++) {
        if (d[j] == inf) continue;
        f[i][0] = min(f[i][0], max(f[j][1], f[i - j][0]) + d[j]);
        f[i][1] = min(f[i][1], max(f[j][0], f[i - j][1]) + d[j]);
      }
    }
    if (f[n][0] == inf) {
      cout << "-1\n";
      continue;
    }
    cout << f[n][0] << '\n';
  }
  return 0;
}

C - tree

现在是11:2011:20，离结束还有100min100min
但是脑子已经被T2榨干了，导致当我正确理解题意时已经只剩80min80min了qwq
T2都烧烤了那么久，T3要是能过我就是zrr，所以直接打纯暴力
犹豫了1s1s改用树剖还是用倍增求LCA，树剖代码太长，但是当初学倍增LCA的恐怖经历最终击败了我
树剖，启动！
但是写的时候我感觉我就是个zrr，就求个LCA写了93行qwq
CPP
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 2e5 + 5;

LL n, f[N * 2], d[N], son[N], top[N], fa[N];
LL a[2][25], mod, rt, t, sz[N];
vector <int> v[N];

void dfs1 (int x, int ff) {
  fa[x] = ff;
  d[x] = d[ff] + 1;
  sz[x] = 1;
  son[x] = 0;
  for (int i : v[x]) {
    if (i == ff) continue;
    dfs1(i, x);
    sz[x] += sz[i];
    if (sz[i] > sz[son[x]]) {
      son[x] = i;
    }
  }
}

void dfs2 (int x, int t) {
  // cout << x << ' ' << t << '\n';
  top[x] = t;
  if (son[x]) {
    dfs2(son[x], t);
  }
  for (int i : v[x]) {
    if (i == fa[x] || i == son[x]) continue;
    dfs2(i, i);
  }
}

void qwq () {
  for (int i = 1; i <= n * 2; i++) {
    f[i] = 1;
    for (int j = 0; j < 21; j++) {
      f[i] *= a[(i >> j) & 1][j];
      f[i] %= mod;
    }
  }
}

int lca (int x, int y) {
  for (; top[x] != top[y];) {
    if (d[top[x]] < d[top[y]]) swap(x, y);
    x = fa[top[x]];
  }
  return d[x] < d[y] ? x : y;
}

int main () {
  // freopen("tree3.in", "r", stdin);
  // freopen("tree.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 1, x, y; i < n; i++) {
    cin >> x >> y;
    v[x].emplace_back(y);
    v[y].emplace_back(x);
  }
  for (cin >> t; t--;) {
    cin >> rt >> mod;
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j <= 20; j++) {
        cin >> a[i][j];
      }
    }
    qwq();
    dfs1(rt, 0);
    // for (int i = 1; i <= n; i++) {
    //   cout << sz[i] << ' ' << son[i] << ' ' << fa[i] << '\n';
    // }
    dfs2(rt, rt);
    LL ans = 0;
    for (int i = 1; i <= n; i++) {
      LL s = 0;
      for (int j = 1; j <= n; j++) {
        s += f[j + d[lca(i, j)]];
        s %= mod;
      }
      s *= i;
      ans ^= s;
    }
    cout << ans << '\n';
  }
  return 0;
}
还是树剖写起来顺手：）
用倍增的都是zrr

D - miss

哎呀，只剩40min40min了！
直接写特殊性质，因为奇数位置始终有棋子，所以答案会乘2(n+1)/22^{(n + 1)/2}
然后偶数位可以随便动，就算一下C的前缀和就好了
CPP
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 5e5 + 5, mod = 1e9 + 7;

LL n, q, qwq[N][2], c[N];
string s;

LL qpow (LL x, LL y) {
  LL ret = 1;
  for (; y; y >>= 1) {
    if (y & 1) {
      (ret *= x) %= mod;
    }
    (x *= x) %= mod;
  }
  return ret;
}

LL C (LL x, LL y) {
  return qwq[x][0] * qwq[x - y][1] % mod * qwq[y][1] % mod;
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> q >> s;
  s = ' ' + s;
  LL sum = 0;
  for (int i = 1; i <= n; i++) {
    if (i & 1) continue;
    sum += s[i] - '0';
  }
  qwq[0][0] = qwq[0][1] = 1;
  for (LL i = 1; i <= n; i++) {
    qwq[i][0] = qwq[i - 1][0] * i % mod;
    qwq[i][1] = qpow(qwq[i][0], mod - 2);
  }
  for (int i = 0; i <= n / 2; i++) {
    c[i] = C(n / 2, i);
    c[i] += c[i - 1];
    c[i] %= mod;
  }
  LL tmp = qpow(2, (n + 1) / 2);
  cout << tmp * c[sum] % mod << '\n';
  for (int x; q--;) {
    cin >> x;
    if (s[x] == '0') {
      s[x] = '1';
      sum++;
    } else {
      s[x] = '0';
      sum--;
    }
    cout << tmp * c[sum] % mod << '\n';
  }
  return 0;
}

T1，漏掉了一种情况
T2，对最短路算法的时间复杂度不熟

评论

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

正在加载评论...