第二次参加ICPC现场赛。

去年第一次去北大北京赛站瞎搞搞，混了个铜奖，今年是奔着金奖去，可惜还是没能如愿。

一个月前的CCPC秦皇岛拿了个银，教练说ICPC比CCPC拿牌容易多了，我队就这么信了。

不过南京赛站真的是各路神仙齐聚，吃瓜心态，佛系比赛。

抵达南京

周五下午的高铁从北京到南京，第一次知道原来比赛可以在外面报销三晚酒店，莫名兴奋，结果高铁也莫名晚点15分钟，又晚点10分钟，突然又晚点1分钟（魔性的一分钟），然后终于在延后的计划发车时间开始检票了，20年人生第一次遇到高铁晚点。

到了南京已经比较晚了，大晚上点烧烤外卖，低估了南京吃辣的程度，微辣的烧烤，虽然作为重庆人的我没啥感觉，但是两个北京队友都不行了，第二天都拉肚子了，真的好怕变成一个人的比赛。下次出来一定别乱吃东西了！

接下来就正常程序，睡觉，早饭，签到，午饭，热身赛。。。

不过不得不说南航食堂挺不错的，餐券很棒！

热身赛

凉身赛现场，两题飘过。

A

题目大意：Hello World!!!（不过原题目是欢迎来到南航，并不知道南航怎么拼，不过题目就是答案）

当时还没有发题册，网站上只能看到题目名称，队友上来说“你信不信直接输出”，交了就过了，真的笑哭了。不过这样都不是FB，好像是第三个提交的，各路神仙都很有先见之明啊！

B

题目大意：16进制数依次排列‘123456789ABCDEF101112...’，两种询问

1）询问第i位是什么字符

2）询问第i位以前，字符c出现了多少次

就是一个模拟，改了半天并没有过，队友觉得自己血对，咱也不知道啥情况。

C

题目大意：CF原题，链接：https://codeforces.com/problemset/problem/1228/E ，题目数据范围加大了，n是1e5

容斥加一步组合数的变化就可以了，具体不解释了，还好打过cf这一场，而且补了这道题。

D

题目大意：忘了。。。

据说是广义后缀自动机，我队表示并不会，猜到是后缀自动机，现场开始现学，菜鸡滚粗。

正式赛

上来翻开题册，看到A题的题目长度，猜测一定是一道签到题，就让队友先上去敲着代码，自己推完公式刚好接上，就直接交了。3min一发A，这种SB题，以后就放弃本地测试吧，说不定还能拿个全场一血。

A

题目大意： 给正整数n，找到一个最小的整数k使得对于{1,2,3,...,n}中的所有大小为k的子集内都存在至少两个数有整除关系。

• 很容易想到，倍数关系最小为2，所以只需要选取所有大于n/2的数，这是满足无整除关系的最大子集
• 再随意添加一个数都会出现整除关系。
• 所以结果公式就很简单了

$$ ans = (n+1)/2+1 $$

接下来是漫长的时间，我队接近两个小时没过题，个人很喜欢H题这样的机智题，本来很有把握的题，18分钟作业提交一发WA，后来一直没想到特例就搁置一旁了，Minisam写了很久I题，全场没一个人过，dbq是被我带跑偏的节奏，RE加TLE，然后Roark跟榜写了K，敲完板子，发现没有跑出来样例，这两个小时就这么过去了。

之后我跟榜写了C题，写的挺快的，两个半小时左右终于又一发A，还是跟榜比较正常。

C

题目大意： 给一个 n×m 的整数矩阵，求满足下面条件的路径有多少条：任意起点，路径长度至少为4，路径上每个元素必须有边相邻，且元素差值为1，且是无法再拓展的路径。

• 直接对相邻元素差为1的两点建边，+1方向的有向边。
• 然后BFS跑拓扑即可
• 由于长度大于4，对每个点记录到该点长度为1、2、3以及大于等于4的路径数，跑到头的路径记录答案。

之后没过多久，Roark反应过来没加多组用例，上去改了一点又过了K题

K

题目大意： 给三角形三点坐标和点P坐标，要求找一点Q，使得线段PQ平分三角形面积且P，Q都在三角形的边上。

• 计算几何选手对着板子敲了一通就过了
• 如果点在三角形定点上，就是对边中点
• 如果点再边上，就先连接所在边的对顶点，计算分成两个三角形的面积比，再把大的三角形以P为顶点分成两个三角形使得满足对应的面积比即可。

这时候出去上洗手间的我回来了，真就出赛场一瞬间突然灵光一现，H题有个特殊用例，回来加上之后马上又A了。

H

