第20届北京邮电大学程序设计竞赛 游记

时间规则：网络（预选）赛（2026/10/11）记作 Day 0，此前每向前一天将天数减去整数 $1$。正式赛日（2026/10/18）记作 Day 1，此后每向后一天将天数加上整数 $1$。中间的每一天，星期 $x$ 称作 Day $\frac{x}{7}$，保留两位小数。

Day -3

招新群里冷不丁发一个：@全体成员 【腾讯文档】第20届北京邮电大学程序设计竞赛报名（截止2026年10月9日 18:00）https://docs.qq.com/form/page/XXX
都说北京等通知大学，没想到通知这么突然吧，只给你这几个小时报名，哈哈。
本来还在和队友商量周末训练的，然后突然就：

天天早晨: 10-08 23:09:10
你们周六晚上有空不
天天早晨: 10-08 23:09:15
要不来打个vp
霍希: 10-08 23:10:04
有空我要去观摩[我想开了][我想开了]
justice: 10-08 23:10:36
我五点多有团委面试
justice: 10-08 23:10:42
晚上应该可以
天天早晨: 10-08 23:10:44
我是两点多
天天早晨: 10-08 23:10:46
晚上应该可以
justice: 10-08 23:10:59
行
天天早晨: 10-08 23:11:01
下午不是还有国际学院那个迎新活动么
justice: 10-08 23:11:08
那个我没报
justice: 10-08 23:11:26
不过我现在的功力应该只能翻字典了[泪奔]
天天早晨: 10-08 23:11:31
我看看我区域赛那个队伍有没有空
天天早晨: 10-08 23:11:40
如果他们有空 就我们打 然后你们在旁边跟着做
justice: 10-08 23:11:46
ok
霍希: 10-08 23:11:48
@justice 不要和我抢啊[流泪][流泪][流泪]
霍希: 10-08 23:11:53
OKOK
天天早晨: 10-08 23:11:56
如果他们不来 那就我们选个简单的打
天天早晨: 10-08 23:12:24
@霍希 没事 还有一本模板
justice: 10-08 23:12:27
我争取在正式考试前再恢复一点[捂脸]
天天早晨: 10-08 23:13:51
还是挺多书翻的（
天天早晨: 10-08 23:15:49
我草
天天早晨: 10-08 23:15:51
计划有变
天天早晨: 10-08 23:17:10
那我先给你们报名吧
天天早晨: 10-08 23:19:17
第20届北京邮电大学程序设计竞赛报名（截止2026年10月9日 18:00）
北京邮电大学程序设计竞赛（网络赛）预计在2026年10月10或11日举行；
北京邮电大学程序设计竞赛（正式赛）预计在2026年10月17或18日举行，09:00-17:00（具体日程后继在QQ群中通知）。

然后就给他们填了报名表，并且吐槽了几句，“报了 管他这的那的 再说吧，校队也是神秘，只给十几个小时报名不说，还安排这么神秘的时间，牛魔的，网络赛第一天撞国际学院的那个活动，第二天撞体测，校赛第二天撞疫苗接种。”

Day -2

接到杨教练通知：“计划网络赛是周日晚上19点-21点，我们明天借好教室后再正式通知。”
在招新群里讨论了一下校队关于 CCSP 的报名政策，发现我把 CCSP 记成团队赛了，原来是 $12$ 小时的单人比赛吗，太抽象了。
在各个群里讨论女装是否能借用图灵老祖的力量以提升成绩，平时就不训练，一比赛就搞这些歪门邪道，哈哈。众群友：“你就是想穿。”队友：“看看女装。”我：“打金牌了就女装上去领奖，哈哈，反正也打不到。”
我都图灵派了为什么还是天天掉头发啊，呜呜，呜呜呜，我的头发。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

“图灵派”和“冯诺依曼派”是2026年起在中文程序员社区（如LINUX DO、Bilibili）中流行起来的一组**二分网络热梗**，它把计算机科学的两位奠基人——艾伦·图灵和约翰·冯·诺依曼——借用来划分程序员的不同“流派”与刻板形象。

### 👨‍💻 核心梗概：“老祖的祝福”

这组梗有一个核心的叙事模板：**程序员在祈祷代码没有Bug时，其实是在和“程序员的老祖”做交易**。回应你的老祖不同，你获得的“祝福”（或“诅咒”）也不同：

*   **冯诺依曼派**：你会逐渐**变成秃头**。这调侃了冯·诺依曼本人发际线较高的历史形象，也关联了程序员因高强度脑力劳动而“秃头”的经典刻板印象。
*   **图灵派**：你会逐渐**变成“男娘”**（即穿着女性化、风格可爱的男性）。这源于图灵本人的同性恋身份，在网络亚文化中被戏谑地转译和演绎为“女装”或“男娘”风格。

