CSP-S 游记

· · 生活·游记

感觉上次游记没写好。再写一个。

首先放出我 CSP 集训更改过多少个个人签名。

2026.10.30 晚上睡了 \epsilon 小时。

【数据删除】怎么 CSP-S 在下午啊？？？？

14:25 压缩包密码 Oct31==Dec25?

还不如去年的 RenJieDiLing+特殊符号 呢

14:30

开场。题目名称都这么难听，【数据删除】。

进行大学习。T1 怎么是扇贝题啊，三等线要 100 了。

14:39

T1 打完了，大洋里过了。

T2 什么玩意？？？题面大阅读。

::::info[地铁/subway]

题目描述

B 市共有 m 个地铁站，编号为 1 到 m。每个地铁站都有一个站厅，地铁口与站厅之间有一条通道，往返耗时相同。从第 v（1 \le v \le m）个地铁站的地铁口走到站厅需要 w_v 的时间。

B 市共有 n 条地铁线路，编号为 1 到 n，其中第 i（1 \le i \le n）条线路经过 k_i 个地铁站，编号依次为 a_{i,1},a_{i,2},\ldots,a_{i,k_i}。在第 a_{i,j}（1 \le j \le k_i）个地铁站处，从站厅走到第 i 条线路的站台需要 t_{i,j} 的时间，往返耗时相同。同一条线路不会重复经过同一个地铁站，即 a_{i,1},a_{i,2},\ldots,a_{i,k_i} 两两不同。

由于空间有限，每个地铁站最多有 d 条线路经过。此外，B 市的地铁网络是连通的，即任意两个地铁站都可以通过若干条线路互相到达。

小 R 有 q 个出行计划。对于第 r（1 \le r \le q）个出行计划，小 R 将从第 x_r 个地铁站的地铁口出发，乘坐地铁到达第 y_r 个地铁站的地铁口，途中可能进行若干次站内换乘。每次站内换乘都需要从一条线路的站台先走到站厅，再从站厅走到另一条线路的站台。每个出行计划的总步行时间为进出站和换乘的步行时间之和。小 R 希望每个出行计划的总步行时间都尽可能少。

你需要帮助小 R 求出，每个出行计划的最小总步行时间。

输入格式

从文件 subway.in 中读入数据。

输入的第一行包含五个非负整数 c,n,m,d,q，分别表示测试点编号、地铁线路数、地铁站数、每个地铁站最多被几条线路经过，以及出行计划数。特别地，若 c=0，则该测试点为样例。

输入的第二行包含 m 个正整数 w_1,w_2,\ldots,w_m，依次表示从每个地铁站的地铁口走到站厅需要的时间。

输入的第 i+2（1 \le i \le n）行包含 1+2k_i 个正整数，其中第一个正整数为 k_i，表示第 i 条线路经过的地铁站数；接下来 2k_i 个正整数为 a_{i,1},t_{i,1},a_{i,2},t_{i,2},\ldots,a_{i,k_i},t_{i,k_i}，其中 a_{i,j} 表示第 i 条线路经过的第 j 个地铁站，t_{i,j} 表示从该地铁站的站厅走到第 i 条线路的站台需要的时间。

输入的第 r+n+2（1 \le r \le q）行包含两个正整数 x_r,y_r，分别表示第 r 个出行计划的起点和终点所在的地铁站编号。

输出格式

输出到文件 subway.out 中。

输出 q 行，其中第 r（1 \le r \le q）行包含一个非负整数，表示第 r 个出行计划的最小总步行时间。

输入输出样例 #1

输入 #1

0 2 5 20 2
4 1 9 2 5
3 1 5 2 7 4 6
3 2 3 3 4 5 7
1 3
1 2

输出 #1

32
17

输入输出样例 #2

输入 #2

0 3 7 20 2
8 3 6 1 7 2 9
3 1 4 2 5 5 100
3 2 6 3 1 7 2
4 3 2 5 100 4 6 6 7
1 6
2 3

输出 #2

35
16

说明/提示

样例 1 解释

B 市有 5 个地铁站，从各地铁口走到站厅需要的时间分别为 4,1,9,2,5。

B 市有 2 条地铁线路，其中第 1 条线路依次经过第 1,2,4 个地铁站，第 2 条线路依次经过第 2,3,5 个地铁站，两条线路在第 2 个地铁站相交。

