清华集训2015 游记

day -1

火车上打了一上午的植物大战僵尸(pvz)。。学会了不用车子玩坚果保龄球2的方法。。简单来说就是不去捡钱。。

中午做大死点开了CC月赛。。开始想WAYPA不是傻逼树分治么。。后来发现是我脑子进水了

晚上找了cyb、彭老师等学长聚一聚。。

早早地睡了。

day 0

跟毛爷爷一间房。。毛爷爷就是爷。

试机这种事情没有写的必要了。。哼着chocological的前半段，蹦蹦跳跳回了宾馆。这是个伏笔

mx:"你有什么隔膜吗"

rhl:"pvz啊"

mx:"那就玩啊"

然后膜到了一种全新的打法。。开局全屏向日葵，阳光5k+然后种高贵的攻击植物!%%%

玩了半晚上pvz。。myy还跟我传授了pvz的经验。。比如说“机枪射手打100个普通僵尸就是打一个伽刚特尔，忧郁菇打100个普通僵尸就是打一个普通僵尸”。。%%%

还有运气好得到了成就。。不用车子推掉空袭。。你有在气球僵尸来之前种7个阳光菇的RP，为什么不用在考试上呢以及只用玉米加农炮打僵尸快跑。。

然后开始敲板子。。敲了两个小时带花树得出结论。。如果明天考带花树我就写随机！

真是爽啊。

day 1

进了考场其实还是很紧张的。。

第一眼感觉。。T1是LCT。。很像长跑那个题。。要在线的话应该是强行LCT了。现在看来我真是捉急啊

T2。。40分很显然。。100分矩乘?或者收敛的话直接搞?

T3。。我猜他卡kdtree!但是老子就写kdtree了!

然后赶紧把T2暴力和T3的kdtree搞了。。测了T3圆的数据好像跑的还可以?更虚了

然后推了推T2。。没有什么卵用

T1的话直接看成有向图，大概是缩一下强连通分量。。就变成了一个DAG。。不对呀应该是一棵树。。大概是缩点之后维护分量内的环长gcd，每次询问链上gcd和链上权值。。

写了一发树的。。然而LCT好像并不能维护这种来了$+w$去了$-w$的权值。。就弃疗了。

掂量了一下。。好像我只会$k,t$都不等于$3$的。。什么只有30分?不高兴玩T2去。

把$n$改成了$\min(n,10^7)$。。没戏了不会做T2。。

准备动T1的10分（离线的树）。。然而已经11:00了。。把树构出来每次求LCA得到两点距离。。然后链上gcd怎么办?

然而我看提交记录。。一堆人过掉了T1的大样例。。大样例有那么容易么。。

。。。

突然觉得不对。。不一定是链上的环才能走。。只要是一个连通块中的就可以走了。。我tm十一点才想到这个。。那么双连通性也就没什么卵用了。。只要记录一个连通块的环长gcd就可以了。。

真是脑子进水。。被长跑那题带得太深。。

然后求LCA的时候写出了这种代码：

p=LCA(a,b);

len=dep[a]-dep[p]+dep[p]-dep[b];

艹。。距离居然与LCA无关。。然后想了想的确是这样。。走到根再走回来。。跟xor是类似的。。。

爽啊。。

写了个暴力。。拍了一发。。死了几回。。12:00的时候才搞完。

总结一下T1的性质。。连通块LCA。。只有加边。。只要维护深度(根到点的距离)。。

妈的！好像会仙人掌上的在线算法。。大概就是，对每个点维护它到连通块内某个点(根)的距离，每次加入一条边，如果是树边用启发式合并更新小块的距离；否则找出它对应的环算出路径长度，更新连通块gcd。。如果是仙人掌的话显然是对的。。如果是普通图那么可以当骗分。。

超好写。。

还有30分钟，感觉自己萌萌哒

然后整个人开始一通乱搞。。各种乱拍。。不会造仙人掌干脆造普通图。。边权-10~10纯随机。。

