校内互测第一周(East!XI~East!XV)总结(窝还是退役吧QAQ

= =真是不想说啥了。。。

像我这种沙茶蒟蒻还是早点滚粗的好。。。

Day1 East!XI 出题人：18357

打开题瞬间傻了。。。三道树上问题。。。三道。。。

T1：给定一棵N个节点的无根树，求每个节点到其它的节点的∑(路径长度xor M)。

M<=15

TM这傻逼题我写了个0~15的Trie树。。。明明记录个0~15的数组就好了啊QAQ

写的时候编译器还尼玛鬼打墙。。。单步调试一切正常，结果输出出来就是一坨负数。。。

最后写了个内存池才搞定。。。3h就这样滚蛋了

结果后三个点MLE。。。简直令人想冲墙打一拳

T2：给定一棵森林，支持Link和查重心

暴力40滚粗

其实启发式合并调整一下重心就好了。。 我这傻逼。。。

跪Eolv A了。。。

T3：BZOJ 3784 树上的路径

他你不会写这题你他出出来干嘛 操

。。。冷静

出题人自己写个了点分治，然后用菊花和链把点分治卡掉

最后在题面上告诉我们：第9个点是链，10是菊花

你他在考我分类讨论吗？谁TM稀得特判你的链和菊花？

。。。冷静*2

结果最后暴力写挂拿了10分。。。

[捂脸熊]我醉了

跪wyfcyx 想出了nlog^2n的做法然后成功被卡常

总结：

1.数据结构一定要开内存池！！！

2.别在T1浪费太多时间

3.暴力也要出几组数据Check一下，不要自信

4.像我这样的人最好早点滚粗

Day2 East!XII 出题人：wyfcyx

T1:拉灯游戏图上版 n<=35

自信高斯消元+暴力枚举自由元 怒40分

加了几个防卡的特判结果一点用没有。。。

正解是meet-in-the-middle。。。想不到啊想不到

18357把所有自由元取0怒拿90 真是醉了[捂脸熊*2]

T2:给定两个长度为n的序列 任选完备匹配 求和相同的对数最多多少

想到FFT，根本不会写，暴力50滚粗

结果是设定一个阀值，阀值以下FFT，阀值以上暴力。。。

妈呀。。。[捂脸熊*3]

T3:给定一棵树，多次询问某个点到标号在某段区间内的点的最小距离

怒分块乱搞

一开始时限3s 结果考一半要改成1.5s 被我死缠烂打改回3s。。。

最后在开了O2的情况下卡时拿到90分。。。剩下一个点爆栈了。。。

【幸好时限没改小不然废了】

正解是动态树分治- - 不会啊QAQ

据说一开始的标程是线段树维护虚树？简直。。。

然后凭着T3的90分拿到Rank1。。。[捂脸熊*4]

总结：

1.对于数据范围小的题不要慌 通常解法很多？(反正还是拿这种题没辙啊

2.不要在递归里开太多东西

3.像我这样的人最好早点滚粗

After Story:

考完这次试之后我怒切了捉迷藏和紫荆花之恋。。。233333

Day3 East!XIII 出题人：PoPoQQQ

终于到我了。。。

T1:ONTAK2014的某道构造 uoj群里讨论过这个题我就顺便加进来了 (还祈祷了半天他们没发现，结果真的没发现2333

由于正解太难想我留了60分暴力。。。结果居然只有wyfcyx拿全了！

然后。。。xjk搜索90。。。妈呀。。。。[捂脸熊*5]

T2:平面上给定一些圆，问某个圆能不能不触碰其它圆到达无穷远处

把指定圆的半径加到其它圆上，然后相交的圆连边，判断指定圆圆心出发的射线是否与某个环有奇数个交点

16bitwar写了个平面图结果MLE 怨我不开大内存 一个数据范围300的题我给你开512MB内存？。。。

wyfcyx乱搞90分 被我构造的数据卡掉一个点 随机数据全过了。。。 难怪保护古迹那个题用错误的判内部点方式能过。。。

T3:我精心做了两天数据的提答。。。TM最高分20究竟有没有认真答啊。。。

18357爆零，美其名曰：我前7个点都分析并且跑了，后3个点也看了

。。。然后跑出一堆1 样例都没过你不知道么

第一个点我精心构造了个72居然一群人输出1我真是醉了

总结：

1.数据不要做得太水 该卡的还是要卡 多写写暴力和乱搞看看分数如何

2.数据不要做得太水 该卡的还是要卡 多写写暴力和乱搞看看分数如何

3.数据不要做得太水 该卡的还是要卡 多写写暴力和乱搞看看分数如何

4.像我这样的人最好早点滚粗

Day4: East!XIV 出题人：16bitwar

T1:给定字符串A和B，求A的最长的在B中的前缀，允许失配一次

后缀自动机暴力O(n^2)能A你信么。。。

正解好简单。。。就是枚举左端点然后Hash一下嘛。。。

我这沙茶。。。

T2:BZOJ 3678 wangxz与OJ

无压力AC 权当刷题了

T3:给定一个序列，多次选一个区间做Nim游戏，右端点指定，左端点任选，然后问右端点最多取走多少，【第一次取走的就真的取走了】

题意没说明白导致爆零。。。

正解是块套Trie，我并没有理解到题目中还有【修改】这一层含义，写了可持久化Trie。。。

总结：

1.不要看到字符串就想到后缀自动机 明明我还没学明白这家伙。。。

2.仔细读题QAQ

3.像我这样的人最好早点滚粗

Day5 East!XV 出题人：Eolv

T1:BZOJ 3658 Jabberwocky

分治+树套树，nlog^2n 60滚粗

我这傻逼要是把树套树换成主席树就A了啊。。。

正解是链表+树状数组？啥做法。。。

wyfcyx和我想的一样，主席树写挂了，照样60滚粗

T2:傻逼递推+矩乘

T1写了3h，这题压根没看。。。

明明就是傻逼题。。。

T3:二分图最大环覆盖

网络流建图没建出来，爆零滚粗

然后这次考试最高分60。。。我醉了。。。醉了。。。醉了。。。

总结：

1.别在T1浪费太多时间

2.别在T1浪费太多时间

3.别在T1浪费太多时间

4.像我这样的人最好早点滚粗

。。。。。。。。。。。。。。。。。。。。。。。。。。。。

算了。。。。我太弱了。。。。还是早点滚粗吧。。。。。。。

别浪费省队的资源了。。。。。。。。。。。。。。。。。。。

死んでろ！！！老子才不会滚粗呢！！！不管是为了自己还是谁也好！！！战个痛快！！！！F！！！！

喵哈哈哈哈哈！！！！！