【浮生掠影】2019 浙大校赛 BY NESS @ hash
计算机
生活
随想
这是今年打的第一场比赛，成绩咱就不管了，总体玩的还是比较开心的。感觉光阴没有虚度，感觉前方还有着希望，而这就够了。
作为一次经历，一次体验，打比赛在生命中自然是有其价值的，它是一个节点，串起了过往无数日夜的辛劳准备与或狂喜或迷惘的期望。它不一定是结果，也不代表旅程的结束，以我当前的追求来看。它只是一个中点，是生活的增味剂，是另一种形式的酒与诗歌。无用，然而有趣。
说起比赛，首先想到的还是以往略显单调但也有滋有味的高中生活。想起以前翘课出去打NOIP，参加清华的不知什么考试，还有寒暑假在杭州在上海在环中的日日夜夜。关键并不在成就与从中得到的对自我的肯定，虽说这也是较重要的一环。我更喜欢的是合法翘课的感觉，喜欢的是纯粹出去玩这样一种心境。有一种逃离的快感，叛逆的甜蜜。而我所逃离的是什么呢？是日常？是普通？抑或无趣？在这层意义上，今天我仍然生活在高中时代的心理状态中。
热身赛
日程的话，早上有个热身赛，九点半开始。在此之前七点半至九点是所谓检录。下午一点正式开赛，打四个小时，直至五点。这样看下来，大半天都被打掉了。晚上其实也主要在想这回事，会有“如果这题做出来就没有遗憾啦”，诸如此类的想法。于是这约莫就是这一天的主旋律了。原先zc嫌时间太久想翘掉的，但见xn没翘也就没翘了。谢天谢地，如果他们两位翘掉了估计我就只能对着屏幕两行泪了跟着翘了。
虽说这是校赛，但我们对待得真挺随便。没碰代码一个月的我也就随便搞了点板子，没碰代码一个月的zc赛前一天开始调环境。赛前一个月基本完全没准备。赛前一天才开始和xn交流板子行不行。有些过于娱乐了？毕竟经验过少，但毫不慌张并调好心态或许比瞎准备一通发现自己方向错了来得有益，于我看来。
早上的热身赛真的挺热身，zc花了一大半时间在配环境：sublime、visual studio、code，一个个都试过去了，花了好长时间嘞。还下了大数的模板，也测试了一下。然而下午居然重启电脑了，题目也收回去了！我妹子还没认全呢555
里面有个C题很好玩。就是有十二张图片（ACG作品中的妹子人物），二十四个名字，把名字和图片对应，输出，没有输入。名字都是假名表示的，图片也都是同人画师的作品，搜图难度不小。估计是颜色的问题，不管什么百度搜图谷歌搜图效果都不能看。在p站上查画师效率也不是很高，于是只得慢慢搜名字（一个一个妹子认识过去）。有点烦的一点就是有些名字搜不到，不管在萌百上还是其他网站上，这就会让人比较泄气，怀疑是否漏了谁，从而对答案正确性与自己的努力产生怀疑。搜了一些名字，发现自己御宅指数还真是低，敏感性也比较差，看到”Tohsaka Rin“时脑海中完全没有图象。东方的人物我也认不全。这可能还跟接触的体系有关系吧，我是没啃过生肉的，知道的东西也都很表层，在欣赏ACG作品缺乏联系观，也缺乏对妹子萌点人物特征的宏观认识，对于作画等等的认识也实在是肤浅。想想自己只是个假的肥宅，有些假的难受。
A题的话，让你判断一个数列是不是peak sequence，简单模拟即可。但我忘掉了和peak sequence相关的知识欸。我好弱啊。
D题是顺序买书，已知书的总数、每本书的价格和买的本数，买书的策略是贪心，求最大携带的钱数。一开始想能否二分答案，但想想不行，具体哪里不行就讲不清了……之后想到贪心的思路：把前k本都买下来，剩下的钱再不足买剩下任何一本书，那么这个钱数是符合要求的，而且超过它就不符合要求了，可行！就是不知道这个思路该置于知识网络的哪个位置。我对于算法的认识，在微观层面，还是非常容易搞混且相当想当然的，这是一个得改的毛病。
B题是给出一个括号序列，给出了一套生成序列的规则，让你求第k个序列从第l项到第r项有个多少‘(’。这题当时没人提交（估计都在查C题吧），我初步想法是这样的：序列是无穷的，故要在一个周期内界定它，而后面的序列和前面的序列又可以通过set判重来得到”序列的周期“（二维的概念啊，有意思）。总之就是有点恶心的模拟了，加上模乱搞不知行不行得通……无法实践验证想法，就不细想了。
比赛本身
想做题的话，戳这里qwq。
比赛开始时还是有些紧张的，中午睡得也不咋样，总之不是特别有状态。开赛后首先看的是B题，而xn在看A题，zc在配环境。B题定义了一类“偶素数”，还有“偶合数”，让求给定的“偶阶乘”最多能拆分为多少个“偶素数”，本质上应该是$2^s || n!, s = \sum\limits_{i = 1}^ \infty \lfloor \dfrac{n}{2^i} \rfloor$的变形。但是数据量级是$10^{1000}$，不写大数不行。于是zc和xn讨论G的时候，我一直在打板子。这个板子是半年前的，记得当时减法没搞，就没管，不想除法里需用到减法，一下就慌起来了。还有大数比较等等也都没有写，心情就比较地烦躁。中间想到用java写，或者写二进制的大数，但都碰上了问题。临结束时瞎写了一通，不知哪儿出问题了。这题也便不了了之了。想来还是有些遗憾。
除去B题，我第二个看的是J题，当时已有队伍提交了。这题讲的是给定正数n，让找满足$x + n = y$的一组合数x，y，任意输出一组即可。我当时拍脑袋想想x=2n，y=3n不是满足条件嘛，但觉得这样过于简单了。和xn交流后也没发现问题，但交上去就是一个明亮的WA。为什么呢？是流输入的问题么？总之不会是数据范围的问题吧。搁了一会儿后，xn测试时候来了个“1”，输出“2 3”。很明显，错掉了。于是我只能尴尬地换成x=8n，y=9n，这才搞定。此时已经过去45分钟了。
不光J题开始没过去，E题一开始也卡在这了。背景就不讲了，总之水题一道，但水水的我们过也过不去，就比较烦。zc花了一些力气把dev调教对，然后测试了自己构造的数据没发现什么问题。此前有交流，此后有深思，卡了好一会儿呢。最后又是xndl敏锐地察觉到虽然输入是在$10^9$，即int范围内的，然而我们有用求和，之后规模可能会超，得换long long。果不其然，改了数据类型后顺利拿到了一血。
后面我看的题是I，涉及到逆元、平均数、方差、选子集，极端数据还达到了恐怖如$2^{40}$的规模。想来不推结论肯定TLE的，但有何结论呢？从没做过跟方差有关的题，对于子集也不知如何高效处理，只能是对着题干空着急，发呆。简单化简了一下方差，搞出来一个线代课上好像曾见过的矩阵，忽然又想道”正定二次型“这个名词，可又死活不知道接下去怎么办了。这题也就弃了。
其他题我基本没看了，状态很糟。zc主要是搞C，xn主要在搞A。C和A我都没看，听他们说前者是简单模拟，后者用搜索或许可以。然而都TLE掉了。于是zc又给C剪枝，剪一会，交一遍，TLE，然后略有所思又想出来一个剪枝，我打一会儿大数就得起来一下给大佬让座，很是有趣~xn的A也优化了一遍又一遍，最后想试试卡时，在语法上又折腾了老半天，可最后还是没弄出WA。我差不多在两个小时后就没有认真打的念头了。看看人家碗里的气球，互膜互黑，倒也不错。
于是只能凄凉地拎着三个气球回来了，其中一个被吹走了，一个气放掉了，还有个踩爆了。看着人家手中气球满得都溢出了，不由得感叹自己菜得就像被人家踩爆的气球，何其可怜，多么无助。
早上刷名单的时候发现wyh也参赛了，寻思人家肯定是solo的。最后在榜上果然赫赫有名，着实是厉害。膜了人家一波，好不愉快。
现场赛与网络赛
比赛的形式在很大程度上对发挥会有影响。一直都不喜欢去机房，因为那边的环境，因为那里的键盘。对于这些我都很不习惯。讨厌配环境，讨厌看见稀奇古怪的错误，讨厌程序正确却跑不起来的无力感。在这类问题上，我一直不愿意走出自己的舒适区。
此外，现场赛有很多额外的限制，比如不能查东西。查询一般只在对事物有一定认识时才会奏效。查算法一般都是无效的举动。查语法更频繁些，因为这些东西我记不住，而且我觉得它没啥思维深度。查到原题查到相关算法还是少数，是值得高兴的事情，比如之前的趣味C，比如寒假的网络赛中那个让我告别0AC的组合数取模的板子。
回来今天来。中间，大数的板子搞不出来，zc想用java试一试，但是在语法上就碰到问题了。连大数初始化都搞不起来，更不用谈运算了。事后这些东西一查便知，但当时就是搞不起来。最后xn想卡时，但#include
开卷虽然看上去比闭卷更为轻松，但若是对知识体系没有明确的认识，往往只能又慌又无助地乱翻书，效率非常低下。故，在这样的限制下我们当怎么做呢？首先还是要搞清楚自己受了什么样的限制，提前做好准备，有所对策，才不至于在事后后悔。虽然在本次比赛我们也没有可以后悔的理由。
机房的键盘，真心是叫人难受，敲起来又慢，还没有快感。不过即便是如此，我也还是有需要反省的地方。打字容易出错，快捷键用得还不顺（尤其ctrl不会用），等等。这些相对思维是外部的事物，但做好了能起增益效果。一来是需要有提升的意识，意识到自己和键盘和自然语言间的羁绊还不够深；二来是要有科学的方法，归纳出哪些快捷键是能够提升效率的，归纳出自己在打什么词的时候特别容易出错，在此基础上有所提升。
最后是环境，这个东西真心无聊，我尤其讨厌。但这是很常见的问题，尽管我并不“喜欢”它，我仍然“需要”解决问题的能力。环境不光是指机器上编译、链接、运行等步骤，还关乎对于软件的熟悉程度。视图、快捷键，等等。一个视图没调出来，尤其对状态有一定影响，因为它将原本连贯的思路与预期切断了。不喜欢用dev，VC++，看着那些复杂的条条框框看得很难受，这些软件有做到以人为本么？作为普通用户（然而，它们本就不是为普通用户设计的），我觉得开发者，是有所不足的。（但是，今天仍有许多学校和教师鼓励使用这些老旧的产品，他们是否需要反思呢？）可既然大环境如此，我也便只能熟悉其架构而无法奢谈转变。如何熟悉呢？或许我需要在机房找找答案。
合作与对抗
程序设计的竞赛大抵有两类，一类时段较长，如各类开发比赛，动辄几个月的。另一类时段很短，ICPC是一个，还有像黑客马拉松呀，Game Jam啊，它们关注的是爆发力，竞技性更强些。zc说前者更能体现与赛者的能力，不过后者往往更加紧张刺激一些，打得有趣，看榜也有趣，看别人满桌子气球的样子更有趣。
而且往往来说呢，第一类比赛的“合作性”会更强些，而后一类的“对抗性”则占了上风。作为一名蒟蒻，我一向是喜欢“通力合作”的，高中时候每回数竞的模拟考都会参与大家的讨论。记得打NOIP前报了个不知什么网络赛，然后就和蒋哥一起合作了。题目今天不记得了，当时感觉和自己的能力还是在一个数量级内的，做得比较有成就感。和蒋哥分享看法，给他看自己的代码然后收到肯定的信号，一起感叹最后一个有多毒瘤。真的很好玩，很有意思，很开心。今天想来，还是宝贵的记忆呢。
NOIP倒是合作不了了，也就考完后简单谈了谈感受，谈了谈这个输出格式之恶心，谈了谈试卷对于ds之偏爱，其实其他“有意思”的考试考完也是这样的。坐着大巴，背着待会语文考试的答案，拖着辘辘饥肠，等待着原应是KFC结果是“江西小炒”的晚饭，回到期中考的轨道中。没有若有所失的感觉，只是在平静中，一个阶段已经结束了。
ICPC倒是在对抗中也体现着合作的。有幸我们还能够交流，能够发现一些隐蔽的问题，也能得到更广的视野，在一定程度上。但是，交流也并不是件简单的事情，它甚至并不“自然”。不过，这些已经是下个标题的主题了。
沉默与交流
debug，往往来说，都是件孤独的事情，甚至可以说是反人性的。但是开题并不是孤独的，它代表着希望，虽然希望时常会转化为绝望。为了让希望成为希望，我们需要更全面更深入而非想当然的思考，在一定程度上，交流能做到这点。可交流本身也并不容易。先回顾一下当时吧。
我们开始的策略还是得当的，不同的人开不同的题，但之后的步骤，我认为我做得并不好。我有B题的思路，但我完全无法将其表述给队友，为什么？在向xn介绍J题的思路时，我用的语气是较为肯定的，绝对的，“2n肯定是合数”，这样的交流有效吗？后来xn开了A题，zc开了C题，我只“大致地”听了听他们的思路，而未对细节有深入的思考。非常失败。
交流的一方面是传递自己的想法，在这个过程中要尽量避免隐蔽的想当然的想法；另一方面，交流是关于聆听的，而非“听见”：对方的思路是如何展开的？他有什么可能的错误？他没提到什么？
在交流时，不应是你一句我一句并且交谈没有中心。二或三人交谈时，一方当作为领导者，把握着对话的小主题、中心问题。其他人需要发散思维的广度。提出尽可能多的解决方案，并对其做出一定深度的拓展。然后是围绕可行的方案收敛思维。如是反复。
对这个话题想的还不多，也没什么条理，先放着吧。
补题时间
弱鸡的我的代码在这里QAQ，仅供参考。
A
比赛时一直被数学题搞得状态不佳，A和C都没看。结果A是2019.04.21AC的，而C是2019.04.20AC的，放了好几天嘞。
A的大意就是给定一组男人一组女人，每个人都有身高和偏好，其中身高各不相同，偏好为0表示只和比ta矮的人匹配，偏好为1表示只和比ta高的人匹配。问什么样的匹配方案能使总配对数最高。
看上去有点像什么二分图匹配，也好像可以搜索解决，于是我就不大想做……认真看了看，感觉贪心可以搞，那就试试贪心吧！
先把所有人按身高排序，然后顺序检索。每时每刻检索到人都是“可匹配的人”中最矮的，如果ta的偏好是0，就可以把ta跳过了；如果ta偏好是1，看看后面第一个和ta匹配的人，配对之。（容易证明，这样的贪心保证了全局最优性，证明的话，考虑如果不是贪心的策略，就替换吧）这里用last[0]与last[1]分别维护上次贪心得到的男/女性的位置，即可保证检索与匹配的复杂度是O(n)，加上排序，O(nlogn)，可行。
但是自己写的时候有点想当然，last只开了一个。题目里的数据又特别小，没出问题，于是百WA不得其解，之后将自己的思路表述出来才发现这一问题，从中可见有效交流的重要性。
B
在4月的16号早上，我开始调整自己的大数模板。先是写了个python的数据生成器，并加了些自己构造的数据，然后是用python调出用以对拍的程序，再是重构（debug_fc.bat，整合了debug_BigNum_py.py等），使这个板子的结构更加清晰。之后加减乘除均通过了测试。在此之后，开始上B的代码，碰到段错误，之后是TLE。
看了看别人用python写的程序，可谓如梦初醒！我的思路是{ans += n / two;two *= 2;}，但是{n /= 2;ans += n;}完全能实现等价的操作。在数学上，二者是等价的；可是两者在计算上的复杂度并不等价！尤其我的大数除大数中用减法模拟取模或许会占掉很长的时间，而我局限在前一种想法中，没有拓宽思路，这十足是个教训了！另外，我没有在纸上继续推结论，而只是在脑袋里想想，这或许也是个不好但也难改的习惯吧。
C
题意的话，是给定机器人的行为模式还有房间的结构，求机器人运行k步后捡了多少垃圾。具体不表。
初看似乎是模拟题，但是k可以高达10e18次，所以复杂度要么是min(f(n, m), k)，要么是O(k^1/3)这类。后者貌似在组和题里更有可能出现，我们就考虑前者吧，由剪枝降低复杂度。但是这个枝怎么减呢？
题目中的x由中间及其周边五点的值唯一确定，故这五点值若不改变而机器人停留在原位（即机器人什么都没做），它必将循环地无所作为。直接模拟k = 10e18的话，很大一部分时间都是耗在这上面的，所以这种枝一定得剪。
但光剪徘徊在原地的枝还不够。原地徘徊是一种自环，其他的路径也可能成环（比如，(2, 2) -> (2, 3) -> (2, 2)），要把这些也剪掉。怎么判断走的确实是环（即后面的路径与前面的循环）呢？只要看再走到同一点时ans有无改变即可：若无，则机器人从该点返回该点的路径中没有捡垃圾，也就是它接下来走的路将与此前完全相同。这样，剪枝就分析好了：
1 | memset(vis, -1, sizeof(vis)); |
（但是这么漂亮的东西并不是自己想的而是抄来的QAQ）我一开始是用set判a, b, cmd的三元组，发现不对，之后换成map加上经过一点的次数。zc的方法是在捡垃圾里面加上{vis[a] [b] = vis[a-1] [b] = … = 0;}，都WA了。看到一排的WA心情就会发生微妙的改变，要么是变佛，要么是不搞出来不睡觉这样。我是挺佛的，看看人家的剪枝这么优雅就把自己的给丢了，谁知道哪个神仙地方出了bug，这题也不好拿数据对拍。今天想想，光看“该点”的状态还是不够的，因为在路径中间捡完垃圾回到原点，后面仍可能走新的路径，故而要用更“全局”的东西来记录状态，我们应当是错在这点上。
这题的复杂度我还不会分析。若n、m取最大值，机器人至多在多少步后退出？我还没有想明白。
下面是D题，题干就不念了，没有输入，要求给出足够好的机器人捡垃圾策略。AC条件为在给定步数内，给定多组随机数据，平均捡垃圾率足够高。
随便分析了一下，看三进制下算出来的x的值。首位不会为1，所以1打头的都可以填I（同理01111这些也是不可能的）；首位为2的时候yy一下，都填P。然后首位为0时开始转移，依据旁边的点的结构，旁边的点会呈现出什么样的结构呢？
然后我就不知道了，就咕咕咕啦。
G
题目本身比较简单，关键点在于将正负分开来考虑，然后每次贪心即可，详情参考代码。
问题是为什么会想到将正负分开来考虑呢？
I
题意：给定n个点及其权w，给定m组约束关系（即有m对点不能同时选取），令x为$\prod w_i, i \in S$，S为n个点中任选若干点的满足约束关系的子集。问所有x的方差对1e9+7取模的结果。
题目中n最高达40。这个数量级下直接模拟（2^40）稳超时的。如何压缩时间呢？我一开始是觉得这里头会有什么微妙的数学结论的，就随便推了推，也就把方差展开了一下，结果并没有什么用。
康了康网友的题解意外地发现并查集可以用来解决选子集的问题！考虑这样的数据，n=3，m=0。这时候共有8种选取方式。而8=2^3，我们可以用这样的代码来计算所有x的和及所有的选取方案：
1 | for(int i = 1;i <= n;i++) |
这样的思路像不像生成函数？$\sum x = \prod(1 + w[i])$。”正常“的dfs是把右式中每一项列出来计算，而这里我们是注意到了这个式子本身，从而将右边的式子逐项计算，大大减少了计算复杂度！从O(2^n)到O(n)，这是怎样的突破呀！
上面的例子是m=0的，如果有约束条件呢？我们就用并查集，看看哪些项可能存在关联，把他们放到一个集子里（这样，集子与集子之间就是相互独立的，可以像前面一样运用乘法法则啦！），前面的方法也要改写成这样：
1 | for(LL i = 1;i <= n;i++) |
tree[i]储存”可能存在关联“的元素，tree[i].size() == 0就表示这个元素被并到其他集子里去所以不需要检索了。dfs是暴力搜索在一个集子里的x的总和和可能的子集数，记作temp_x与temp_num。说到这里，核心的元素应该都阐释清楚了，具体部分可以看代码。最后的ans的计算公式是将方差化简所得到的，此处不表。dfs选子集是通过位运算进行的，此处也不表。模运算中的技巧如求逆元等同样不表。
这样的代码能应付这题了，下面我们来看看复杂度吧：上面我们对复杂度的认识还只是较为粗浅的，只考虑了一种情况。但并查集真的能在任意情况下对算法起到优化作用吗？考虑下面这组数据：n=4，m=3，约束关系为(1, 2)，(1, 3)，(1, 4)。把它推广下去，则算法的复杂度还是O(2^n)！
聪明的读者想必注意到了：在并查集内部，其他数都还是没有关联的，能否将之分配到新的集子中呢？若行，则这样的迭代要如何进行呢？对此我尚未想明白，读者诸君若有想法，欢迎联系，共同探讨。
总结一下经验教训吧：
①没有想到在模的意义下处理ave、ans（我真傻，真的，我单知道有理数运算可行；我不知道在模的意义下更方便处理），从而无处着手。
②没有想到存储sum_x2，sum_x来直接得到ans的值，但这应该是小问题，反映的更多是我的经验不足。
③MOD的处理，对每一个运算都要想是否需要取模，是否为负，特别是读入的时候。
④1和1ll不是同一个东西！这谁debug出来呀！
J
观察了一下其他队伍的情况，相当多的队都是直接AC或是WA一发后在2-5分钟后就能调AC的，少量队伍调了30分钟乃至3小时。相比之下我们的20分钟（中间还放了一放）还是相对顺利的。但是对于边界数据，我的觉察程度还不够敏锐。
其他题还没补，先放放好了。
初写于2019.04.14
完稿于2019.04.25