专栏文章

251023cch模拟赛总结

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

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@miniyvth
此快照首次捕获于
2025/12/02 03:11
3 个月前
此快照最后确认于
2025/12/02 03:11
3 个月前
查看原文
100 + 40 + 50 + 40 = 230
我怎么T2都做不出，我太菜了qwq

A - string

他们都说做过，但我怎么一点印象都没有qwq
看懂题就看了挺久的还以为左半部分不是从中间分开，看了样例才看懂
然后就是一个非常明显的分治，用dfsdfs就能AC了
CPP
#include <bits/stdc++.h>
#define LL long long

using namespace std;

int n;
string s;

int get_ans (int l, int r, char c) {
  if (l == r) {
    return s[l] != c;
  }
  int mid = l + r >> 1, sl = 0, sr = 0;
  for (int i = l; i <= r; i++) {
    if (i <= mid) {
      sl += s[i] != c;
    } else {
      sr += s[i] != c;
    }
  }
  return min(sl + get_ans(mid + 1, r, c + 1), sr + get_ans(l, mid, c + 1));
}

int main () {
  // freopen("string.in", "r", stdin);
  // freopen("string.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> s;
  s = ' ' + s;
  cout << get_ans(1, n, 'a');
  return 0;
}
破案了，是23年春季训练10的F题，我当时甚至做出来了
这是我当时的代码：
CPP
#include <bits/stdc++.h>

using namespace std;

long long t, n, f[200010][30];
string s;

long long dfs (int l, int r, int a) {
  if (l == r) {
    if (s[l] == 'a' + a - 1) {
      return 0;
    } else {
      return 1;
    }
  }
  long long mid = l + r >> 1;
  long long ret = min(dfs(l, mid, a + 1) + r - mid - (f[r][a] - f[mid][a]), 
                      dfs(mid + 1, r, a + 1) + mid - l + 1 - (f[mid][a] - f[l - 1][a]));
  //cout << l << " " << r << " " << a << " " << ret << endl;
  return ret;
}

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  for (cin >> t; t--;) {
    cin >> n >> s;
    s = ' ' + s;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= 26; j++) {
        f[i][j] = f[i - 1][j];
      }
      f[i][s[i] - 'a' + 1] = f[i - 1][s[i] - 'a' + 1] + 1;
    }
    cout << dfs(1, n, 1) << endl;
  }
  return 0;
}
也太丑了qwq

B - shot

很久没见过这么恶心的题了qwq
看懂样例花了30min30minqwq，然后心态就炸飞了：）
样例解释都不给一个
看完样例之后感觉像贪心，还像dpdp，甚至想到了区间dpdp
感觉还是更像贪心（实际上正解是dpdp，我太菜了qwq），从样例中猜到了一个错误的结论：从11开始往右走，经过一个关卡的时候顺便把小怪杀死，大怪剩一滴血，到nn了之后往回走
于是枚举往回的时候走到哪。写出来之后发现小样例过了，大样例过不去。但是已经只剩1.5h1.5h了，而且真的太复杂了，直接去看T3
没想到捞到了40pts40pts：）
CPP
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const LL N = 1e6 + 5, inf = 1e18;

LL n, a[N], r1, r2, r3, d, s[N][2], f[N], ans;

