话说省队集训居然开放所有人参加，于是参加的人远远不止15个……

作为高一参加省队集训的蒟蒻WAer……

自然是被神犇们爆虐咯……

Day1

计算几何。

居然有两道省冬原题，所以今天训练并没有什么卵用。

一堆人高分。

然后我有一道原题被卡精度，WA了50分。

坐等本WAer明天继续爆炸= =

Day2

计算几何。完全写不动的东西。

上午讲了各种凸包、半平面交、旋转卡壳之类的东西，由于我是口胡选手所以自然以为都会了2333

然而下午的测试让我明白了我是多么的naive。

第一题：给 $n$ 个平面 $xOy$ 上的动点（保证不存在始终重合的），时刻 $t$ 第 $i$ 个动点位置 $(kx_i\cdot t+bx_i,ky_i\cdot t+by_i)$，$i$，$j$ 连一条边当且仅当存在 $t\in(-\infty,+\infty)$，求图的最大团。

一眼看没什么思路，先敲了个 $O(2^nn)$ 暴力。

第二题，平面上有两个点集 $A$，$B$，$A\cup B$ 内没有三点共线，每个 $B$ 中的点 $i$ 有 $p_i$ 概率选，$1-p_i$ 概率不选，求选出的点的凸包内 $A$ 中的点个数期望值。

想了下不知道能不能用期望的性质搞，但很快被我叉掉了。

算了先弃这一题。

第三题，给两个点集 $A$，$B$，求顶点都在 $A$ 中的最大凸多边形使得其内部没有 $B$ 中的点。输出方案。

……这不是原题吗？虽然我当时也没做出来不过我会做，哈哈。

不过似乎挺难写？算了回去看第一题。

第一题研究了挺久，推了个式子 $\frac{ky_i-ky_j}{kx_i-kx_j}=\frac{by_i-by_j}{bx_i-bx_j}$ 但并没有什么卵用。

想了想决定加个垂直于 $xOy$ 平面的 $t$ 轴，于是变成三维空间求两两相交的直线集。

看样子这些线共面，于是枚举两条线确定平面然后统计平面上的线，呼……终于写完了……

接着开始搞第三题。

排序以后可以DP，开始写各种情况。

一写两三个小时过去了……

终于写完，样例过不了，又调了好久才过样例。我代码能力该是有多弱啊= =

由于省队集训名义上比赛时间是5h，实际上只有4.5h，只剩下半个小时左右了。

赶紧敲第二题暴力。

敲完了。

第一题对拍没问题。然而这题随机数据几乎答案都是1和2，对拍并没有什么卵用。

结果意识到一个问题——

不仅可能所有线共面，还有可能所有线不共面但共点！

觉得要改很麻烦，没时间改了。再说也许数据弱呢

第三题出了一组数据WA了，又改了几个地方才过。要结束了，没时间对拍了。感觉这下没问题了

完了似乎要跪了。。。

开始评测，结果……

第一题……（有问题的程序能过吗？）

WA，WA，WA……！

狂WA不止，只剩25分，崩了。

第二题暴力20分。

第三题……一定要A……一定要A……

还是狂WA！！大崩盘！！

只有27分。

3题加起来仅72分。这下惨了。

看了下其他人，第一题几乎都是暴力高分，有人暴力100分、95分还有其它高分。

据说第一题数据很弱，但偏偏卡掉了我的错误程序= =

第三题暴力有50分。

妈呀我怎么两题都挂成不到暴力分了？

immortalCO 240分虐场%%%

我们学校其他几个人都100多分，新高一的学弟也全都比我高。

我去！真的垫底了！早知道就交个暴力

一定是我太弱了。我写挂了两题，我是傻逼【然而immortalCO却说我太强了，这是怎么回事？？

晚上没心思做题了一晚上都在思考人生233

回去调了一下，发现第3题纯属自己作死，不仅三角形区域判错了，还把读入的点排序把标号弄乱了，简直不可饶恕的错误。

下次一定要想清楚再写！

坐等本WAer明天继续爆炸

