251120noip模拟赛总结

· · 个人记录

100 + 100 + 42 + 0 = 242
T3炸了8ptsqwq

A - print

绿题写了40minqwq 我是不是没救了

一开始读错题了，花20min写了一个非常cutezrr的set乱搞假做法（虽然正解也是set），然后发现小样例都过不去，骂了1s自己是cutezrr，就把代码删了

继续烧烤正解

感觉是直接模拟每一个任务给哪个打印机

注意到，我们可以把打印机分成两类：1.等待时间为0的；2.等待时间不为0的。

首先肯定优先用第一类的

第2类就用set，以时间为第一关键字，编号为第二关键字排个序（用pair存）。没有一类打印机的时候就选这一类的s2.begin()就好了

每次接到一个新任务的时候，先把第二类里面能变成第一类的扔进第一类里面

第一类也是set，直接存编号。用完一个就更新一下时间，扔进第二类里面

（讲的顺序有些抽象，但考场上就是先想到第二类再想到第一类的（没错第二类就是一开始cutezrr的假做法））

然后就可以做叻：）

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

using namespace std;

const int N = 2e5 + 5;

LL n, m;
vector <int> ans[N];
set <pair <LL, int>> s1;
set <int> s0;
struct aa {
  LL s, t, i;
} a[N];

bool cmp (aa x, aa y) {
  return x.t < y.t;
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].s >> a[i].t;
    a[i].i = i;
  }
  for (int i = 1; i <= m; i++) {
    s0.insert(i);
  }
  sort(a + 1, a + n + 1, cmp);
  for (int i = 1; i <= n; i++) {
    for (; s1.size() && (*s1.begin()).first <= a[i].t; s0.insert((*s1.begin()).second), s1.erase(*s1.begin()));
    if (s0.size()) {
      int j = *s0.begin();
      s0.erase(j);
      ans[j].emplace_back(a[i].i);
      s1.insert({a[i].t + a[i].s, j});
    } else {
      pair <LL, int> p = *s1.begin();
      s1.erase(p);
      ans[p.second].emplace_back(a[i].i);
      s1.insert({p.first + a[i].s, p.second});
    }
  }
  for (int i = 1; i <= m; i++) {
    cout << ans[i].size() << ' ';
    sort(ans[i].begin(), ans[i].end());
    for (int j : ans[i]) {
      cout << j << ' ';
    }
    cout << '\n';
  }
  return 0;
}

T2 - ship

这场T2比之前都简单：）

一眼dp，两眼背包

第一维肯定是要滚动掉的啊 然后就会了$q = 1$的做法：） 烧烤$q ≠ 1$，去了趟厕所就烧烤出来叻好耶 再开一个数组：$mn[i][j]$表示从$1$加速到$2^i\times 3^j$，比一开始就用这个速度最少多花多少时间 然后把查询和加速器放一起离线，一边$dp$一边更新答案 哎呀，这个样例怎么这么恶心，四舍五入的位数都那么抽象，不能直接fc qwq 花了$10min$手写了一个check，大样例都过了：） 不是为什么样例$4$跑的这么慢qwq 输出一下clock，不豪，1112ms qwq 优化，注意到样例里面有很多$x = 1$的~~cutezrr~~加速器，所以在$dp$的时候可以直接continue掉 还是挺慢的，继续优化：还是因为样例里面有很多的1，所以可以一边遍历加速器一边累加速度的上限，$dp$的时候就可以少枚举一些状态 居然只要一百多$ms$了，这下应该能过了吧？？（本来理论复杂度就是对的，不过就都怪zrr ```cpp #include <bits/stdc++.h> #define LL long long using namespace std; const int N = 1e5 + 5, K = 35; const double inf = 1e18; LL n, q, qwq[5][2], zs[K][K]; double f[K][K], mn[K][K], ans[N]; struct aa { LL p, x, t; } a[N * 2]; bool cmp (aa x, aa y) { return x.p < y.p; } int main () { ios::sync_with_stdio(0), cin.tie(0); cin >> n >> q; for (int i = 1; i <= n; i++) { cin >> a[i].p >> a[i].t >> a[i].x; } for (int i = 1; i <= q; i++) { cin >> a[i + n].p; a[i + n].t = i; } zs[0][0] = 1; for (int i = 0; i <= 32; i++) { for (int j = 0; j + i <= 32; j++) { if (i + j == 0) continue; if (i) zs[i][j] = zs[i - 1][j] * 2; if (j) zs[i][j] = zs[i][j - 1] * 3; } } qwq[1][0] = qwq[3][0] = 0; qwq[2][0] = 1, qwq[4][0] = 2; qwq[1][1] = qwq[2][1] = qwq[4][1] = 0; qwq[3][1] = 1; sort(a + 1, a + n + q + 1, cmp); fill(&mn[0][0], &mn[33][0], inf); fill(&f[0][0], &f[33][0], inf); f[0][0] = 0; mn[0][0] = 0; int s2 = 0, s3 = 0; for (int i = 1; i <= n + q; i++) { for (int j = 0; j <= s2; j++) { for (int k = 0; k + j <= 32 && k <= s3; k++) { f[j][k] = min(inf, f[j][k] + 1.0 * (a[i].p - a[i - 1].p) / zs[j][k]); } } if (a[i].x) { s2 += qwq[a[i].x][0]; s3 += qwq[a[i].x][1]; s2 = min(s2, 32); s3 = min(s3, 32); if (a[i].x == 1) continue; for (int i2 = s2; i2 >= qwq[a[i].x][0]; i2--) { for (int i3 = min(32 - i2, s3); i3 >= qwq[a[i].x][1]; i3--) { f[i2][i3] = min(f[i2][i3], f[i2 - qwq[a[i].x][0]][i3 - qwq[a[i].x][1]] + (double)a[i].t); if (f[i2][i3] != inf) { mn[i2][i3] = min(mn[i2][i3], f[i2][i3] - 1.0 * a[i].p / zs[i2][i3]); } } } } else { ans[a[i].t] = inf; for (int j = 0; j <= s2; j++) { for (int k = 0; k + j <= 32 && k <= s3; k++) { ans[a[i].t] = min(ans[a[i].t], 1.0 * a[i].p / zs[j][k] + mn[j][k]); } } } } for (int i = 1; i <= q; i++) { cout << fixed << setprecision(10) << ans[i] << '\n'; } // cout << clock() << '\n'; return 0; } ``` ## T3 - string 怎么只有我用了线段树qwq 都怪zrr 打暴力 $n = t.size()$ 首先$O(n^2)$的预处理出$t$的每一个位置开头，最长的对应的$s$的前缀 虽然不知道有什么用但是看起来很有用的样子 考虑如果确定了一个区间，该怎么算它最少被多少个前缀覆盖 首先想到$dp$，倒过来$dp$，非常典的找到它的最长前缀对应的那一段区间里面，$dp$结果的最小值，然后+1 但是这样是$O(n^2)$的，想到用线段树优化，变成$O(nlogn)