int main () {
  freopen("shot.in", "r", stdin);
  freopen("shot.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> r1 >> r2 >> r3 >> d;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  s[0][1] = inf;
  for (int i = 1; i < n; i++) {
    LL tmp = min(r2 + d, r1 * a[i] + r1 + d);
    f[1] += tmp;
    f[i + 1] -= tmp;
    tmp = min({r1 * a[i] + r3, r2 + d * 2 + r1, r1 * a[i] + r1 + d * 2 + r1});
    s[i][1] = min(s[i - 1][0], s[i - 1][1]) + min(r2 + d * 2 + r1, r1 * a[i] + r1 + d * 2 + r1) + d;
    s[i][0] = min(s[i - 1][1] + min(r2 + r1, r1 * a[i] + r1 + r1) + d, min(s[i - 1][0], s[i - 1][1]) + r1 * a[i] + r3 + d);
  }
  LL sum = 0;
  ans = inf;
  for (int i = 1; i <= n; i++) {
    sum += f[i];
    ans = min(ans, sum + min(s[i - 1][0], s[i - 1][1]) + min({r1 * a[n] + r3, r2 + d * 2 + r1, r1 * a[n] + r1 + d * 2 + r1}) + (n - i) * (d + r1));
    // cout << sum << ' ' << min(s[i - 1][0], s[i - 1][1]) << ' ' << min({r1 * a[n] + r3, r2 + d * 2 + r1, r1 * a[n] + r1 + d * 2 + r1}) << ' ' << (n - i) * (d + r1) << '\n';
  }
  cout << ans;
  return 0;
}
一大坨shit，又难写又难调qwq

C - array

一眼看上去是我爱吃的数据结构shit（赛后发现确实是我爱吃的线段树
第二眼就不会了：）
首先烧烤一下，一个完整的数组怎么算能删掉几个：
把每个i−aii - a_i算出来，就是前面要删掉的个数，如果前面能删掉的个数≥\ge它就能删。因为当前面删到这么多的时候就把它删了不会影响前面，如果影响了后面，就把后面该删的先删了
考虑到只剩1h1h多一点，而且没有更多的思路，直接打暴力。
1、2个子任务就按上面讲的O(nq)O(nq)做就好了
子任务3应该也可以这样做（但是我RE了，不知道为什么）
子任务4就暴力预处理（或者也相当于加了个记忆化）（但是我还是RE了，不知道为什么）
期望得分：80，但是挂了30qwq
CPP
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 2e5 + 5;

int n, q, a[N], f[100][100];

int main () {
  freopen("array.in", "r", stdin);
  freopen("array.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= 100; i++) {
    int sum = 0;
    for (int j = i; j <= n; j++) {
      int tmp = j - a[j];
      if (tmp >= 0 && sum >= tmp) {
        sum++;
      }
      if (n - j < 100) {
        f[i - 1][n - j] = sum;
      }
    }
  }
  for (int x, y; q--;) {
    cin >> x >> y;
    if ((n <= 3000 && q <= 3000) || n - (x + y) <= 50) {
      int sum = 0;
      for (int i = 1 + x; i <= n - y; i++) {
        int tmp = i - a[i];
        if (tmp >= 0 && sum >= tmp) sum++;
      }
      cout << sum << '\n';
    } else {
      cout << f[x][y] << '\n';
    }
  }
  return 0;
}

D - festival

30min30min打完4040分暴力：）
n,m≤8n,m \le 8的点就O(n!)O(n!)的爆搜，枚举一下起点就可以直接搜了
然后还剩10min10min，我在最后1min1min打完了基环树的暴力：）
首先用栈找环，然后看11的边是不是都在这个环上，就可以拿到了
还好一遍对了，1min1min绝对调不了任何的东西：）
CPP
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 1e5 + 5;

int t, n, m, vis[N * 2], s1, ss[N], tt, ans1, qwq[N * 2];
struct edge {
  int x, c, i;
};
vector <edge> v[N];

bool dfs (int s, int x, int sum, int k) {
  if (sum == s1 && x == s) return 1;
  if (k == m) return 0;
  int ret = 0;
  for (edge i : v[x]) {
    if (vis[i.i]) continue;
    vis[i.i] = 1;
    ret |= dfs(s, i.x, sum + i.c, k + 1);
    vis[i.i] = 0;
  }
  return ret;
}

void dfs1 (int x, int fa) {
  // cout << x << ' ' << fa << '\n';
  for (edge i : v[x]) {
    if (i.x == fa) continue;
    if (vis[i.i]) {
      int sum = 0;
      for (; ss[tt] != i.i; tt--) {
        sum += qwq[ss[tt]];
      }
      sum += qwq[i.i];
      if (sum == s1) {
        cout << "Yes\n";
      } else {
        cout << "No\n";
      }
      ans1 = 1;
      return;
    }
    vis[i.i] = 1;
    ss[++tt] = i.i;
    dfs1(i.x, x);
    if (ans1) return;
    tt--;
    vis[i.i] = 0;
  }
}

int main () {
  freopen("festival.in", "r", stdin);
  freopen("festival.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  for (cin >> t; t--;) {
    cin >> n >> m;
    s1 = 0;
    for (int i = 1; i <= n; i++) {
      v[i].clear();
    }
    for (int i = 1, x, y, z; i <= m; i++) {
      cin >> x >> y >> z;
      v[x].emplace_back((edge){y, z, i});
      v[y].emplace_back((edge){x, z, i});
      vis[i] = 0;
      qwq[i] = z;
      s1 += z;
    }
    if (n > 10) {
      ans1 = 0;
      tt = 0;
      dfs1(1, 1);
      continue;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
      ans |= dfs(i, i, 0, 0);
    }
    if (ans) {
      cout << "Yes\n";
    } else {
      cout << "No\n";
    }
  }
  return 0;
}
感觉代码写的很混乱，最后一点点时间太急了：）

T2磕的太久了，而且甚至没有想到dpdp
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了

评论

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

正在加载评论...