专栏文章

251016cch模拟赛总结

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

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@minlek58
此快照首次捕获于
2025/12/02 04:19
3 个月前
此快照最后确认于
2025/12/02 04:19
3 个月前
查看原文
100 + 100 + 100 + 30 = 330
没想到全都大小样例一遍过的代码居然没有挂分
我还以为是样例太水qwq

A - cipher

T1写了50min50min，是不是没救了qwq
首先看到括号就想到，(是11，)是−1-1然后前缀和。但是这个题会在前缀和减成负数的时候把它变成00
猜到有一个分界点ii，然后ii左边的?都改成(，ii右边的都改成)
所以就枚举这个ii，考虑怎么算答案：
如果把ii往右移一个，把一个)变成(，那么分22种情况：
1.如果ii是已经配对过的：
把它配的对删掉（ans−1ans-1），然后因为前缀和加了22，所以可以把后面的前22个没配对的)配上（如果没配对的数量<2<2就不配对）
2.如果ii没有配对：
因为它没配过对，所以前缀和只会加11，那就把后面的第一个没配对的配上（如果没有没配对的就不配）
然后就在这些答案里面取最大值就可以了：）
CPP
#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≤20n \le 20，直接状压
先考虑一个字符串的匹配的括号序列的前缀个数怎么算，其实就是在它的前缀和减成负数之前的00的个数
然后再思考当一个字符串接到另一个后面时答案会加多少。如果前面的字符串的前缀和有负数，答案就不会变。否则就会加上它的前缀和的第一个 <<前面的字符串的和 之前的 前面的字符串的和 的个数
所以要预处理一些东西：
  • 每个字符串的和
  • 每个字符串的前缀和数组里面，每个值出现的次数（但是如果在这个值之前有比它小的就不能统计了）
  • 每个字符串的前缀和数组里的最小值
然后就可以状压了：）
CPP
#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
但是稍微优化了一下就过了：）
因为AttAtt和HpHp都是不降的，所以答案也是不降的，有一个−1-1后面就都是−1-1，然后想到双指针
然后问题变成了：如果已经得到了答案，怎么算伤害
可以用分块，d=sqrt(V)d = sqrt(V)
当 Atti≤dAtt_i \le d 时，在遍历每个牌的时候，枚举AttAtt然后直接加到它的伤害里
当 Atti≥dAtt_i \ge d 时，在遍历每个牌的时候，把它的攻击加到树状数组中它的血量的位置。然后在遍历老国王的时候，枚举牌的攻击次数，算出对应的血量，伤害加上树状数组里面的和∗*攻击次数就好了：）
时间复杂度O(mlogV+nsqrt(V)logV)O(m log V + n sqrt(V) log V) ，期望得分60pts−100pts60pts - 100pts（视常数）。
结果没卡常就直接过了：）：）：）：）：）
CPP
#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上挂成60pts60pts了qwq，所以改了以下这些地方：
1
CPP
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;
}
jj从aaaa开始循环
2
CPP
for (; query1(aa) < bb && ans <= n; ans++) {
  add(a[ans].b, a[ans].a);
}
if (query1(aa) < bb) {
  ans = -1;
  cout << "-1\n";
  continue;
}
改成这样：
CPP
LL tmp = query1(aa);
for (; tmp < bb && ans <= n; ans++) {
  add(a[ans].b, a[ans].a);
  tmp += (a[ans].b / aa + (a[ans].b % aa ? 1 : 0)) * a[ans].a;
}
if (tmp < bb) {
  ans = -1;
  cout << "-1\n";
  continue;
}
然后就过了：）

D - glass

呀 怎么只剩30min30min了，赶紧打个暴力
dpdp，设f[i][j]f[i][j]表示第ii层，从第11层到第ii层一共用了jj个ACAC，每一层都至少存在一个 ACAC的方案数
转移的时候枚举这一层有几个ACAC就可以O(n3)O(n^3)了：）
但是写完之后测大样例114 514的时候WA了，因为部分分里面写的是n≤500n \le 500但有514514所以数组开小了qwq 调了1010多分钟
然后我就把数组开成了2000∗20002000 * 2000，不小心多捞了5pts5pts：）不小心成为了唯一一个30pts30pts：）
CPP
#include <bits/stdc++.h>
#define LL long long

using namespace std;

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

LL n, m, f[N][N], pw[N], cch[N][2];

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 qwq (LL x, LL y, LL z) {
  LL ret = z;
  ret *= cch[y][1];
  ret %= mod;
  return ret;
}

int main () {
  // freopen("glass.in", "r", stdin);
  // freopen("glass.out", "w", stdout);
  cin >> n >> m;
  if (m < n) {
    cout << 0;
    return 0;
  }
  pw[0] = 1;
  for (int i = 1; i <= n; i++) {
    pw[i] = pw[i - 1] * 2 % mod;
  }
  cch[0][0] = cch[0][1] = 1;
  for (LL i = 1; i <= m; i++) {
    cch[i][0] = cch[i - 1][0] * i % mod;
    cch[i][1] = qpow(cch[i][0], mod - 2);
  }
  f[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      LL tmp = 1;
      for (int k = 1; k <= j; k++) {
        tmp *= pw[i - 1];
        tmp %= mod;
        f[i][j] += f[i - 1][j - k] * qwq(i, k, tmp) % mod;
        f[i][j] %= mod;
      }
    }
  }
  cout << f[n][m] * cch[m][0] % mod;
  return 0;
}

T1想到分界点的事情花的时间太久了，T3一开始一直在想二分，留给T4的时间太少：）
我还以为我T3 60pts60pts都拿不到qwq 没想到直接A掉了：）

评论

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

正在加载评论...