但是还要枚举区间，这样总共就是O(n^3logn)，也太大了qwq

于是先枚举区间右端点，然后倒过来枚举左端点，顺便把dp整了，优化到了O(n^2logn)看起来能拿50pts

考虑到只有50min了，我对T4还只是看懂了题意，于是先不打线段树，先只写O(n^3)的，拿30pts

去T4烧烤了一会，决定回来把线段树打了，没想到5min就打好了，虽然后面又调了5min：）都怪zrr

#include <bits/stdc++.h>
#define LL long long
#define ls k << 1
#define rs k << 1 | 1

using namespace std;

const int N = 5e3 + 5, inf = 1e9;

int id, nn, a[N], k, f[N][N], ans, n, ans1[N], tree[N];
string s[15], t;

void push_up (int k) {
  tree[k] = min(tree[ls], tree[rs]);
}

void build (int k, int l, int r) {
  tree[k] = inf;
  if (l == r) return;
  int mid = l + r >> 1;
  build(ls, l, mid); build(rs, mid + 1, r);
  push_up(k);
}

int query (int k, int l, int r, int l1, int r1) {
  if (l >= l1 && r <= r1) return tree[k];
  int mid = l + r >> 1, ret = inf;
  if (mid >= l1) {
    ret = query(ls, l, mid, l1, r1);
  }
  if (mid < r1) {
    ret = min(ret, query(rs,  mid + 1, r, l1, r1));
  }
  return ret;
}

void update (int k, int l, int r, int k1, int x) {
  if (l == r) {
    tree[k] = x;
    return;
  }
  int mid = l + r >> 1;
  if (mid >= k1) {
    update(ls, l, mid, k1, x);
  } else {
    update(rs, mid + 1, r, k1, x);
  }
  push_up(k);
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> id >> nn >> k;
  for (int i = 1; i <= nn; i++) {
    cin >> s[i];
    s[i] = ' ' + s[i];
  }
  cin >> t;
  n = t.size();
  t = ' ' + t;
  for (int i = 1; i <= n; i++) {
    for (int l = 1; l <= nn; l++) {
      for (int j = i; j <= min(n, (int)(i + s[l].size() - 2)); j++) {
        if (s[l][j - i + 1] != t[j]) break;
        a[i] = max(a[i], j - i + 1);
        // cout << i << ' ' << l << ' ' << j << '\n';
      }
    }
    // cout << a[i] << ' ';
  }
  // cout << '\n';
  for (int r = n; r >= 1; r--) {
    build(1, 1, n + 1);
    update(1, 1, n + 1, r + 1, 0);
    for (int l = r; l >= 1; l--) {
      f[l][r] = inf;
      if (a[l]) {
        f[l][r] = query(1, 1, n + 1, l + 1, min(r + 1, l + a[l])) + 1;
      }
      // cout << l << ' ' << r << ' ' << f[l][r] << '\n';
      update(1, 1, n + 1, l, f[l][r]);
      ans += max(0, k - f[l][r] + 1);
      if (k - f[l][r] + 1 > 0) {
        for (int i = l; i <= r; i++) {
          ans1[i] += k - f[l][r] + 1;
        }
      }
    }
  }
  cout << ans << '\n';
  for (int i = 1; i <= n; i++) {
    cout << ans1[i] << ' ';
  }
  return 0;
}
//bu yao zha qwq bu yao zha qwq bu yao zha qwq bu yao zha qwq bu yao zha qwq bu yao zha qwq bu yao zha qwq bu yao zha qwq bu yao zha qwq

但是炸了8ptsqwq

下午上whk的时候突然想起，改到线段树之后没有按新的部分分的需求开long long！！

我居然没有开long long！！！都怪zrr！！

T4 - party

太恶心了，烧烤了一下纯暴力，发现比线段树还难打，于是跑回T3打线段树，这个题没创建文件：）

long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！
long long！！