题目大意：王子向公主求婚。宫中有三种群体，公主为首赞成婚礼的，皇后为首不赞成婚礼的，毫不关心的吃瓜群众。这三种人分别有a，b，c个。这些人分别待在各自的房间，王子可以向房间内的人提出以下三种问题：
1）你是谁（询问身份，有公主，皇后，侍卫，仆人等等）
2）在X房间内的人是谁
3）公主在哪个房间
所有人都会回答问题，赞成婚礼的人会提供正确的答案，不赞成的人一定会提供错误的答案，吃瓜路人的答案可能正确可能错误。问现在王子至少要问几个问题就能确保找到公主所在的房间，如果永远不能则输出-1

• 这里面最麻烦的是吃瓜群众，他们在某些特定的情况是好人，某些又是坏人，可以把当前的局势推向最坏的方向，所以就把他当作局势最坏的情况即可。
• 很容易想到如果只有好人和坏人，我们询问公主在哪个房间，如果好人多于坏人，而好人的答案又是一致的，那么指向最多的房间就一定是公主的房间。
• 再加上吃瓜群众，我们要求好人多于坏人，那吃瓜群众就都当作坏人最不利，所以要求好人数量大于坏人和吃瓜群众的和。即 a > b+c 才符合要求。
• 同理我们会思考坏人多的情况，可以枚举1个好人2个坏人的情况，无论如何都不行。
• 之后再考虑询问次数最少，只需要知道一个回答出现了 b+c+1 次那么就知道了正确答案，所以询问 2(b+c)+1 次即可。
• 但是有一个trick的地方，1 0 0 答案为多少，只有公主一个人，那tm就不需要问了，直接抱走！（想出特例的时候内心崩溃）

半小时过了3道题，瞬间有了点心理安慰。

跟全场做 J 题，但是到最后也没过，这题后面再讲。

看见学校另外一个队过了 B 题，于是开了这道题，我队英语能力真的堪忧，这题读题读了大概20多分钟，还好瞎找找规律猜对了，封榜后过了这题。

B

题目大意： n×m 的矩形格，任意选定起点，每次可以走相邻的元素，问染色所有格点有多少种方案。染色的路径需要满足一个条件，走过每一个点时，需保证从起点到该点至少存在一条最短路径已染色。

• 先打表找规律吧（人工打表，当时就推了 4×4 以内的吧）
• 除了 1×n 的矩阵，猜到一个结论如下：

$$ ans_{n,m} = ans_{n-1,m} + ans_{n,m-1} $$

• 特判 1×1 时为 1，1×n 时为 2
• 其他情况满足上述规律，即杨辉三角，乘上系数即可

$$ ans_{n,m} = 4×C_{n+m-2}^{n-1} $$

• 回过头想一想这个结论可以由猜想得来
• 所有的终点保证在矩形的顶点上，增加一行或一列只能直接从终点开始延展
• 所以 n×m 的矩形可以由 (n-1)×m 的矩形添加一行，n×(m-1) 的矩形添加一列得来

另外我队还开了的两道题，但是赛时都没有通过，简单说一下题意吧。I 题从比赛开始写到比赛结束， J 题一共写了四个版本，真的心力憔悴。

J

题目大意：A和B各有n个队伍，A每队的能力值给出，B每队由代码手和端茶送水的两个人组成，给出每个人的能力值，且该队伍能力值为这两人能力值之和。A、B的n支队伍随机对战（一共有n!种对战可能），如果B队能力值大于A队则能获得A队对应的分数，问组队后B战队最大得分期望乘n。

• 期望很容易得到，即能获胜的得分和
• 问题就简化为一个任务分配问题，二分匹配最大权，变成了KM板子题

但是很trick的点是，通用模板bin巨的板子KM是错的，本来是O(n3)的算法，板子是O(n4)的，多少队死在这里。

一队友真的心态崩了，本题一共敲了4套板子，KM、SPFA费用流、Dijkstra费用流、zkw费用流，都无力回天。最后知道是板子的锅。

I

题目大意：给定n+1个非负整数表示能量值（最大50），初始能量值为a0，每次选择的能量值只能小于等于当前获得所有能量值的和，问一共有多少种选择序列。

• 很容易想到暴搜，暴搜当然血T
• 50的划分数在2e5左右，所以可以记忆化搜索。（但是并不会怎么进行记忆化映射）
• 赛后听说vector&sort+map就可以了，准备赛后开放补题后试试，未亲测。

最后比赛结束，鼓掌撒花！

比赛总的来说，比较满意，但有遗憾，实力不足也运气欠佳。

上海再战吧！佩奇们冲鸭！

（最后放上我队吉祥物们）