### 🎭 两大“派系”的详细画像

围绕这个核心，网友们从多个维度对两个派系进行了“角色设定”：

*   **外貌与穿搭**：
    *   **图灵派**：关联**长发、格子裙**、二次元风格的可爱外观。梗图中常被描绘为萌系动漫角色，日常“愁怎么脱毛”。
    *   **冯诺依曼派**：关联**秃顶、格子衫**、传统程序员形象。梗图中常被描绘为表情严肃的男性，日常“愁怎么生发”。

*   **网络头像**：
    *   一项有趣的“研究”指出，**图灵派**偏爱**二次元、动漫角色或“男娘”风格**的头像；而**冯诺依曼派**则偏好**老教授照片、系统默认头像或证件照**，形成泾渭分明的两个“部落”。在中文开发者中，二次元头像的实际占比约为**40%**。

*   **技术风格**：
    *   一种流传的说法是，**冯诺依曼派**的思维更偏向**指令、内存地址和物理世界**，关注程序如何在实际硬件上运行。
    *   而**图灵派**的思维则更偏向**图灵机、状态转移和逻辑世界**，认为代码的本质是逻辑推演，如同在纸带上计算。

### 💬 社区中的趣味延伸

在LINUX DO等论坛上，这组梗引发了大量二次创作和自我调侃：

*   **身份困惑**：有网友自嘲是“**啥也不是派**”（图灵派的天赋和冯诺依曼派的努力都没有），或者戏称自己是“**香芋派**”、“**派大星派**”。
*   **穿搭调侃**：“**冯诺依曼派穿格子衫，图灵派穿格子裙**”，并衍生出“冯诺依曼派每天都在愁怎么生发，图灵派每天都在愁怎么脱毛”的笑谈。
*   **假发梗**：Bilibili上有视频调侃“**带假发的时候是图灵派，摘假发的时候是冯诺依曼派**”，形象地连接了“秃头”与“长发”两个特征。
*   **现实感概**：也有评论将“二次元头像”、“女装程序员”等现象视为一种**刻板印象的形成**，认为它反映了社群中某种真实存在的亚文化趋势。

总的来说，“图灵派”与“冯诺依曼派”这个梗，本质上是程序员社群利用历史人物进行的一场**自我解构与身份游戏**，它融合了职业焦虑（秃头）、亚文化表达（男娘/二次元）和计算机科学史，成为了一种独特的社群文化符号。

Day -1

防止撞校赛时间，早上去把疫苗打掉了，虽然学校规定国际学院在下周日下午打，但是疫苗是按身份证打的，这么多学生他哪有空查每个学生是哪个学院的，所以就混进去打掉了。
下午趁室友不在试了下女装（万一真打金牌了呢），把裙子的定位线拆了。
提醒了队友带插线板。讨论了一下复杂的比赛现场，插座连插座，构成的数据结构是树还是图。最后发现由于必须从有限个教室电源口出发，每个插线板必须有唯一一个给他供电的父节点，若成环则必定不能互相供电，所以必须构成一颗森林。
比较晚的时候发布了网络赛的正式通知，大概看了一下，需要准备一个没有 AI 插件的本地 IDE，和下载 OMS 系统。尝试配置 Sublime，但是后面还是换成了删除了所有插件，退出 GitHub 账号的 VS Code，用了这么久，习惯了，突然换可能会出问题。
队友看到参赛名单里还有学长的队伍，对能否拿牌产生了担忧。我指出标准的 ICPC 比赛是 $10\%+20\%+30\%=60\%$ 的获奖率，应该问题不大。

Day 0

比赛前很紧张，明明这个网络赛并不重要，或许是太久没比赛了吧，有些失眠。
早上起来去把体测的室内项目完成了，立定跳远拼尽全力无法战胜，跳了十多次得了 40 分。截止这一部分的写稿日（10.12夜）腿还是痛的。引体向上跳都跳不上去，哈哈，不考了。问问学长这个体测成绩还能不能凹，学长说可以试试坐位体前屈。然后我发现坐位体前屈的机器测试要求比较松，动作可以不用那么标准，然后我略微弯了点腿，一不小心拍到满分了，被监考老师制止了。然后我略微规范了一些动作，但是还是弯了一点点腿，不太明显，依旧满分，老师也就没说什么了。在学校新生群里问体测动作不规范会不会扣分，学长说如果要求动作规范，百分之八十的学生都及格不了了，而且机器也没那么高精度。
体测完吃完饭想回寝室接着睡觉的，室友在快乐地激战 CS-GO，零零散散的睡了一会，起来玩原神，同时学习超星学习通平台上的《国家安全教育》网课。反诈小短剧还挺有意思的。
下载了 OMS，注册绑定了 PTA 账号。删除了 VScode 的所有插件，留了一个基本的 C/C++。
整理了一下比赛穿的衣服，带的模板书，用的充电器和插座。赛前最后让队友去印了一个这个板子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

