251016cch模拟赛总结

wendywu · 2025-10-16 16:01:48 · 个人记录

100 + 100 + 100 + 30 = 330
没想到全都大小样例一遍过的代码居然没有挂分
我还以为是样例太水qwq

A - cipher

T1写了50min，是不是没救了qwq

首先看到括号就想到，(是1，)是-1然后前缀和。但是这个题会在前缀和减成负数的时候把它变成0

猜到有一个分界点i，然后i左边的?都改成(，i右边的都改成)

所以就枚举这个i，考虑怎么算答案：
如果把i往右移一个，把一个)变成(，那么分2种情况：

1.如果i是已经配对过的：
把它配的对删掉（ans-1），然后因为前缀和加了2，所以可以把后面的前2个没配对的)配上（如果没配对的数量<2就不配对）

2.如果i没有配对：
因为它没配过对，所以前缀和只会加1，那就把后面的第一个没配对的配上（如果没有没配对的就不配）

然后就在这些答案里面取最大值就可以了：）

#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 1e5 + 5;

int T, n, q[N], t, h;
string s;

int main () {
  // freopen("cipher.in", "r", stdin);
  // freopen("cipher.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  for (cin >> T; T--;) {
    cin >> n >> s;
    s = ' ' + s;
    int sum = 0;
    t = 0;
    h = 1;
    int tmp = 0, ans = 0;
    for (int i = 1; i <= n; i++) {
      if (s[i] == '(') {
        sum++;
      } else {
        sum--;
        tmp++;
        if (sum < 0) {
          q[++t] = i;
          sum = 0;
          tmp--;
        }
      }
    }
    ans = tmp;
    int ans1 = 0;
    for (int i = 1; i <= n; i++) {
      if (s[i] == '?') {
        for (; h <= t && q[h] < i; h++);
        if (q[h] == i && h <= t) {
          h++;
          if (h <= t) {
            tmp++;
            h++;
          }
        } else if (h <= t) {
          h++;
          if (h <= t) {
            tmp++;
            h++;
          }
        } else {
          break;
        }
        ans = max(ans, tmp);
        if (ans == tmp) ans1 = i;
      }
    }
    cout << n - 2 * ans << '\n';
    for (int i = 1; i <= n; i++) {
      if (s[i] != '?') cout << s[i];
      else if (i <= ans1) cout << '(';
      else cout << ')';
    }
    cout << '\n';
  }
  return 0;
}

B - seq

怎么又是括号

首先我们发现n \le 20，直接状压

先考虑一个字符串的匹配的括号序列的前缀个数怎么算，其实就是在它的前缀和减成负数之前的0的个数

然后再思考当一个字符串接到另一个后面时答案会加多少。如果前面的字符串的前缀和有负数，答案就不会变。否则就会加上它的前缀和的第一个 <前面的字符串的和 之前的 前面的字符串的和 的个数

所以要预处理一些东西：

• 每个字符串的和
• 每个字符串的前缀和数组里面，每个值出现的次数（但是如果在这个值之前有比它小的就不能统计了）
• 每个字符串的前缀和数组里的最小值

然后就可以状压了：）

#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 25;

int n, f[1 << 21], s[N], ans, mn[N];
unordered_map <int, int> mp[N];

int main () {
  // freopen("seq.in", "r", stdin);
  // freopen("seq.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    string ss;
    cin >> ss;
    for (int j = 0; j < ss.size(); j++) {
      if (ss[j] == '(') s[i]++;
      else s[i]--;
      mn[i] = min(mn[i], s[i]);
      if (s[i] <= mn[i]) {
        mp[i][s[i]]++;
      }
    }
  }
  for (int i = 1; i < (1 << n); i++) {
    int sum = 0;
    f[i] = -1;
    for (int j = 1; j <= n; j++) {
      if (i & (1 << j - 1)) {
        sum += s[j];
      }
    }
    for (int j = 1; j <= n; j++) {
      if (!(i & (1 << j - 1))) continue;
      int sum1 = sum - s[j];
      if (sum1 < 0) continue;
      if (f[i - (1 << j - 1)] == -1) continue;
      int tmp = f[i - (1 << j - 1)] + mp[j][-sum1];
      ans = max(ans, tmp);
      if (mn[j] + sum1 >= 0) {
        f[i] = max(f[i], tmp);
      }
    }
  }
  cout << ans;
  return 0;
}

C - france

我T3居然过了！！
T3题解：

时间复杂度O(m log V + n sqrt(V) log V) ，期望得分60pts~100pts（视常数）。

交到vj上面就变成60pts了qwq
但是稍微优化了一下就过了：）

因为Att和Hp都是不降的，所以答案也是不降的，有一个-1后面就都是-1，然后想到双指针

然后问题变成了：如果已经得到了答案，怎么算伤害

可以用分块，d = sqrt(V)

当 Att_i \le d 时，在遍历每个牌的时候，枚举Att然后直接加到它的伤害里

当 Att_i \ge d 时，在遍历每个牌的时候，把它的攻击加到树状数组中它的血量的位置。然后在遍历老国王的时候，枚举牌的攻击次数，算出对应的血量，伤害加上树状数组里面的和*攻击次数就好了：）

时间复杂度O(m log V + n sqrt(V) log V) ，期望得分60pts - 100pts（视常数）。

结果没卡常就直接过了：）：）：）：）：）

#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 3e5 + 5, V = 605;

LL n, m, v, ans, d, s[V], tree[N];
struct aa {
  LL a, b;
} a[N];

int lb (int x) {
  return x & -x;
}

void add (int x, LL y) {
  for (; x <= v; x += lb(x)) {
    tree[x] += y;
  }
}

LL query (LL x) {
  LL ret = 0;
  for (; x; x -= lb(x)) {
    ret += tree[x];
  }
  return ret;
}

LL query1 (int x) {
  LL qwq = 0, ret = 0;
  for (LL i = x; i - x < v; i += x) {
    LL tmp = query(min(i, v));
    LL tmp1 = tmp - qwq;
    qwq = tmp;
    ret += i / x * tmp1;
  }
  return ret;
}

int main () {
  freopen("france.in", "r", stdin);
  freopen("france.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m >> v;
  d = sqrt(v);
  for (int i = 1; i <= n; i++) {
    cin >> a[i].a >> a[i].b;
  }
  ans = 1;
  for (LL i = 1, aa, bb; i <= m; i++) {
    cin >> aa >> bb;
    if (ans == -1) {
      cout << "-1\n";
      continue;
    }
    if (aa <= d) {
      for (; s[aa] < bb && ans <= n; ans++) {
        for (int j = 1; j <= d; j++) {
          int tmp = a[ans].b / j;
          if (a[ans].b % j) tmp++;
          s[j] += tmp * a[ans].a;
        }
        add(a[ans].b, a[ans].a);
      }
      if (s[aa] < bb) {
        ans = -1;
        cout << "-1\n";
        continue;
      }
      cout << ans - 1 << " \n";
    } else {
      for (; query1(aa) < bb && ans <= n; ans++) {
        add(a[ans].b, a[ans].a);
      }
      if (query1(aa) < bb) {
        ans = -1;
        cout << "-1\n";
        continue;
      }
      cout << ans - 1 << " \n";
    }
  }
  return 0;
}

但是交到vj上挂成60pts了qwq，所以改了以下这些地方：

1

for (int j = 1; j <= d; j++) {
  int tmp = a[ans].b / j;
  if (a[ans].b % j) tmp++;
  s[j] += tmp * a[ans].a;
}