251023cch模拟赛总结

· · 个人记录

100 + 40 + 50 + 40 = 230
我怎么T2都做不出，我太菜了qwq

A - string

他们都说做过，但我怎么一点印象都没有qwq

看懂题就看了挺久的还以为左半部分不是从中间分开，看了样例才看懂

然后就是一个非常明显的分治，用dfs就能AC了

#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题，我当时甚至做出来了

这是我当时的代码：

#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

看懂样例花了30minqwq，然后心态就炸飞了：）

样例解释都不给一个

看完样例之后感觉像贪心，还像dp，甚至想到了区间dp

感觉还是更像贪心（实际上正解是dp，我太菜了qwq），从样例中猜到了一个错误的结论：从1开始往右走，经过一个关卡的时候顺便把小怪杀死，大怪剩一滴血，到n了之后往回走

于是枚举往回的时候走到哪。写出来之后发现小样例过了，大样例过不去。但是已经只剩1.5h了，而且真的太复杂了，直接去看T3

没想到捞到了40pts：）

#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 - a_i算出来，就是前面要删掉的个数，如果前面能删掉的个数\ge它就能删。因为当前面删到这么多的时候就把它删了不会影响前面，如果影响了后面，就把后面该删的先删了

考虑到只剩1h多一点，而且没有更多的思路，直接打暴力。

1、2个子任务就按上面讲的O(nq)做就好了

子任务3应该也可以这样做（但是我RE了，不知道为什么）

子任务4就暴力预处理（或者也相当于加了个记忆化）（但是我还是RE了，不知道为什么）

期望得分：80，但是挂了30qwq

#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

$n,m \le 8$的点就$O(n!)$的爆搜，枚举一下起点就可以直接搜了 然后还剩$10min$，我在最后$1min$打完了基环树的暴力：） 首先用栈找环，然后看$1$的边是不是都在这个环上，就可以拿到了 还好一遍对了，$1min$绝对调不了任何的东西：） ```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磕的太久了，而且甚至没有想到$dp

我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了
我太菜了