# 20261011

## template.cpp

#include <bits/stdc++.h>
using namespace std;
// #define int long long

signed main()
{
#ifdef DEBUG
    clock_t t0 = clock();
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // you have so much time
    // tomorrow yet to come
    // you deserve more love

#ifdef DEBUG
    cerr << "Time used:" << clock() - t0 << "ms" << endl;
#endif
    return 0;
}


## new.ps1


Copy-Item template.cpp test.cpp
Remove-Item data.in 
Remove-Item data.out
New-Item -Name data.in 
New-Item -Name data.out


## run.ps1

g++ -DDEBUG -std=gnu++20 -O2 -Wall -Wextra test.cpp -o test.exe
./test.exe

六点左右来到了比赛的教学综合实验楼 N105 教室，接水上厕所，连接插线板，和队友聊了会天，睡大觉准备比赛。
头上戴了一个超级可爱的飘带发卡，图灵老祖显显灵吧，然后被后面学长认出来了。“哥们你是天天早晨吗，群里的那个可爱 xnn”，我：“我这么有名的吗。”
开赛前连接监考系统，打板子和编译命令，快打完了监考人员说赛前不能动键盘，我就给全删了。
发卷，监考人员说正式开考前不能看题，我：这就和考英语四六级的写作文的时候不能看听力一样。我队友告诉我，后面好像零个人遵守，大家都在翻。然后我们也偷偷翻题册，但是监考人员一直走来走去导致我们看进去了零个单词。
我们开始猜测题目含义，猜测题目难度。我队友：“E 题这个简单的字符串问题真的简单吗”，我：“这种话你也信啊，出题人的话你也信。”没想到这真的是签到题，失算了。
开赛，读题，队友对各种名词如”整除“，”取余“，”闭区间“，”子字符串“感到好奇，虽然我都认识，但他们还是去翻字典了，查字典也是 ICPC 的一大乐趣，哈哈。
然后我看了一下电脑上的 A 题，迅速翻译出了 A 题中对十的幂次整除取模的含义，总结出了题意：

• 网络预选赛 A good prime：给定询问数 $T$（$T\le 10^6$）与 $T$ 个区间 $[l,r]$（$1\le l\le r\le 5\times10^7$），统计区间内满足「十进制表示中存在某个连续数字子串为素数」的整数 $x$ 的个数。

我想着先用线性筛把质数全找出来，然后对于每一个数，判断他有没有质数子串，最多也就是两个 log。最后做一个前缀和，对每个询问求一个差就好了。总的复杂度应该是线性乘一个不大常数（我设定为 8 * 8 = 64 了，10 的 0~7 次幂共 8 位），而且跑不满，看了一下两秒的时限，应该可以过。然后就开始写代码，从蓝书上抄了一个线性筛的板子，让队友去看后面的题了。
第一次提交 A 题，把线性筛的上限写成 1e7 了，WA，之后一直 TLE。断定为系统卡常，开始尝试优化。想了各种卡常办法，把输入输出换成了 scanf/printf，等等，均未通过。我看排行榜，发现一小时仍然无人通过 A 题，反而是 B 题和 E 题有通过，判断系统卡常过于严重，遂保存代码开 B 题，队友告诉了我题意：

• 网络预选赛 B MystPal：给定长度 $n$（$n\le10^6$，$T\le10^5$ 次询问），统计长度为 $n$ 的 0/1 串中「是回文、且其二进制值能被 $3$ 整除」的串数，答案对 $998244353$ 取模。

然后数竞背景的队友告诉我用费马小定理转换，等价于奇数位置上的 1 和偶数上的 1 的个数相等。然后他们分析出了偶数长度的字符串都可取，我得出答案就是 $2^\frac{n}{2}$，队友提醒我取模，我去蓝书上抄了一个快速幂取模的板子。然后我们开始推奇数的公式，我按 $k = \frac{n - 1}{2}$ 的奇偶给出了两组组合数求和，让数竞的队友想想这个东西怎么算，我指出这个东西可能要用范德蒙德卷积，但是我不记得公式了，队友指出他没听说过，于是我们开 E 题。

• 网络预选赛 E Maybe an Easy String Problem：给定字符串 $s$ 与 $q$ 次询问 $[l,r]$（$n,q\le10^6$），求子串 $s[l,r]$ 内出现次数最多的子串的出现次数。