对于第 1 个出行计划，小 R 将从第 1 个地铁站前往第 3 个地铁站：他可以先从第 1 个地铁站的地铁口走到站厅，再走到第 1 条线路的站台，乘坐第 1 条线路到达第 2 个地铁站后走回站厅，再走到第 2 条线路的站台，乘坐第 2 条线路到达第 3 个地铁站后走回站厅，最后走到第 3 个地铁站的地铁口，总步行时间为

w_1+t_{1,1}+(t_{1,2}+t_{2,1})+t_{2,2}+w_3=4+5+(7+3)+4+9=32.

对于第 2 个出行计划，小 R 将从第 1 个地铁站前往第 2 个地铁站：他可以先从第 1 个地铁站的地铁口走到站厅，再走到第 1 条线路的站台，乘坐第 1 条线路到达第 2 个地铁站后走回站厅，最后走到第 2 个地铁站的地铁口，总步行时间为

w_1+t_{1,1}+t_{1,2}+w_2=4+5+7+1=17.

样例 2 解释

B 市有 7 个地铁站与 3 条地铁线路，其中第 1 条线路依次经过第 1,2,5 个地铁站，第 2 条线路依次经过第 2,3,7 个地铁站，第 3 条线路依次经过第 3,5,4,6 个地铁站。

对于第 1 个出行计划，小 R 将从第 1 个地铁站前往第 6 个地铁站：他可以先从第 1 个地铁站的地铁口走到站厅，再走到第 1 条线路的站台，乘坐第 1 条线路到达第 2 个地铁站后走回站厅，再走到第 2 条线路的站台，乘坐第 2 条线路到达第 3 个地铁站后走回站厅，再走到第 3 条线路的站台，乘坐第 3 条线路到达第 6 个地铁站后走回站厅，最后走到第 6 个地铁站的地铁口，总步行时间为

w_1+t_{1,1}+(t_{1,2}+t_{2,1})+(t_{2,2}+t_{3,1})+t_{3,4}+w_6=35.

对于第 2 个出行计划，小 R 将从第 2 个地铁站前往第 3 个地铁站：他可以先从第 2 个地铁站的地铁口走到站厅，再走到第 2 条线路的站台，乘坐第 2 条线路到达第 3 个地铁站后走回站厅，最后走到第 3 个地铁站的地铁口，总步行时间为

w_2+t_{2,1}+t_{2,2}+w_3=16.

样例 3

见题目目录下的 subway/3.in 与 subway/3.ans。

该样例满足测试点 4 \sim 6 的约束条件。

样例 4

见题目目录下的 subway/4.in 与 subway/4.ans。

该样例满足测试点 9 \sim 11 的约束条件。

样例 5

见题目目录下的 subway/5.in 与 subway/5.ans。

该样例满足测试点 12 \sim 15 的约束条件。

样例 6

见题目目录下的 subway/6.in 与 subway/6.ans。

该样例满足测试点 16 \sim 19 的约束条件。

样例 7

见题目目录下的 subway/7.in 与 subway/7.ans。

该样例满足测试点 22,23 的约束条件。

数据范围

对于所有测试数据，均有：

::cute-table{tuack} | 测试点编号 | n \le | \sum_{i=1}^{n} k_i \le | d \le | q \le | 特殊性质 | | :---: | :---: | :---: | :---: | :---: | :---: | | 1 \sim 3 | 3 | 10 | 20 | 10 | 无 | | 4 \sim 6 | 50 | 300 | ^ | 200 | 无 | | 7,8 | 200 | 400 | ^ | ^ | A | | 9 \sim 11 | 500 | 1000 | ^| 10^5 | ^ | | 12 \sim 15 | ^ | 2 \times 10^4 | ^ | 2000 | B | | 16 \sim 19 | ^ | 5 \times 10^5 | ^ | 10^5 | ^ | | 20,21 | 2 | ^ | ^| ^ | 无 | | 22,23 | 500 | ^ | 2 | ^ | ^ | | 24,25 | ^ | ^ | 20 | ^ | ^ |

特殊性质 A：每条线路至多经过 2 个地铁站，即对于所有 i（1 \le i \le n），均有 k_i \le 2。

特殊性质 B：对于所有线路经过的所有地铁站，从站厅走到对应线路站台的步行时间都相同，即存在正整数 T，使得对于所有 i,j（1 \le i \le n，1 \le j \le k_i），均有 t_{i,j}=T。

想到了什么，会了。

15:03

T2 过了大洋里。开 T3。

研究了一会，发现这题的关键，总结就草稿纸上一句话：

鉴定为清仓甩卖

然而并不如清仓甩卖，很快就调过了。CCF 毒瘤能力下降了啊。

16:01

T3 手打一遍过大洋里？？？再见。

