专栏文章

251120noip模拟赛总结

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

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@min43f8w
此快照首次捕获于
2025/12/01 20:14
3 个月前
此快照最后确认于
2025/12/01 20:14
3 个月前
查看原文
100 + 100 + 42 + 0 = 242
T3炸了8pts8ptsqwq

A - print

绿题写了40min40minqwq 我是不是没救了
一开始读错题了，花20min20min写了一个非常cutezrr的setset乱搞假做法（虽然正解也是setset），然后发现小样例都过不去，骂了1s1s自己是cutezrr，就把代码删了
继续烧烤正解
感觉是直接模拟每一个任务给哪个打印机
注意到，我们可以把打印机分成两类：1.等待时间为00的；2.等待时间不为00的。
首先肯定优先用第一类的
第2类就用setset，以时间为第一关键字，编号为第二关键字排个序（用pairpair存）。没有一类打印机的时候就选这一类的s2.begin()s2.begin()就好了
每次接到一个新任务的时候，先把第二类里面能变成第一类的扔进第一类里面
第一类也是setset，直接存编号。用完一个就更新一下时间，扔进第二类里面
（讲的顺序有些抽象，但考场上就是先想到第二类再想到第一类的（没错第二类就是一开始cutezrr的假做法））
然后就可以做叻：）
CPP
#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比之前都简单：）
一眼dpdp，两眼背包
f[p][i][j]f[p][i][j]表示速度乘了ii个22，jj个33，在位置pp达到这个速度的最少用时
第一维肯定是要滚动掉的啊
然后就会了q=1q = 1的做法：）
烧烤q≠1q ≠ 1，去了趟厕所就烧烤出来叻好耶
再开一个数组：mn[i][j]mn[i][j]表示从11加速到2i×3j2^i\times 3^j，比一开始就用这个速度最少多花多少时间
然后把查询和加速器放一起离线，一边dpdp一边更新答案
哎呀，这个样例怎么这么恶心，四舍五入的位数都那么抽象，不能直接fc qwq
花了10min10min手写了一个check，大样例都过了：）
不是为什么样例44跑的这么慢qwq
输出一下clock，不豪，1112ms qwq
优化，注意到样例里面有很多x=1x = 1的cutezrr加速器，所以在dpdp的时候可以直接continue掉
还是挺慢的，继续优化：还是因为样例里面有很多的1，所以可以一边遍历加速器一边累加速度的上限，dpdp的时候就可以少枚举一些状态
居然只要一百多msms了，这下应该能过了吧？？（本来理论复杂度就是对的，不过就都怪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()n = t.size() 首先O(n2)O(n^2)的预处理出tt的每一个位置开头，最长的对应的ss的前缀
虽然不知道有什么用但是看起来很有用的样子
考虑如果确定了一个区间，该怎么算它最少被多少个前缀覆盖
首先想到dpdp，倒过来dpdp，非常典的找到它的最长前缀对应的那一段区间里面，dpdp结果的最小值，然后+1
但是这样是O(n2)O(n^2)的，想到用线段树优化，变成O(nlogn)O(nlogn)
但是还要枚举区间，这样总共就是O(n3logn)O(n^3logn)，也太大了qwq
于是先枚举区间右端点，然后倒过来枚举左端点，顺便把dpdp整了，优化到了O(n2logn)O(n^2logn)看起来能拿50pts50pts
考虑到只有50min50min了，我对T4还只是看懂了题意，于是先不打线段树，先只写O(n3)O(n^3)的，拿30pts30pts
去T4烧烤了一会，决定回来把线段树打了，没想到5min5min就打好了，虽然后面又调了5min5min：）都怪zrr
CPP
#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
但是炸了8pts8ptsqwq
下午上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！！

评论

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

正在加载评论...