:::
:::info[引言]
`期中数学和物理总分进不了班里前15,就别想去早培!`
:::
## Day -114514
饿啊饿啊饿啊,我是可爱的初二小蒟蒻喵,我要向 CSP 宣战了喵!
给€€£ 捐款了 200¥喵!
暑假没有训 whk,全在训 OI,而且训的成果很差喵!
开学后我变成了由班级 whk 成绩构成的小根堆中的最有资历的老祖宗喽!
同桌好强。
## Day -41
去初赛了喵!
上午我爸开车带我去的,大概八点半到场吧。金桥双语实验的环境还是很美妙的。公共书架就是和普通学校不一样,还有《高等数学》和《数学女孩》(非常喜欢的书)。
J 组随便考的吧,92pts 好像。结果并没有我同桌[^0]的小学同班同学[^1](他 96pts)高。于是跟同桌开玩笑说:“你是越往上爬,环境越弱。”
感觉错的题应该就是一道 bfs 的单选题忘算起点,然后手算质数题蒙错了,然后最后一道 l\_min,r\_max 看反了吧。大概就这样。J 组没啥用。
下午面积到了 Cola2012, huyichen0903, Hugo12168, qianhy\_cool, Au1nk[^yiduichuangxinban]。以及对面好像坐着一个之前受过 bhq[^2]指导的 NGOIer[^3]。
提高组简直是噩耗。考前没怎么练 S 的初赛,导致一堆题做错了,单选题好像只对了七道。阅读理解还看错一堆。完型填空也没蒙对多少。反正是让我原形毕露。
考完后紧张了一周。
同桌安慰我。
## Day ?
出分。J92,S60。紧张了好几天。
linzhiyuan2013 给了我张 njsy 和 njgz 的晋级选手分数表。发现被一堆学妹学弟单调队列。难受了好久。
Cola2012 的分竟然和我们著名的一位学姐[^hya]差不多高。
同桌鼓励我,一定要超越他们啊。/fendou
## Day ??
卡 0.5pts 过 S。用的希沃查的 JS 晋级线,激动(更多是吓)得叫了。
被全班观摩。
:::info[期间的 whk]
数学周练极其糟糕。附上学测网 rating。其他科目也不用提,基本都是凑合的状态。政史更是基本没有自主的背诵。至少和七年级相差很大。期间被家长骂了不知道多少次,甚至初三都不让参赛了。唉。
同桌让我进前 3。
:::
## Day ???
给€€£ 捐款 870¥。当时就感觉,一个月时间可能有点来不及再练提高组了,有种不太好的预感。
## Day 0
晚上“延时托管”和老班请了假,也许带着祝福奔赴校门口。然而因为和 zhonglele 去的太早了,所以就在门口看了会儿模板。事实上赛时一个都没用上。
约莫过了二十分钟,浮木来接我了。木给我买了美味的巧克力、法棍一样的面包和炫迈口香糖。然后到了江阴高铁站,江阴高铁站真的好小。看到了 zhonglele 和小学同学,以及别的学校的打 csp 的。
高铁上刷脸没过,走人工通道,浪费 2min。高铁上在写 [P3373](/problem/P3373)。结果一个小时没写完,气死我了。
到了酒店,发现有一堆同桌的老乡组团来的。在电梯上被 syz[^4]高一 OIer 感叹被单调队列。但不是因为他们起步晚吗,我真的很弱,学了三四年才这个水平。虽然同桌跟我说亲戚没有一个考上省宜中的。哦对了,好像还有个九创的 dalao[^?],但是不认识。
晚上先到 dyy1234 的房间找教练 xiaolu\_88 那和 unsigned\_short, lucky\_luogu, dyy1234, qyh0\_km[^xiaoluxuesheng] 写了场 S 模拟赛(dyy1234 弟弟也在场,听说被 dyy 教的二年级就知道了【】[^lu]是什么意思),获得了 0pts 的好成绩。教练告诉我和 zhonglele 今年做好拿不到一级的准备。
回到自己房间。终于把 [P3373](/problem/P3373) 写完了。23:46 睡觉。
悠哉悠哉,辗转反侧。
## Day 1 比赛日
### 入门组
06:15 起来了喵。
酒店早饭好吃。
打车达到 NUAA。打错门了。又打了一次。浪费半小时。
跑到大楼门口,发现领队快走了。前面看到了一位 njgz 的女选手,好像之前被教练 lianghua 叫去集训的时候遇到过,好像是八创的(被学妹单调队列了)。不是你们想的那位著名女选手。
:::warning[尬聊]
> 我:`“你好喵,我是不是之前在njgz看到过你喵?”`
她:`“是的呀,xzj!”`
> 我:(wc 她怎么知道我名字的,我在 njgz 都没跟别人说过我叫什么,就算说过她也听不到。)
> 我:`“???你咋知道我名字的?”`
她:`“我怎么会不知道呢?”`
> 我:`“???”`
(上楼)
(到了考场门口)
> 我:`“给你块巧克力。”`
她:`“谢谢。”` 并领取。
:::
此外我后面排着一位比较低龄的人。
进考场了。座位是环形的。
不小心坐成 S 组的座位了。被监考嘲笑。于是监考向大家宣告一定要看清自己的座位。
监考叫我们不要带纸质资料进考场。我发现我校服口袋里不小心塞了张语文周末讲义。于是上交。
:::warning[尬聊]
> 我:(手持语文讲义)`“老师,垃圾桶在哪里”`
主监考:`“...你放门口吧。”`
> 我把语文讲义放在门口。
另一位监考看了我的纸质资料,没绷住。
:::
不小心把语文每月课堂练习分数条带过来了。气死我了。我带了这么语文资料,考场上竟然默写不出 [OI 史上最有文采的文章](https://qoj.ac/problem/10148)。监考终于绷住了。
待我处理完所有问题后,已经过去了半个小时。
听说隔壁考场有个人不小心把 `cspj.zip` 删掉了。全场爆笑。
下发密码 `Treat?Trick!`[^jpass]才发现今天是万圣夜。
大约浏览了一下试卷,发现自己好像只能写 A。很紧张。
哎呀,这个 A 不是一眼题吗。3min 写完。[^ABCDF]
:::info[A 题解]
我常常找寻座位。
生命瞬间定格在脑海。我将背后的车厢裁剪、折叠、蜷曲,揉捻成五个座位。
座位之间亦有分别:A、B、C 在过道左侧,D、F 在过道右侧,C 与 D 之间是过道,而 E 从未存在。列车有十七节车厢,01 和 16 是一等座,其余才是二等座;每节二等座十八排,每排五个座位,座位号由两位排号和一位大写字母组成。题目里震撼的分讨掠过考生的思绪便一生无法忘怀,而更为普通平常的字母编号在题目的冲刷下只留下些许残骸。找寻宛如入梦,太过清楚便看见 C 与 D 之间的过道,无法愉悦自己的幻想;过分模糊又把 E 当成真座位,坠入虚无。只有字符间的对称,纸牌下的置换,那恰到好处的朦胧,才能满足我对美的苛求。
找寻总在不经意间将我裹进泛黄的 pdf 里。重聚又分别的字母,存在又滚木的样例,种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上,像从 02 号车厢一路数到 17 号,却总在 01 和 16 号一等座前想起自己买的是二等座票。曾经的日子无法重来,我只不过是一个过客,一个拿着合法座位号、却可能坐进别人记忆过道里的乘客。至于同车厢、同排、同侧、相邻,官方数据只肯给我四位 01,像给回忆做四次安检,多一个字母都不认。但我仍然渴望在每一次追忆之旅中留下闲暇时间,在一个场景前驻足,在岁月的朦胧里瞭望过去的自己,感受尽可能多的甜蜜。美好的风景曾流过我的身体,我便心满意足。
题面已经凝固,我带着回忆向前,只是时常疏于在意,字母序号也在改变着各自的形态。这给我的写题旅程带来些许挑战。
我该在哪里落座?我问我自己。
(本文使用 DeepSeek-V4.1-Flash-1017 进行了润色)
:::
:::warning[A 裹脚布]
实际上我自认为我 A 的码风还可以。
YJ 是*岩浆*(`minecraft:lava`)的缩写。
235 是前三个质数的字符串拼接。因为我非常喜欢*初等数论(Elementary Number Theory)*。
```cpp
// YJ is cute. OvO
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using LL = __int128;
template<typename T = ll>
T qr() {
T x = 0;
int c = getchar(), e = 1;
for (; !isdigit(c); c = getchar()) if (c == '-') e = -1;
for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return e * x;
}
template<typename T>
void qr(T& x) {
x = qr();
}
template<typename T>
void qw(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) qw(x / 10);
putchar(x % 10 + '0');
}
constexpr int MAXN = 235235;
constexpr ll INF = 235235235235235ll;
int main() {
freopen("travel.in", "r", stdin);
freopen("travel.out", "w", stdout);
string a, x, b, y;
cin >> a >> x >> b >> y;
int r1 = a == b;
int r2 = r1 && x[0] == y[0] && x[1] == y[1];
int r3 = r2 && (x[2] == 'A' && y[2] == 'B' || x[2] == 'A' && y[2] == 'C'
|| x[2] == 'B' && y[2] == 'A' || x[2] == 'B' && y[2] == 'C'
|| x[2] == 'C' && y[2] == 'A' || x[2] == 'C' && y[2] == 'B'
|| x[2] == 'D' && y[2] == 'F' || x[2] == 'F' && y[2] == 'D'
);
int r4 = r2 && (x[2] == 'A' && y[2] == 'B' || x[2] == 'B' && y[2] == 'A'
|| x[2] == 'B' && y[2] == 'C' || x[2] == 'C' && y[2] == 'B'
|| x[2] == 'D' && y[2] == 'F' || x[2] == 'F' && y[2] == 'D'
);
cout << r1 << r2 << r3 << r4 << '\n';
return 0;
}
```
:::
幸亏我写的 F。
开 B。好像不会。开 C。呃呃呃把玩了几只样例,发现处理每一位 `1` 的个数与 $m$ 的关系即可。5min 实现好。
:::warning[C 裹脚布]
```cpp
// YJ is cute. OvO
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using LL = __int128;
template<typename T = ll>
T qr() {
T x = 0;
int c = getchar(), e = 1;
for (; !isdigit(c); c = getchar()) if (c == '-') e = -1;
for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return e * x;
}
template<typename T>
void qr(T& x) {
x = qr();
}
template<typename T>
void qw(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) qw(x / 10);
putchar(x % 10 + '0');
}
constexpr int MAXN = 235235;
constexpr ll INF = 235235235235235ll;
int n, m;
ll a[MAXN], c[MAXN];
int cnt[32];
int main() {
freopen("and.in", "r", stdin);
freopen("and.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; ++ i) cin >> a[i], c[i] = a[i];
for (int b = 0; b <= 31; ++ b) {
for (int i = 0; i <= n; ++ i) {
if (a[i] & (1 << b)) {
++cnt[b];
}
}
}
for (int b = 0; b <= 30; ++ b) {
if (cnt[b] < m) {
for (int i = 1; i <= n; ++ i) {
if (c[i] & (1 << b)) {
c[i] ^= 1 << b;
}
}
}
}
sort(c + 1, c + 1 + n, greater<ll>());
// for (int i = 1; i <= n; ++ i) {
// cerr << "c_" << i << ": " << c[i] << '\n';
// }
ll ans = ~0ll;
for (int i = 1; i <= m; ++ i) {
ans &= c[i];
}
cout << ans << '\n';
return 0;
}
```
:::
回滚看 B。想了个极其抽象的思路,调了两个小时。由于太难描述,在此附上代码节选:
:::warning[B 裹脚布]
```cpp
// YJ is cute. OvO
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using LL = __int128;
template<typename T = ll>
T qr() {
T x = 0;
int c = getchar(), e = 1;
for (; !isdigit(c); c = getchar()) if (c == '-') e = -1;
for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return e * x;
}
template<typename T>
void qr(T& x) {
x = qr();
}
template<typename T>
void qw(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) qw(x / 10);
putchar(x % 10 + '0');
}
constexpr int MAXN = 235235;
constexpr ll INF = 235235235235235ll;
int main() {
freopen("string.in", "r", stdin);
freopen("string.out", "w", stdout);
int n;
cin >> n;
vector<ll> a(n + 2, 0), b(n + 2, 0);
vector<ll> pa(n + 2, 0);
vector<ll> pb(n + 2, 0);
vector<char> c(n + 2, 0), d(n + 2, 0);
ll L = 0;
for (int i = 1; i <= n; ++ i) {
cin >> a[i] >> c[i];
pa[i] = pa[i - 1] + a[i];
}
b = a;
reverse(b.begin(), b.end());
d = c;
reverse(d.begin(), d.end());
for (int i = 1; i <= n; ++ i) {
pb[i] = pb[i - 1] + b[i];
}
vector<ll> p(1, 0);
for (int i = 1; i <= n; ++ i) {
p.push_back(pa[i]);
p.push_back(pb[i]);
}
p.push_back(0);
sort(p.begin() + 1, p.begin() + 1 + (n << 1));
int nn = unique(p.begin() + 1, p.begin() + 1 + (n << 1)) - p.begin();
vector<int> A(nn + 2, 0), B(nn + 2, 0); // { raw_index }
for (int i = 1; i <= nn; ++ i) {
auto it = lower_bound(pa.begin(), pa.end() - 1, p[i]) ;
A[i] = it - pa.begin();
}
for (int i = 1; i <= nn; ++ i) {
auto it = lower_bound(pb.begin(), pb.end() - 1, p[i]) ;
B[i] = it - pb.begin();
}
ll ans = 0;
for (int i = 1; i <= nn; ++ i) {
if (c[A[i]] != d[B[i]]) {
// cerr << "p_" << i << ": " << p[i] << ' ';
ans += p[i] - p[i - 1];
// cerr << "now ans: " << ans << " idx: " << i << '\n';
}
// if (p[i] > p[nn] / 2) {
// // break;
// cerr << "ED!\n";
// }
// if (ans > 24500) {
// break;
// }
if (n & 1 && A[i] == n + 1 - B[i] || !(n & 1) && A[i] == n - B[i]) { // ??? why this is right!!!!
break;
}
}
cout << ans << '\n';
// cerr << "tot_len: " << p[nn] << '\n';
// cerr <<
// ll lst_cut = 1;
// vector<pair<ll,ll>> r(1, {0,0});
// for (ll i = 1, j = 1, li = 0, lj = 0; i <= n, j <= nn; ++ i) {
// if (p[j] == pa[i]) {
// }
// }
// ll t_tot = 0;
// if (L & 1) {
// ll mid = (L + 1) >> 1;
// } else {
// ll mid = (L + 0) >> 1;
// ll rt_endi = -1, rt_endj = -1;
// for (int i = 1; i <= n; t_tot += a[i], ++ i) {
// if (bega[i] <= mid && mid <= enda[i]) {
// rt_endi = i;
// }
// }
// }
return 0;
}
```
最后挂了个点。
:::
此时我已经没有时间思考 D 了,所以随便打了个 36pts 的暴力,后来写了个特殊性质,优化了一下暴力,大概长这样(有点 AI):
:::warning[D 裹脚布]
```cpp
// YJ is cute. OvO
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using LL = __int128;
template<typename T = ll>
T qr() {
T x = 0;
int c = getchar(), e = 1;
for (; !isdigit(c); c = getchar()) if (c == '-') e = -1;
for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return e * x;
}
template<typename T>
void qr(T& x) {
x = qr();
}
template<typename T>
void qw(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) qw(x / 10);
putchar(x % 10 + '0');
}
constexpr int MAXN = 532532;
constexpr ll INF = 235235235235235ll;
int n, m;
ll a[MAXN];
int nxt[MAXN], lst[MAXN]; // lst[value] = index
ll cnt[MAXN];
void brute_force1() {
vector<int> cnt(m + 1, 0);
for (int beg = 1; beg <= n; ++ beg) {
vector<stack<int>> lst(m + 1);
// fill(lst + 1, lst + 1 + m, -1);
vector<int> exist(n + 1, true);
for (int i = beg; i <= n; ++ i) {
if (lst[a[i]].size()) {
for (int j = lst[a[i]].top(); j < i; ++ j) {
exist[j] = false;
// cerr << j << " out! \n";
if (lst[a[j]].size()) {
lst[a[j]].pop();
}
}
}
lst[a[i]].push(i);
}
for (int i = beg; i <= n; ++ i) {
if (exist[i]) {
// cerr << "round " << beg << " exist idx" << i << '\n';
++cnt[a[i]];
}
}
}
for (int i = 1; i <= m; ++ i) {
cout << cnt[i] << ' ';
}
cout << '\n';
}
void brute_force2() {
vector<int> cnt(m + 1, 0);
for (int beg = 1; beg <= n; ++ beg) {
vector<stack<int>> lst(m + 1);
vector<int> exist(n + 1, true);
vector<int> rm_r(n + 1, -1); // rm_r[l] = r + 1; [ )
for (int i = beg; i <= n; ++ i) {
if (lst[a[i]].size()) {
auto tmp = lst[a[i]].top(); // now lst
for (int j = tmp; j < i; ++ j) {
// cerr << "111\n";
if (rm_r[j] != -1) {
// cerr << "Skip" << j << "to" << rm_r[j] << " i: " << i << '\n';
j = rm_r[j];
// cerr << "j=" << j << '\n';
if (j >= i) {
break;
}
}
exist[j] = false;
// if(j==4702) {
// cerr << exist[j] << '\n';
// }
// cerr << j << " out! \n";
if (lst[a[j]].size()) {
lst[a[j]].pop();
}
// ++j; //
}
rm_r[tmp] = max(rm_r[tmp], i);
}
lst[a[i]].push(i);
}
for (int i = beg; i <= n; ++ i) {
if (exist[i]) {
// cerr << "round " << beg << " exist idx" << i << '\n';
++cnt[a[i]];
}
}
}
for (int i = 1; i <= m; ++ i) {
cout << cnt[i] << ' ';
}
cout << '\n';
}
int main() {
freopen("card.in", "r", stdin);
freopen("card.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; ++ i) cin >> a[i];
// fill(nxt + 1, nxt + 1 + n, -1);
// fill(lst + 1, lst + 1 + n, -1);
// for (int i = 1; i <= n; ++ i) {
// if (lst[a[i]] != -1) nxt[lst[a[i]]] = i;
// lst[a[i]] = i;
// }
// vector<pair<int, int>> r;
// for (int i = 1; i <= n; ++ i) {
// if (nxt[i] != -1) {
// r.emplace_back(i, nxt[i] - 1);
// }
// }
// sort(r.begin(), r.end());
// auto s = r;
bool chkA = true;
for (int i = 1; i < n; ++ i) {
if (a[i] > a[i + 1]) {
chkA = false;
break;
}
}
if (chkA) {
vector<ll> cnt(m + 1, 0);
for (int i = 1; i <= n; ++ i) ++cnt[a[i]];
vector<ll> pre(m + 1, 0);
for (int i = 1; i <= m; ++ i) {
pre[i] = pre[i - 1] + cnt[i];
cout << pre[i] << ' ';
}
cout << '\n';
// cout << accumulate(cnt.begin(), cnt.end(), 0);
return 0;
}
if (n <= 500) brute_force1();
else if (n <= 5000) brute_force2();
else brute_force2();
return 0;
}
```
:::
期间犯了很多唐人实现错误。
最后 2min 极限调完。赶紧把 `freopen` 的注释删掉,拷到准考证文件夹,记录字节。
估分 $100+100+100+[40,52]=[340,352]\mathrm{pts}$。不知道他们为何在震惊 $352$ 这个分,这个分又不高。还有人说我控分喵。气死我了。
出考场的时候看到了 Cola2012。
qyh0\_km 估分两百多,具体忘了。
zhonglele 想到正解了,但没写完。于是 $300$ 分。
其他人我不知道。
### 中午
我让我们的家长不要在酒店吃,来不及,就是不听。
但是午饭还是挺好吃的。好像点了两家,一家是南京大排档,另家忘了。
吃完饭赶紧过去。路上 zhonglele 和我谈论人际关系的问题,好像是关于心理经理的。听完后我有点惭愧,感觉自己的真正的内心世界得以受到他的深度交流,真的很幸福。
### 提高组
到了 NUAA 发现领队已经走了。一个人也没面积到。赶紧跑到考场。
S 组考场比 J 组小多了,还很不舒服。座位左边是一个临港科创的人。右边忘了,好像是连云港的。
密码好像是 `Oct.31!=Dec.25`。双关语[^sg]。
看了一下卷子,发现 BCD 都挺离谱的样子。害怕。`巧克力好吃`
开 A。`巧克力好吃`。有点慌,感觉是一道黄题,又有点没头绪。`巧克力好吃`。手玩了一下样例。`巧克力好吃`。发现好像排序后答案对于某种处理方式具有单调性。`巧克力好吃`。结果不知道怎么想的,又反证出来没有单调性。`巧克力好吃`。思 `巧克力好吃` 考 `巧克力好吃` 了 `巧克力好吃`**2`巧克力好吃`. `巧克力好吃`5`巧克力好吃` 个 `巧克力好吃` 小 `巧克力好吃` 时**的 `巧克力好吃` 双 `巧克力好吃` 指 `巧克力好吃` 针 `巧克力好吃` 没 `巧克力好吃` 调 `巧克力好吃` 出 `巧克力好吃` 来。这时我就知道我这次可能又要像去年一样拿不到奖了,内心非常紧张。`巧克力好吃`
赶紧跑去把 C 的暴力 40pts 写了。`巧克力好吃`。期间因为忘写 `q.pop();` 浪费十分钟。`巧克力好吃`。总耗时约 40min。
然后滚回到了 A,绝望地写了个暴力。`巧克力好吃`。写完暴力发现单调性,直接改成二分。`巧克力好吃`。一次没调过大样例。`巧克力好吃`。我气得飚了口不文明用语。`巧克力好吃`。早知道这样直接先打个暴力再观察自己的代码改成二分就行了,双指针大可不必,边界太麻烦了。浪费了 $\frac35$ 的考试时间。自此,奠定了我只有二级的结局。
最后尝试写 BD,发现 B 怎么也读不懂。最后 5min 写了个 D 的特殊性质,当然了,写出来的肯定是错的。然而离正确结果只差除以四。吃好巧克力了。
记完文件大小后发现自己浑身上下都在抖。这是我初中一年多以来最紧张的一次。
那一道双指针,那一张题目描述,击碎了我的 $\sqrt7$ 梦。
$100+0+40+0=140\mathrm{pts}
:::warning[裹脚布]
A
// Yan JIANG is very cute ! ! ! ! He will help me AK 2026 CSP-S2.
/*
wo chang chang zhui yi guo qu
sheng ming shun jian ding ge zai nao hai
wo jiang bei hou de shi jian cai jian zhe die quan qu, rou nian cheng tian shang dup duo bai yun.
yun duo zhi jian yi you fen bie
*/
#include <bits/stdc++.h>
using namespace std;
// using ll = long long;
using ll = __int128;
using LL = __int128;
const int MAXN = 532532;
const ll INF = 532532532532532ll;
template<typename T = ll>
T qr() {
T x = 0, e = 1;
int c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') e = -1;
for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * e;
}
template<typename T>
T qr(T& x) {
return x = qr<T>();
}
template<typename T>
void qw(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) qw(x / 10);
putchar(x % 10 + '0');
return;
}
ll n, m;
ll a[MAXN], p[MAXN], P[MAXN], q[MAXN], Q[MAXN];
void good() {
sort(a + 1, a + 1 + n, greater<>());
vector<ll> div; /// fen ge xian de you mian de dian de bian hao
for (ll i = 1; i <= n; ++ i) {
if (a[i] != a[i - 1]) {
div.push_back(i);
// cerr << "div_" << ": " << i << '\n';
}
}
ll ans = 0;
ll lsta = a[1];
ll lstdone = 1;
ll lstuse = 0;
ll r1 = -1, r2 = -2;
for (ll I = 0; I < div.size() - 1; ++ I) {
ll i = div[I];
ll nx = div[I + 1];
ll use = 0;
ll j = lstdone;
ll tmp = 0;
for (; use <= m - lstuse && j <= n; ++ j) {
use += a[i] - a[j];
// cerr << "i:" << i << " j:" << j;
// cerr << " now use: " << use << '\n';
if (use > m - lstuse) {
use -= a[i] - a[j];
// cerr << "i:" << i << " use:" << use << " j:" << j << '\n';
if (i == 1) {
// cerr << "fff " << n *
}
break;
}
} // j: first dont valid
// --j;
// cerr << "[ " << i << ", " << j << " ] use: " << use << " lstuse: " << lstuse << '\n';
lstdone = j;
lstuse = use - (a[i] - a[nx]) * (j - nx);
// cerr << "[i, nx]: " << i << ' ' << nx << ' ' << "use: " <<
if (j - i > ans) {
r1 = i, r2 = j;
}
ans = max(ans, j - i);
if (I > 10) { //
break;
}
}
qw(ans),putchar('\n');
// cerr << "sum: " << n * *max_element(a + 1, a + 1 + n) - accumulate(a + 1, a + 1 + n, 0ll) << '\n';
// cerr << "r1: " << r1 << " r2: " << r2 << '\n';
}
void brute( ) {
sort(a + 1, a + 1 + n, greater<>());
vector<ll> div; /// fen ge xian de you mian de dian de bian hao
for (ll i = 1; i <= n; ++ i) {
if (a[i] != a[i - 1]) {
div.push_back(i);
// cerr << "div_" << ": " << i << '\n';
}
}
ll ans = 0;
ll r1 = -1, r2 = -1;
for (ll i = 1; i <= n; ++ i) {
ll use = 0;
ll j = 1;
for (; (use + a[i] - a[j]) <= m && j <= n; ++ j) {
use += a[i] - a[j];
}
if (j - i >= ans) {
r1 = i, r2 = j;
}
ans = max(ans, j - i);
if (j > n) {
break;
}
// if (I > 10) { //
// break;
// }
}
qw(ans),putchar('\n');
qw(r1),putchar(' '),qw(r2),putchar('\n');
// cerr << "sum: " << n * *max_element(a + 1, a + 1 + n) - accumulate(a + 1, a + 1 + n, 0ll) << '\n';
// cerr << "r1: " << r1 << " r2: " << r2 << '\n';
}
int main() {
freopen("crystal.in", "r", stdin);
freopen("crystal.out", "w", stdout);
qr(n),qr(m);
for (int i = 1; i <= n; ++ i) qr(a[i]);
sort(a + 1, a + 1 + n, greater<>());
auto mx = *max_element(a + 1, a + 1 + n);
vector<ll> p(n + 2, 0);
for (int i = 1; i <= n; ++ i) p[i] = p[i - 1] + mx - a[i];
ll ans = 0;
for (ll beg = 1; beg <= n; ++ beg) {
// for (ll end = beg; end <= n; ++ end) { // [beg, end]
// ll cur = p[end] - p[beg - 1] - (end - beg + 1) * (mx - a[beg]);
// if (cur <= m) {
// ans = max(ans, end - beg + 1);
// }
// }
ll l = beg, r = n;
ll now = 0;
while (l <= r) {
auto mid = (r + l) >> 1;
if (p[mid] - p[beg - 1] - (mid - beg + 1) * (mx - a[beg]) <= m) {
l = mid + 1;
now = mid - beg + 1;
} else {
r = mid - 1;
}
}
ans = max(ans, now);
}
qw(ans), putchar('\n');
// bool chkB = 0;
// if (n >= 2) {
// chkB = 1;
// ll d = a[2] - a[1];
// for (int i = 2; i <= n; ++ i) {
// if (a[i] - a[i-1] != d) {
// chkB = 0;
// }
// }
// }
// if (chkB) {
// // cerr << "dengg\n";
// qw(min((ll)n, (ll)floor(0.5l * (1.l + sqrtl(1.l + 8.l * m / (a[2] - a[1]))))));
// putchar('\n');
// } else {
// brute2();
// }
return 0;
}
// this is the template
B
// Yan JIANG is very cute ! ! ! ! He will help me AK 2026 CSP-S2.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using LL = __int128;
const int MAXN = 532532;
const ll INF = 532532532532532ll;
template<typename T = ll>
T qr() {
T x = 0, e = 1;
int c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') e = -1;
for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * e;
}
template<typename T>
T qr(T& x) {
return x = qr<T>();
}
template<typename T>
void qw(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) qw(x / 10);
putchar(x % 10 + '0');
return;
}
int main() {
freopen("subway.in", "r", stdin);
freopen("subway.out", "w", stdout);
cout << "You have no egg! \n";
return 0; // must!!!
}
// this is the template
C
// Yan JIANG is very cute ! ! ! ! He will help me AK 2026 CSP-S2.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using LL = __int128;
const int MAXN = 532532;
const ll INF = 532532532532532ll;
template<typename T = ll>
T qr() {
T x = 0, e = 1;
int c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') e = -1;
for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * e;
}
template<typename T>
T qr(T& x) {
return x = qr<T>();
}
template<typename T>
void qw(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) qw(x / 10);
putchar(x % 10 + '0');
return;
}
using T = long long;
struct Edge {
int u, v;
ll w;
};
struct To {
int v;
ll w;
const bool operator>(const To& that) const {
return w > that.w;
}
};
void solve() {
ll n, d;
cin >> n >> d;
vector<ll> x(n + 2);
vector<vector<To>> g(n + 1, vector<To>{});
for (int i = 1; i <= n; ++ i) {
cin >> x[i];
}
// cerr << "input done\n";
for (int i = 1; i <= n; ++ i) {
for (int j = i + 1; j <= n; ++ j) {
if (x[j] - x[i] <= d) {
// g[i].push_back({j, x[j] - x[i]});
// g[j].push_back({i, x[j] - x[i]});
g[i].push_back({j, 1});
// g[j].push_back({i, 1});
// cerr << "+\n";
}
}
}
// vector<vector<ll>> fr(n + 2, vector<ll>(n + 2, 0));
ll tot = 0;
for (int s = 1; s <= n; ++ s) {
vector<ll> dis(n + 1, LLONG_MAX / 2);
vector<int> vis(n + 1, false);
vector<ll> cnt(n + 1, 0);
// priority_queue<To, vector<To>, greater<To>> pq;
// pq.push({s, 0});
queue<int> q;
q.push(s);
dis[s] = 0;
cnt[s] = 1;
// while (pq.size()) {
while (q.size()) {
// auto t1 = pq.top();
// pq.pop();
// auto u = t1.v;
// auto w = t1.w;
auto u = q.front();
q.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto& t2 : g[u]) {
auto v = t2.v;
auto w = t2.w;
// cerr << "uv " << u << ' ' << v << '\n';
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u];
// cerr << "push: " << u << '\n';
// pq.push({v, dis[v]});
q.push(v);
} else if (dis[v] == dis[u] + w) {
cnt[v] += cnt[u];
}
}
}
// cerr << "dis: " << dis[n] << '\n';
for (int t = 1; t <= n; ++ t) {
// cerr << s << " cnt " << t << ": " << cnt[t] << '\n';
if (cnt[t] == 2) {
++tot;
}
}
}
// qw(tot),putchar('\n');
cout << tot << '\n';
}
int main() {
freopen("migrate.in", "r", stdin);
freopen("migrate.out", "w", stdout);
int c, t;
cin >> c >> t;
for (; t--; ) {
solve();
}
return 0; // must!!!
}
// this is the template
D
// Yan JIANG is very cute ! ! ! ! He will help me AK 2026 CSP-S2.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using LL = __int128;
const int MAXN = 532532;
const ll INF = 532532532532532ll;
template<typename T = ll>
T qr() {
T x = 0, e = 1;
int c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') e = -1;
for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * e;
}
template<typename T>
T qr(T& x) {
return x = qr<T>();
}
template<typename T>
void qw(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) qw(x / 10);
putchar(x % 10 + '0');
return;
}
int main() {
freopen("hub.in", "r", stdin);
freopen("hub.out", "w", stdout);
int c, t;
cin >> c >> t;
for (; t--; ) {
int n, k;
vector<vector<int>> g(n + 2, vector<int>{});
vector<int> candrt;
for (int i = 2; i <= n; ++ i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
if (v == u + 1) {
candrt.push_back(v);
}
}
int rt = *min_element(candrt.begin(), candrt.end());
int l = g[rt][0], r = g[rt][1];
ll lmn = LLONG_MAX;
int lcnt = 1;
for (auto & v: g[l]) {
if (v == l) continue;
l = v;
++lcnt;
}
int rcnt = 1;
for (auto & v: g[r]) {
if (v == r) continue;
r = v;
++rcnt;
}
cout << lcnt + rcnt << '\n';
}
return 0; // must!!!
}
// this is the template