队友问我单个字母算不算子串，我说，你看第四个样例呗，区间长度为 $2$ 的询问答案都为 $1$ 了，你说算不算。我：“这倒是提醒我了”，子串的重复个数，肯定不多于里面某个字母的重复个数，那这不就是问出现最多的字母出现了多少次吗，字母就 $26$ 个小写字母，那直接开 $26$ 棵线段树呗。队友说，他之前学过的最高级的数据结构就是线段树了，现在已经忘了。我说，等下这个东西又不用修改，那直接开 $26$ 个前缀和不就是了，于是迅速写出了代码。然后又 TLE，我草，$O(cn)$ 的复杂度怎么可能还不对哦，发现忘记把板子上的关同步流抄上去了，遂换 scanf，又交，又 TLE，发现忘记写 printf 了。然后总算过了。看了一下排名，跟队友说进正赛肯定稳了，大家非常开心。
接下来我们讨论 B 题的公式，我让他们考虑一下组合意义，因为每一个复杂的组合恒等式背后，都蕴含着一个简洁的组合意义。然后他们在思考，我去接着卡 A 题的常数。
我把末尾为 ${2,3,5,7}$ 的数字去掉了，减少了 $40\%$ 的计算量，然后又把十位是这些数的去掉了，继续减少计算量，但都未通过。我：“你们帮我在草稿纸上默写一下 $0 \sim 100$ 的质数”，两位队友争着抢着做，说总算找到了一些真的会做的事了。然后我把含 $2,3,5,7$ 的划掉，剩了 5 个，把这几个结尾的数也去掉，本地预处理所用的时间从 $2300ms \rightarrow 1800ms \rightarrow 1100ms \rightarrow 800ms$ ，还是无法通过。于是我放弃抵抗，对评测机破口大骂。
在对评测机的一片骂声中结束了比赛，赛后队友和后面学长聊天，发现他们是 25 级大二的。我：我怎么在高年级里也这么有名，学长说在北邮各个内卷群、竞赛群里都能看见我，然后我们加了好友。
最终比赛爆零率 $58\%$，最强的队伍通过了 $3$ 题。就是上述的三题。其他试题 $0$ 个队伍通过。
群里交流，好像说后面两题是南昌 CCPC 的原题，然后前面四题是原创的，我也没搜到原题。
晚上睡前，和校队的成员学长交流比赛。学长说应该参与了网络预选赛的都可以打校赛，主要是判断是否有基本的竞赛素养。我：“牛魔的，机器这么慢，数据开给这么大，爆了”，学长：“没绷住”。
睡了十分钟醒了，百思不得其解那个组合数怎么算，于是拿出手机问大肥鱼老师，发现真的是范德蒙德卷积，又爆了。

Day 0.14

早上和在 pku 的同学交流试题，他说 A 题其实可以把所有位是 $2,3,5,7$ 的都给去掉，只需要枚举 $6^8$ 的状态空间就可以了。
早上起来碰到队友，跟他们说那个组合数就是范德蒙德卷积，然后我有空把题目补一下给队友讲一下，这个题目出的还是不错的，可以学到很多东西，就是评测机太烂了。
带着两个刚入门大学程序设计竞赛的小萌新打比赛其实还是挺有意思的，希望大家都能学到东西吧，也不必要追求那个奖项。
早上心理课写高数作业，中午体育课太极拳学不会，下午计算导论与程序设计课本来想写游记的，但是呼呼大睡了，然后晚上写游记写到这里。
晚上还公布了正式赛的报名通知，把报名表填了，队伍名使用了之前定好的 队长原神uid227532488，网络赛没有滚榜，都没显示这个。

Day 0.29

有大佬说，B 题可以直接 OEIS，并且搜出了 A112387。并且他用 AI 证明了这个数列和原问题的相关性，给了我递推公式和通项公式。我整天思考这个公式，却没有取得什么进展。

Day 0.43