Day3

上午的组合数学实在无聊（压根没学到什么新的算法之类），于是去Codechef刷水题，结果一直WA，调不出来，烦。

唉一定是我太弱了，我就是WAer。

下午是咱们学校IOI神犇kfdong（由于他太强了经常AK，以下称为AKF）的题。

由于昨天挂了两题今天一直觉得会挂= =

第一题是一道大天朝数据结构，像我这样的数据结构渣都能有思路看起来是高分一片啦。

写了个堆。每次把一个最小的取出来拆成两个扔回去。

第二题是个图论题。

脑补了下缩SCC以后是个“最短路=最长路=1”，DP套DP？

后来发现自己SB了，其实就是按 $s$ 到点的距离分成 $0$ 和 $1$ 两类，不能有从 $1$ 到 $0$ 的边，从 $0$ 到 $1$ 的边必须加进 $E'$。

最小割。

第三题是个排列计数，觉得是个水题就开始研究了。

然而并没有研究出来。

最后交了个状压DP。

回头检查前面两题，第一题对拍没问题，第二题一拍就WA了……

然后才发现$s$，$t$不能到达的点不能被归为任何一类，需要扔掉。还好发现及时……

没时间检查第三题。

开测。

最后一题暴力好像写挂了，小点WA，只得了30分，暴力分都没拿满。

看了下结果，果然第一题各位神犇各种高分。某位女神犇lyq第一题拿了高分，然后AKF让她讲下做法然而她并没有讲？（不会是写挂的正解吧）

std用了线段树，immortalCO也是用线段树A了这题。咦我的做法怎么和他们的不一样？233

由于immortalCO第二题最小割建图错了少了50分，我就被狂膜了（其实我第2题图也差点建错了）

坐等本WAer明天继续爆炸- -

Day4

RP大爆发，今天居然没爆炸。

上午讲了一些能从我唯一会的初等数论初步（高中数学选修4-6）中学到的数论知识，依旧没新东西。

于是我、immortalCO、lightning和A队爷isdkfj、lxe交流了下貌似被取消了的省队交流题，于是我分享了一道普及组难度题立马被秒【果然我太弱了只会水题，isdkfj和lxe的题好丧根本不会= =

immortalCO写了个树分解A掉了UOIP十合一太强啦%%%

下午的题喜闻乐见。第一题是个有重复元素的错排，直接推行不通，想到我在学校讲过的研究HAOI2016Day1T2的错排想了个容斥原理做法，发现用在这题恰好合适。第二题是个CF原题，我当时想了好久，有点卡常数，强行优化了一发不知道有没用。第三题一眼数位DP想了想做不了，干脆枚举数字集合跑个集合DP跑得巨慢不过能过就行了。

很虚，还好第2题没TLE。

果然每题AC的人都很多……

wwx大爷请我讲了下第一题做法，由于没准备似乎讲错了几个地方？

WAer的flag（immortalCO：frog）：如果第 $i$ 天没炸，那么第 $i+1$ 天一定炸。

坐等本WAer明天爆炸- -

Day5

果真爆炸了。

本来写的今天上午杂题选讲，变成了Mobius Inversion选讲【本来以为这个昨天会讲然而并没有

下午的题简直图论专场，好坑。

第一题：一开始有个空图，每次加一条无向边或询问两点最早是在第几次加边后连通，点数和操作数不超过 $5\times 10^5$。

去年immortalCO教我的并查集裸题。

第二题：一个有向图，每条边有个容量，一开始 $K$ 个人都在起点，每天每个人可以选择一条出边走过去，但每天走每条边的人数不能超过容量，求至少要几天才能让所有人都到终点。

想了想网络流，发现只会 $O(|V|^2|E|K^3)$，只有暴力分，那算了网络流暴力分就暴力分吧。

第三题：给带权完全图 $G=(V,E)$，求 $V$ 的一个划分 $(V_1,V_2)$，最小化 $\max\{w(u,v)|u,v\in V_1\}+\max\{w(u,v)|u,v\in V_2\}$，$|V|\le 250$。

