安徽游记 III

发表于 2019-10-01 更新于 2019-12-08 阅读次数：

12 天的培（kao）训（shi），坚持每日总结。

Day9 to Day12.

Day9

考试

炸了，今天出的题好诡异。

第一题一道博弈论，题意好迷，没太看懂就去做后面的题了，
到后面离考试只有 5min 了再回来看 T1, 暴力都好难打，
于是信仰一波 std::cout << 0 << std::endl ，水到了 12' 。

第二题是给出将数组 a 变换到 b 的方式，要求用 b 求 a ，
式子里面有按位或、异或、bicount 什么的，莫非是 FWT ?
于是推式子，如果真的是 FWT 的话求出 a 到 b 的变换应该可以推出 b 到 a 的逆变换。
于是乎我花了一个小时搞来搞去，重新推了一遍 FWT （这个式子真的 6 没办法套用常用的位运算卷积），
果然可以从 a 用分治 3 个 for $ O(n log(n)) $ 变换到 b 。
但是和普通的 FWT 最不一样的就是这玩意不能“蝴蝶变换”，仅从 x, y 两个数推不到新的 x, y 。
woc 那我怎么解方程求逆变换？当时有点绝望了开始怀疑 FWT 做不了，
又去看了看 T3 ，不可做啊似乎，于是决定爆肝 T2 。
我就手玩小数据，推推式子再找找规律，搞了大概 1h 发现把 b 做一遍异或逆变换再乘二再把 b[0] 减去原来的 b[0] 好像就是 a ！
我还证明了它在 n 小于 8 的正确性，然后手玩了 n = 8 时的情况，错了。。。
再次绝望，想了好久大概又过了 30min 吧突然发现之前手玩算错了，我靠重新手玩，完全符合规律。
~~好嗨哟，感觉人生达到了高潮~~
快速敲完 KET （ kewth 变换可还行）交了上去，结果最后爆 long long 了，爆 long long 了， long long 了，了。。。
100' -> 60'

第三题交互题，实在没思路就想着能不能卡掉他的交互器来玄学 AC ，
（以下玄学操作，请勿模仿）为此我研究了大约 40min 的 syzoj 交互原理。
考场上的提交得不到反馈，我就去同样用 syzoj 的 LOJ 上试着提交一下尝试尝试。
然后第一波提交， CE 。。。
改了一下再次提交， wating, wating, wating....
woc 无限 wating? 感觉不对经，看了看 LOJ 的评测记录，然后。。。
woc 自我 CE 代码后的所有评测全是 wating 不动，当时就懵逼了 loj 被我卡爆了？
事实证明只是 loj 卡了一下，过个 3min 的样子就恢复了。。。
我还读了下下发的交互器，于是我搞懂了这玩意的交互原理，
但是实际的交互程序是另一个程序，下发的交互器只是和你的代码一起编译后和交互程序交互，
看了看交互器最后 AC 的输出，然后在 solve 函数里打了份一样的就 exit(0) ，交了。
结果。。。没过，实际评测的交互器和下发的交互器完全不同。。。（但是确实可以卡，后面会说）

讲题

今天的讲题真欢乐，一位大佬屡次上台嘲讽出题人。

T1 就是 dp 啊，加个启发式合并状态，如果不把时间浪费在 T3 说不定能想出来的。

T2 不想说了，心累，在变换过程中做除法就不会爆 long long ， AC 。

T3 随机分治？感觉挺 6 但是没懂。
但是我还是通过奇技淫巧 AC 了。。。

爆掉这辣鸡交互

我还真不信这交互器天衣无缝，再次看交互器，
交了几个错误的程序，发现我能得到的信息只有交互程序给出的信息，
再蠢也不会把重要信息放提示信息里头嘛，感觉似乎没办法了。
又交了一次， CE 了。。。
这时转机出现了，我看了眼编译信息， woc nice 大夫 g++ 给的编译信息真详细：

/sandbox/1/a.cpp:5:6: error: 'QCNT' was not declared in this scope
out,QCNT,'\n';
  ^
/sandbox/1/a.cpp:5:6: note: suggested alternative:
In file included from /sandbox/1/a.cpp:2:0:
/sandbox/1/c.h:74:5: note:   'lkjjhkfdlhgkjdfgf5454::QCNT'
int QCNT;