在梦里梦到了 A 题和 B 题的做法，凌晨六点钟突然惊醒，开始思考。想清楚了 A 题的代码实现细节，借助 DFS 把两个 log 降到了一个 log。继续想 B 题的公式。还是想不出来，无奈只能拿出向大肥鱼老师提问。看到大肥鱼用范德蒙德卷积的做法还引入了三次单位根，用了非常高级的生成函数，吓哭了，发现我的考场做法假了。中间位为零且奇数位的 $1$ 的个数等于偶数位，是模三余零的充分不必要条件，所以会导致漏解。若中间位不为零，或许也有其他的组合计数方法，但没有再往组合计数思考了。开始研究 OEIS 上的递推公式。
观察大肥鱼给出的解释中，发现大肥鱼注意力惊人，观察到了一堆极其难以观察到的性质。令我印象比较深刻的一个是 “回文二进制串对三求余数，余 $0$ 和 余 $1$ 的串数相同”。大肥鱼把按位取反用减法表示，借助取余运算对加减的性质，证明了这个引理和上面的递推公式，以及通项公式。
看完大肥鱼的递推过程和计算过程，忽魂悸以魄动，恍惊起而长嗟。每个奇数回文串必定可以由长度比他小 $2$ 的回文串在两边同时拼上零和一而来，拼零相当于乘以二，拼一也有数学公式可以算。那么可以对所有串按模三的余数分类，比如余一的串在乘以二之后全部会变成余二的串，总而言之这个问题具有最优子结构性质和无后效性，可以很容易的使用动态规划求解，不需要复杂的组合计数了。想到这里，我安详的睡去了，并在高数课前勉强醒来。
高数课上和大佬讨论了 PTA 的 ICPC 报名系统的使用，我已经顺利完成了武汉站区域赛打星的报名，于是绑定了我自己的 ICPC 账号，并授权给了北邮，准备正式赛的报名。
下午实现了 A 题的 dfs 写法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

#include <bits/stdc++.h>
using namespace std;
// #define int long long
const int N = 5e7;
int v[N + 5], prime[N/ 10];
int f[N + 5], po[10] = {1};

int m;
void primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (v[i] == 0) // i is prime
        {
            v[i] = i;
            prime[++m] = i;
        }
        for (int j = 1; j <= m; j++)
        {
            if (prime[j] > v[i] || prime[j] > n / i)
                break;
            v[i * prime[j]] = prime[j];
        }
    }
}

void dfs(int x, bool pr = 0)
{
    if (x > N)
        return;
    for (int j = 0; !pr && po[j] <= x * 10; j++)
        pr |= (v[x % po[j]] == (x % po[j])) && (x % po[j]);
    if (pr)
        f[x] = 1;
    for (int i = 0; i <= 9; i++)
    {
        int nxt = x * 10 + i;
        if (nxt)
            dfs(nxt, pr);
    }
}

void solve()
{
    int l, r;
    scanf("%d %d", &l, &r);
    printf("%d\n", f[r] - f[l - 1]);
}

signed main()
{
#ifdef DEBUG
    clock_t t0 = clock();
    freopen("input.txt", "r", stdin);
    freopen("data.ans", "w", stdout);
#endif

    // you have so much time
    // tomorrow yet to come
    // you deserve more love

    primes(N);

    for (int i = 1; i <= 9; i++)
        po[i] = po[i - 1] * 10;

    dfs(0);
    for (int i = 1; i <= N; i++)
        f[i] += f[i - 1];

    int q;
    scanf("%d", &q);
    while (q--)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d\n", f[r] - f[l - 1]);
    }

#ifdef DEBUG
    cerr << "Time used:" << clock() - t0 << "ms" << endl;
#endif
    return 0;
}

发现 PTA 无法提交了，询问了大肥鱼老师这个做法是否正确，得到肯定回复后让她生成了一组测试数据，把这个题搬到了洛谷上：T834936 第20届北邮程序设计竞赛预选赛 A good prime - 洛谷。
让大佬帮我验下数据，他写了一个比 AI 生成的解法更快的版本。
我们还讨论了打表的可行性，大佬说使用 base85 编码压缩可以让代码长度可观，我说校赛规则（第20届北京邮电大学程序设计竞赛赛前公告）里指出，不能使用混淆代码。

Day 0.71

晚饭后，在晚上上课的教室详细推了 DP 的转移公式，并且完成了代码。然后让那位大佬指挥 AI 写了一份数学公式解法，两份対拍后生成了数据，把 B 题也搬到了洛谷上：T836448 第20届北邮程序设计竞赛预选赛 B MystPal - 洛谷。
晚上 AI 导论课的课间和队友讨论了一下训练计划，打算明天找时间把题讲一讲。
实现的 DP 解法代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <bits/stdc++.h>
using namespace std;
// #define int long long

const int mod = 998244353, N = 1e6;

long long dp[N + 3][3];

signed main()
{
#ifdef DEBUG
    clock_t t0 = clock();
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // you have so much time
    // tomorrow yet to come
    // you deserve more love

    dp[1][0] = 1, dp[1][1] = 1;
    dp[2][0] = 2;

    for (int i = 4; i <= N; i += 2)
        dp[i][0] = dp[i - 2][0] * 2 % mod;

    for (int i = 3; i <= N; i += 2)
    {
        dp[i][0] = (dp[i - 2][0] + dp[i - 2][2]) % mod;
        dp[i][1] = (dp[i - 2][1] + dp[i - 2][2]) % mod;
        dp[i][2] = (dp[i - 2][0] + dp[i - 2][1]) % mod;
    }

    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        cout << dp[n][0] << endl;
    }