好难，只会 $20$ 分暴力枚举子集，剩下的干脆随机枚举一些子集不知道能不能多过一些点。

之后仔细研究了下，觉得只要枚举作为答案的边，可以黑白染色判定？想了下发现有一部分行不通。又想了一会儿觉得好像是2-SAT，结果我果然是傻逼最后推出了3-SAT的式子……

于是弃疗了。

看着本校神犇个个搞出第三题。

然后我交的第三题随机化乱搞——

WA

WA

WA

……

后面的8个点乱搞全WA了（我真的不擅长乱搞）。

于是就炸了。

分数只有昨天的一半高。

我们学校的几乎都把第三题做出来了，就算没AC也有高分。

就我一个只拿了暴力的 $20$ 分。

我太弱了。

immortalCO，lightning 230分虐场%%% 他们第3题都AC了。

dick32165401 180分rank3%%% 他第3题70分。

都比我强。

听讲评，第3题确实是2-SAT。

卧槽！我再一次活生生地把正解给放走了= =以后做这种题一定要手工枚举下变量的取值观察规律！

坐等本WAer明天继续爆炸。

Day6

wwt大神前来交流，赞，虽然生成函数我搞不懂= =

然后wwt让immortalCO和我各上台讲了一道题

下午的题太坑爹，三题都不会。

第一题：给 $s\le 60$ 个01矩阵作为 $s$ 个点数不超过 $10$ 的无向图的邻接矩阵，求这 $s$ 个矩阵组成的集合有多少个子集满足异或后对应的是连通图。

完全不会，写了个 $O(2^s|V|^2)$ 的暴力弃疗。

第二题：随机生成一个长度为 $n\le 10^5$ 的01串，每次生成一对 $1\le i < j \le n$ 然后把第 $j$ 位改成第 $i$ 位，串变成同一个数的时候停止，求某个给定串在变化中的出现次数的期望值在模 $10^9+7$ 意义下的精确值。

完全不会，写了个 $O(8^n)$ 的暴力弃疗。

第三题：定义一个置换 $A$ 的 $F(A)$ 表示做这个置换至少多少次才能回到初始状态，求所有 $n$ 个元素的置换 $A$ 的 $F(A)^2$ 的平均值在模给定质数 $p$ 意义下的精确值，$n\le 200$，$10000 < p < 10^9$。

觉得挺有意思的，先敲了个 $10$ 分的 $O(n!n\log n)$ 暴力，然后开始研究怎么做。

既然每个点都一样，那就设答案为 $f(n)$？

接着枚举 $1$ 所在的轮换大小，然后……发现由于答案是一堆 $\mathrm{lcm}$ 的和，性质有点类似取 $\mathrm{max}$，和乘积做法完全不一样= =

就觉得 $n$ 怎么才 $200$ 这么小……改一改状态。

设答案为 $f(n,l)$，其中 $l$ 为当前的 $\mathrm{lcm}$ 值。然后枚举 $1$ 所在的轮换大小 $k$，推出了

$f(n,l)=\sum_{k=1}^nC_{n-1}^{k-1}(k-1)!f(n-k,[l,k])$

然后跑了一下发现状态数爆炸了，因为 $l$ 可以非常大。开了个hash表来存状态，发现状态似乎只有 $10^7$~$10^8$ 级别，但转移复杂度高= =

看了一下这题 $n$ 才 $200$，或许可以打表？

然后发现由于要模 $p$，打表必须高精度……去写个高精吧。

写完高精以后跑了一下发现跑到 $100$ 多就跑很慢了……还特占内存……

开始怀疑高精有没写炸，和 long long 的对比，没啥问题。

然后再把高精的进制由 $10^9$ 改成 $10$ 跑出来结果却不一样了……卧槽真写炸了

发现高精加有个地方数字长度用了另一个数的长度，于是爆出去了得到了奇怪的结果【幸好早发现否则就真的爆零啦

改过来以后和 long long 对比以及和 $10$ 进制对比都完全一样了。

