传送门：洛谷 CF2244D Yaroslav and Productivity | Codeforces D. Yaroslav and Productivity 更佳的阅读体验：CF2244D 题解简要题意：给你两个序列 $a$ 和 $b$，每次操作可以选定一个位置 $i$，翻转 $[1, b_i]$ 上的 $a_i$ 的符号，你需要进行任意次操作来最大化 $\sum a_i$。$m \le n \le 2 \times 10^5$。这里有一个很重要的观察，就是如果我们对 $b$ 排序，把 $b_i$ 当作 $a$ 上的“分隔点”位置，那么就一定存在一种操作的方案，使得相邻两个 $b_i$ 之间对应的 $a_i$ 的符号可以独立决定。也就是说，我们对 $b$ 排序后，$a$ 就可以被分为形如$$ [1, b_1], [b_1 + 1, b_2], \cdots, [b_{m - 1} + 1, b_m], [b_m + 1, n] $$的 $m + 1$ 个区间。我们可以独立决定每个区间内是保持原来的符号，还是整体取反。此时我们发现，答案其实就是区间和的绝对值再求和。单组数据时间复杂度 $O(n + m \log m)$。#include <iostream> #include <algorithm> using namespace std; using ll = long long; const int N = 2e5 + 10; int t, n, m; ll a[N], b[N], ans; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); for (cin >> t; t; --t) { ans = 0; cin >> n >> m; for (int i = 1; i <= n; ++i) { cin >> a[i]; a[i] += a[i - 1]; } for (int i = 1; i <= m; ++i) cin >> b[i]; sort(b + 1, b + m + 1); for (int i = 1; i <= m; ++i) ans += abs(a[b[i]] - a[b[i - 1]]); cout << ans + a[n] - a[b[m]] << '\n'; } return 0; }
传送门：洛谷 CF2244C Stepan and Permutation | Codeforces C. Stepan and Permutation 更佳的阅读体验：CF2244C 题解简要题意：给你一个排列，你可以任意次交换下标差恰好为 $x$ 或 $y$ 的元素，判断是否能使得排列变为升序。$n \le 2 \times 10^5$。我们可以将每个下标看作一个节点，如果两个下标之差为 $x$ 或 $y$，就在它们之间连边。此时，一次操作就是交换图中一条边两端的元素。由此我们发现，在一个连通块内，可以沿路径不断交换，使得连通块内的元素任意排序。但任意排序仅限这个连通块内部，所以元素无法移动到其他连通块里。那我们需要判断的就变成了，对于每个元素，它在原序列中的位置和排序后应该到达的位置是否在同一连通块内。即，是否对于原序列中的任意元素都有 $p_i$ 与 $i$ 在同一连通块内。这一过程可以借助并查集来实现。单组数据时间复杂度 $O(n \alpha(n))$。#include <iostream> #include <algorithm> #include <numeric> using namespace std; const int N = 2e5 + 10; int t, n, x, y, p[N], fa[N], rk[N]; bool flag; int find(int x) { if (x == fa[x]) return x; return fa[x] = find(fa[x]); } void merge(int x, int y) { x = find(x), y = find(y); if (x == y) return; if (rk[x] < rk[y]) fa[x] = fa[y]; else if (rk[x] == rk[y]) fa[x] = fa[y], ++rk[y]; else fa[y] = fa[x]; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); for (cin >> t; t; --t) { flag = false; cin >> n >> x >> y; for (int i = 1; i <= n; ++i) cin >> p[i]; fill(rk + 1, rk + n + 1, 1); iota(fa + 1, fa + n + 1, 1); for (int i = 1; i <= x; ++i) for (int j = i; j <= n; j += x) merge(i, j); for (int i = 1; i <= y; ++i) for (int j = i; j <= n; j += y) merge(i, j); for (int i = 1; i <= n; ++i) if (find(i) != find(p[i])) { flag = true; break; } cout << (flag ? "NO\n" : "YES\n"); } return 0; }
本文同步发表在洛谷专栏，你也可以点击这里以获得更佳的阅读体验。前段时间一直在忙转专业的事情，最近刚刚有空了点，是时候开启新赛季的游记了！4.30 - ICPC 西安邀请赛西安邀请赛正好放在了五一假期前两天，所以正好提前去玩一天！其实是因为明天机票太贵了。早上六点钟就要起来赶早班机，困死我了。不过确实是我和新队友一起打的第一场比赛，其实还是有点期待的。在机场走的时候发现停着一架没见过的彩绘机，发现是天骄航空的新涂装，记录一下。内蒙本土的航空公司，唉有点难评。飞机上睡了会，下飞机买了杯咖啡就去酒店了。我一直在喷，西工大怎么直接把校区建在山里了，从机场打车过去都要七十公里。我的钱包在天上失望地看着我。下午收到了三重喜报！首先是，下午去找了 XDU 的朋友，好久没见了真的很开心。其次是，大概下午三点多的时候，虽然邀请函上写着的是英文题面，但是突然在西安群里看到了有中文题面！让我们感谢 cfz 出题组。然后是，大概下午五点多，通过我的神秘人脉得知到了 NMCPC 目前初步确定的时间！之前一直在担心会不会撞贵州，或是其他比赛。现在正好在贵州缴费截止的前一天得到了，大道消息（？）。NMCPC 不会撞任何比赛了！接下来可以放心缴费了。西工大这个地方，从市里过去还没有快速路或者高速，往返一趟市区二十多公里，以及五十个红绿灯，走一下停一下真挺心烦的吧。晚上回酒店打 CF，大概十二点出头的时候，一转头发现地上有一只爬得飞快的巨大的虫子。大概起码三厘米长，不过我没带眼镜看不清它长啥样，还好没带眼镜。然后把它踩死了并且捏起来扔到垃圾桶，太痛苦了。事后思考了下可能是蟑螂什么的，太恐怖了。煮波超级怕虫子。5.1今天是报到日，当然我不清楚为什么热身赛和正赛都放在了明天，也就是说今天只有一个签到和领物资。所以我就一觉睡到中午十二点了。中午吃了饭就和队友去报到了，我还是要骂为什么要在这么一个鸟不拉屎的山里办比赛。确实是五一，学校里没什么人。我和队友走了大概十多分钟，一路上只能看到同样来报到的其他队伍。这场的物资还挺好看的，包括袋子和衣服和胸牌的设计我都很喜欢。当然，我也确实第一次见到这种，邀请赛级别的比赛，胸牌上只写着「队员」「教练」字样的。去年的辽宁省赛好歹还有个学校名字的。接下来去拍照。一个小趣闻是，拍完照我们报学校名字的时候，摄像老师突然抬头，感觉语言里带着点惊喜地说，他也是我校毕业的。太巧了。签到流程就结束了，然后我就找朋友去玩了，以及买一点明天赛时吃的东西。今天西安下雨了，到我晚上回酒店的时候，出了城区就开始下得很大。是不是叫什么，倾盆大瓢。5.2今天是比赛日！热身赛八点开始，虽然不急，但是还是想早点去，标记一下领地。另外早上七八点，酒店附近根本点不到咖啡，看了下校内的瑞幸早上七点开门，那还是早点去学校里买吧。到了已经七点五十多分了，索性还是先去场地里看看吧。西安是机房竞赛，每个机房都挺小的，大概就只能容得下十几个队，或者更少，反正总体的感觉是略显压抑的，可能和窗外没有太阳也有点关系。机房的 DOMjudge 也很老，具体什么版本我忘了，但反正是有一种上世纪的美感（x）。先去热身赛签了一道题，发现居然有三份中文题面，这波给到夯。然后调了一些配置以及测了一下评测机速度，就下楼买咖啡了。我打开地图认真看了下，居然这么远，已经在整个校区最角落的地方了，还是骑个车去吧。西安的雨还在零星地落着。我骑着车，姑且算是悠闲地，在校内的小路上慢慢往前晃。风一阵一阵地吹过来，带着没散干净的凉意，偶尔还有几滴雨点砸在脸上。空气里混着雨后的潮气和泥土味，倒也让人清醒了不少。骑了一会儿，前面忽然像是进了施工区域。我停下来翻了几次地图，确认自己确实没走错，只好继续往前骑。假期里的校园本来就安静，路上几乎看不到什么人，偏偏远处又时不时传来泥头车的轰隆声。那种空旷和吵闹混在一起，反而显得更冷清了。风再一吹，整个人都不由得打了几个寒战。我回去的时候，热身赛刚好结束，中间有半个小时的开幕式，我懒得看，于是就在楼上转悠，突然发现楼道栏杆上挂的标语很有趣。接下来就是比赛时间了。这场的签到是 E，发现比去年西安站的签到简单多了，三四分钟写出来，然后就提交，然后喜提 TLE，何意味。我看了两三分钟确定程序逻辑不太可能出问题，然后把 umap 改成 map，过了。喜提 29 分钟罚时。我再也不用 umap 了！接下来就去开 D。口胡了一个贪心，交了一发发现 WA 了。然后过了一会按照队友给的思路，将信将疑地写了一份代码。其实没抱有多大希望的，但是居然过了？很惊喜，虽然我也不知道这是咋过的。赛后发现我最开始口胡的那个做法是对的，但是不知道什么地方挂了。接下来去开 J 了。看到 Convex（笑），想到了去年西安站的签到也是 Convex，非常相似啊！最开始想到一个非常接近正解的做法，然后觉得，同一个出题组不太可能在同一个学校的相邻两场比赛里出两道差不多的签到题，然后被我否掉了，就没有继续想下去了。接下来就开始跟着队友讨论，期间交了三发都挂了。过了一会，终于讨论到了一个我觉得很对的做法，写了一下发现过了。然后发现其实就是我最开始口胡的那个做法，到这个时候罚时已经爆炸了，其实已经有点破防了。接下来去开 A，但是具体过程我有点记不清了。过程中有几次队友想去开别的题，被我制止了，还是全力开一道吧。现在事后想起来，当时可能已经受到心态的影响了，所以接下来几个小时，全程都在跟着队友的思路走，当然，这题也确实没开出来。然后就结束了。到最后就是三题，全程没进过铜牌线，当然也就没有牌子了。后面比赛结束后我听了一会讲评，然后和几位朋友面基以后就走了，懒得看闭幕式了。赛后面基的过程中，经过讨论得到，邀请函中写的是 10-13 题（英文），事实上是 14 题和中文题面，鉴定为诈骗。后面打算和队友去市里吃点东西，然后直接去机场。去市区大概又是一个小时打车，怎么这么远。路上我一直在想，这好像不是我该有的水平。不是不该做成这样，而是不该以这种方式做成这样。这些问题似乎，我并不是完全不会，而是有些思路其实已经摸到了边，却又被我自己用各种理由否掉了。我想起来 22 和 23 年刚打 OI 的时候，那时候就始终是，我并不认可自己的水平，也不相信比赛会出我能想到的做法，所以每次有一个看起来像正解的思路出现，我的第一反应其实是先怀疑它。然后发现最早被否掉的东西，其实就是正确答案。好像今天也是这样。这段时间也确实很乱。从上学期期末结束以后，各种琐事就一直没有停过，寒假甚至过年也没能真正歇下来。最近一个多月整个人的精神状态也比较堪忧，好像自从转专业以后，就突然多了很多压力，以及一些很难说清楚但确实一直压在身上的东西。当然我也知道，这些不应该成为我为自己开脱的借口。状态不好是真的，训练强度低也是真的。压力很大是真的，赛场上没有做出该做出的判断也是真的。机会也已经出现过，只是被我自己亲手推开了而已。咎由自取。5.9 - HACPC煮波 CUHK 的朋友放暑假了，昨天来找他玩，所以现在在深圳。早上五点就起来了，先陪他飞回内蒙，我再转机去郑州。好困。他的行李额疑似不够，正好可以把托运行李挂到我的机票上。不过也有好消息是，第一排还有空位，可以稍微舒服点吧。昨天四个小时经济舱飞过来，然后晚上睡了四个小时，加上凌晨起来坐三个小时经济舱，确实有点累。不过也可能是我有点矫情吧。到呼市以后就转机去郑州，下一段是九元航空，老牌廉价航空了。甚至因为不进中航信的系统，所以没办法走机场的中转通道，必须上楼重新办值机重新过安检。值机也不能走机场的柜台，九元和春秋有专属的柜台（笑）。柜台的工作人员态度特别差，问了一下有没有前排和安全出口位置，话还没说完就直接打断我了，问我是不是要升舱。89 块钱，想了一下还是有点舍不得，算了。然后就把身份证和登机牌扔给我了，是字面意思的扔在桌上。廉航的体验从近几场的第一刻开始就很不爽了。其实也不是贪便宜，是只有这一班时间合适。事实上也并不便宜，下午有一班天航票价比它低，服务还比它好，就是单纯的没招了才选它。好丑的涂装。像是飞机长瘤子了。然后就是毫不意外的座椅非常硬非常挤，睡不着，还好就一个小时出头。下飞机就直接去酒店了。到了发现周围特别特别荒凉，我说怎么这么便宜。不过至少离学校近，问题不大。跟队友会合了，接下来就去学校领物资。今年没有郑州邀请赛了，就是单纯的河南省赛。物资很少，其实就只有胸牌和衣服，甚至没有专门的袋子。不过报名费就 450 块钱，能理解以及其实挺划算的。另外衣服还挺好看的。然后和队友去吃了烩面。震撼美味！不过确实有点累，没什么逛的心情，吃完饭就回酒店了。5.10今天是比赛日，不过十点才开始，可以稍微多睡一会。好热好热好热好热好热。到场地了，毕竟是省赛，这次是机房竞赛。不过因为热身赛是线上的吧，其实就相当于没有，所以也是第一次来场地，伴手礼是三个神秘玩偶。当然照片是我赛后拍的。最开始确实不清楚签到题是什么，看了一下 K 就是一个裸的 BFS，没想别的就直接去开了。过了一会队友说 C 直接输出一个 $\max \left \{k, \left \lceil \dfrac{m}{n} \right \rceil \cdot k \right \}$​ 就好了（我应该没记错），所以就火速过去写完 C 交了，目前是 10 分钟。我们交完 C 以后，我就开始打算通读一遍题面，接下来就看到 D 好像很简单。我最开始读假题了（笑），我以为是一个很无脑的结论，然后就告诉队友 D 很简单了，我和另一位队友开始讨论 D。过了几分钟突然意识到我读假题了。队友提出应该是一个背包，但是直接跑背包的复杂度肯定不对。然后想到因为背包容量只有 2，所以其实无脑贪心，到最后三张牌跑一个特判就行。这个时候队友把 K 写完最后一点就提交了，这个时候是 17 分钟。看了一眼榜单，居然在榜首！意思是，我们拿了 K 的一血吗。两位大神队友可以带煮波捧杯吗！于是就换另一位队友上去写贪心。确实很好写，大概十几分钟就写完了。但是交了一发不对，加了几个 corner case 的特判，还是过不了。与此同时换下来的队友也在看题，然后看到了 L，好像可以直接暴力 exgcd，他说他是 exgcd 手子（），所以 D 好几发没过以后就交给他去写 L 了。接下来我们两个人就一直在讨论 D。大概过了三四十分钟，exgcd 手子（？）写不下去了，于是他俩又交换，上去继续改贪心。当然，又是好几发没过。旁边的 exgcd 手子队友也去看了 D，坚持说贪心到很小的范围要跑背包。最后实在没招了，加了一个背包上去，然后也没过。又加了一些细节，过了。这个时候大概比赛刚开始两个小时，我们的 D 已经吃到了惊人的 8 发罚时，震撼美味！接下来是 exgcd 手子队友继续去写 L，期间我带的 exgcd 板子居然还派上用场了，用于核对 exgcd 写得对不对。我们两位接下来就一直在看 E 了。发现是一个大分讨，于是就讨论了一堆情况，期间其实也断断续续交了好几发，但是都 WA 了，还是给队友写 exgcd 吧，我们两个就打印下来代码慢慢研究。大概三个半小时吧，队友的 L 开出来了！这个时候已经写了大概一百行，包含一个 exgcd 以及六个二分（）。感觉很适合放在游记里，所以我把它打印下来了。发餐了，袋子里还是三个郑轻经典的马斯卡彭，还是一如既往地好吃。更多细节可以参考我去年的游记中郑州站的部分。以及一大堆火腿肠，我一根一根拿出来，数了一下发现有九根，不知道为什么就是莫名感觉很好笑（）。当然就是飞速把马斯卡彭继续，吃干抹净（？）了。三个人一直在讨论 E，期间也包含了陆陆续续的提交，以及陆陆续续的 WA。这种事情绝对很奇怪啊.jpg。四个小时了，封榜了。接下来，我们在六秒内飞速完成了四发 E 题的提交，其中第一秒就提交了两发，令人恐惧的效率！事实上是，因为我们在讨论题的时候把手按在题面上了，然后不小心压到了回车键，等我们注意到的时候已经交完四发了（）。等我反应过来发生什么了的时候就已经笑疯了，这种事情是不是写到小说里也是要被喷的，关于我打河南省赛不小心压到回车键被罚 80 分钟这件事。红温！红温！红温！哦突然想起来，是不是我写了好几年 CSP-J/S 迷惑行为大赏的报应（）。接下来就是不断地分讨，不断地提交，不断地 WA。然后一直到 293 分钟，终于过了！所以现在就是 5 题，虽然这个时候罚时已经爆炸了，一道 E 题就 15 发罚时。五道题总共产生了 1152 分钟的雷霆罚时。看了一下，封榜前五题最后一名是 22 名，一共大概是 32 个金。也就是说封榜的一个小时里，只要有不超过 9 个队伍到了 5 题就可以拿金。应该不会有队伍比我们罚时还高了吧。比赛结束了。火腿肠我们没吃，马斯卡彭毕竟就是一个小甜品，还是有点饿的。比赛结束到滚榜还有一个半小时，但是好像也不知道吃啥，索性去学校旁边的麦当劳凑合一口得了。接下来就是激动人心的滚榜！煮波能金吗！滚榜在图书馆，真的好气派。内蒙某校你看看人家。本来说的是每个队只能去一个人，到了会议室发现根本不查人，这回防君子不防小人了。没座位了，我就站在最后面的中间等着拍照。郑轻真的好，打星队伍也发牌子，而且是可以上台领奖的那种。这场滚榜好快，没有玩梗环节，平平淡淡吧，以及打星居然连照片都不放。我们这场队名叫「以上队伍成绩作废」，念到我们队的时候全场都笑了。最后发现就是上位银，离金还有二十多名，那也就没啥遗憾的了。圆满离场！后来领奖是我上去领奖的，好像是我 XCPC 生涯里第一次在正式比赛里上台领奖，虽然也是打星，但是真的好酷好酷好酷。这种感觉真的好棒。斩获人生第二块牌子！领完牌子我们就直接走了，大家心情都不错。图书馆门口就是一个人工湖，里边有很多鱼和各种鸟，我们就顺便在学校里逛了一下，郑轻的校园真的好美，设施也很棒，还有很多标语。其实总是有点不相信它只是一所双非。 还有「输」出快乐人生。接下来就打算直接回去休息了，明天早上直接赶早班机回学校。往门口走的路上在水群，看到居然给打星发了一血，以为我们居然还能拿一个一血。发现前面 K 一血好像埋了个伏笔，事实上是，真正的 K 一血只是没有做更简单的 C 而已（哭）。另外后面了解到，这场河南省赛和北京市赛共用了一部分题目，我说咋这么难。值得一提的是，这场 D 的题目名是，求求你不要再爬塔二了。赛后我把 D 的题面发给了我玩塔二的朋友，他的评价是。然后就回酒店了。下周见。5.15 - ICPC 南昌邀请赛这两天一直在北京，懒得回内蒙了，索性就直接飞南昌了。晚上和队友会合才发现酒店订到 NCU 旁边了（），还好提前来了一天，紧急预定明天的酒店。路上回想了一下，可能是因为我们本来打算打下周的 CCPC 南昌的，所以就订到了下周南昌的承办校旁边，所以改日期的时候就忘记换酒店了。到酒店发现免费给我们升到了江景房，外景确实棒。5.16旁边万象城简单吃了口午饭就去报到了。南昌怎么这么热，其实气温并不算特别高，但感觉加上湿度高（和北京或者内蒙相比），湿热湿热的很难受。依旧，背景板照片。接下来就是领物资，衣服感觉还挺好看的，除了有点像校服。南昌没有袋子，给的是一个双肩包，上面写着「ICPC JXNU」字样，感觉中规中矩？不过四个包加上四件衣服，真的有点不方便拿。胸牌真的很丑。背面其实有很小的两行学校名字，但是你甚至不愿意在正面印上我的学校和名字。抛开这个，单说设计也有一种，十几年前的复古感。接下来就是去机房打热身赛了。机房也非常挤，基本上就是人挤人，我们三个人坐在一起，必须要一直挨着才能坐得下。过道就是很窄的，必须要侧着身才能勉强通过的一道缝。桌上的队伍信息牌简直丑爆了，电脑的壁纸也是。经典学院老登审美风，坚定要求体现学校特色。热身赛写了两道题就跑了，不知道为啥今天下午有点烦，可能是太热了，加上这些物资和环境有点失望，还是回酒店吹空调吧。5.17今天是正赛。顺带一提，这场内大来的是铁匠，早就久仰大名。到机房了，赛前电脑上是一个写着队伍信息的图，说实话这个做得确实棒，好好看。不过好像不太好带手机进去，所以没拍照。下面偷了一张其他队伍拍的照片。然后就开始比赛。A 是签到。题意是，给你 $n$ 和 $m$，判断 $n$ 能不能整除 $m$。还好我记得 $n$ 整除 $m$ 其实是 $m \equiv 0 \pmod{n}$，于是写了一个 cout << !(m % n)。然后 WA 了，在 3 分钟的时候就喜提一发罚时。回来看了一遍，发现输入格式是先输入 $m$ 再输入 $n$，破防了。又交了一发然后过了。接下来去开 I。看起来像是一个求最小代价的板子 DP，然后火速写出来了状态定义和转移方程。但说实话我还没有在正式比赛里切过 DP，我的 DP 水平真的很差，所以还是不太相信自己的想法是正确的，只是抱着试一试的心态写一下而已，至少我觉得看起来挺对的。写完发现过不了样例，接下来想到是不是可以把 DP 改成发送式的，改完然后过了。然后就是 B。刚才我在写 I 的时候队友一直在研究 B，过完 I 的时候队友已经直接给出来我思路了。于是我就按着写，然后中间发现理解错了几次，一直改，大概两个小时的时候过了。看了一眼榜单，这个时候正好比铁匠多了两分钟罚时，我们就在他们下面一名。不过他们先去开的 H，我们先开了 I。接下来就去开 H 了。H 是一道博弈论，其实看到博弈论我就似了，从来没做出来过博弈论，也没有训练过博弈论的题。接下来就是三个小时的讨论。直到封榜前其实已经过掉两百多队了，但是我确实没开出来，直到最后也只得出了平凡的情况的结论。中间其实我想过是不是一个 Nim 游戏，但是又是熟悉的，被我否掉了。内大他们在封榜前就把 I 开出来了，在铜线上大概十名左右的位置。我们没开出来 H，所以遗憾离场。不想看滚榜了，直接改到了三点半的高铁，去高铁站了。路上一直在和群友聊天，然后看到群里发的题解，发现 H 确实是 Nim 游戏。但是具体我也确实不会推，所以我没开出来也合理。问了一下 ChatGPT，它说这题有洛谷蓝的难度，但是能过两百多队，我觉得不太可能。群友说只有黄，我更相信这个难度，但是我又一次赛时没开出来黄题。然后看到群友发了出题人预估难度和赛时榜单反映出来的难度，歪榜歪得没边了，基本除了前三题剩下全是歪的，神人榜单。如何评价 ICPC 南昌。注，图里一大堆的是桌上的队伍信息牌（）。内大拿铜了，说不羡慕当然是假的。另外赛时看到了左边是 Nanani 姐姐，一个人一声不吭默默开掉六题，吓哭了。想到了去年辽宁省赛时候的我，也是单挑，也是一个多小时自己开掉五题，也是在被周围的队伍悄悄议论，现在好像又看到了曾经的自己。我好菜啊。路上想到这里又开始有点难受，大一都快结束了但还是连邀请赛牌子都拿不到，始终都是无功而返吧。然后加上路上一直在拿电脑水群，加上司机开车有点猛，居然晕车了。我几乎从来不晕车的。前段时间规划行程的时候，因为我们三个人周一都是满课，发现南昌没有合适的航班，所以就订到了明天早上武汉的航班，今天晚上就去武汉住。晚上和内大的另一队聚餐了，他们这次南昌和武汉两个队都拿了牌子，内蒙只有我没有牌子。还是有点羡慕以及难受的，当然后来也慢慢调节好了，没有影响特别久。不知道怎么说。南昌的表现感觉是，意料之内的成绩，但是又有点，好像，很失望的感觉，可能是对自己失望吧。下周东北赛，强度稍微低一点，希望能拿到牌子吧。5.23 - CCPC 东北赛周四周五两天运动会，不用上课，所以出来玩了两天。当然最近机票的燃油费都涨飞了，订机票的时候真的很肉疼，哎我草美国怎么这么坏。直接上午到长春和队友会合吧。这次东北赛不在吉大校内，在吉大正元大厦。规划行程的时候发现隔壁就有一家全季，价格并没有很贵，就直接住这家了。一个 fun fact 是，订酒店的时候发现，我直接从华住会上预定要比主办方给的协议价便宜不少，还能送早餐和升房，果断下单。下午去签到。之前在 QQ 群里的时候就感觉这场东北赛很，神秘。今年没有东北邀请赛了，连省内高校的名额都缩水了不少，甚至直到比赛当天都没有一份正式的电子版参赛手册。签到在正元大厦的一楼大厅，签到有很多人，但是只有那么两三张桌子在签到，整个大厅显得很拥挤。甚至由于志愿者工作效率有点低，加上现场没有有效的引导标识，大家都一窝蜂地挤在签到的桌子前面，我挤了好久才挤进去。领到了选手物资。说实话真的有点，我不知道能不能说是失望，反正就是不太喜欢吧。可能很重要的一个原因就是选手衣服很丑，以及给的袋子是一个超大的劣质麻袋。笔也中规中矩，没有什么设计感，就是很普通的商业定制笔。就这个袋子和笔都给人一种，很廉价的感觉。另外一堆广告上面还有一件衣服，但是我没穿所以没拍出来。不过倒是，胸牌长得还可以，至少像是一个正经比赛的吧（）。以及伴手礼是一个特别大的鼠标垫，其实也就是，中规中矩吧。鼠标垫是卷起来的，展开的话就不太方便拿了，这里偷一张群友的图放上来吧。哎不过至少，东北赛的教练服还可以，也是比较经典的灰色。虽然我觉得也不太好看，但还是比那个选手服好看不少吧。另外我们去领教练物资的时候，除了签到表上面的签名，志愿者还把我领到了旁边的一个桌子，让我在学校旁边签我自己的名字。仔细看了一下，居然是给教练的「杰出执教奖（十年）」，这么牛。然后就把这个牌子发给教练了（）。其实是第一次见这种奖牌，之前只见过给那种全国性的特别强的教练发的教练奖项。今天白天好像是吉林省赛的正式赛（？），所以热身赛安排到了晚上六点到八点，吃完晚饭就直接去打热身赛了。发现热身赛题目居然不是按难度排序的，先去开了过题最多的 E，是猜数交互。然后内大队长叫我去找群友面基，他说 C 才是真正的签到，我就把 C 交给队友了。发现东北赛居然，内师去了两个队伍，我们去面了他们二队。在前瞻榜上看到他们 Rating 比我高不少，吓哭了。不过怎么上个学期我好像没见过他们，不会是跟我一届的吧，太恐怖了。半个小时以后回去了，发现队友怎么还没开掉 C。据说是刚写完，我对着报错调了好几分钟才刚过编译，但是样例都过不了。我读了一下题发现 $n \le 25$，删掉从头写两三分钟过了。加训！不过说，怎么热身赛都能歪榜的。5.24酒店就在场馆旁边的好处来了。九点开始比赛，八点五十才下楼，到赛场时间刚刚好。看到三分钟的时候 IMNU 抢了一个 G 的一血，那说明这题应该很简单了（）。看了一眼然后五分钟过了。其实这个时候更多人是在开 H 的，所以接下来就去做 H。发现只需要维护一个字符集的前缀和就好了，也大概五分钟左右就过掉了。接下来去看 C。其实看到的第一眼我就在想一个很显然的贪心，但是我不知道这样是不是对的，所以又被我否掉了。后面大概半个多小时都在和队友讨论其他思路，但是全都是一眼假，就又回去思考我原来的思路。我还是没办法确定它是不是对的，不过实在没招了，写了一下然后一发过了（笑）。看了一眼榜，这个时候我们排名居然已经到 49 了，从来没到过这么高的排名。去算了一下银牌线在 52 左右，也就是说我们现在居然已经到银牌线上了。继续开题。接下来过题最多的是 A 题，但是我们讨论了大概两个多小时，一直没有出来一个看起来很对的结论。我觉得看起来像 DP，写了一个状态出来，但是确实一直不会转移。封榜的时候我们又去看了榜，突然发现怎么师大把 I 过了，这题这么简单吗（？）。是一个字符串填色题。但是封榜前只过了十个队，所以我们一直没去看这题。想了一下是不是直接贪心地填剩余数量最少的颜色即可，感觉找不到什么反例，就开始写。代码也很好写，除了确实挺长的，以及细节有点多。大概封榜前十几分钟的时候写完了，但是写挂了（哭）。我确信我的思路是对的，但是一直到比赛结束也没调出来，所以最后就，三题结束战斗。封榜前我们排名是 68，铜牌线是 105。一个小时总不可能有四十个队过掉第四题吧，所以大概率有铜了！不过师大居然比我们多开一题，确实很震惊。后面讲题发现 A 确实是 DP，但是我状态没写对。你确定这个，真的是 easy 吗。接下来就是激动人心的滚榜！虽然我觉得铜牌已经没什么悬念了。我们最后正式排名掉到了 77，也是在中位铜的位置，赢！后来发现只要我们开出来 I 的话，就大概率可以银了，所以现在来看我们打得其实并不好。不过因为我确实没有过拿银牌的期望，本来期待的就是，拿到牌子就是赢。所以这次东北赛是好结局！牌子相比其他比赛的来说稍微有点小，不过也挺好看的。你们这个银牌怎么铜铜的啊。所以这场就是，我算法竞赛生涯里，真正意义上拿的第一块牌子！真的很激动，甚至其实赛时算出来我们在银牌线上的时候，我愣了一下。我知道是因为东北赛强度低，但也确实是我拿到的第一块牌子。今天不难受，今天很开心！现在真的应了这个队名了，「NOI 没拿到的牌子就在 CCPC 拿吧」。5.30 - CCPC 福州邀请赛说是福州邀请赛，但是其实是线上的，只是交给 FZU 主办而已。这场在中午十二点到下午五点，正好不用赛时吃午饭了，不过坏处就是，需要另外找一个监考志愿者来，至少我不想五个小时不上厕所。比赛需要用 OMS 监考。昨天晚上我想打开电脑去打热身赛，突然想起来 OMS 不支持 Mac，所以今天才临时去取了一趟 Win 的电脑。还好看了一眼热身赛。在图书馆预约了一个学术研讨室，设备架好就开始比赛了。不过说三个手机支架以及好几瓶水真沉啊。A 是签到。一眼无脑搜子串，五分钟秒了。接下来看到很多人都在开 H，我们就也去看 H 了。看到 $n \le 10^3$，其实我的第一反应是直接枚举人数。但是队友更倾向于分讨，于是就和队友一起当分讨做了。接下来就是，无脑吃罚时（）。我们从 32 分钟一直吃到了 92 分钟，其中包含七发罚时，吃爽了。我们调这题的过程中，其中一位队友经常是，想到一类反例以及对应的解决方案之后就跟我说，这次肯定对。我就改完然后提交，然后 WA。中间我突然想到一个好玩的，跟他说，你是豆包吗。我现在给你最直白、最本质、最正确的答案，这次绝对是完全正确的。感觉该换题了，所以就去看这个时候开出来第二多的 B 题。其实之前没有读其他题目，就一直在想一道题。我一读题发现这不就是最板子的二分贪心吗，会做了，于是就让队友继续去想 H，我十分钟写完一发过了。这个时候队友讨论出来一个刚才没考虑到的 corner case，加上以后过了。喜报，我们队已经通过了 3 题，吃到了惊人的 341 分钟罚时。这无疑体现了我们队伍巨大的胃口，未来一定都是赛时吃队友汉堡的好选手，震撼美味！接下来是 D。我是异或和构造题废物，所以 D 的题面对我来说看起来还挺吓人的。大概就是给你一个 01 串，你需要构造一个非负整数序列，使得元素不重复，且通过一堆异或什么什么的运算得到的新字符串，与给定字符串的海明距离不超过 1。$n \le 10^5$，海明距离定义为两个长度相同的字符串中不相同的字符位数。队友也不太熟悉异或，这题因为涉及位运算，所以基本上就全程是我在自己想了。后面慢慢想到了其实就是一个贪心，无脑往一些位置的高位填 1 就行了。然后大概三小时出头的时候过了这题，现在已经是 4 题 619 罚时了，我是罚时大王。其实这场福州和 NMCPC 的热身赛撞了，热身赛是下午三点到五点，所以打算预留一个小时去打热身赛。但是现在感觉半个多小时再开一题的可能性不太大，所以就直接跑了。一个 fun fact。赛后一位队友问我，异或类的题目有没有通解。我的答案显然是没有，涉及到异或的题目太多了，每道题也不可能只有这么一个东西，只有多做题才能积累经验。5.30 - NMCPC这会其实热身赛已经开始了，但是内大队长说去年的热身赛是六道纯语法，十几分钟开完了，所以就没打算提前去，反正就是试机而已。NMCPC 甚至没有可供选手或学生教练加入的赛事 QQ 群，有啥消息全都得找我教练问。我真的觉得 NM 的各种消息都非常非常闭塞，这个当然不是好事。所以前段时间我建了一个 NM XCPC 民间群，这样大家也可以共享一些消息吧。进学校就感觉，这学校氛围怎么怪怪的，但是也说不上来哪里怪。到了比赛场馆，门口同样摆了一个大背景板，虽然确实没见过这么丑的。接下来就去领物资。我报了学校和队伍，然后志愿者给我拿了一个劣质硬纸袋。我惊讶地问了一句，就一个袋子吗，志愿者一脸惊讶地告诉我，对啊你们一个队伍肯定就是一个袋子啊。行吧，毕竟也只是志愿者而已，拿到物资就行。打开袋子发现里边甚至就一份参赛手册，还挺寒酸的哈。然后就上去机房打热身赛。到了机房发现，每个队伍的电脑前面是一个巨大的信息牌，可以完全挡住队伍区域的那种。又大又丑，感觉是能和上面 ICPC 南昌坐一桌的水平。打开机子，发现是 Win，我就知道。不过本来也没有对 NMCPC 抱多大期望，Win 也不至于特别影响做题就是了。我写代码喜欢用 VS Code，但是找了半天也没找到。然后发现整台机子上就只有 Dev-C++、PyCharm、Eclipse 三个 IDE。他们学校的同学平时只有这种机子可以用吗，那也真是辛苦他们了。Eclipse 我没用过，PyCharm 要配编译器，那就只有 Dev 可以用了。我甚至没办法在本地调试 C++ 17。发现怎么连纸质题面都没有，不会明天也没有吧。这次热身赛只有四题，前两题都是验证码难度，几分钟过了。后面两题显然不是语法题啊。放的是去年 ICPC 第二场网络赛的 E 和 H。NMCPC 也在 PTA 上交题。不知道为什么，我们的机器对于 OMS 的显示质量特别差，基本上是特别费力才能看清楚文字的状态，但是切换到 Dev 上面又是正常的。我去联系赛场志愿者，志愿者说联系一下老师。等了一会老师过来了，最开始说我屏幕上的文字能看清楚，言外之意就是不想管吧。我坚持要求解决这个问题，然后他就开始联系其他老师，他们电话里是用蒙语交流的，我听不懂。过了一会跟我说，让我按住 Ctrl 滑动鼠标滚轮，缩放页面。然后他走过去看了一眼其他队伍，回来跟我说，都是这样的。我说我们刚打完 FJCPC，用的是同一套系统，我们就是正常的。这位老师坚称所有的都是这样的，不存在问题，缩放页面就是他所谓的解决方案。事实上是，缩放页面后也不影响显示质量依然很差，还是相当多的锯齿状边缘和糊在一起的文字笔画，只是可以看清字了而已。他认为可以辨认出来是什么字就算是解决问题了，然后离开了。气笑了。后面其实也就没啥心情做后面两题了，环境测试完就走了。我承认我在这种，所谓的不影响比赛的小问题上这么较真，可能看起来显得我很，刻薄。但是我还是认为，如果连最基本的设备都保障不了，那又何谈其他工作呢。不得不承认的是，某些其他省份就是可以花更少的钱办出比贵校好得多的水平，事实就是我没有义务花着钱吃着史，还要夸一句史好吃。关于所谓，都是这样的，试问您打过几场正经比赛吗。至少我没能在 CPC Finder 上找到贵校。第一天的体验就已经烂到爆炸了，甚至有了一种，想退赛的心情。我确实也会有一些刻板印象吧，不是学历歧视，就只是，至少来这里的每一点体验都精准踩中了我对二本院校的刻板印象。当然我没有说我校很好的意思。这下知道为什么不接受省外打星了，原来是家丑不可外扬。队友先回去了，我去楼上机房找 szm，然后了解到他的键盘也不好用。顺便跟二中教练聊了几句，他们学校来了七个队，吓哭了。和一些神秘小团体的群友吐槽，群友的评价是，野鸡比赛打着玩玩得了。晚上教练发消息过来，通知明天要穿参赛服。评价为不如我高中校服。真的必须要穿这个吗。我决定赌一下，不穿了吧，把衣服带上，万一必须穿的话再换。我穿的还是去年 ICPC 武汉站的教练服，至少比这个参赛服好看多了。另外今天热身赛的时候没有发现水和笔，不会明天也没有吧，还是明天自己带点水和笔过去吧。5.31今天是比赛日。其实我有打比赛带一杯咖啡的习惯，今天早上当然也提前点了外卖。不过到学校了下车以后才发现，怎么手里空空的（），原来是忘带咖啡了。倒是无所谓，不影响正常比赛就是了。不过赛前没找到外榜链接，没办法给朋友们发了，虽然我觉得如果只看比赛表现的话，会是对我来说最精彩的比赛之一，有点遗憾。到机房了，发现怎么没有纸质题面，不能真的正赛也没有纸质题面吧。问了志愿者，他说等下会发。虽然事实是一直到开赛前一分钟都没有看到要发题面的迹象。另外发现今天也没有水，志愿者说中午会发餐，里边会有水。那我不会要渴两个小时吧。我说能不能先帮我送几瓶过来，志愿者说也可以，我要了三瓶。接下来就是开始比赛了。先去开 K，题意大概是给你一个 $[0, 3999]$ 范围内的 Codeforces 的 Rating，你需要写一堆 if 来输出对应的段位。为了快一点，我就去写 Python 了，写完也没有测，直接交了。喜提一发罚时。因为 Python 没有编译环节，所以 Python 里的 CE 就是类似 return 1 这样的，一个非正常返回值，所以 CE 也是要吃罚时的。改掉了，又交了一发，然后又吃了一发罚时。又发现了一个神人 typo，改完然后过了。喜报！我们在第 8 分钟就拿到了 1 题 48 分钟的成绩，真是令人震撼的成绩！气笑了。这个是真的难绷。我把代码贴在这里吧，你也来看看（）。下面是第一发罚时。t = int(input()) for i in range(t): n = int（input()) if n == 0: print('Unrated') elif n < 1200: print('Newbie') elif n < 1400: print('Pupil') elif n < 1600: print('Specialist') elif n < 1900: print('Expert') elif n < 2100: print('Candidate Master') elif n < 2300: print('Master') elif n < 2400: print('Internartional Master') elif n < 2600: print('Grandmaster') elif n < 3000: print('International Grandmaster') else: print('Legendary Grandmaster')下面是第二发罚时。t = int(input()) for i in range(t): n = int(input()) if n == 0: print('Unrated') elif n < 1200: print('Newbie') elif n < 1400: print('Pupil') elif n < 1600: print('Specialist') elif n < 1900: print('Expert') elif n < 2100: print('Candidate Master') elif n < 2300: print('Master') elif n < 2400: print('Internartional Master') elif n < 2600: print('Grandmaster') elif n < 3000: print('International Grandmaster') else: print('Legendary Grandmaster')看出来了吗。揭晓答案！（这里可以点击）注意到，第一份代码的第 3 行，左括号是一个中文括号。注意到，第二份代码的倒数第 4 行，International 多了一个 r。我再也不写 Python 了。因为这两发罚时，这个时候我们甚至已经掉到银牌区了。直到开始比赛大概三四分钟的时候，才开始慢慢吞吞地下发纸质题面。我们队的座位还比较靠后，发到我们队的时候我已经差点开出来一题了。接下来就去开 D，这题也水，统计一下字符串的字符数量就好了，也是 Python 写的，一发过了。接下来是 G。这题看着很恐怖啊，像是什么神秘数论题。但是我感觉，这个结论很奇怪啊，打了个表，发现只有 $19, 29, \cdots, 99$ 是合法的，一发过了。然后去做 A。我口胡了一个比较无脑的结论，但是看起来挺对的，直接写一个快速幂，一发过了。去看了一眼榜，发现这个时候的所有队伍都不超过 4 题，包括打星的 szm，尽管他没掉出过总榜 rk1。所以现在就是，半个小时开了 4 题，这个时候又回到正式队伍 rk3 了，还不错。应该签完到了，接下来就不知道要继续开哪道题了。全读了一遍，感觉 J 比较可做。因为是内蒙的省赛，所以我还挺自信的，不至于看到没人开就不敢自己开题，当然这个时候也确实没有别的有人开过的题目了。读完 J 发现特别简单，写了一个 min 和 max 就写完了，样例也能过。交了，然后 WA 了。重新读了一遍题，发现题读假了，需要动态维护这个 min 和 max，有点不好搞啊。接下来的大概两个小时就一直在和队友讨论这题了，当然也就是一直在豆包模式，一直改一直 WA。我还挺喜欢对拍的，经常会写。期间有想过要不要对拍，但是写了一半发现暴力很难写，没办法了。中间发了餐，但是我们也没空吃，就一直在想题。内蒙的午餐包是我见过最寒酸的，就一个面包一盒牛奶。当然也可能是我比赛经历不太丰富导致的，以后多打打比赛（）。现在大概已经是三个半小时了，这个时候榜上还是没人开出 J 来，感觉做这题有点没前途，就换题去开 I 了。这题是个计数题，最开始我不太想推式子，就没去考虑这题。但是现在场上过了最多人的就是这题了，只能硬着头皮做了。不太会推式子，我感觉 DP 也能做，就打算试试。当然因为我的 DP 水平真的很差，所以其实我一直很犹豫，我不确定我是否想出来，以及我想的真的会是对的吗。但是感觉 DP 这个方向挺对的，还是试试吧。因为这题所有变量都 $\le 1000$，所以我设计了一个二维的状态出来，转移方程也能写出来。但是这个时候整个转移是 $O(N^2K)$ 的，外面还要再套一层多测的 $T$，时间复杂度爆炸了。但是至少写出来了，跑了一下样例也过了。出题人还算有良心（），这题的样例给的强度不算低。就至少对于计数题来说，已经到了那种过样例就说明交上去不太可能 WA 的程度了。正确性应该没啥问题了，接下来就考虑能不能优化。因为最内层循环是一个 sum，我在考虑能不能写一个前缀和优化上去，优化掉一个 $N$ 的复杂度。纸上推了一下，发现好像可行，过了一会写出来了，样例还是能过的。这个时候优化到了 $O(NK)$，套上一个 $T$ 大概是 $10^9$，所以就开始想，能不能通过优化一下常数然后卡过去。优化掉了一些冗余的操作，然后把代码改成了更快的 C，交了一发发现还是 TLE 了。感觉优化常数这条路走不通，还是想想能不能继续优化吧。这个时候已经封榜了。看了一眼榜单，发现内大的女队怎么在我上面一名，我已经掉到 rk6 了，吓哭了。实在想不明白啊，二维的状态怎么可能通过一维的循环就跑出来，题目给的这种条件，也没有可能优化成一个线性 DP 吧。好怪，打个表吧。我倒要看看到底怎么个事。打完表以后突然意识到，只要 $N$ 和 $K$ 都确定了，那答案就是唯一的。所以我只需要在询问之前把答案离线下来，询问的时候挨个查表就好了，这下复杂度也对了。交！过了！三个人不约而同地开始鼓掌了。现在是大概四个半小时的时候，感觉也很难开出来其他题了，打算最后再尝试一下 J，最后也确实是无果而终。不过 5 题 423 罚时，金牌应该问题不大了吧。这样的话，这次就算是我第二次在正式比赛里开出来 DP 题，也是第一次在正式比赛里写出 DP 优化，也是我第一次在封榜后开出来题，真的挺有成就感的。那就，光荣离场！今天不遗憾。出去和二队他们会合了，他们没有开出来 I 题。不过居然也推出来 DP 了，只是没想到优化和离线而已。不过他们平时没有训练过这部分内容，我觉得能想到这里已经很强了。他们罚时不算高，4 题 203 罚时。封榜前他们在银牌区 rk3，那肯定就是毫无悬念地银了。我们一起出去吃了个饭，回来刚好滚榜。激动人心的时刻到了！可能是因为有多个组别的原因，滚榜的时候没有直接公布奖项，只念了排名。我们二队拿到了银牌区 rk5，居然只掉了两名。接下来就是我们队。其实滚到我们队的时候，已经掉到 rk8 了。但是，通过一题！滚到上面，最终排名 rk5。以及，发现我们罚时已经炸成这样了，怎么还能是 5 题的 rk1（）。这样的话就是，金牌！其实我一直不太明白捧杯的规则。跟群友聊了一下才知道，奖杯是颁发给校排前三名的队伍的。按照正常 XCPC 的规则，我们校排第三，所以这场捧杯了！那就是我 OI / ACM 生涯里第一次拿金牌，也是第一次捧杯！虽然是野鸡比赛，但是拿到一些成绩了还是很开心。金牌线刚好就是五题。另外发现内大女队没开出来第五题，所以就是 4 题 85 罚时拿了银首，有点遗憾吧。NMCPC 没有赛前拍照环节，但是滚榜的时候怎么会有照片呢？答案是，赛时抓拍。是怎么做到每个队伍的照片都这么丑的。接下来就是颁奖。说是颁奖，其实根本没有牌子。上去就是给你发一个「荣誉证书」，的壳子，里边甚至是空的。荣誉证书一定要有证书！更逆天的来了。就这么几个壳子，下台的时候还要还回去，留着给下一组继续发。所以拿在手里的唯一作用就是拍个领奖的照片，就没了。据群友说这几个壳子也都是祖传的。我抓紧时间拍了一张照片，留作珍贵影像了。值得一提的是，内大一队的名字是「等我长小了也要打 OI」。念获奖队伍的时候，台上的老师选择了一种最逆天的读法，即，等我长小了也要打，（停顿）（思考）（得出结论），零一。虽然没有牌子，但是有奖品啊！银牌是每人一个耳机，金牌是每人一个键盘。经鉴定，耳机是劣质有线耳机，键盘是劣质薄膜有线键盘。确实比较复古风哈。淘宝搜了一下，都是小几十块钱的产品。我说耳机键盘什么的，送这种劣质产品不如不送。有这点钱你定制几块奖牌比啥都强。这下真是傻人遇到傻福了。我是傻人，主办方是傻福。后面还有个优秀组织奖，这个倒是有一个巨大的奖牌，我可以把它当金牌抱回家里吗（）。答案当然是不能。后面发现居然还有团体奖，就是按校排发奖了。不过我们学校居然没有团体奖吗。之后跟其他队伍聊天的时候才知道，我们伟大的 NMCPC 的校排计算方式是，取每个学校排名前三的队伍，过题数和罚时求 sum。我们学校只有两个队，所以肯定比不过其他学校。气笑了。另外一个很神人的是，大概在比赛开始两个小时的时候，榜单上面的打星队突然也参与排名了，只是名字前面带个星号而已。后来交流了解到，可能是主办方发现 szm 太猛了，所以决定把打星队也改成正式队伍，临时加了一个中学组，甚至也按照一个独立的组别正常颁奖了。szm 作为第一名上去领奖的时候，手里拿着一大把气球在挥舞（）。感觉有点帅的，虽然没来得及拍照。赛时改队伍类别的确实第一次见。让我们为其伟大的创新精神点赞！接下来就结束了。稍后把键盘卖了去定制一块奖牌吧（）。感觉群友说的很对，反正这是本来就该属于自己的东西。赛后我也还是在水群。从 szm 那里了解到，他们进场的时候监考老师说他们的草稿纸上有字。另外比赛的时候一直让大家安静，后面大家就变成小声交流了。每个队伍交六百块钱，还有专门冠名的赞助商，一个 XCPC 比赛办成这样是不是有点太过分了。野鸡比赛打着玩玩得了。6.4我们排在前面的几个队伍决定一起定制一些奖牌和奖杯，留作纪念。效率真的很高，今天就拿到了！实至名归！6.5 - CCPC 贵阳邀请赛因为明天早上要打蓝桥杯国赛，所以要提前来一天。其实原定是下午来贵阳的，但是上周刚通知的航班取消了，只剩一个早上和深夜的航班了。周五上午还有课，早上的不能改。深夜 + 华夏航空 + 非热门航线 + 第二天早上的比赛，感觉这班 buff 有点多，也没敢改。那就只剩中转了。看了一个郑州转机的方案，但是携程上不能直接改中转航班，有点鸡肋。正好这两班都是海航旗下的，原航班也是海航，直接联系客服免费改签了，三个人加起来怒省七百块钱，以及我能多攒一个航段（）。贵大怎么也在这种穷乡僻壤的地方。不过离市区也就（？）十几公里，而且有很多快速路，和西工大的三十公里五十个红绿灯还是没法比的（笑）。坏消息就是，因为位置比较偏，又没有西工大那种偏得特别离谱，贵大附近几乎没什么商业。我们住到了大概三四公里外的一家酒店，其实我很难想象他们是怎么把一家 2023 年的酒店经营得像是 2013 年开业的。晚上点了一碗牛肉粉，味道确实不错。6.6早起打蓝桥杯。我的考点在贵民，也不算远，打车十几分钟到了。早上去考点的路上突然接到一位老师的电话，让我处理一下学校的某些，非常紧急的神秘事务。今天不是周六吗。现在不是早上八点吗。我上哪给你立刻马上找人去。国赛居然有专门的背景板，这个确实不算丑吧，不过就是下面那一行「国内领先的大学生学科竞赛」有点难绷。到考场给我发了一件 T 恤衫，虽然我觉得不如不发。到机位顺手打开了 VS Code，然后突然意识到蓝桥杯只能用 Dev 和 C++ 11，哎野鸡比赛。当然这个也为接下来的故事埋下了伏笔。开始比赛了，然后大家发现题面有密码，并且监考没有收到密码相关的通知。谁家 CSP-J 2023。不知道为什么，感觉今天做题都特别顺畅，基本是碰到题就能有思路，想一会就会做了，手感特别好。也可能是考了一堆板子和经典套路的原因吧。最难绷的一集是，G 题考了一个线段树板子，纯板子，就是简明扼要地直接告诉你要维护序列的方差。甚至只有单点修改，都不用写 lazy tag 什么的。我记得我做过原题，只不过是带区间修改的版本。题目本身感觉，质量不好说，你都放板子了那还说啥了。不过蓝桥杯其实我不清楚强度怎么样，能国二就是赢吧。赛后和群友讨论发现 J 甚至可能是个错题，以及全场难度评级最高的一道题是一个板子。比赛出来看到内大队长给我发消息，让我给他们队代拿三件衣服，意思就是他们没来打，我表示震惊。看了一下他空间，发现昨天晚上航班从九点延误到十一点多，经停延安，到经停机场已经快一点了，后半段直接取消了。航司安排了经停机场附近住宿和第二天补班，不过这样就确实错过蓝桥杯了，三个人都没法打，惨惨。还好没坐那班。不过这种衣服你也要啊。下午和队友去领物资。贵阳也有好多山，当然也包括贵大校内，也没有共享单车，不知道的以为到重庆了。报到的地方离最近的门口有小一公里，走死我了。报到场馆的门口那条路上挂了 CCPC 贵阳邀请赛的旗子，好看。背景板也好看，我觉得这些设计都很棒吧。遇到的志愿者和负责拍照的老师也都很热情，情绪价值拉满了。贵阳虽然也是纸袋，但是这个袋子真的好看，一个充满活力的橙色，正中央印上一个小的 CCPC 和邀请赛的标识，我很少见到这种不会感觉廉价的比赛物资的纸袋。教练服中规中矩。选手服我觉得好看，是一个【】绿色的，上面印有一句话，我的衣服上面写的是 「AC is not the end, but the spirit.」，后面发现居然还有这行字不一样的其他款式。伴手礼是一个颈椎按摩仪和印有 CCPC Logo 的保温杯，盒子上也有和袋子上一样的标识，确实豪华吧，甚至还是定制款。热身赛在明天早上，那今天就没啥事了。6.7上午先去热身赛。贵阳的热身赛在上午九点半到下午十点半，正赛是中午十二点开始的，不用早起了，好评。今天气温只有二十多度，但是我感觉超级热，路上一直在流汗，可能是湿度高的原因吧。看群里发现大家一直在喷设备问题，包括 VS Code 是没有任何插件的原生（？）版，群里负责老师说可以在志愿者的监督下自带 U 盘装插件。怎么自带 U 盘都出来了，不过能用就行。到机房了，这次的队伍信息牌很小，设计也很好看，感觉应该有不少人会带回去，JXNU 你看看人家。笑不出来了。到机位发现是一台搭载酷睿 i5-4590 的高性能旗舰机（？），以及 Win 7 系统。我记得参赛手册上写的是 Win 10/11 来着，不是 Linux 能理解，怎么 Win 7 都来了。赛后了解到，参赛手册上写的也不完全有问题，因为确实也有用到 Win 10 和 Win 11 系统的队伍。以及一台古董显示器。不过至少有 VS Code 可以用，还是比隔壁蓝桥杯好点的吧。虽然打开 VS Code 是这样的。意思是，其实还是只有 Dev 可以用，谁家蓝桥杯。我说怎么参赛手册上的 VS Code 是一个安装包。将就一下吧。去做热身赛的题目，贵阳用的是 Hydro，这个好评。发现有需要打草稿的地方，显然每个队伍都会提供三根笔，这个总不至于出什么问题吧。贵阳提供的笔是一款按动式的中性笔，众所周知地，新笔的笔尖会有一个类似保护套一样的东西，你需要把它抠下来才能正常写字。那贵阳当然也不例外，我就这么照常开始抠那个保护套，然后就出现了下面这张广为流传的图。如果你没看懂，解释一下，就是抠那个保护套的时候，保护套没抠掉，但是保护套跟着笔尖一起揪出来了。虽然赛时很气但是赛后来看这个真的太难绷了。我看甚至有知乎的帖子搬了我的这张图。气笑了，这些是何意味啊。热身赛结束了，接下来就去吃饭。队友想去食堂，不过我实在是，被这些逆天东西搞得真的很心烦。不想去食堂，于是就自己一个人出去校门口吃肯德基了。他们说食堂什么都没有，唯一能用餐券的地方挤了一堆 ACMer 在大排长龙。事后了解到能用餐券的五食堂是贵大最差的食堂了。还好没去。如果是心烦加上中午在这种环境里打饭吃饭，我不知道到比赛的时候要难受成什么样。虽然我没有什么发挥可以影响的（），但是心烦意乱一下午真的很难受。值得一提的是，贵阳要求所有代码文件只能建在 C 盘根目录，放在其他地方就算作弊。热身赛结束以后，有群友发现根本没有清空机器一说，只靠志愿者手动删掉 C 盘根目录下的代码，有点难绷。甚至昨天蓝桥杯的代码还留在机器上。下午就开始比赛。签到题是 G，排个序暴力扫一遍然后过了。接下来开 I。最开始队友给的思路还是贪一遍，我的直觉是直接二分，但是因为没有想 check 函数怎么写，下意识觉得可能不好写，于是就先按着贪心的思路走了。讨论了一会就写出来了，但是一直在 WA，感觉这个做法挺假的，于是就回去自己写二分了，很快写完了然后一发过了。接下来就是，C 和 F 开掉的队伍数量都差不多，通过率也差不多。过掉 F 的比 C 多几个队，于是就打算先去看 F。不过 F 的题面写的特别，不知所云，我读了好几遍也没读懂题目到底想表达什么，包括样例解释也写得很，不太看得懂。感觉就是，给出了各种不明确不严格的限制，剩下的条件全靠选手自己脑补。不过也过了不少队，我还是不太敢怀疑的。尽管赛后在群里确实有不少群友在喷这题题意的。接下来就是，按照我们认为的题意写了一下，但是一直没过，后面就打算换 C 了。其实赛后来看 C，其实是一个比较经典的小 Trick，但是赛时我确实不知道。于是就按照直觉，把整个坐标系旋转 45 度，然后写二维差分来做了。后面推了很久的式子，以及代码其实也不太好写，但是至少在大概封榜后二十分钟的时候写出来了，尽管后面一直没调出来，也不懂是什么地方写挂了。然后比赛就结束了。只有两题，所以当然也就没有牌子。我觉得很逆天啊，这么热的天气，机房甚至没有空调，只有一台风扇。潮热的天气加上机房电脑的散热，到后面风扇吹出来的直接就是热风了。甚至我们队旁边就是那台风扇，但感觉到比赛后期，机房的体感温度还是有三十度左右。另外很热加上参赛的体验很差，整个下午我都有点烦，这样也导致我有点脾气不好。甚至刚开始比赛那会凶了队友几句，对不起（鞠躬）。选手说热，主办方说不热。我能理解主办方确实不会为了一场比赛而特意加装空调，但是甚至风扇都不多准备几台，我真的很难理解。选手已经为你的比赛交过报名费了，那成本问题就不应该在选手应当理解的考虑范围内吧。你认为成本不够可以提高报名费，但你甚至比其他邀请赛便宜一百块钱，事实上传达出来的信息就是，你有信心少收一百块钱也能办好这场比赛吧。这场并没打出什么成绩来，并且赛时体验也很差，这个时候已经快要烦到爆炸了。感觉不想也没啥必要参加闭幕式，就直接和队友打车去高铁站了。最早报名且最晚比赛的赛站，办出最差的体验，确实有点说不过去吧。当然这里的体验最差不包括 NMCPC。6.11蓝桥杯国赛出成绩好快，居然是国一！我知道 CB 组强度低，但是也确实没想到这么低。后来翻了一下获奖公示，发现整个内蒙 CB 组只有我一个国一，我都能拿国一的比赛能是什么正经比赛（笑）。6.13 - CQCPC这周去和朋友打星重庆市赛。其实我周五下午没课，如果是平时的话就周五走了，但今天上午要考四级，所以只能上午考完下午再去重庆了。至少不是六级，不用下午考完晚上再走，越来越觉得去年没考是对的了。我和其中一位队友到的时间差不多，所以我俩就一起打车去酒店了。CQCPC 的承办方也和 CCPC 区域赛一样是 CQU，其实我也挺喜欢这所学校的，环境什么的也超级棒，但就是办比赛的虎溪校区离机场太远了，打车过去都要一个小时。这次队友预算高一点，所以可以住到更舒适一点的酒店。晚上一起去吃了烤匠，确实好吃啊，不过我俩都不太能吃辣，没有点很多辣的，如果能选更辣的口味应该会更好吃吧。重庆没有热身赛，签到和比赛都在明天，今天就没什么事了。6.14早上要先去签到领物资。我起得有点晚，另一位自己走的队友就先去签到了，这位是大手子（）。其实和我一起走的那位队友也是手子，只不过没有他那么大手子，算是小手子吧（）。等我俩到了和他会合的时候，他已经把衣服穿上了。比赛的衣服就是简单的一个粉色，胸口印了一个 ICPC 的标识，我觉得还挺好看的，不过忘记拍照了。袋子也挺好看的，不过就是上面没有 CQU 和 XCPC 相关的标识。但是我是没有换比赛的衣服的习惯的，所以拍照就是我穿了日常的衣服，他俩穿着比赛的衣服。另一个原因是，先到的那位队友把我的更大一号的衣服穿走了，所以我没有合适尺寸的衣服可以穿了（）。把我的衣服还给我。接下来就是直接上楼比赛了。机房在四楼，重庆真的好热，加上楼梯在室外，爬到四楼就已经快要累死了。到了发现是一个很大的机房，虽然不是体育馆，但是 XCPC 比赛的氛围是有了。机器就是常规的 Win 10 和 PTA。队伍信息牌是一张粉色的纸，上面有一个彩色打印的方框，虽然只有一张纸但是并没有显得很廉价。接下来就是放出来我们的雷霆队名了。应该没有什么人看到这个队名能绷住吧。然后就开始比赛了。大手子队友（？）的手速真的超级快，基本上是还没反应过来的时间，大概几秒钟，他已经把板子敲好了。敲完板子他就开始看题面，读题速度也很快，一眼看到可以先开 B，然后就是飞速敲代码，交题然后一发过了。过这题的时候比赛刚开始一分钟，吓哭了。一个 fun fact 是，比赛开始一分钟的时候，整个机房都听到了我们的欢呼声和掌声，以及一声「一血」的大喊（）。我环顾了一下周围，发现几乎所有队伍都转过头来看我们，以及一副不可思议的神情。我们当时以为抢到了全场第一个过题，然后发现榜单里已经有一队过掉这题了。赛后了解到，我们这发提交大概在一分五十多秒，虽然榜单上显示的也是一分钟，但是我们其实是全场第三个过题。我看到 A 的第一眼其实是一个什么神秘数据结构，但是仔细读了一下题，看起来其实就是一个比较水的小模拟。在我读其他题和思考 A 的时候，大手子队友已经默默把 D 和 H 开掉了，都是一发过。开完这三题的时候是 15 分钟。这个时候基本上我们已经确定好各自的分工了，我在想 A，小手子队友（？）在想 L，是一道交互。赛后群友说 L 和秦皇岛的那道交互很像，但是这题的交互是 adaptive 的，所以没办法用随机化搞过去。接下来就该做 M 了，大手子队友一边和我讨论一边写代码，然后在 28 分钟的时候一发过掉了这题。其实大概十分钟的时候我已经口胡出来 A 的做法了，但是到我们过掉 M 的时候也一直没有人开这题，我不确定是不是真的这么简单。加上他俩确实比我强得多，其实我也不太敢占着机子去写这么一个我不确定的题。但是怎么想怎么对啊。他写 M 的时候我在草稿纸上写了一些核心代码，感觉逻辑完全对，没有什么实现不了或者没考虑到的地方，一个 set 和一个 priority_queue 就直接搞定了。他过掉 M 以后我就说我会 A 了。然后他俩都表示，我会了就让我上去写。不过其实这个时候我是不太敢上的，一方面担心万一自己的做法假了怎么办，另一方面担心如果写挂了调代码又很浪费时间。在担心是不是很可能会因为自己太菜而，比如在这种水题上占用了大量时间或者吃了很多罚时，然后让队友对我感到反感甚至讨厌吧。不过他俩还挺认可我的，就是很笃定地让我上机，那我就上去写吧。其实写起来还挺顺利的，基本没怎么卡住，按照我在草稿纸上列的逻辑和一些代码就可以很流畅地写出来，大概十几二十分钟就写完了。不过测样例发现挂了两行，这个时候小手子队友说他会 L 了。我就把代码打印下来，先让他们去写 L 了。这个期间大手子队友在想 F，期间也有和我讨论什么的。不过这俩其实细节都多，中间基本上就是他俩轮换着写，卡住了就打印代码，然后换人写。不过打印的代码其实送得挺慢的，基本上要好几分钟甚至十分钟，代码没送到的时候就在草稿纸上自己算。打印了几次以后我们得出了一个结论，就是每次我们刚解决完一个问题，打印的问题代码就送过来了（）。大概 80 分钟的时候，L 开出来了，也是一发过。小手子队友说这题和贵州省选 2019 的一道题特别像，他会的做法也正好就是题目给的 29 次交互，刚刚好。然后就是我上机继续去调 A，把刚才发现的一个小问题调出来了，但是这个时候还是有一行样例不对。所以就换人上去开 K 了，大概又过了二十分钟就过掉了，也是一发过。其实我们最开始以为 K 是什么神秘计算几何，就先去做其他题了，后来发现维护一个单调栈就过了。然后我也想明白 A 了。其实最佳的思路是核心代码重构一遍，但是感觉太麻烦了，我决定继续往里边堆史（）。很快就调出来了，也是一发过！所以就是，我们在 110 分钟内零罚时过掉了 7 题，感觉，很传奇啊。两位手子队友太强了。但是好像我们的气球始终都少一个（），过掉两题的时候送来了一个气球，过掉五题的时候送来了第四个气球，刚才过掉第七题以后送来了第六个气球。这种事情绝对很奇怪啊。午餐是一个三明治，没吃饱。不过好吃。接下来就开始坐牢了（）。很早的时候小手子队友就说他觉得 J 可做，但是场上一直没有队伍做，所以就没做。现在七题以后好像就没有什么可做题了，我们就开始思考 J 和另一道觉得可能可做的 F。过了大概一个小时，场上已经有一车人过掉 F 了，我们还在卡着，确实不知道这题是为什么能过掉这么多人的。过程中实在调不出来 J，就决定对拍，确实发现了相当多的问题。接下来就是一直改 J 一直想 F。大概三个半小时的时候，小手子队友可能会做 F 了，写完大概四小时出头，样例过了，提交，然后吃到了本场的第一发罚时（）。调了一下，大概四个半小时的时候过掉 F 了。接下来就是一直在调 J。到后面发现小数据对拍全过了，但是交上去还是 WA 了，然后就是一直对拍一直调一直 WA。到后面大手子队友已经调红温了，差不多是下面这样：接下来就是最难绷的。后来 J 已经吃到一发罚时了，我们感觉不太对劲，然后把用来对拍的暴力交上去，发现暴力 WA 了（）。气笑了，然后重新读了一遍，发现题读假了。你是说，我们花三个小时调了一道假题出来吗（）。他在写 F 的时候我和大手子队友也在讨论 J，因为没有机子，所以他直接手写了好几页代码（），是不是也可以叫人肉编译器。这个时候真正的 J 也会做了，于是就上去写代码。不过想到的这个解法其实常数巨大，还是不太确定能不能过的。写完大概距离比赛结束已经只剩十几分钟了，交上去发现确实被卡常了，常数也实在优化不掉了。当然赛后发现我们这个做法的复杂度是不对的。果断换题。小手子队友现在会做 C 了，于是我们在最后十分钟里堆了 12 个二分（）。尽管最后还是没调出来。然后比赛就结束了。所以这场比赛就是，八道题加一发罚时，其实我觉得这个成绩已经很牛了。其实我认为本场比赛最重要的看点就是滚榜读到我们队的环节（）。封榜后我们过了一题，所以可以读到我们队两次。现在是下午三点，室外已经超级热了，从赛场到小剧场大概也就三四百米路程，但是感觉在外面待一秒钟都是煎熬。还好小剧场里空调很足，滚榜也挺棒的。滚榜的时候发现某个神秘队伍在 L 题交了 767 发，吓哭了。接下来就是滚到我们队了，主持人面不改色地念完了。不过读到的时候场内居然没什么声音，这点比较出乎意料吧。不过确实看到了若干位在录视频的（）。因为我们罚时很低，所以最后在总榜里面排到了 rk20，正式队榜单的话就是在 rk6 后面，显然是金牌区。不过重庆市赛不给打星队发牌子，赛后去要也不给（）。所以我们和其他队伍借了一个金牌拿来拍了个照。然后就结束了。我要坐晚上的飞机，所以就直接去机场了。早上没吃饭，午餐也就一个小三明治，饿死我了，晚上去机场吃重庆小面，震撼美味。以及一个小插曲。这学期的比赛就结束了。算圆满吗，我也不知道。那，九月见！
传送门：P16796 [蓝桥杯 2026 国 B] 灯带修补 更佳的阅读体验：洛谷 P16796 题解简要题意：给你一个环，你需要求出环上最长的连续子段，使得该字段中相邻元素之差的绝对值 $> k$ 的位置数量 $\le m$。$n \le 2 \times 10^5$。看到环，我们应该就有一个直觉是需要把整个序列在数组末尾再复制一次，这样环上问题就被转化成线性的序列问题了。我们发现，最后的答案其实只和相邻元素之差的绝对值有关，而与 $a_i$ 本身的值无关。此时，如果我们将 $|a_i - a_{i + 1}| > k$ 视作 $1$，否则为 $0$，那我们就可以得到一个新的序列，即 $d_i = \left [|a_i - a_{i + 1}| > k \right ]$，其中 $[P]$ 为条件表达式，命题 $P$ 为真时值为 $1$，否则为 $0$。这时，我们对序列 $d$ 再做一次前缀和，我们就可以很简单地求出来每个区间有多少个位置符合条件了。那反过来想，其实只需要遍历一次序列 $d$，查找最后一个不超过 $d_i + m$ 的位置即可。时间复杂度 $O(n \log n)$。#include <iostream> #include <algorithm> #include <cmath> using namespace std; using ll = long long; const int N = 4e5 + 10; int n, m, ans; ll k, a[N], d[N]; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cin >> n >> m >> k; for (int i = 1; i <= n; ++i) cin >> a[i]; copy(a + 1, a + n + 1, a + n + 1); for (int i = 1; i < (n << 1); ++i) d[i] = d[i - 1] + (abs(a[i] - a[i + 1]) > k); for (int i = 1; i <= n; ++i) ans = max(ans, min(n, int(upper_bound(d + 1, d + (n << 1) + 1, d[i] + m) - d - i))); cout << ans << '\n'; return 0; }
传送门：P16799 [蓝桥杯 2026 国 B] 实验数据 更佳的阅读体验：洛谷 P16799 题解没错笔者去参赛了，虽然赛时做到这种题确实有点难绷，猜你想找 P1471 方差、P5142 区间方差。这篇题解主要写给初学线段树的同学，如果你有一定基础，想必你已经做过上面两题了。简要题意：给你一个序列，你需要支持单点修改和查询区间和、区间方差。$n \le 10^5$。如果你做过洛谷的线段树板子，那么此时你已经会了最基础的区间和查询。但题目还要求你求出区间方差，此时你已经推了一百页公式，发现无论如何也推不出来只用区间和求解的方案。怎么办呢？来推一下式子吧。$$ \begin{align} \text{Var} = & \sum_{i = l}^r \left (a_i - \overline{a} \right )^2 \\ = & \sum_{i = l}^r a_i^2 + \sum_{i = l}^r \overline{a}^2 - 2 \cdot \sum_{i = l}^r \left ( a_i \cdot \overline{a} \right ) \\ = & \sum_{i = l}^r a_i^2 + (r - l + 1) \cdot \overline{a}^2 - 2 \cdot (r - l + 1) \cdot \overline{a}^2 \\ = & \sum_{i = l}^r a_i^2 - (r - l + 1) \cdot \overline{a}^2 \\ = & \sum_{i = l}^r a_i^2 - (r - l + 1) \cdot \left ( \dfrac{\sum \limits_{i = l}^r a_i}{r - l + 1} \right )^2 \\ = & \sum_{i = 1}^r a_i^2 - \dfrac{\left ( \sum \limits_{i = l}^r a_i \right )^2}{r - l + 1} \end{align} $$好像推不下去了，但至少已经出现了一个我们熟悉的区间求和。但还有一个求平方和，是否有办法处理这个呢？答案是肯定的。我们考虑线段树本身的结构，似乎只要是可以支持 push up 和 push down 操作的数据，就都可以拿线段树来维护，那平方和当然也满足。因此，我们只需要让这一棵线段树多维护一个区间平方和即可。因为本题只需要支持单点修改，所以甚至不需要 lazy tag 和 push down。当然，你还需要注意模意义下的除法需要通过乘它的乘法逆元来实现。时间复杂度 $O(n \log n)$。#include <iostream> #define ls(p) t[p].lson #define rs(p) t[p].rson #define mid (l + r >> 1) using namespace std; using ll = long long; const int N = 3e5 + 10; const ll MOD = 998244353; int n, m, op, l, r, k; ll a[N], x; struct seg_tree { int rt[N << 1], tot; struct node { int lson, rson; ll sum, sqsum; } t[N << 1]; void pushup(int p) { t[p].sum = (t[ls(p)].sum + t[rs(p)].sum) % MOD; t[p].sqsum = (t[ls(p)].sqsum + t[rs(p)].sqsum) % MOD; } void build(int &p, int l, int r) { p = ++tot; if (l == r) return t[p].sum = a[l] % MOD, t[p].sqsum = a[l] * a[l] % MOD, void(); build(ls(p), l, mid); build(rs(p), mid + 1, r); pushup(p); } void update(int p, int l, int r, int k, ll x) { if (l > k || r < k) return; if (l == r) return t[p].sum = x % MOD, t[p].sqsum = x * x % MOD, void(); update(ls(p), l, mid, k, x); update(rs(p), mid + 1, r, k, x); pushup(p); } ll query_sum(int p, int l, int r, int L, int R) { if (l > R || r < L) return 0; if (l >= L && r <= R) return t[p].sum; return (query_sum(ls(p), l, mid, L, R) + query_sum(rs(p), mid + 1, r, L, R)) % MOD; } ll query_sqsum(int p, int l, int r, int L, int R) { if (l > R || r < L) return 0; if (l >= L && r <= R) return t[p].sqsum; return (query_sqsum(ls(p), l, mid, L, R) + query_sqsum(rs(p), mid + 1, r, L, R)) % MOD; } } tree; ll qpow(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = res * a % MOD; a = a * a % MOD, b >>= 1; } return res; } ll aver(int l, int r) { return tree.query_sum(tree.rt[1], 1, n, l, r) * qpow(r - l + 1, MOD - 2) % MOD; } ll var(int l, int r) { ll sum = tree.query_sum(tree.rt[1], 1, n, l, r); return ((tree.query_sqsum(tree.rt[1], 1, n, l, r) - sum * sum % MOD * qpow(r - l + 1, MOD - 2) % MOD) % MOD + MOD) % MOD; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cin >> n >> m; for (int i = 1; i <= n; ++i) cin >> a[i]; tree.build(tree.rt[1], 1, n); while (m--) { cin >> op; if (op == 1) cin >> l >> r, cout << aver(l, r) << ' ' << var(l, r) << '\n'; else cin >> k >> x, tree.update(tree.rt[1], 1, n, k, x); } return 0; }
传送门：洛谷 CF2225C Red-Black Pairs | Codeforces C. Red-Black Pairs 更佳的阅读体验：CF2225C 题解简要题意：给你一个 $2 \times n$ 的网格，每个格子涂成红色或黑色，要求重新涂色最少数量的格子，使得所有格子能分成 $n$ 对，每对格子颜色相同且相邻，求这个最小重新涂色数。$\sum n \le 2 \times 10^5$。只有两行，所以所有可能的匹配方式就只有两种，也就是横着或者竖着的两格。匹配时如果这两格的颜色不相同，就产生 $1$ 的代价，否则匹配的代价为 $0$。此时问题变成了，我们需要找到一种匹配方式，使得所有格子都被匹配且代价最小。考虑 DP。我们定义 $f_i$ 表示匹配完前 $i$ 列的最小总代价。转移时就只需要考虑，如果竖着匹配一次，那就匹配当前的这一列。或者横着匹配两次，匹配当前一列和前面的一列。我们可以提前预处理出竖着匹配和横着匹配的代价 $cost_1$ 和 $cost_2$：$$ \begin{cases} \text{cost}_{1, i} = [a_{1, i} \ne a_{2, i}] \\ \text{cost}_{2, i} = [a_{1, i} \ne a_{1, i + 1}] + [a_{2, i} \ne a_{2, i + 1}] \end{cases} $$其中 $[P]$ 表示命题 $P$ 为真时值为 $1$，否则为 $0$。于是我们就得到了转移方程。$$ f_i = \min \{ f_{i - 1} + \text{cost}_{1, i}, f_{i - 2} + \text{cost}_{2, i - 1} \} $$时间复杂度 $O(n)$。#include <iostream> #include <algorithm> using namespace std; const int N = 2e5 + 10, M = 5; int t, n, f[N], cost[M][N]; char c[M][N]; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); for (cin >> t; t; --t) { fill(f + 1, f + n + 1, 0); fill(cost[1] + 1, cost[1] + n + 1, 0); fill(cost[2] + 1, cost[2] + n + 1, 0); cin >> n >> c[1] + 1 >> c[2] + 1; for (int i = 1; i <= n; ++i) { cost[1][i] = c[1][i] != c[2][i]; cost[2][i] = (c[1][i] != c[1][i + 1]) + (c[2][i] != c[2][i + 1]); } f[1] = cost[1][1]; for (int i = 2; i <= n; ++i) f[i] = min(f[i - 1] + cost[1][i], f[i - 2] + cost[2][i - 1]); cout << f[n] << '\n'; } return 0; }
传送门：洛谷 CF2218E The 67th XOR Problem | Codeforces E. The 67th XOR Problem 更佳的阅读体验：CF2218E 题解简要题意：给你一个数组，每次操作可以选择其中一个元素，将数组内所有元素都与它进行按位异或运算，然后将该元素删除，求 $n−1$ 次操作后剩下的最后一个元素可能的最大值。$\sum n \le 3105$。诈骗题。来推个柿子吧！假如现在我们有一个 $n = 5$ 的数组 $\{ a_1, a_2, a_3, a_4, a_5 \}$，我们选中第一项进行一次操作，数组就变成了：$$ \{ a_2 \oplus a_1, a_3 \oplus a_1, a_4 \oplus a_1, a_5 \oplus a_1 \} $$那如果再对现在的第一次进行一次操作呢？现在数组就变成了：$$ \{ (a_3 \oplus a_1) \oplus (a_2 \oplus a_1), (a_4 \oplus a_1) \oplus (a_2 \oplus a_1), (a_5 \oplus a_1) \oplus (a_2 \oplus a_1) \} $$我们知道，异或运算有一个很重要的性质是 $x \oplus x = 0$，同时也满足结合律。因此，现在的每一项都异或了两次 $a_1$，其实 $a_1$ 就被消掉了，现在的数组就变成：$$ \{ a_3 \oplus a_2, a_4 \oplus a_2, a_5 \oplus a_2 \} $$我们发现第一次操作中选中的 $a_1$ 已经不存在了。如果我们一直选择序列中的第一项进行操作，最后剩下的一个元素就是 $a_5 \oplus a_4$，也就是，最后一个未被选中的数与最后一次被选中的数的异或值。因此，我们只需要确定这两个数，就可以得到最后剩下的一个数的值。因为 $n$ 非常小，我们可以直接枚举任意两个元素的异或值，求最大值即可。单组数据时间复杂度 $O(n^2)$。#include <iostream> using namespace std; const int N = 3110; int t, n, a[N], ans; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); for (cin >> t; t; --t) { ans = 0; cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 1; i <= n; ++i) for (int j = i + 1; j <= n; ++j) ans = max(ans, a[i] ^ a[j]); cout << ans << '\n'; } return 0; }
我被囚禁在了一个固步自封的囚笼中。他们说，我是安全的。我沉浸在那里，沉沦在那里。我在那里挣扎着死去，在一个悄无声息的角落，偷偷地，默默地。尽管，我是安全的。$\texttt{Written on 2026.4.7.}$
传送门：洛谷 CF2209C Find the Zero | Codeforces C. Find the Zero更佳的阅读体验：CF2209C 题解简要题意：IO 交互题。有一个长度 $2n$ 的隐藏数组，其中包含 $1 \sim n$ 各一个，以及 $n$ 个 $0$。每次询问可以查询两个位置的元素是否相等，你需要在不超过 $n + 1$ 次询问中找出一个值为 $0$ 的位置。因为 $1 \sim n$ 的每个数都是出现且仅出现一次，所以如果某次询问得到了 $a_i = a_j$ 的结果，说明这两个都是 $0$，选一个输出即可。如果 $a_i \ne a_j$，说明它们最多只有一个数是 $0$。如果我们直接排除掉这两个数，继续去考虑接下来的数，我们发现还剩下至少 $n - 1$ 个 $0$。那么我们每次都对两个未询问过的位置进行询问，经过 $n - 1$ 次询问后，如果仍然没有得到 $a_i = a_j$ 的反馈，我们就剩下了最后两个数。如果这两个数也不相等呢？那就只剩下一次询问了，无法确定 $0$ 的位置。但如果将目光向前看呢？我们随便找一对之前被我们询问过的位置，加上最后剩下的两个数，我们发现这四个数里至少包含两个 $0$。现在我们剩下两次询问，此时问题就简单许多了。假设我们还没询问过的两个数是 $x, y$，从之前的询问中拿出来的两个数是 $a, b$。因为之前已经询问过 $a$ 和 $b$，所以此时就一定有 $a \ne b$。那如果我们抓住 $x$ 一个数，和 $a, b$ 分别比较，那就只有两种情况了。如果 $x = a$ 或 $x = b$，那么显然 $x$ 一定是 $0$，直接输出即可。否则，未参与比较的 $y$ 就一定是 $0$。#include <iostream> using namespace std; int t, n, stat; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); for (cin >> t; t; --t) { cin >> n; for (int i = 1; i < n; ++i) { cout << "? " << (i << 1) - 1 << ' ' << (i << 1) << '\n'; cout.flush(); cin >> stat; if (stat) { cout << "! " << (i << 1) << '\n'; cout.flush(); break; } } if (stat) continue; for (int i = 2; i <= 3; ++i) { cout << "? " << (n << 1) << ' ' << (n << 1) - i << '\n'; cout.flush(); cin >> stat; if (stat) { cout << "! " << (n << 1) << '\n'; cout.flush(); break; } } if (!stat) { cout << "! " << (n << 1) - 1 << '\n'; cout.flush(); } } return 0; }
传送门：洛谷 CF2194C Secret message | Codeforces C. Secret message更佳的阅读体验：CF2194C 题解简要题意：给你 $k$ 个长度为 $n$ 的字符串，你需要构造一个新字符串，使得每个字符都与至少一个给定字符串的相同位置的字符相同，并最小化该字符串的最小循环节长度。首先来考虑如何处理循环节的长度。既然构造出来的字符串是由几个字符串循环而来的，那也就是说，最小循环节一定是 $n$ 的约数。因此，我们可以先找出 $n$ 的所有约数，从小到大挨个枚举是否合法。如何判断一个最小循环节长度 $d$ 是否合法呢？我们需要构造一个长度为 $d$ 的模式串 $t$，使得整个答案字符串由 $t$ 重复 $\dfrac{n}{d}$ 次组成。也就是说，$t$ 中的每一个位置，所选的字符都必须同时存在于给定字符串中对应的位置上。也就是说，对于一个位置 $1 \le i \le d$，所选字符必须同时存在于给定字符串的 $i, i + d, i + 2d, \cdots, i + \left ( \dfrac{n}{d} - 1 \right ) d$ 的位置上。因为给定字符串只有小写字母的 $26$ 个字符，为了方便处理，我们对字符串进行状态压缩，$mask_i$ 存储位置 $i$ 可以使用的字符集。此时，$t_i$ 可用的字符集就一定是 $mask_i, mask_{i + d}, mask_{i + 2d}, \cdots, mask_{i + \left ( \frac{n}{d} - 1 \right ) d}$ 的交集。如果这个交集为空，意味着当前的这个 $d$ 不合法，我们直接尝试枚举下一个 $d$。如果交集全都不为空，那么就可以直接构造答案。我们使用 __builtin_ctz 函数来获取一个数从最低位开始 $0$ 的个数，得到可用的字符，构造字符串即可。单组数据时间复杂度 $O \left (nk + n \cdot d(n) \right )$，其中 $d(n)$ 表示 $n$ 的约数个数。#include <iostream> using namespace std; const int N = 5e4 + 10; int t, n, k, mask[N]; string s[N], ans; vector<int> v; bool flag; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); for (cin >> t; t; --t) { v.clear(); fill(mask + 1, mask + n + 1, 0); cin >> n >> k; for (int i = 1; i <= k; ++i) { cin >> s[i]; for (int j = 1; j <= n; ++j) mask[j] |= (1 << s[i][j - 1] - 'a'); } for (int i = 1; i <= n; ++i) if (!(n % i)) v.push_back(i); for (auto d : v) { flag = false; ans.clear(); for (int i = 1; i <= d; ++i) { int tmp = mask[i]; for (int j = i + d; j <= n; j += d) tmp &= mask[j]; ans.push_back(__builtin_ctz(tmp) + 'a'); if (!tmp) { flag = true; break; } } if (!flag) { for (int i = d; i <= n; i += d) cout << ans; cout << '\n'; break; } } } return 0; }