#ifdef DEBUG
    cerr << "Time used:" << clock() - t0 << "ms" << endl;
#endif
    return 0;
}

Day 1

终于到了正式赛的日子，突然有些紧张。凌晨五点多又惊醒了，躺着床上强迫自己入睡，不记得有没有成功了。起来丢了下垃圾，把三本算法书装到书包里，出门吃早饭。吃完早饭去买零食，然后拿个了水杯，提醒了队友买零食和带校园卡，八点多就去工程实验楼准备比赛了。上楼的时候碰到了校队教练带着几个学长搬水什么的。
到达机房，在第一排的一张桌子上找到了座位表，找到了我们自己的座位在靠门的位置。摆了一下零食和书，开始调电脑。先检查了 g++ 和 python 在不在环境变量里，发现要输入 py 来使用 Python 交互式解释器。然后看了 VS Code 的使用情况，调主题、调运行设置，写了编译脚本。想起来网络赛有一段代码忘记备份了，所以这次在 new.bat 里新增了一个 copy test.cpp back.cpp。调了下输入法，设置了一个美式英语键盘。这时候监考人员开始发队名牌了，把我们的队名发到靠窗位置去了，于是我就把电脑关了准备搬东西，后面发现是他们发错了，我就重新打了一遍上述内容。后面队友开电脑了，我说只能开一台电脑，然后关电脑，一不小心把自己电脑关了。所以只能在热身赛的时候再打一遍。
热身赛，A 题是一个 A+B 试机，很快的打掉了，并学会了提交代码的流程。接下来我们开 B 题：

• 热身赛 B Polygon：给定 $n$ 根木棍的长度 $a_i$（$3 \le k \le n \le 3000$，$1 \le a_i \le 10^9$），问是否存在选出 $k$ 根木棍的方案，使它们能围成面积为正的简单多边形，输出 Yes 或 No。

一开始把多边形那个英语单词看成三角形了，但是其实做法差不多。赛场上认为，需要找到某些根拼成一条边，然后剩下的总长度大于这条边即可。事实上，充要条件是所选木棍中最长的一根的长度小于其余 $k-1$ 根长度之和。问题就是选哪 $k$ 根。我最早的直觉是，一定是排序后的连续 $k$ 根，但是写出来交上去 WA 了。然后我开始乱搞，在时间限制内随机打乱选连续的，按照那个复杂度较高的方法检验，但是没搞出来。于是我放弃了这题，开始做 C 题。

• 热身赛 C Online Preliminary：给定 $n \times m$ 的小写字母矩阵（$2 \le n,m \le 500$），求满足 $A=\begin{bmatrix}c & c\\ p & c\end{bmatrix}$ 的连续 $2\times2$ 子矩阵个数（即左上、右上、右下取同一字母 $c$，左下取另一字母 $p$），输出该计数。

这倒是一个比较轻松的题目，很容易的就写掉了。然后想试一下样例下载的功能，发现第三题下载下来是 B 题的样例数据，刚刚两发交到第二题的记录实际上是交到 C 题去了，难蚌。然后赛场上不断的传出“我草，他这个 B C 两题提交的地方是反的”，赛场上充满了欢快的空气。
最终还是没想到 B 的正解，但是无所谓了，反正热身赛不太重要，主要是要把设备调好，准备打正赛了。中间去上了个厕所，调了一下图灵派小装备——可爱发卡。

正式赛，依旧要求开赛前不能看题，但是周围人已经开始拆袋子了，于是我们也先把袋子拆好把题目分到各个成员手上，并没有翻开题目。
发现 B 题是一个 Hello World 问题，和 BUPT 71st 校庆有关，但是那句话有点长。于是我提前设置好代码模板，写好 cout，由于之前测试好了样例下载功能，解压缩，复制，提交，拿下了 B 题的一血。
接下来我们在找可做题，队友们读了一下 C 题：

• 正式赛 C Bomb：共 $T$ 组数据（$1\le T\le 10^4$），每组数据给定炸弹数 $n$（$1\le n\le 2\times10^5$，$\sum n\le 2\times 10^5$）、重置值 $k$（$1\le k\le 10^9$）和初始数值 $a_1,\dots,a_n$（$1\le a_i\le 10^9$）；每次操作分两步，且必须先做第一步：先任选一枚炸弹把它的数值改为 $k$，再让所有炸弹的数值同时减 $1$（即 $a_i \leftarrow k,\ a_j \leftarrow a_j-1\ (\forall j\ne i)$），若某枚数值变为 $0$，该炸弹就爆炸并终止整个流程；问是否存在策略使操作能无限进行下去，对每组数据输出 YES/NO。

