吃薯片邮寄

· · 生活·游记

前言

S T1 没开 longlong 我无疑是愤怒的。

day0.99

抚琴带我去看了眼那个叫啥大学(不记得了 /kel),疑惑,现在大学都随便进的吗?

我去居然住的那个叫啥亚朵酒店,听说很高档。

晚上散步的时候还看到了 cos 老师?

虽然但是不知道 cos 的谁 /ll。

酒店前台人真好,还帮我打印了准考证。
还有个前台好帅

day0.999

突然发现酒店电视可以投屏,欧克啊南部档案我来了!!!

然后我又发现酒店电视没有奇异果,二刷失败 /ll。

骗你的我最后看的是熊大

day1.01

吃早饭的时候隔壁桌有这么一组对话:

A:这酒店也是疯了,周六一个房间这么贵。
B:我也纳闷呢,今天还这么多人。

ok啊我这个好心人也是听不下去了哈,我就插了一句解释了一下。

day1.25

到考场了哈哈哈。

怎么隔壁的隔壁是个初三的,炸鱼?

轻松切掉 T1T2T3。

T4?第一眼看不出来咋写。我好菜 /ll。

🧊🧊🧊

第一眼看不出来咋写是吧。

那我打个暴力吧。

部队,T4 这个游戏我好像玩过。

打完暴力之后玩了 3h 纸牌。

100 + 100 + 100 + 24

以下是交给教练的总结:

J

T1

几个 if 结束。

T2

双指针 l, r 记录左右两端的位置,i, j 记录左右两边是哪一段。

T3

按位贪心。

T4

bzd。还没改。

day1.5

下考了哈哈哈。

为什么我们机房有人 T3 不会。

不管了我要回酒店吃点好的。

day1.55

中午竟然点外卖?抚琴你没有心。

不过吃的还好。

虾线没有去掉我生气了。

day1.60

睡了一觉。

day1.75

直接一波开考。

T1 秒了(骗你的我没开longlong)

告诉你们我错哪了。

我的考场代码:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 5e5 + 5;

int n, ans;
ll m, a[N], pre[N];

bool check(int x, int i, int k) {
  return k * (i - x + 1) - pre[i] + pre[x - 1] <= m;
}

int puck(int l, int r, int i, ll x) {
  while (l < r) {
    int mid = l + r >> 1;
    check(mid, i, x) ? r = mid : l = mid + 1;
  }
  return l;
}

int main() {
  freopen("crystal.in", "r", stdin);
  freopen("crystal.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; i++) {
    pre[i] = pre[i - 1] + a[i];
  }
  for (int i = 1; i <= n; i++) {
    int x = puck(1, i, i, a[i]);
    ans = max(ans, i - x + 1);
  }
  cout << ans;
  return 0;
}

正确代码:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 5e5 + 5;

int n, ans;
ll m, a[N], pre[N];

bool check(int x, int i, ll k) {
  return k * (i - x + 1) - pre[i] + pre[x - 1] <= m;
}

int puck(int l, int r, int i, ll x) {
  while (l < r) {
    int mid = l + r >> 1;
    check(mid, i, x) ? r = mid : l = mid + 1;
  }
  return l;
}

int main() {
  freopen("crystal.in", "r", stdin);
  freopen("crystal.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; i++) {
    pre[i] = pre[i - 1] + a[i];
  }
  for (int i = 1; i <= n; i++) {
    int x = puck(1, i, i, a[i]);
    ans = max(ans, i - x + 1);
  }
  cout << ans;
  return 0;
}

我的 40pts 呜呜呜。

本来我 187 的。

T2 题面一开始没看懂 /ll。

玩了半小时冲浪哈哈哈。

突然看懂题面。

T2 想出 Floyd 之后把自己否定了。

欧克啊打暴力。

欧克啊又玩了半小时纸牌。

60 + 28 + 24 + 15

交给教练的总结:

S

T1

贪心。

注意到如果要选一段长度为 m 的子序列 s_1, s_2, \dots, s_m 时 s 之间的差要尽可能的小。

所以先排序,嗯对。

对于每个 i 求能够选到的最右边的那个位置我们可以通过二分查找解决。

T2

Floyd。

我唐了。

考场上想到了然后把自己的思路否定了。

你说我为什么当时听到是 Floyd 的时候这么疑惑呢?

把路径当点做 Floyd(因为坐地铁不耗费时间),然后询问时枚举从哪个站上车就可以了。

嗯对是的我现在还不会 T3,但是好心学长 @Gcend 说会给我讲哈哈哈。

day1.90

吃晚饭时间到!

隔壁火锅店好便宜啊,还挺好吃。

我妈来跟我们一起吃饭了嘿嘿。

day1.99

回家了 /kel。

当时我还不知道我 T1 要开 longlong。

于是我肥肠开心。

于是我还看了会儿南部档案哈哈哈。

dayINF

T1 没开 longlong 气疯了。

本来是 HN 初一女生第三的(骗你的现在好像也是)。

本来 187 的。

本来……

好吧根本没有什么本来。

错了就是错了。

没有什么为自己开脱的理由。

今年最大的遗憾估计还是 S 组 T1 吧。

遗憾也没啥用了。

只能明年再战了 /ll。