251030cch模拟赛总结

100 + 100 + 92 + 5 = 297
赛前最后一场了：）只要再吃一次ccf的shit就好了：）
但是马上就要期中了qwq whk去s

A - anagram

为什么

n \le 5000

，但是我只能想到

O(n)

的做法，想不到

O(n^2)

qwq

因为字典序最小，所以优先填能填的里面最小的。如果填了之后，有一个字母需要填的个数比能填它的位置多，就填另一个

CPP

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

using namespace std;

const int N = 5e3 + 5;

int n, s[3], zs[N][3];
char ans[N];
string cch, cwj;

bool check (int i) {
  if (s[0] < 0 || s[1] < 0 || s[2] < 0) return 0;
  if (s[0] > zs[i][1] + zs[i][2]) return 0;
  if (s[1] > zs[i][0] + zs[i][2]) return 0;
  if (s[2] > zs[i][0] + zs[i][1]) return 0;
  return 1;
}

int main () {
  // freopen("anagram.in", "r", stdin);
  // freopen("anagram.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> cwj >> cch;
  cwj = ' ' + cwj; cch = ' ' + cch;
  for (int i = n; i >= 1; i--) {
    s[cwj[i] - 'a']++;
    zs[i][0] = zs[i + 1][0];
    zs[i][1] = zs[i + 1][1];
    zs[i][2] = zs[i + 1][2];
    zs[i][cch[i] - 'a']++;
  }
  for (int i = 1; i <= n; i++) {
    if (cch[i] == 'a') {
      ans[i] = 'b', s[1]--;
      if (!check(i + 1)) {
        s[1]++;
        ans[i] = 'c', s[2]--;
      }
    } else if (cch[i] == 'b') {
      ans[i] = 'a', s[0]--;
      if (!check(i + 1)) {
        s[0]++;
        ans[i] = 'c', s[2]--;
      }
    } else {
      ans[i] = 'a', s[0]--;
      if (!check(i + 1)) {
        s[0]++;
        ans[i] = 'b', s[1]--;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    cout << ans[i];
  }
  return 0;
}

B - intdiv

居然没挂：）

只有当有一个质数在

c-d

里面出现的次数比在

a-b

里面少才不能整除

所以先用线性筛筛出所有的质数，询问的时候枚举质数，用前缀和算出区间里面的出现次数，比较一下就A了

CPP

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

using namespace std;

const int N = 1e7 + 5, P = 7e5 + 5;

LL t, a, b, c, d, p[P], cnt, isp[N];

int get_sum (LL x, LL y) {
  LL ret = 0;
  for (LL i = y; i <= x; i *= y) {
    ret += x / i;
  }
  return ret;
}

int main () {
  // freopen("intdiv.in", "r", stdin);
  // freopen("intdiv.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  for (int i = 2; i <= 1e7; i++) {
    if (!isp[i]) {
      p[++cnt] = i;
    }
    for (int j = 1; j <= cnt && p[j] * i <= 1e7; j++) {
      isp[p[j] * i] = 1;
      if (i % p[j] == 0) break;
    }
  }
  for (cin >> t; t--;) {
    cin >> a >> b >> c >> d;
    int ans = 1;
    for (int i = 1; i <= cnt; i++) {
      if (get_sum(b, p[i]) - get_sum(a - 1, p[i]) > get_sum(d, p[i]) - get_sum(c - 1, p[i])) {
        ans = 0;
        break;
      }
    }
    if (ans) {
      cout << "Yes\n";
    } else {
      cout << "No\n";
    }
  }
  return 0;
}

C - eraser

1h

切完了T1-2，然后磕了

3h

首先通过手玩+烧烤发现，题目其实问的是，选一些数，再选另外一些数，最小化它们和的差

然后发现是人类智慧，当

n>31

的时候直接输出

0

n \le 31

的时候就用折半搜索（每个数乘

1、0、-1

）

结果只有

92pts

，

n == 31

的TLE了qwq

补题的时候特判了一下，

n == 31

就输出

1

CPP

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

using namespace std;

const int N = 1e5 + 5;

LL n, a[N], ans, mid;
set <LL> se;

void dfs (int x, LL s, int t, int f) {
  if (t > 0 && x > mid) {
    if (f) {
      se.insert(s);
      if (s >= 0)
        ans = min(ans, s);
    }
    return;
  }
  if (t < 0 && x == mid) {
    auto k = se.lower_bound(-s);
    if (f && s >= 0) ans = min(ans, s);
    if (k == se.end()) return;
    if (f) {
      ans = min(ans, (*k) + s);
    }
    // cout << (*k) << ' ' << s << '\n';
    return;
  }
  if (ans == 0) return;
  dfs(x + t, s, t, f);
  if (ans == 0) return;
  dfs(x + t, s + a[x], t, 1);
  if (ans == 0) return;
  dfs(x + t, s - a[x], t, 1);
}

int main () {
  freopen("eraser.in", "r", stdin);
  freopen("eraser.out", "w", stdout);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  if (n > 32) {
    cout << 0;
    return 0;
  }
  ans = a[1];
  mid = n / 2;
  dfs(1, 0, 1, 0);
  if (ans == 0) {
    cout << 0;
    return 0;
  }
  dfs(n, 0, -1, 0);
  cout << ans;
  return 0;
}

D - escape

5

分！

CPP

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

using namespace std;

const int N = 3e5 + 5;

double n, t, m, k, l, r, v;

int main () {
  // freopen("escape.in", "r", stdin);
  // freopen("escape.out", "w", stdout);
  cin >> n >> t >> m >> k >> l >> r >> v;
  cout << fixed << setprecision(3) << (t - l) / (v + m * k);
  return 0;
}

不会人类智慧，我没有智慧，我是sb！！

251030cch模拟赛总结

文章操作

A - anagram

B - intdiv

C - eraser

D - escape

相关推荐

评论

251030cch模拟赛总结