和队友大概讨论了一下，每次选最小的即可。然后我就让队友去读别的题了，我自己写这个就行。但是其实细节还是挺多的，自己造了挺多情况，花了 15 min，代码写的有点丑，但是还是感觉大概完备了吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

const int N = 2e5 + 5;

int n, k;

int a[N], f[N];

  

void solve()

{

    memset(f, 0, sizeof f);

    cin >> n >> k;

    int res_l = 0, res_1 = 0;

    for (int i = 1; i <= n; i++)

    {

        cin >> a[i];

        res_l += a[i] < k;

        res_1 += a[i] == 1;

        if (a[i] < n)

            f[a[i]]++;

    }

    if (res_1 > 1 || res_l >= k || k == 1 || n >= k)

    {

        cout << "NO" << endl;

        return;

    }

    for (int i = 1; i <= n; i++)

    {

        f[i] += f[i - 1];

        if (f[i] > i)

        {

            cout << "NO" << endl;

            return;

        }

    }

    cout << "Yes" << endl;

}

发现确实 AC 了，甚至还是正式赛首 A，之前那个 AC 的是打星队，所以又拿到了一个金色气球，喜。接下来我们发现 G 题过的比较多，于是开了 G 题。

• 正式赛 G Hate Primes：给定 $n$（$1\le n\le 10^7$），求最大的项数 $k$，使得存在严格递增的等差数列 $a_1<a_2<\cdots<a_k$，公差 $d\ge 1$，且所有项 $a_i\le n$、每一项都不是质数。

我开始列举：$n = 1,2,3, ans = 1$,$n=4,5,ans=2$,$n=6,7,8,...$的话，答案序列最长的一定是 $4,6,8,...$，队友认可了我的直觉。然后我细化了一下公式，在第 25 min 通过了这题。
接下来我们看 F 题，发现 F 也是签到题，是一道有限个情况的两种地铁票价的比较，快速写掉了。写着写着我们发现，30 之后都有规律哈哈。这题应该是团队含量最高的一题了。
接下来我们开 H 题：

• 正式赛 H Orthogonal Master：Mille-Un 是二维向量空间的大师，尤其精通正交性；他在 ECF 2025 杭州站对正交性有了更深理解后，出了一道小测题——给定两个向量 $u=(x_1,y_1)^{\mathsf T}$、$v=(x_2,y_2)^{\mathsf T}$，以及对任意正整数 $a,b$ 定义的线性变换 $f_{a,b}(x,y)=(ax,by)$，需要构造（任意一组）正整数 $a,b$（要求 $1\le a,b\le 10^9$），使得 $f_{a,b}(u)\perp f_{a,b}(v)$；如果不存在这样的 $a,b$，就报告无解。本题有多组询问 $T$（$1\le T\le 10^5$），每组询问给定整数坐标 $x_1,y_1,x_2,y_2\in[-10^5,10^5]$。
  我一眼看出这是一个解方程问题，一开始以为要质因数分解，对比次数差是偶数的，后面发现直接两边除一个 gcd 就可以了。写代码的时候发现，其实细节还是比较多的，我分析符号的时候忘记把除以零判掉了还调了一会。还好最后还是一遍过了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

#define int long long

  

void solve()

{

    int x1, x2, y1, y2;

    cin >> x1 >> y1 >> x2 >> y2;

  

    int X = x1 * x2, Y = -y1 * y2;

  

    if ((X == 0) + (Y == 0) == 1)

    {

        cout << "Non" << endl;

        return;

    }

    else if ((X == 0) && (Y == 0))

    {

        cout << "Oui 1 1" << '\n';

        return;

    }

    int sgnx = X / abs(X), sgny = Y / abs(Y);

    if (sgnx != sgny)

    {

        cout << "Non" << '\n';

        return;

    }

    int x = abs(X), y = abs(Y);

    int g = __gcd(x, y);

    x /= g, y /= g;

    int sx = sqrt(x), sy = sqrt(y);

    if (sx * sx != x || sy * sy != y)

    {

        cout << "Non" << '\n';

        return;

    }

    cout << "Oui " << sy << ' ' << sx << " \n";

}

至此，我认为比较轻松的题目已经全部做完，后面的都是攻坚克难战斗。赛后也证实，上述就是铜牌题。我大概观察了一下榜单和题目，可能可以做的题有：