note 那一排暴露啦，这命名空间 lkjjhkfdlhgkjdfgf5454 也是没谁了（另外还发现了源码的位置 /sandbox/ ）。
但是出题人以为套一个乱七八糟的 namespace 就没事了？
然而还是被我发现了哈，于是通过这个 namespace 直接获取了交互器里存的答案，
成功 AC ，辣鸡交互器。

看了看提交记录，我是第二个玄学 AC 的，第一个的 AC 代码提交时还没有那 sb namespace ，
所以说，我是第一个发现这鬼畜 namespace 并通过它 AC 的 :)
然后从我 AC 后就陆续有人玄学 AC, 代码我都看了一遍，大同小异，全是用这 sb namespace 过的（变量名、注释都跟我的长一个样），
开创先河哈。

后面再改改就是 65B 全场最短 AC 代码。

后来又看了看，还有一名大佬用另一种方式爆掉了这辣鸡交互器。
比我 6 多了，竟然直接搞到了交互器判 AC 的方式给写 solve 函数上了， %%% 。

声明：
交互器确实是可以做到无法被爆破的，
我今天成功爆掉交互主要原因是交互的封装方式漏洞百出，
把交互的主要部分直接给 include 进来了，
正确的方式是将交互的关键部分写在真正处理交互的通过输入输出交互的程序里面。
去看看 loj 的交互题，把附加文件下下来，
那附加文件就是封装了一下和交互器的交互方式，你不用都没关系。

Day10

考试

第一题乍一看要动态维护逆序对？感觉不太可做，后面直接交了暴力， 30 分。

第二题字符串，感觉像是贪心，但是有一些情况不好判断，
最后打了字符串做状态的暴力 DP ，我估摸着复杂度是 $ O(n^3) $ ，
于是就只开了 30' 的部分分的数据的大小的数组 n = 100 ，交了，果然是 30' ，
然而我把数组开到 2000 （ 60' 的范围）后就过了 60' ，这。。。
60' -> 30' ~~论复杂度分析的重要性。~~

第三题式子题，乍一看似乎可做，然后简化简化简化，简化成了这样一个题意：

在正整数范围内解方程 x * phi(x) = 2m ，m 已知。

我一看这么简洁的式子，枚举一下 2m 的因子应该差不多了，
一看数据范围： $ m ^{18} $ ，第一档暴力 10' 范围： $ m ^9 $ 。。。
还多组数据，一共 100000 组。。。
连暴力都过不去啊我去。
最后实在没思路，就预处理了一部分 phi 再暴力去搞，结果爆零。。。

讲题

第一题其实真的容易，根本不要动态维护逆序对，
题目要求的只是使逆序对最小的一个循环的位置，
考虑一个数从最左边被扔到最右边后对逆序对数量的影响，其实是不会变的，
维护这个影响的数列，那么就是要求一个最小前缀和的位置，
每次修改就是交换两段区间，虽然逆序对数量会改变，但是根本不用管，相对的影响还是不变的，
那这玩意一个平衡树搞上去就好了。

第二题我似乎摸到正解的前一半了，
贪心把能直接求的字母搞出来后对于剩下的求一个字典序最大后缀好像是，
~~那这玩意一个后缀数组搞上去就好了。~~
然而似乎还是要考虑一些情况，还没改出来。

第三题数论神仙题（我竟然以为 T3 可做），
正解复杂度 $ O(log(m)) $ ，神仙做法，
什么二次剩余什么欧拉定理什么质因数玄学分解都用上了，
好难，出题人讲了两遍都没听懂。

Day11

倒计时两天。

考试

第一题平面图上随机游走求到 n 的期望路径？
30' 高斯消元暴力分比较容易想到，其他的就没思路了，想着先去打后面的题。
最后回来打 T1 的时候连高斯消元都没打出来（我太菜了）。。~~其实是改昨天的题去了~~

第二题博弈题？乍一看似乎可做，然后简化简化简化，简化成了这样一个题意：

给定数列 a, b, c, 选 a 中的 x 个数替换成任意数使得 $ i: a_{i-1} + b_{i-1} a_i a_{i-1} + c_{i-1} $ 求最小的 x 。

然后这玩意 $ O(n^2) $ DP 嘛 $ O(n) $ 状态 $ O(n) $ 转移，
我以为可以得 10' + 20' + 30' 三个子任务的分，
结果 subtask2 的数据范围比 subtask3 大，但是是一个特殊情况，判掉就好了，我没打。。。
60' -> 40'

第三题没思路，暴力枚举行枚举列枚举每个位置 24k 纯暴力，拿到了 40' 的好成绩。

讲题