T4 看着好困难啊放弃。40 分似乎不难。

16:38

40 分打完了。爱怎么还有两个小时啊。摸鱼吧。

记录一下草稿纸上这之后都有什么

::::info[草稿纸] 来自中原一群伙伴结庐东南山尘缘难尽默对寒窗龙珠合十在胸膛秉承千年卓绝意志潜修东南山宁静致远风雨声响不绝如缕持香案香火在雨中烧几十个暑和寒血脉相连一方苦行山龙珠九转十二金光返指五岳和三江香火在雨中烧几十个暑和寒血脉相连一方苦行山龙珠九转十二金光返指五岳和三江来自中原一群伙伴结庐东南山尘缘难尽默对寒窗龙珠合十在胸膛秉承千年卓绝意志潜修东南山宁静致远风雨声响不绝如缕持香案香火在雨中烧几十个暑和寒血脉相连一方苦行山龙珠九转十二金光返指五岳和三江香火在雨中烧几十个暑和寒血脉相连一方苦行山龙珠九转十二金光返指五岳和三江香火在雨中烧几十个暑和寒血脉相连一方苦行山龙珠九转十二金光返指五岳和三江

昨日一去不复回哦吔开心比什么都贵覆水不能再收回哦吔 桃花谢了有玫瑰人生几十年总会有风雨来陪潇潇洒洒赴会今不醉不归往事后不后悔慢慢去体会此刻朋友这杯酒最珍贵快把酒满上干了这杯大声歌唱好朋友好朋友今宵多欢畅 ::::

这个人 240 分，这下知道研究地铁的好处了。

终于交卷了离场！！！！！！！！！

::::info[一些神秘的事情] 我曾经把 地铁/subway 的略微弱化版扔给 Txoi 后觉得没有任何意义遂删除。 ::::

啊【数据删除】 T4 好像没那么难啊。

没事干仿写文章就行了。

::::info[NOI考场被洪水水淹了，孩子逃生忘记提交代码痛失金牌，这才是人生的第一次考验] 还记得那年 NOI，考场地势低洼，天降暴雨，洪水漫进考场，没学过游泳的孩子慌忙逃生，连代码都忘了提交。分数线公布后是 556 分。后来有人从考场废墟里把代码捞出来一跑——558 分，刚好卡线金牌。

孩子回来时眼泪汪汪地对我说：“水一下子就淹过了脚腕，还在不停地往上涌。”而前排那个主场选手显然早有准备，洪水一来，他转身去楼道抱了个氧气瓶，回来把比赛打完才走。原来比赛考察的从来不是算法能力，而是你能不能在瞬息万变的考场上从容自若。

赛后圈子直接炸了。那个主场选手平时训练就戴着耳机、套五层口罩练肺活量，一看就是备足了功课。开考前一小时，长江堤坝被炸开一个口子，洪水正对着考场冲过来，监考老师全部撤离，他却缩在桌下躲过人员搜查，继续答题。源源不断的长江水养活了他的线段树，最终助他拿下 NOI 第一。

从那以后，孩子每进一所学校，第一件事就是看防汛物资放在哪里。NOI 考场上是长江水，IOI 考场上就可能是核事故，甚至外星人。我给他买了注铅的训练服，平时就穿着练，真到考场上遇到更严重的情况才不会慌。

第二年省选，考场设在 102 楼。飞机撞楼的时候别人全跑了，等着加时，他不慌不忙，一直待到大厦倾塌前最后一分钟才按下提交键，跳伞逃生。虽然赛后确实加了时，但他还是凭着那多出来的几分钟，硬生生多拿了 20 分。 就这 20 分，让他从省选边缘杀进了 A 队。

有人开始质疑：他是不是故意的？平时训练就爱带磁铁，这次直接把飞机引过来撞楼，连累所有人。

这就是省选结束后 24 小时内，信竞家长圈的真实写照。有人谩骂，有人庆幸，有人默默退群。竞赛选的从来不是一个人的水平，而是一个人能否在考场大楼被撞的情况下，依然坚持学习。

机构老师说他当年打 WC，写了棵字典树。雨水充沛的考场里，那棵树疯长，终究突破了树枝能承受的极限——字典一本本砸下来，不是新华字典，是一本本辞海，每本几千克重。但他还是坚持把比赛打完，拿了块银牌。

赛后他去质问出题人，为什么把字典树退化成链导致树不平衡、砸伤选手。出题人沉默地指了指旁边那个戴着头盔的选手。从那以后，他命令学生写代码时必须离电脑 30 米远。

“你要学会与半径 30 米的字典树共存。”