拍死了几次。。好像没有非仙人掌图带来的困难。。然后就拍不死了。。难道是正解?

爽。。

查了longlong和极限数据。。结束前两分钟交了。。

真tm刺激。

下午讲题的时候。。T2正解也是醉了。。语言杀?T3存在可想可写的$O(\log^2 n+k)$做法，%%%

顺便黑一发myy(天哪不会掉RP吧

“你来随机指定一个满分选手”

“mx”

%%%

晚上浪。。

day 2

好像之前立了一堆奇奇怪怪的flag。。然后今天果真爆炸啦!

“T2应该是傻逼题吧”

写写写 写完了 调调调 下考了

爆零

群里发的前26名成绩里，没有看见jiry_2，没有看见Newnode。

没有想过，那么神的人都会被运气捉弄。。真是悲伤。

这种辣鸡考试（雾

记得昨天晚上毛爷爷跟我说，他最喜欢的题是暴力$O(n!)$，正解$O(n)$，出到$n=100$，想得到$O(n^4)$就想得到正解。他说TC上有不少的这样的题，可惜我很少刷TC。他说最近的OI比赛，这种题真是太少了。

再回过头来看今天的大爆炸。。

T1：“你会仙人掌吗？不会滚蛋！会的码码码 没有码出来滚蛋！”(upd:正解果然是压位 还有卡空间

T2：“你会物理吗？不会滚蛋！会的码码码 没有码出来滚蛋！”

T3：“你会打牌吗？不会滚蛋！会的码码码 没有码出来滚蛋！”

。。。

毕竟毛爷爷说的“好题”不是那么容易出出来的。

不过还能说什么呢。。毕竟还是自己发挥的问题啊。。光怪出题人并没有什么用。。

不知道明天的题又是什么画风。。我猜是             算了不立flag了

CHCINEMA意料之中地fst了。。论过样例就交的危害

唔，还有一件重要的事——

老子不玩pvz了。。垃圾游戏。。毁我青春。。

完全凭运气的老虎机

完全凭手速的砸僵尸

闭着眼睛都可以过的宝石迷阵

垃圾游戏。。。老子不玩了。。浪掉的时间还不如看看总结打打cc激霸题。。

(upd:后来还是在浪在打pvz。。cc激霸题弃疗了

day 3

据说今天有mato的提答。。一想到“诡异的文本处理”我就想哭。。

那是我第一次在有提交答案题的比赛中死磕传统题啊。

如果有mato的提答老子绝对不做！

点开题看到了mato的提答。。看了看觉得就是IOI的odometer吗。。前几个subtask还是可以拿分的。。比odometer还是水一些。。

看了看T1。。高斯消元。。不对好像几乎没有环。。应该是可以直接dp的。。不过并没有看到$h\le 10^5$。。

T2是不明觉厉的概率题。。nmb

决定先把mato题的可做部分做了。。

1和2是送肉。。3也是送肉

4还好。。5写不出。。妈蛋

想了想可以用伪代码!先把任务用C++一样的代码写出来，最好只包含题目中给的指令，然后翻译成题目中给的指令。

因为5和6的需要可以写成

if (v_1 & 1)
 if (v_2 & 1)
   ans=ans<<1|x_11;
 else
   ans=ans<<1|x_10;
else
 if (v_2 & 1)
   ans=ans<<1|x_01;
 else
   ans=ans<<1|x_00;

比如说第5个点就是x_11=1，其他都等于0。第6个点x_01=x_10=1，其他等于0。

第7个点。。要处理进位。。日哦。。

乱改了一下。。第6个点的x_11改成了2。。

好像是对的哦。

70分。。太棒了。。

然后稀里糊涂玩了第8个点，套到第9个点上去发现过了。。

。。果真是odometer弱化版么。。我只会做odometer前3个subtask。。

第10个点。。好像我不会比较两个数。。准确地说是不会break。。我是智商小于160的弱智（雾）

好像是一血。。希望有90。。应该是人生中第一个一血（雾） 也许是oi生涯最后一个

已经10:30了觉得不做T1对不起出题人的良心（雾）就开始写T1。。

过不了样例

写了个高斯消元 轻松过样例，交上去没问题。。就开始造小数据拍，拍错了调。。

感觉还好呀。

还是虚啊，交了一个极限数据到uoj上测。。他告诉我文件不能超过10M。。

日

大概12:00的时候写完T1。。看了看T2觉得阶乘算法有50分。。胡乱推了个式子码码码 过不了样例 只有可能是式子推错了。

看到数据范围$n\le 3$骗自己那个点应该是$n=2$。。

最后两分钟重新推了式子。。觉得并没有什么卵用 就弃疗了。

看着T2的差评慢慢超过T3 心里稍微受到了点安慰。

又是一上午逗逼的日常

看到T2有分的好像都考的比我好?

瞬间产生了对T2的仇恨。。这是OI比赛不是微积分期末考试。。

算了算了考挂自己弱。。

猛然间看到一个叫“楚悌仁”的账号以为是某人的真名=_=||

回宾馆用inhibition洗刷自己的大脑 觉得听这样的歌还挺有滋味的 听说一首歌就是一个跌宕起伏的故事呢。7分钟的长歌（也许不长）。。

day 4

觉得今天一定是三道传统题！

一点开

v

flea

king

什么鬼。。T1好像是物理题。。还出现了picks博士这种不科学的东西。。日

然后点开T3。。交互?!

点开T2。。交互?!

什么画风啊。。

物理题肯定不去动啦!吸取了day2的教训。。

让我先看一看。。求电流的。好像没有串并联。。咦不是直接输出水柱高度么

然后想了一想发现题面好像很好懂。。

交了个暴力不管。

T2是什么鬼?要求确定一堆抛物线的下轮廓的最顶端。。妈呀好奇怪的画风。。

T3那个式子一开始没有看懂。。然后发现就是给出两个变量的值你可以指定第三个变量的值?不错哦。。

好像还有奇怪的抱枕加成。。想起我在uoj上中了两回结果抱枕被发错了两次。。就没了想法。。

T2的话首先询问$1$和$m$。。然后询问哪个点呢?那就询问两条抛物线的交点$i$吧。。如果$i$的抛物线是这两抛物线中的一个，那么$i$好像就是最高点了?好像可以做到$n$次询问。。不错

写了一发好像过不了样例。。算了交个暴力走人，去看抱枕第三题。

我会$A+1$。。进位直接推。。不对$T$太大了。。$T$应该是log级别的。。可以用线段树维护进位。。就这样了。

好像过不了其中一个subtask。。我要$9\times 10^5$个跳蚤真是爽。

然后去想T1正解。。发现自己不会处理操作5。。想了想如果硬要处理操作5那么可以丢掉操作1。。码了两下好像拍不死了。。

打T2正解。。发现也是拍不死。。怎么拍都拍不死。。就是没过大样例

这游戏能玩?

没事有7分。。我的答案应该是$\le 2n$的。。

去玩T3。。照着grader写掉了暴力加法然后写了个$2\times 2$乘法。。觉得加法好像可以分治。。刚写完来不及调就下考了。。日。

一切都结束了。

就差出成绩出个榜啥的了。。不过还有冬令营，榜的意义不是很大?

。。。

然后一看

T2写挂啦!好像挂了第一个点。。日没有特判啊。。但是为什么10分都挂了。。

T3写挂啦!乘法挂掉了?upd:其实是忘了交>_<

一堆人切掉了T1。。50分狗表示混不下去了。。

打了4天暴力。。。。。。。

这感觉。。

真是。。

爽啊。。。。。

不知道那个老规矩“暴力打完了就能进各种队”今天是否还成立。至少在NOI上不成立了吧，清华集训也不好说了。

还是太弱啊。

(雾)

题解见页面【清华集训】。哦今天开更。