第一题解方程线性代数 blabla, 但是看了看 Rank1 的代码，
发现就是一个矩阵乘法，卧槽 $ O(n^3) $ 过 3000 ？
经 *** 分析，平面图上的边数是 $ O(n) $ （最大是 3n - 6 ），
所以高斯消元里的矩阵的点数是 $ O(n）$ 的，
然后就可以根据之前 pics 讲过的方法 $ O(n) $ 做矩阵乘法（ n * n 的矩阵与列向量相乘），
做 n 遍，复杂度 $ O(n^2) $ 。

第二题似乎是最难的，我挂到 40' 都能是全场 rank1 。。。
难点主要在简化题意上，简化后出题人说这就是个普及题了（ woc 我是不是不适合学信息），
DP 可以优化，设一些坐标搞到平面上后将转移用线段树维护优化到 $ O(log(n)) $ ，
但是把所有点对应到平面后，还有种更简单的做法就是求出最长下降子序列 x, 答案就是 n - x 。
这个结论的证明折腾了一下午，还是很妙的。

第三题暴力优化 dfs 可以水 90 分？
正解先枚举行再筛选列将单调性用桶存起来再转移大概是，正在改。

爆肝 Splay

这三天都在爆肝 Splay, 突然又对 Splay 的翻转操作有了更深的理解，
也发现 Splay 真不是那么万能的，许多操作用 Splay 做会多一些不必要的麻烦，
尤其是维护不对称信息还要带区间翻转的时候，似乎根本做不了？
硬要做的话就必须强制让维护的信息对称，
比如要是维护最大前缀和，要支持区间翻转就得还同时维护个最大后缀和。
不说了，去他的信仰，正在学无旋 Treap 。

Day12

最后一天。

考试

第一题已看完题 woc 这不就解方程嘛，手动消消元什么的就行了，
出题人这么良心？于是就开始打，打完后测了测样例， woc 过了。
再把大样例下下来一看， woc 出题人这么良心每道题 5 组大样例？
全都测了一遍，全过了，交了，这个时候考试开始 59min 12s 。。。
但是还是很荒，担心会写炸，然后就对着代码检查检查改了几个细节，
改着改着又测了测时间， woc 要跑 0.9s+ ，这不会被卡常吧？
又慌了起来，但是出题人说不会卡常，还下发了 io 模板，
套上 io 模板后再测 0.2s+ ，松了口气，最后交了一次，
这时候考试开始 101min 15s 。。。
考完后看了下，其实我第一次交就 AC 了，白折腾这么久。。。

第二题神奇题，打了个暴力，期望 60' ，
感觉可以把状态放平面上通过单调性什么之类的优化，
但是没有具体的优化方案（我的计算几何真的是一片空白），
结果最后暴力挂了？只有 10' 啊后面 50' 全 WA 了我一脸懵逼。
还在找错。

第三题哇神仙题，一看就不可做的那种，打完暴力后挣扎了一下，
得到了 30' 的好成绩。

讲题

今天又被爆踩了，T1 A 了一片，拉不开差距。

第二题果然是计算几何神仙题，什么凸包二分三分，什么半平面交，什么李超线段树。
完全不会，只能等我计算几何基础打好后再来重做这题了。

第三题出题人说打表找规律题？反正我是没看出什么规律，
然后出题人证明了一些结论，有这些结论就能 50 行内解决这题了，
正在试图独立证明这些结论。。。

爆肝 Treap

写完暴力自闭之后就滚去学无旋 Treap 了，看懂后感觉这 split + merge 的操作很 6 。
然后自己写了写，过程中学到一个新操作： 空指针调用成员函数
woc 发现直接用空指针调函数就只要在函数里判一判，调用端省了无数个 if ，

方便死了，然后上午打完下午交了文艺平衡树，
woc 全部 RE ???
把数据下下来，本地跑了一下， AC 。。。
woc 玄学本地 AC 提交 RE ？
改了细节再交，还是全 RE ，
那到洛谷 IDE 上测一下？一测， AC 。。。
woc 玄学洛谷 IDE AC 提交 RE ？

然后各种测试

最后肝到晚上，终于认识到空指针调成员函数是多么不安全的行为。。。

emm 最后发现 Treap 无论是速度还是码量上都没好到哪去（难道是我实现太烂？），
对于文艺平衡树来说，无旋 Treap 略慢，代码还略长，只是空间消耗略少。

THE END

安徽芜湖 12 天，每天都很充实，虽然也有遗憾。

HNOI 2019, RP ++.