果断数组开满内存开始打高精表。一边打一边想前2题。

第1题……真的没思路！！

第2题……也许可以试一试简单情况？我把 $n$ 比较小的情况试了一遍，发现有很多答案是一样的也许有结论？再试了下……发现……

我的程序011和100跑出来的结果居然不一样，一定是哪里又挂了。可是样例居然过了这样例简直弱

第3题打表打到 $n=169$ 以后爆内存了。看来这题的打表瓶颈在于内存

然后发现剩下的时间不多了，而且这应该能拿比较高分数了。

去调第2题，调出来了，有一步少乘了一个经常等于1的变量。【差点这题就爆0了

最后想从第2题观察出的一些结论里推出什么算法，但最后以失败告终了。我真弱。

成绩出来了。

ExfJoe 180分rank1%%% 怒A第3题%%%

immortalCO 150分rank2%%% 怒A第1题%%%

还好我高精没写狗，第3题打表拿了80分。然而前2题都只有暴力分就这么垫了。

讲题的时候发现我该是多么SB啊。

第1题就是个我之前用它A过、今天上午还被wwt请去讲的某一题的做法容斥原理，然而我居然没A

第2题太丧，各种结论，想不到其实也正常

第3题，这不就是之前做过的NOI2015D1T3寿司晚宴吗？？做过的题都能忘真是被自己的低智商秀逗了233【果然我还需要提高自己的姿势水平

于是今天再次被屠

明天就是省队集训的综合测试了，感觉明天要挂得更惨，坐等爆炸

上UOJ，发现动物园莫名被hack了，去CC，发现自己之前以为A了的一题中间WA了一个点，一晚上感觉整个人都不好了

综合测试

紧张的综合测试。

第一题是个定义比较复杂的题，一开始题目看错了还以为是傻逼题。

写完觉得不太对劲，再看才发现题目看错了【卧槽

于是经过转化一下，变成求解 $40$ 个元素、$80$ 个约束的集合覆盖问题。

集合覆盖问题不是 NP-Hard 问题吗？完全不会，先放着。

第二题是个求树上随机选点期望值的题，目测把期望值转化为点对计数就行了。

也许能A？

第三题是个与异或和乘积有关的组合优化题。

一开始想到网络流，然后一看数据范围：矩阵大小是 $5\times 10000$……

明白了什么……又想复杂了状压DP就行了【再说网络流3方复杂度跑不动

于是开场码第三题，很快就码完了，结果样例过不了。

发现有个地方 | 和 & 弄混了，改。

发现有个 x 和 y 反了，改。

发现有个地方该用 + 用了 |，改。

改完以后终于过样例了。1个多小时过去了。好虚。

接着去码第二题。

点分治感觉很虚，因为点数 $50000$ 还要跑 $10$ 遍，简直 TLE 的节奏。果断改成写树形DP= =

写了挺久终于过样例了。这时候已经2个多小时了。

然后去想第一题的序列有没什么特殊性质。

发现只有部分分有一些性质，有个部分分每个集合都是一个区间，且满足单调性，显然这是可以DP的。

【3题DP的傻逼选手WAer

$n\le 20$ 的就写个 $O(2^nn)$ 暴搜吧。

写完暴搜和DP，调了一会，然后对拍了一下自我感觉没问题，差不多4个小时了吧。

最后觉得与其继续想有啥特殊性质不如回去检查后2题。

第2题对拍过了。

第3题想写对拍，发现暴力没时间写了……算了那就测组极限数据……过了。

弃疗。感觉虚炸了。

最后成绩出来了，发现我第1题50分，被其他神犇各种虐，分数都比我高。

第2、3题差不多大家都A了。

然后就被踩了= =囧

isdkfj队长260分rk1%%%

lightning第一题各种剪枝高分%%%

坑。早知道没有特殊性质我干嘛不写搜索剪枝？要是多写剪枝就A了。

【另外第1题正解居然是DLX优化暴搜简直了

最后我的省队集训就这么滚粗了

就要NOI了，然而以我现在实力很可能要挂，紧张。