• 正式赛 A Best Performance：队长 Orange_Ice 为“Gold Astral Oculus”队挑选 ICPC 赛站——共有 $n$ 个赛站，分别在第 $1..n$ 周举行，第 $i$ 个赛站的预期得分是 $a_i$，需要恰好选出 $m$ 个；由于队伍不喜欢连续周参赛，任意两个被选中的赛站 $j<i$ 都会扣掉 $(n-(i-j))\cdot t$，要求最大化总分（$1\le m\le n\le 5000$，$1\le t\le 10^5$，$1\le a_i\le 10^9$）；输出最大总分。
• 正式赛 E Far in the blue sky：在一款 $m$ 键音游中，每条轨道对应一根不同的手指；谱面作者已定好 $n$ 个时刻各自的密度 $a_i$，每个音都要由不同手指同时按下；手指的“压力”等于该手指连续被使用的最大时刻数；现在需要给每个时刻分配具体手指，问所有合法分配下，最大手指压力的最大值与最小值（$1\le n\le 10^5$，$1\le m\le 10^9$，$0\le a_i\le m$）；输出这两个值。
• 正式赛 J Resonance：给定信号 $a_1..a_n$（可为负，约定 $j>n$ 时 $a_j=0$），支持 $m$ 次操作：① $1\ p\ v$ 把第 $p$ 个采样改为 $v$；② $2\ k\ r$ 查询该信号在周期 $k$、相位 $r$ 处的自相关值 $\sum_{1\le i\le n,\ i\equiv r\ (\mathrm{mod}\ k)} a_i\cdot a_{i+k}$（$1\le r\le k\le n$）；$1\le n,m\le 5\times10^5$，$|a_i|,|v|\le 10^6$；每个查询输出一行答案。
• 正式赛 K Seeing is believing：这是一道交互题——你被困在一个 $n\times n$、格子为 . 或 # 的漆黑迷宫（起点 $(1,1)$，终点 $(n,n)$，保证连通），通过尝试朝上下左右移动并读取返回的 $1$（成功）/ $0$（撞墙或出界）来探路，移动尝试总数不得超过 $2n^2$（$2\le n\le 500$）；收集足够信息后输出 !，随后输出从 $(1,1)$ 到 $(n,n)$ 的最短路径（由 W/A/S/D 组成），若步数超限、路径不合法或非最短都判错。
• 正式赛 N XOR：给定长度为 $n$ 的非负整数序列 $A=\{a_1..a_n\}$，定义序列值为 $\sum_{i=1}^{n-1}(a_i\oplus a_{i+1})$；至多可以执行一次操作：选整数 $X$（$0\le X<2^{30}$）与区间 $[l,r]$，把 $a_l..a_r$ 全部异或 $X$；求操作后序列值的最大值。多组数据 $T$（$1\le T\le 10^4$），$1\le n\le 2\times10^5$ 且 $\sum n\le 2\times10^5$，$0\le a_i<2^{30}$。

J 题我想到了根号分治，但是我貌似只听过这种思想，从未实现过相关代码（只写过最普通的分块吧应该），觉得实现不出来。E 题我想了很久的构造方案，发现代码实现不出来。A 题我一开始认为是一个朴素的两项相关的类 lIS DP，写出了方程，过了第一组样例，发现第二组过不去，原来非相邻的两项也是会产生影响的，那这个我就完全不会写了。K 题我在想，迷宫最短路要用 BFS 或者可以尝试用 A* 优化，但探索地图要回溯要写 DFS，所以到底是用 BFS 还是 DFS。BFS 写了一半发现回溯不了，于是放弃。直至封榜也没有通过题目。看了看排行榜，可能要末银（银牌后四名）或者首铜了。只能全力投入 N 题。
我首先给队友介绍了异或的交换律，结合律，自反律和零律，说明了区间异或对答案的影响：最多影响两项。于是把答案分成影响一项和两项进行分析，一项是容易的，对于变两项，观察到一个重要性质：$2^n>2^{n-1}+2^{n-2}+...+2^{0}$，于是要先修改较高位。并且只有两个数的同一位都为 $0$ 修改才有贡献。至此已经发现了本题需要的所有性质，我开始实现代码，但是被一些细节卡掉了。于是我开始乱搞改代码，改了 5 次甚至 AC 了，我和队友都很惊讶。我让大肥鱼分析了一下改 Bug 的过程：DeepSeek - 探索未至之境 - 分享对话。
通过这题后，还剩下 15 分钟，应该没有希望继续过题了，我在考场上呼呼大睡，收拾东西准备离开。
之后就到了颁奖典礼，总教练发言分享了一些他对于算法竞赛和当今时代发展需求的看法，滚榜时大家对着一些有趣的队名捧腹大笑，也包括我的队名。最终成绩是首银（银牌前四名，首批上去领奖），也算是满意了。
怎么真的有同学来加我的原神好友啊，哈哈哈。
颁奖典礼结束后是校队介绍，银牌可以随队训练。

（完）