WrongAnswer的博客好久没刷UOJ了，结果回来随便做一题就被卡死了。
0分程序：http://uoj.ac/submission/312569
100分程序：
http://uoj.ac/submission/312567
http://uoj.ac/submission/312568
http://uoj.ac/submission/312571
http://uoj.ac/submission/312572
http://uoj.ac/submission/312573
完全不知道0分程序错在哪，本机测小数据也没问题，把0分程序瞎改成各种等价的程序都能100分，就是这个程序会0分，而且交几次都是0分。
UPD：
别看那么多了，我写了个20分暴力都挂了：
http://uoj.ac/submission/312608
就看下这个程序哪里挂了就行了。
这个Hack是不合法的，因为 $p=5$ 不满足题目条件“不存在两个正整数，使得他们倒数的和等于 ${3\over p}$”：${1\over 2}+{1\over 10}={3\over 5}$。可见这题的Validator是有误的。
正确的Validator：
def check(p):
for x in xrange(p/3+1,p*2/3+1):
if p*x%(3*x-p)==0:
return False
return True看alphaGem的blog才发现有这个坑。。。我考场上也没发现，还好数据良心放我过了。。。
这题强制在线，$\mathrm{ans}$ 的范围是 $(n-1)l=1.99999\times 10^9$，而 $p_0$ 的范围是 $10^9$，于是 $p_0+\mathrm{ans}$ 超出了 int 的范围。
有趣的是std也有这个问题，于是我尝试hack其他人的代码失败了。
作为无实力退役选手参加Astar玩玩，居然卡进决赛了。综合NOI排名（约47）和Astar线上赛的平均排名（约45），估计我的最终排名在40-50之间，拿奖是没希望了，就当一次旅游吧。
报道等一系列行为。
对欢迎仪式的认识环节感到严重不习惯。
来到考场，发完密码条，诶怎么用户名是奇怪的名字？试了下，登不进去。然后通知说登录名是前面那个数字。
登进去一看，傻眼了，这个决赛居然是要我们写AI？exm？一直以为决赛和前面几轮一样传统。原来更像Codechef的Challenge啊。（后来想了想，Astar是个启发式搜索的算法，看这个名字也应该想到要考你写AI啊）然而我就打过少得可怜的几场Codechef，根本不会AI的那套理论啊，好尴尬。
仔细看题目，写的是一个类似多人贪食蛇的AI。贪食蛇在二维平面上进行，但可以沿任何方向移动，不仅仅是上下左右，以及蛇可以自交（非常赞啊）。局面会随机生成食物和障碍，吃食物会加长、减速，出界或者碰障碍或者和别人的蛇撞，蛇会死。还有加速道具啥的不过我没用过。当时觉得我滚粗稳了（最后确实是这样）。
前三四个小时是练习赛，不计入总分。于是我就开始胡搞，想想不管怎么样也得搞出个能活一段时间的AI。怎样避开障碍呢？脑补了一会儿物理常识，如果把障碍想象成电荷，利用斥力似乎就能避开障碍了？于是yy了个引力场，设当前蛇头 $H$ 的速度为 $v$，对每个障碍 $O$，给 $v$ 加上一个与 $OH$ 同向，大小反比于 $OH^2$ 的速度 $v'_O$，相当于施加一个“力”，最后输出合速度 $v+\sum_Ov'_O$ 方向。
问题是 $v'_O={k\over OH^2}$ 不会弄，就想，如果就地转弯的半径是 $r$，那么在 $OH=2r$ 的时候令 $v'_O=v$ 应该就稳了吧。这么想，推了会儿就写，写完交上去。
结果第一轮测出来发现我蛇一开始就死了！撞到下方的墙了，怎么萎事？不是很懂，就打了个100*100的表输出蛇在每个方向受到的“力”，发现好像都是同一个东西。接着看代码发现我把一个距离和速度搞混了，改。改完以后又发现这个力大得有些夸张，在场地中间这个力还是那么大，很不符合常识啊。
思索了一会儿发现，我的程序假设四周设满了障碍，每个障碍对蛇一个力，合力就巨大无比了，就调了参数。
吃食物还没写，赶紧写。大概是，如果附近最近的食物周围没有对方的蛇或者障碍，就往食物方向走。写完交上去测第二轮。
第二轮又GG了，莫名其妙往角落里面撞了。又用输出100*100的表观察，感觉速度还是有点奇怪。怀疑式子炸了，一看果然式子完全意识流了，啥都对不上，很无语。赶紧重新推，感觉没有什么问题：
$$v=\omega r\Rightarrow r={v\over\omega}$$
$$v={k\over(2r)^2}\Rightarrow k={4v^3\over\omega}$$
然而突然我发现最后一步 $x,y$ 分量算错了，赶紧改：
$${v_x\over d_x}=-{v\over d}\Rightarrow v_x=-{4v^3\over \omega d^3}d_x$$
改完以后感觉和谐了不少。三四两轮，都拿了几百分，似乎还行？然而一看别人的分数，动辄上千，就觉得很绝望。于是冷静地观察了一下自己为啥会低分。
看着屏幕，我的蛇一开始非常正常地吃食物躲别的蛇，不过躲得有点保守（离别的蛇还很远就扭头就跑）。之后，障碍生成得越来越多，然后我发现，我的蛇开始不停地绕环了！原来我的蛇在一个以三个障碍为顶点的三角形内，受到引力场作用，就一直在中间转，等了好久才出来！
想fix这个问题。
第一阶段测试结束，第二阶段开始正式计分了。
一共三次测试，每两次隔半小时，每次测两轮，一共六轮。
思考了一会儿，觉得障碍不会动，只要靠近时绕过就行了，改成了距离太大就不算作用力，脸滚键盘弄了几个参数限制。然后局面边缘的障碍也只提取靠近的几个。
然而有的人的蛇靠别人的蛇撞上就得了1000+分，感觉这规则真是玄，正常地吃食物每局难以破1000分，别人撞一次就加1000分。想试试能否卡别人赚1000分，发现根本不会弄。
然后第一次测试的两轮，都中规中矩地拿了400+的大众分。观察我的蛇，发现似乎并没有什么变化，还是非常容易受障碍影响。
打完大概17名左右，觉得翻盘困难。
又yy了一会儿怎么卡别人，无果。
似乎还是要优化吃食物的效率？感觉参数还能继续调？又思索了一小会儿，发现障碍只要距离超过 ${2v\over\omega}$ 就不计算作用力，效果应该最好（差不多是和引力场没关系了）。
第二次测试。第三局300+，没进步，还是经常在没食物有障碍或者别的蛇的地方绕。
第四局，卧槽为什么显示效果这么鬼畜？盯着一个以为是自己的蛇看，发现几秒就撞上别人的蛇死了，卧槽不会是我哪里写挂了吧？不可能啊，我的AI这么保守怎么会犯这个错？结果出分，傻眼了，居然只有10分！也就是啥都没吃到。
然而看视频明明那条蛇吃东西了啊？后来通知这组显示效果挂了，蛇头和蛇身不同色，要以蛇身为准。嗯我看到的是蛇头是我的颜色蛇身不是我的颜色的蛇……可是我的蛇呢？找不到？！看到一共三个人10分，视频里看到没吃东西的蛇，策略都不像是我的啊？又数了下发现一组10个人但一开始只有9条蛇？
日哦！不会遇到灵异事件了吧。
至今不知道第四局怎么爆10的。
这时候只有20+名了，翻盘无望。
又yy了一会儿怎么卡别人，无果。
似乎我的蛇太怕别人的蛇了？嗯，对别人的蛇的参数还没调。可惜缺乏经验，对动的东西不是很会把握，于是继续保守向……
最后突然发现自己犯了个傻逼错误！我误把 $\omega=0.05\pi$ 算成了 $\omega=0.05$，怪不得会那么怕障碍！于是开始大幅度改参数，打出100*100速度表，发现只有靠边界两三行的地方会掉头，玛雅这不是太危险了？又调了一会儿调到一个看起来比较适中的参数。
测了五六轮发现，虽然靠障碍近了些但还是浪费一大把。果然还是自己感觉太差，$v=0.1$，$\omega=0.05\pi$ 时，$r$ 大概是 $0.6$ 到 $0.7$ 之间，离边界距离为 $2$ 不是很稳吗？
说到底还是自己被自己输出的调试语句欺骗了，以为一行就是很紧，却没意识到极限掉头不需要一行的距离。
这时候大概19名？
第三阶段测四轮，不能改代码，想想肯定要打铁滚粗了很不爽，就不看战况了。
最后把判定距离调成了预期的理论值，不知道是否有用。
只知道最后看的结果，4100+分，第15名。意料之中地打铁了。
何柱第一名。SkyDec、Stilwell、xllend3、小火车、AKF等IOI/候选队大佬都获奖了。而我呢，就这么空手回家了。
尽管我Astar就这么滚粗了，不过也是第一次体验AI大战，看到了自己和别人的差距，也算是有不少收获了。
旅游、颁奖。
颁奖前和OI大佬们一起在墙上拼了“ysy AK IOI2018”，其实我只拼了一点却莫名被采访QAQ
啥奖都没拿到太遗憾了。
技不如人，甘拜下风，加油努力，来年再战！
退役前的最后一战。
挺紧张的，毕竟我NOI只有#40+，就算把Day2挂掉的66分加上还是只有#20+。不止一题脑抽差一点想出来还是相当不爽的啊。
毕竟还是运气选手唉= =
以及我现在考场心态还是太糟糕。
不过作为国家队的最后一名，我也没有什么太多的梦想吧。保Ag争Au吧。
orz matthew99,xumingkuan,cy。
入住酒店。
刷了CEOI2016D2T1。想了一个比较复杂的做法不知道有没更简单的做法。
NOI同步赛成绩单出来了，作为Day2挂成114分的国家队垫底选手，看着被一大堆人虐感觉也是很奇葩的。(然而同步赛FJ Day2最高分居然也就114?大家都考跪了?)
和xumingkuan住一间。
晚上宋老师带全队四人去McDonald吃了点零食，顺便和另外三人聊了些题目怎么做。深刻感觉我水平低得可怜。
IOI前的ACM模拟赛。
把自己名称改成了orz_immortalCO，暴力膜锟。
A题找了好久的规律，才看出exgcd的做法。
B题只会一种很暴力的DP，过不去。jiaqiyang当场AC了。
C题完全不会。
D题看n<=17以为是傻逼题，然后想了1h还是不会，GG。
E题就是个辣鸡题，研究了好久发现细节很难处理，结果暴力都WA，最后干脆交了个不考虑四点共线，A//B//C时会退化成平方log的程序上去，正确性和复杂度都不对，居然能过。xumingkuan现场写了FFT过了。
最后2题滚粗。我并不能跟上国家队的平均水平。
动员会。没什么好说的。
在飞机上坐了大概10h，意识模糊。
下午Exhibition，没什么好说的。
练习赛。
就是之前做过的题，不过只有2h，来不及AK。
T1用我论文里面的独立集搜索算法拿了70分。虽然说正解更好写但是懒得写了。
T2水题切了。
T3水题切了。
T4提答，暴搜搜出4个点，又搞了4，5两个特殊点，拿了60分。剩下的点没时间搞了。
70+100+100+60=330
明天就是day1了，为自己加油。
Day1。
开场看了三个题，T1是个提答，而且数据点很大不能暴搜，感觉是神奇的构造或者随机化算法，应该要留到最后去争取；T2好像很套路；T3好像一脸不可做。
然后就开T2了。一开始想到费用流，然后思考了好一会儿如何优化这个费用流，发现增广路可能好几段，不太能优化。思考无果就去看T3了。
T3看完题再看数据范围，n<=5000，m<=20000，突然又觉得这题可能才是送分题。然后开始推DP，一开始想记f(i)为从i出发会不会绕道一个有充电点的环上，然后转移有环，搞不出来。又想了想，如果A必胜，那么最优路径就会一直经过充电点，反之n步以后再也不会经过充电点。
想到这里打了一个nm的DP：f(i,j)表示当前在i，走j步将经过多少个点，如果f(i,n)=f(i,2n)则i是0，否则1。虽然不会证但感觉没什么问题的样子，就写。
调到考试开始1:20时过了子任务1,2,3,5，另外两个子任务TLE，38分。看起来这个做法是对的，只是被卡常数了。然后优化常数，在1:40时过了子任务4，49分。继续优化常数终于不TLE了，然而WA在了子任务5的第96个点。
怀疑哪里写挂了，眼调了很久。
把怀疑挂的地方改改，怎么改都过不去，始终49分，WA第96个点。然后就浪费了半个多小时（Ag flag
已经2:20了，没什么救，弃疗去搞T2。
一开始打了个7分暴力。感觉这个题性质奥妙重重，一定有规律。于是拿7分暴力打表找规律，看看发现每段都是一段R一段B，两段最多有一个交点。这样就可以转移了，然而这样仍然是n^2的，在3:13时写了暴力过了子任务3，一共17分。
然后有一种自己这题到手了的感觉，开始想优化转移。看着式子发现是个斜率优化，然而看起来很复杂的样子。随后想想裸上决策单调性好像可以（Ag flag*2
然后以为决策单调性很好写，实际花了半个多小时，调不出来。好不容易调出来发现做法有问题，想fix这个做法又花了一会儿，还是错，惨啊。
这时候T1还没打，很慌，赶紧回去每个点随机输出一个极大的树拿了60分。
最后30min终于决定打T2的靠谱的斜率优化了，打了大概20min。
然而，没调出来（Ag flag*3
最后就悲惨得滚粗了。
60+30+49=139
考完第一个问xmk，他说他拿了274。我一听整个人都要吓软掉了，完了，真的没救了。lzz也拿了接近200分。myy和yjq好像也考跪了。
出来看榜，我#40，Ag分数，xmk#3，就要虐场。唉，这就是实力的差距。
听说T3只有4个人A，xmk就是其中一个。想想我这个做法自己都不会证是不是对的居然能拿49，却不知道骗分应该及时收手，导致浪费大量时间最后没时间做T2，70分没了，活该Ag。
下午回去，非常不甘心地继续调T2的斜率优化，花了大概半小时调出来了。早知道那个不靠谱的决策单调性就不要写了，省出这个时间完全足够A掉T2，70分没了，活该Ag。
在车上和myy，xmk讨论T2，他们说T2不用斜率优化，前缀最值就行。我说式子里不是有一个x吗，然后盯着式子又看了两眼，发现这个x是连续段的开头，是固定的！而不是x[i]会变。要是多思考下，前缀最值比斜率优化好写不知道多少倍。
调T3错误算法，搞T2决策单调性，写T2斜率优化，这三个错只要我任何一个不犯就是209分，但结局是139分。我连续这么多场比赛就没有正常发挥过，IOI又因为自己作死花大量时间在错误算法上而丢掉70分，丢掉Au，成千古罪人。想想真是太后悔了。
晚上去Exhibition到很迟才回宾馆。
Exhibition。
本来很好看的，一想到D1T2就没心情了。
如果是实力Ag也不觉得遗憾，然而明明会做的题却因自己作死浪费时间最后来不及调出来导致Ag，就十分遗憾了。
Day2。
还是花半小时看了三个题，T1、T2都是交互题，目测应该一道简单一道难，T3是传统题，看起来很可做。
然后猜了个T3贪心的结论，答案等于每个环的长度和加上s左边非自环最右和s右边非自换最左距离的2倍，交上去，爆0了。
发现写挂了，改了改交上去，又爆0了。
想了一会儿发现套在一起的环可以一起走，就fix了一下，交上去，50。
不错，起码s=0的对了。
60min过去了，我得了50分。（Ag flag
回去看T1。T1感觉i的个数大于i-1的个数的平方这个约束很奥妙重重，意味着可以用分治暴力搞出所有小于v的位置？然后随手打了个分治，交上去爆20。
然后发现递归到[l,r]时询问mid询问的不是[l,mid)而是[0,mid)，接着想前缀和减减，发现mid和l，r不一定都是v类型。
接着想法就是先随便询问500个位置取个最大的，然后就能判断是不是v了，不是v的只有不到500个，暴力扔掉。
写完交上去，拿了97，把500调参调到480，并没有什么卵用。
100min过去了，我得了147分。（Ag flag*2
感觉为了剩下2分多折腾太浪费时间，就去看T2。
第一感觉是高斯消元解线性方程组，接着想想发现一点也不靠谱。既然是生成树，就一定有什么性质，无环？
随后我的想法是，每个环至少有一条边不属于生成树，这样就可以对每个环询问L（L为环长）次确定环上是边是否属于要求的生成树，这样就能m次询问搞定了。然而只有暴力分。
优化了一会儿拿到51分，继续想，怎么想都只会m次询问的做法。
180min过去了，我得了198分。（Ag flag*3
之后继续搞T3，想想我的做法s不等于0为什么会错，原来s和左右端点夹住s的环不能套在一起。然后加了个贪心，先走到最近的环。
交上去还是50。然后发现5,4,3,2,1,0这种情况没有两个环是嵌套的。接着推出从环A能进环B的条件是A的最左和最右点之间存在B中的点。
看样子是求一个最短的包含s的区间使其能到所有环？写了个bitset+floyd+two pointers，只有12。
和s=0的拍了一会儿拍出WA，手算了一下才意识到在任何位置加边使s能到所有环就行了。
接着写了个复杂度不满的n^2 DP：f(l,r)表示从区间[l,r]出发至少加多少边能到所有环，用hash表存状态，过了70，最后一个Subtask TLE在第66个点。
继续推发现是个最小树形图，然而这东西我只会n^2暴力，想试图观察出什么性质也没观察出来，一定是我太弱了。
T2也没什么好的思路，连完全图都不会做。
最后延长了半小时，然而T2、T3都做不出来，很绝望。
97+51+70=218
两天加起来139+218=357，Ag稳，Au不太行，好虚啊。
出来问了下，xmk 250，lzz 267，myy 219，都比我高分啊。要是我Day1没丢70分就稳Au了。要是大家都会T2，T3……
出来看到中间榜我貌似#23？然后不少人发祝贺？然而还不是最终榜，好虚啊。
最终榜出来了，我#25，好像又卡了一次Au线啊。xmk#2，lzz#3。然而myy还是挂了，惨啊，myy在我心目中一直是最稳的，可是……为什么会这样呢？
仔细想想，我现在的成就有：CTSC 0AC得到Au，NOI 0AC得到Au，IOI 0AC得到Au，感觉没有谁同时拿过这三个成就了。
上午去water park，以为自己退役了无所畏惧了，还是被某大型水滑梯吓怕了。后来玩了几个小型的。
下午Exhibition。
闭幕式。
颁奖按排名从后往前的，然后我是Au上去的第二个。
又开始后悔D1T2了。
考挂滚粗回家。
退役了。
CJK猫，CJK强，CJK是FZYZ的红太阳
尽管immortalCO就要上大学了，但immortalCO永远是FZYZ的红太阳。
感觉我的高二并没有什么进步唉。。。省选Day2连滚两题被翻，WC提答滚粗，CTSC Day2爆炸，APIO被虐。。。依旧一堆题不会做。。。
和省队集训Day 0冲突，用手机在空余时间写的。
T1看完想到O(n^2)的DP，再想想就会O(n+k)了，很快写完。
T2看完想到清华集训2015D1T1，然而细节还是折腾了好一段时间，花了好久才调好。
T3没时间搞，打了个不知道啥复杂度的暴力，实测1e13能跑出来。
期望得分100+100+78=278，实际得分100+80+78=258。
T2写的应该是正解，不明原因被卡常。
又是rank 4。
回宾馆改题，T2跑一组数据发现瓶颈在求逆元，换成标程的那种exgcd就快了一倍，卡过去了。时限1.2s的题标程跑了0.9s，有点想骂出题人。
T3给我的O(sqrt(N))程序加了两个优化就直接AC了。然而考场上没时间了，唉。
AK的hzq84621好像T3写的是O(N^(3/7))标算？好强啊orz
嗯，继续努力。
和省队集训Day 2冲突，没时间打。吃完午饭回宾馆想rush一下T1的75分，没rush出来。
期望得分0+0+0=0，实际得分0+0+0=0。
垫底了。
最后两天总分258。Au线364，Ag线283，Cu线216。拿了个Cu。
作为非省队选手参加了省队集训。。。果然被屠了。
省队互测，大概是15个省队队员加我一个非省队，每人准备一道题完成讲解。（大概是看我去年进了省队但去年没互测于是就给了我这个机会，十分感动。。。于是我成为参加互测的最差选手）
萌萌哒aufeas姐（额好像不能这么称呼。。）第一个上场，dp优化网络流真有趣。虽然她的题我好像不到一小时做出来了。。。
张队长和初三大佬zzq的字符串题也好劲啊。作为不会**自动机的选手在听wrz和张队长题时只能当吃瓜群众。
victbr的原创题也很强。表示我也掉了分块坑。
闫神太巨了，出了一道神级结论题，做法是转成图论问题然后怎么怎么解决。第一步都没看出来的我表示一脸懵逼。。。
猫锟强，临场讲了好几题的更优算法。（然而一直说我是猫说yhx是猫说wrz是猫是什么鬼啊。。。
yhx和ct讲的都是猫锟出的模拟赛题。
作为非正式选手的我最后一个讲。。。讲的是我去年出的校内模拟题。做法很sb，没用什么算法，就是打表找规律然后构造。。。感觉我是最菜的出题人。。。
讲题时台下很欢乐。
zzq现场切了我的题，写出来了。
不得不说现在的省队爷都好劲啊，技不如人甘拜下风。整个听讲过程我不是在膜出题人就是在膜锟膜闫神膜zzq，然而只会膜不会提高自己姿势水平有什么卵用呢。就要退役了我还是啥都不会怎么办啊。
出题人：猫锟（immortalCO）
看了三题，T1是个字符串题，T2是个APIO2016T1的改版，好像能做，T3像之前一道校内训练的题，但是改了，题面很长没看完。
先做T2，想了一会儿发现原题做法用不了，，只能用维护分段函数的做法。O(n^3)。然后花了2h才打对，我好菜啊。
测了一组极限数据直接就跑不出来了，感觉600过不去只能过100。
然后做T1，推推式子发现对S的每个前缀和每个后缀求出它与所有s[i]的LCP之和就做完了。由于不懂SAM的性质就打了个后缀数组+Trie+二分，3e7*log(3e6)的。
又花了1.5h才打完。随机了一组极限数据又跑不出来了，把n改小了看看后缀数组循环次数，发现n=100000只循环了4轮，n=300000却循环满了，感觉像写挂了，就调了很久但无果。后来想想好像Windows的rand有奇怪的循环节就貌似明白了，没管。感觉只拿30+分。
最后只剩半个小时了，T3勉强看完题没时间做，随便打了个贪心连样例都过不去，就结束了。
期望得分在50到140之间吧。
听说很多人都A了两题，好虚啊。
成绩出来了，在期望得分之内，38+18+0=56，rank5。
T2果然被卡常GG。去申诉，重测了一发T2变成31分了。还有不少人申诉，很多原来分数很低的人都翻上来了。
最后成绩38+31+0=69，rank9。
aufeas姐好强啊130怒拿rank1。闫神A掉T2怒拿rank2。T2脑抽了，本来只要维护一个函数，我按<,=,>三个符号维护了三个函数，2s时限跑了2.5s，100被卡成31，打满暴力都比这个高分。不过想想能有前10也还凑合。
回去改题，T2果然换一种记状态方法直接常数除以3，就AC了。T1瓶颈在后缀数组……3e6log3e62比3e7*log3e7还慢，果然后缀数组常数大如nlogn。
下场加油吧。
出题人：n+e（Trinkle）
T1看完以后想到二分答案BIT判定，复杂度nlog²n不知道能不能过3e5。写完之后随便构了一组极限数据跑0.8s+，感觉不是很虚就扔一边了。
T2是个提答，感觉正解是构造，然而想了很久还是不会构造，连个可行解都构不出来，一分都没有，就先跳过。
T3就是个方格取数的简单DP，然而一副卡常数的样子。写完过了样例以后把样例的n，m改大，跑了8s+，优化了一发数组访问跑了4s+，不知道能不能A。
回去搞T2，写了个贪心结果根本不能出可行解，又各种修改贪心姿势仍然无果。手玩了一会儿小数据也构造不出来。浪费了很多时间提答还是0分，非常虚。
接着放弃了贪心，考虑别的做法。先想能不能状压DP，结果第一个点棋盘大小就巨大。。 又分析了一下性质，对于源点入度=0，对于汇点出度=0，其它点入度=出度<=1。这样就能费用流了？
怒写费用流，跑了会跑出前三个点60分，后两个点跑不出来。尝试优化费用流无果。
后来打算退而求其次跑可行解骗分，也跑不出来。
最后期望得分220-260之间吧。
成绩出来，预计得分之内，100+60+90=250，rank2。T3被卡常数了。
已经连续三场比赛被卡常数了。
ditoly 296分虐场了，T2用primal dual跑了96分，不能更神。
后来知道我T3为什么被卡常数了，我作死在读入的时候对输入的数做了前缀和，然后访问2.5e7大小的64位数组慢得要死。
出题人：叶队长（isdkfj）
第一题看完感觉出现恰好一次的数对应的区间可以化成平面矩形区域，找出每个数的下一个和它相等的数之后就可以用线段树维护了，似乎不难写。
第二题看完感觉是个神题，先跳过。
第三题是个提交答案题，输入文件是一个C++程序，要求给一组输入使其输出最小。似乎很好玩。
于是刚了2h的第三题，觉得大概能有80分的样子。有几个点看不出怎么做就随机化乱搞。
回去写掉第一题，发现n=500000极限数据要跑2.2s，有点萎。优化常数无果。可能要被卡成60了。
剩下一个半小时开搞第二题。推了一会儿式子，把和式交换了下求和次序，又套了一层反演，推出一个O(n^3)算法。然而数据范围第一个点n就是2000，完蛋了要爆0了。
写了O(n^3)过了样例，想继续优化复杂度但没时间了。
期望得分140-190。
听说有人推出T2的100分做法FFT，感觉我今天要滚粗啦。
最后还是预期之内，100+0+76=176，rank1。提答有几个点小范围暴搜猜错结论掉了不少分，最后一个点随机化直接爆0。ditoly 175分，rank2，算上前两天ditoly在我前面很多的样子，感觉ditoly要win啦。
fateice提答95分，跪烂。
T2全场都是0分，有毒。
出题人：闫神（fateice）
第一题看完没有除了数据结构优化DP以外的任何想法，然后想想发现树状数组似乎不行，就写了线段树。写完测下极限数据1.4s，怕TLE，就优化了一会儿线段树的常数，又写了个输入优化卡到0.9s，感觉能过就不管了。
第二题是个几何题，求包含边长为1的正n边形的最小正m边形，要求两者中心相同。感觉不是很有思路就先写了特判部分数据，剩下的分段爬山。期望50分。
第三题是个类似ZJOI随机树生成器的提答，要求识别树是随机kruskal生成的还是其点分治树。手写了个生成器然后打出各种特征，发现直径的区分效果最明显，就用直径划分来判断生成了out。后来想想小数据好像有反例，又搞了很久的第一个点，加了各种特征发现和原来的输出没差别就不玩了。期望得分90-100。
回去推第二题，发现了一些奥妙重重的性质，推了好久的端点，貌似取过顶点第一条线的倾斜角为π*gcd(n,m)/nm好像就行了。然而式子一直写错，直到考试最后几分钟才调出来。尽管如此还是担心卡精度不知道能不能拿到100。
期望得分240-300。
一开始文件不小心放在子文件夹里面，考完以后闫神问我为什么没交，才改过来。差点爆0。
最后得分100+100+99=299，rank2。第一题只跑了0.3s+，第二题也没卡精度，第三题第一个点掉了1分。
zzq AK了，orz。wrz第二题模拟退火过了，也是299。ct第三题A了，好强啊。
看完题解发现我第三题SB了，直接判断一棵树是否可能是点分治树就行了，还面向数据找了那么久的规律，就跪了。想想我到现在还不会分析问题性质，吃枣药丸。
出题人：wyf
T1是求把平面点集用一条不经过任何点的直线分成两组的方案数，要求某些点集属于同一组。看完我大致想到一种做法，枚举两个点连一条直线切成两块，判断是否合法。然而线上的点要归哪一边？有点懵逼地继续想，好像可以假设线上的点归同一边。但是好像会算重，那就hash去重咯。
然后就开始考虑枚举一个点，其他点极角排序以后扫描。然而这东西细节真的多。。。旋转的时候分上下有没有点考虑了各种情况。也不知道有没漏。
折腾了快2h终于过样例，然后随便拍几组数据就炸了，调的时候发现bug一大堆。于是继续改改，改了好久，随机数据答案终于对了。
已经2.5h了，时间过半，感觉后两题不太可能都做出来。T2是个字符串计数，T3是个纯数据结构，凭感觉估计T3是什么黑科技题，不太能做，就打了T3的暴力，之后全程刚T2。
T2求的是长度和s相同的小写字符串有多少个字典序不大于s，且它的本身是其所有循环同构中字典序最小的。
一开始把最小表示串打出来想找规律，结果找了很久没发现有用的性质。接着想到，这其实就是求不循环同构的字符串个数，可以burnside引理搞搞。
然而字典序不会处理。又推了好久，把字典序转成了子串包含约束，然后貌似可以KMP搞搞？
先写了个暴力过了样例。
这时候大概剩半个多小时了，推KMP+DP各种环上细节处理不清楚。似乎想出了40～70分，结果最后还是没能写出哪怕比暴力分高一点点的做法。
期望得分150。第一题可能会挂所以还是很虚。
最后果然就滚粗了，0+20+30=50，rank11。T1写挂爆0。
全世界都A了T3。
全程刚前两题，结果一题写挂，一题没刚出来。感觉我这是回家种田的节奏。
晚上调T1，看了会代码发现我犯了一个弱智错误：输入的点编号从1开始，我数组下标从0开始，忘了减1。对拍的数据不是m=0就是分组很规律而且答案很小，没发现问题。于是只可能过m=0的点，然而我m=0的点被卡常数TLE了。改完弱智错误就80分了，再写个radix sort就100分了。
T2推了一晚还是只会n^3。然而T3的分块想了十分钟，打了一个多小时就A了。看来T3真的比T2可做得多，以及我真的很蠢。
出题人：ExfJoe
T1又是类似清华集训2015遥远的星系的题，一开始打了个并查集，结果好像会爆long long，就把并查集全删了改成DFS树。改完以后过了大样例，感觉不是很虚就扔一边了。
T2是树的动态加边求连通块最大基数独立集。看完想想不会是链分治模板题吧，上次写链分治写一下午没调出来已经有心理阴影了，而且这个做法常数很大，200000 1s应该没救。看来一定有更简单做法。只是一时没想到，先跳过。
T3是个十合一提答，求10份代码的输出的期望。代码不用C++用Javascript差评，虽然我看得懂。
折腾了2h搞出了六七个点，也不知道有没错。看了下时间只剩一个半小时了再不做T2就来不及了。
思考了一下觉得这题的性质在于最大基数，可以贪心从下往上取独立集。接着就会了一种启发式合并+暴力扫描到根的链的做法，应该能有50分，写完过了大样例。
继续想这东西怎么数据结构维护，似乎记一个c表示翻转i会不会导致i的父结点状态改变就可以了？找到第一个这样的祖先，端点讨论一下。这可以用树剖线段树维护。
只剩不到半小时，狂码树剖线段树以及维护独立集和c数组，然而主过程还没打，就结束了。
于是乎T2只剩暴力分了。
期望得分210-220。
最后100+35+61=196，rank 4。T2喜闻乐见地挂了50分，然而子任务3水过去了，得分35。很多人T2都是85或者100。
dick32165401虐场了。
回去调代码，发现把启发式合并改成大的往小的里面合并样例就过不去了，原来是因为我记fu是u所在并查集的根，交换u，v的时候忘了重新求fu。然而样例是按子任务3（逐个添加叶结点）造的，没查出错。白丢50分。
后来出题人发现T2一堆人过85分是因为数据造水了。。。然后改数据重测。惊讶地发现我T2还是35分。。。数据还是水？于是莫名其妙地rank 1了。
省队集训结束，成绩比去年还糟。我做出来的题都是一堆人A，我花大量时间想搞的题最后没有一题做出来。
不是自己退步了，就是别人进步得更快。
挺后悔自己高二没有认真刷题的。平时总觉得自己已经很努力了，然而一到考试才明白别人比我努力得更多。
T1看完以为值就是<个数减>个数，随手DP了下组合数结果没过样例，跑了下n=2才知道哪里错了，<>是2不是0。。。然后想到状态里记还没匹配的>个数的一个n^2 DP，写完发现又炸了才知道转移不对，把记一个东西改成了记两个东西，又推了好一会儿才推对。浪费了不少时间。
T2看完发现求的是链上单调栈大小这一玩意，感觉强行树剖维护单调栈不太行。接着直接照着题意想，就想到一个算法：先找出第一个大于c的祖先，然后每次找最近的大于当前点的祖先往上跳。用倍增优化下就一个log了。然后就很快搞定了。
T3求的是一个模线性方程组，不过变量之间的关系构成了基环外向树。那就环上绕一圈列个方程解出来，外向树直接递推。调过样例以后不放心，随机生成了一组数据，结果WA了。调了调发现数据生成器写错了。再生成又WA，发现树的父结点记错了2333总之改了很久才A。
T4看完题以为i能作为最终结果的条件是i右上没有点，左上和右下都在i后面。写完以后样例没过，再想想发现结论是错的。接着想枚举出现过的点集S，是x，y严格递增的，然后确定剩下的点的位置，把剩下点插进S有(n-1)!/∏(i右上角点数|i∈S且i不是S最后一个点)种方案。把枚举换成DP就n^2了，用BIT优化就nlogn了。
T5是个构造题，一开始想贪心，结果构造出来的是fibonacci数列，不是根号的而是log的。想二进制分解也不行。想用多进制数来构造，分成两组，每组递归下去，然后一组乘个系数加个常数，结果打出来发现甚至不如fibonacci数。想构1²，2²，3²……到8就出反例，想打表找规律结果没发现任何规律。
最后还是没做出T5。去看T6想到一种两个log的线段树优化DP，感觉过不去。最后抱着弃疗的心态写，没写完。
最后过了4题，名次好像很后面的样子。考后讨论了下全世界都会T5的构造，zzq好像还是一眼秒的，做法是取一个sqrt(n/2)以内的质数p构造2pi+(i²mod p)。感觉我打死也想不到。。。一定是我太弱了。
还是很好奇大家是怎么想出来的。。。
构造题姿势水平不够，要多接触这类问题。
A题看完就会做了，最优解people和key的对应关系不会交叉，排序以后DP一下就行了。
B题好像是个大模拟，排序以后按环的顺序取，用个树状数组维护区间内被取出的数量。半小时左右的时候写完。
C题看完想到UOJ#21缩进优化，不过n<=100，a<=10^9，那就是用UOJ#21的70分做法咯。由于怕多个log被卡，写了radix sort对端点排序。一遍过Pretest有点爽。
D题想分成过根的和不过根的路径考虑，如果过根并且被根分成的两段在同一子树，就要用2条路径覆盖一个子树。然后想到的做法是f(i,j)表示用j条路径覆盖i层图的方案数，转移分了好多类情况讨论。居然写完就过样例了，好爽。
E题想了一段时间，想出了有环的图以及存在度数大于3的点的图如何构造，并且还构造错了。。。图是二叉树的情况没搞出来（也许直接输出NO？糟糕，有反例。。。），于是E题就没过。
最后rank 10，涨了201的rating，终于上红了，十分感动。这也是我打了这么多场CF里面成绩最好的一次，这场CF难度似乎比以往水，前4题都很快想到了做法，并且也都写对了。往常打CF我最多做出3题。当然也有可能仅仅是我这次的题我刚好会做。
滚粗。
T1目测线段树裸题，结果花了2h才调过所有样例。
T2目测链表+hash裸题，花1h过完样例之后发现样例5开-m32要跑1s+，感觉过不了最大的点，要卡成80了。
T3。。。连续三年NOI D1T3都是读入O(1)的题。。。
我的想法是，如果要求那个玩意，就要用一个单调栈。那么能不能状压单调栈呢？
发现好像可以，而且只要状压2sqrt(K)段的样子。。。然后就觉得N<=1000，K<=10的稳了。
然后我就掉坑了。。。一直在想这个东西怎么优化，优化不了，就想能不能换一种记状态的方式。然而从头到尾思路都是从左到右确定每个高度，压根没想到枚举最小值的位置DP。。。然后还想容斥，也不行。。。于是2h都没想出来。。。唉。。。
最后交了40分暴力，感觉上不了金牌线了。
期望得分：100+80+40=220
去年Day1都有247。。。幸亏早生一年。
后来大家说T3和UNR D2T1撞题，想想发现还真是。。。而且UNR我还做过！人家学的是OI，我学的是什么？暴力？
出成绩，全世界都会T3我不会，一堆人A了T3我只有40。matthew99，fateice，RXDoi都是292，我220。pyz5715，fjzzq2002，victbr也都比我高分。
估计了下我的排名只有30+，比去年还糟糕。
晚上回去把T3的正解打出来了。
心情很不好。
为什么这么简单的一个DP我就是想不到。
为什么最大子矩形我没有除了单调栈和容斥以外的别的想法。最土的办法都没有想到。
枚举第一个最小值在什么位置，求出靠底边的最大子矩形，然后沿最小值位置分开递归下去。
这个可能我高一的时候都会吧。
状压单调栈完全没有优化的余地，我却想了很久怎么优化。
为什么做UNR的时候我都懂这个道理，在考场上就忘了。
白丢60分。
我的脑子去哪了？
我真的是学OI的吗？
曾经以为我学了这么久OI，面对题目必有高论。
然而真正在题目面前，我感受到了自己是多么无力。
看看周围的人，没有一个人像我这么SB，唯独我SB了。
滚粗更严重了。
T1看完题目就大致会做了，2^d暴力枚举x的状态2-SAT。写了1.5h。然而发现极限数据要跑1s+，过不了。
然后简单写了个check测了下样例，一开始check写错以为样例过了，后来故意把out改错发现check还是输出OK，才发现check写错了。改完以后样例挂了，就改了改过了样例。
这时候过了2h。
T2看完以后感觉很可做。
然后开始想，一开始想贪心，想了一会儿的结论发现很迷。。。就去看了下样例，手玩了一会儿发现不对？
然后发现题目理解错了。。。原来不是每次-x，而是变质的部分是确定的。。。md浪费了一个小时。。。
接着发现原先想的结论都是错的，继续想。
想了一会儿感觉好像还是可以贪心的，但是不知道怎么处理s的限制。。。
接着又开始想别的思路，想想发现费用流好像可以做？
接着开始写费用流，写完以后过了样例1，样例2根本跑不出来。输出了下中间结果比对了下好像是对的。
然后想优化费用流，想了一种思路以后发现有问题，叉掉了。。。
又想贪心，然而不知道哪个地方想错了，都贪不对。
剩一个多小时的时候很慌，赶紧去打了T3暴力，回来继续想。
当时十分紧张，感觉要是想不出来就GG了，结果越紧张越想不出来。
折腾了快三个小时，还是只会暴力费用流。
最后十几分钟想到了把图反过来建，好像可以优化，然而时间不够，只好放弃。
期望得分：90+40+20=150
然而更悲剧的事情在后面。
T2挂成4分。
于是总分90+4+20=114。
Cu分数吧。
当时我的心情是绝望的。
结果两天加起来334，如果算上笔试和A队439，集训队线436，刚好超过集训队线一点点。。。感动。当然这个成绩我还是十分不满意的。
回去调费用流，发现我答案没开64位整数以及每天的最后一条边忘了把边权设为剩余库存，改完就60分了。挂成这样居然能过样例1和样例2的一部分，还能有4分让我不至于掉出集训队线，真是喜闻乐见。
继续推费用流，发现我考场上SB地多建了一层点。把图反过来建再去掉这一层点就直接变成喜闻乐见的贪心模型了。
如此简单的80分算法，被我硬生生丢掉了20，又挂成了4分。
我的脑子去哪里了？
这个思想我在校内训练出过不止一次的。
为什么我考场上就是没想出来？
我又问了一次自己，我真的是学OI的吗？
T2我考场上完全应该得到至少80分的。
然而大家都拿到了，我没有。
也许我考场上不是在想题，是在挣扎。
害怕自己想不出来，越想越紧张。
结果越挣扎越出不来。
越挣扎陷越深。
这时，我才真正感受到心态有多么重要。
心态毁了我一整场比赛。
可是，又该怎么办呢？
总结这次NOI的情况，就是：一试脑抽，二试脑抽+心态爆炸+写挂一题，最后名次十分惨淡。
一方面，我从高一到现在几乎没有进步，甚至退步。平时看起来都在努力，但颓的时间太多，而别人的努力比自己多得多。
另一方面，我总以为过了这一年进步很大，考场上总以一种拿前3的目标去打，然后越想不出来，就越急，越急，思路就越乱。比如这次D2T2，参数很多，如果思路急是一定不可能想清楚的。但我由于一开始看错题浪费一个小时，导致只剩两小时左右时就紧张了，思路开始混乱。其实考场上我已经想到了优化费用流，如果我冷静下来，得到80分算法完全没有问题的。这次NOI让我第一次感受到，考场心态真的很重要。
这次NOI没有一题是我得心应手的，暴露了我的实力和心态方面的诸多问题。可以说是IOI前的一次教训。
这次月赛打得不好。传统题难度不大，就是最后一题比较码农。最后区分度主要在Challenge上，然后我Challenge切不动，就滚粗了。
做的时候也几乎是倒着做的。
如果是判断两个序列排序后是否相同，这等价于判断每个数出现的次数是否相同。把每个位置上的数 $a$ 用项 $x^a$ 表示，就转成判断区间和的多项式是否相同。随机质数 $x,p$ 然后在模 $p$ 意义下判断多项式的值是否相等，取 $2$ 个模数基本上不会错了。
但这题要求允许一个位置不同，怎么办呢？
我的想法比较naive就是了。。。用 $c_1[x],c_2[x]$ 分别表示第一个和第二个区间中 $x$ 出现次数，那么两个区间similar的条件是或者 $c_1,c_2$ 相同，或者 $\min\{x|c_1[x]\ne c_2[x]\}=\max\{x|c_1[x]\ne c_2[x]\}$。
考虑如何快速求 $\min\{x|c_1[x]\ne c_2[x]\}$，可以二分 $x$，然后判断 $c_1$ 和 $c_2$ 的前 $x$ 项是否都相等，把 $c_1$ 和 $c_2$ 前 $x$ 项对应的多项式（模意义下）的值搞出来比较就行了。
至于怎么搞出来呢，其实要算的是这个东西：
$$\sum_{l\le i\le r,a_i\le k}x^{a_i}$$
用可持久化线段树前缀和维护每个前缀的区间多项式值，将 $r$ 的线段树与 $l-1$ 的线段树相减后在其上二分即可求出 $\min\{x|c_1[x]\ne c_2[x]\}$ 和 $\max\{x|c_1[x]\ne c_2[x]\}$。
复杂度 $O((N+Q)\log A)$。也许有更优做法……？
一道比较裸的数据结构码农题……
树枝之间构成了有根树的结构。用 $W_v$ 表示结点 $v$ 目前还能再承受的重量，初始状态下，$W_v=w_v$。
对于第1种操作，在结点 $u$ 上挂 $x$ 的重量，那么断开的结点是 $u$ 的祖先中最深的一个 $a$，满足 $W_a < x$。断开 $a$ 相当于把以 $a$ 为根的子树内的重量清零（即对结点 $a$ 进行第2种操作）。如果没有结点断开，则 $u$ 及其所有祖先 $v$ 的 $W_v$ 值都会减少 $x$。
对于第2种操作，将以 $u$ 为根的子树清空，记目前以 $u$ 为根的子树的总重为 $U$，即 $U=w_u-W_u$，该操作将以 $u$ 为根的子树中的结点 $v$ 的 $W_v$ 恢复为 $w_v$，将 $u$ 的祖先 $v$ 的 $W_v$ 增加 $U$。
这两个操作可以用树链剖分线段树来维护，复杂度 $O(n+m\log^2n)$。由于题目要求可持久化，要用可持久化线段树。区间修改的标记最好永久化，可以省内存。（我用的 unsigned 自然溢出，比较两个数时判断两数的差是否不大于 $10^7$，感觉卡不掉）
写起来细节好麻烦啊……前后总共花了大概一天才切掉这题。（当然也有可能是我太菜了）
（论连写两题可持久化线段树是一种怎样的体验）
用 $P$ 表示质数集合，$e(x,p)$ 表示最大的 $t$ 使得 $p^t|x$，则要求的式子是
$$F(L,R,X,Y)=\sum_{i=X}^Y[i\in P]\sum_{j=L}^Re(a_j,i)=\sum_{i=X}^Y\sum_{j=L}^R[i\in P]e(a_j,i)$$
考虑构造一个矩阵，矩阵的第 $i$ 行第 $j$ 列为 $[i\in P]e(a_j,i)$，由于 $10^6$ 以内每个数最多 $7$ 个质因数，因此矩阵中非 $0$ 的数不超过 $7N$ 个。
接下来就是询问子矩形的数值和，把询问转成
$$F(L,R,X,Y)=F(1,R,1,Y)-F(1,R,1,X-1)-F(1,L-1,1,Y)+F(1,L-1,1,X-1)$$
就可以离线之后用树状数组做。时间的话，$(7N+4Q)\log_2a_i\le 2.2\times 10^7$，可以接受的。
感觉很迷的一道题，数据范围这么小似乎就是个暴力题？
暴力枚举两个集合 $i,j$，$O(len_i+len_j)$ 判断两个集合并集是否为全集，总复杂度就是 $O\left(\sum_{i=1}^N\sum_{j=1}^N(len_i+len_j)\right)=O\left(N\sum_{i=1}^Nlen_i\right)$。还可以 $i$ 枚举较大的集合，$j$ 枚举较小的集合，如果 $len_i+len_j < K$ 就不判，省掉至少一半常数。
什么……这就能过了？？？
这题感觉很像NOIP2015普及组T3。。。
做法也相当简单，稍微化简一下式子
$$\sum_{x\in A}\sum_{y\in B}\sum_{z\in C}[x\le y][y\ge z](x+y)(y+z)$$
$$=\sum_{y\in B}\sum_{x\in A,x\le y}\sum_{z\in C,z\le y}(y^2+xy+yz+xz)$$
$$=\sum_{y\in B}\left(y^2\sum_{x\in A,x\le y}\sum_{z\in C,z\le y}1+y\sum_{x\in A,x\le y}x\sum_{z\in C,z\le y}1+y\sum_{z\in C,z\le y}z\sum_{x\in A,x\le y}1+\sum_{x\in A,x\le y}x\sum_{z\in C,z\le y}z\right)$$
把三个数组从小到大排序，然后从小到大枚举 $y$，用Two-Pointers技巧维护最大的 $x\in A$ 满足 $x\le y$ 以及最大的 $z\in A$ 满足 $z\le y$，同时维护 $\sum_{x\in A,x\le y}1$，$\sum_{x\in A,x\le y}x$，$\sum_{z\in C,z\le y}1$，$\sum_{z\in C,z\le y}z$，就做完了。
复杂度 $O(p\log p+q\log q+r\log r)$。
这题我想了挺久的样子，当然也有可能是我太弱了
直接做不好做，先推几个结论。以下用 $(C,S)$ 表示大小为 $C$，和为 $S$ 的集合。
结论一：存在最优解，只有一个集合的和非负。
证明：假设存在两个集合 $(C_1,S_1),(C_2,S_2)$，其中 $S_1,S_2\ge 0$，合并两个集合，得到 $(C_1+C_2,S_1+S_2)$。
新的带权和为 $(C_1+C_2)(S_1+S_2)=C_1S_1+C_1S_2+C_2S_1+C_2S_2\ge C_1S_1+C_2S_2$。
所以可以把非负的集合两两合并，总和不会变少。
结论二：存在最优解，除了和非负的集合以外，每个集合最多包含一个元素。
证明：假设存在集合 $(C,S)$，$C>1,S < 0$。不妨设 $x$ 为集合中的元素，且 $x < 0$。则将集合拆分成 $(C-1,S-x)$ 和 $(1,x)$。
新的带权和为 $(C-1)(S-x)+x=CS-Cx-S+2x=CS+(2-C)x-S>CS$。
所以可以将和为负数且包含多个元素的集合中的负数拆分出来，总和不会变少。
推论：最优的集合划分方案一定是一个包含所有非负数和若干个负数的集合 $X$ 与其余的只包含单个元素的集合。
枚举 $X$ 的大小，把非负数全部放入 $X$。接着考虑哪些数要放入 $X$，由于放入 $X$ 的数的系数不小于 $1$，而不放入 $X$ 的数的系数等于 $1$，故应把最大的几个数放入 $X$。
最后写法是，将序列 $A$ 排序并预处理前缀和，然后枚举 $X$ 的大小 $k$，把后 $k$ 个数分一组，前 $N-k$ 个数每个分一组，用前缀和 $O(1)$ 算答案。
复杂度 $O(N\log N)$。
（感觉这题有更好的分析方法啊？这题只是第三题啊我怎么做得这么麻烦啊？）
水水的纯数学题，不想写题解了。
#include<cstdio>
int main(){
int T,U,V;scanf("%d",&T);
while(T--)scanf("%d%d",&U,&V),printf("%lld\n",(U+V)*(U+V+1ll)/2+U+1);
}水水的智商题，不想写题解了。
#include<cstdio>
int main(){
int T,n;scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int x=500;n--;x--)printf("%d%c",x," \n"[!n]);
}
}刚掉这些题以后，最后剩下两题ES和SBTR。看了下题，感觉不太可做。
求 $\sum_{i=1}^n\lfloor ei\rfloor$，$n\le 10^{4000}$。等等——代码长度限制1KB？！FML？
C++不可A，钦点我们要用Java或者Python这些自带高精度的语言。。。还好我会那么一点儿Python。。。
一开始想是不是要利用 $e$ 的性质而不用求出 $e$ 的高精度近似值，后来想想觉得没救。因为如果这题能做，$n=10^{4000}$ 的答案减去 $n=10^{4000}-1$ 的答案就能得到 $e$ 的高精度近似值……嗯也许这题做法很暴力qaq
继续想，感觉似乎见过类似的题，好像强上类欧几里得算法可以搞过去？
接着就
from decimal import *
getcontext().prec=1000接着 $e=\sum_{i=0}^k\frac{1}{i!}$ 暴力算出 $e$ 的小数点后1000位，然后用类欧几里得算法搞搞搞。。。至于这么搞呢，大概就是考虑函数 $y=kx+b$ 的图象在 $x\in[1,n]$ 区域与 $x$ 轴之间的整点个数，一开始令 $k=e,b=0$，然后每次先把 $k,b$ 模 $1$（同时累加上模掉部分的点数），再把坐标系转90度，把原点移到原来坐标系的 $(n,\lfloor kn+b\rfloor)$ 位置，一直迭代就行啦。
调了很久调过样例，又调了一会儿参数轻而易举把 $n=10^{100}$ 跑过去了，正欢喜的时候测下 $n=10^{4000}$……TLE飞了……
算了先交拿个50分再说，接着想办法优化= =
然后你懂得本sb干了什么事情，各种优化运算次数调精度甚至一边迭代一边把 getcontext().prec 改小什么的都用上了，就是要跑好几十秒，没救2333
接着觉得这题不是什么类欧几里得能搞过去的，就继续想……然而并没有想出更好做法= =b
然后，某天晚上突发奇想，类欧几里得的原始形式不是 $y=\frac{ax+b}{c}$（$a,b,c\in\mathbf{Z}$）吗？如果把 $e$ 写成分数不是就不用 decimal 了？而且从NOI2016上学到的知识，分数类跑得比高精度小数快……
嗯！这样一定会快很多！
然后重新写了一发分数版的类欧几里得算法，居然直接AC了，2333
一看虽然这题时限是2s但Python时限10s，于是我的程序7s+跑过去了……感动……
做完9题以后终于可以专心搞Challenge了。。。
唉。。。说多了都是泪。。。姿势水平不够最后只有89.918分，被fjzzq2002等大爷怒踩。。。
看完题，发现如果转成补集，就是求最大点权和树形导出子图。然后看数据类型，
1、$N\le 20$，暴力。。。
2、$N\le 40$，好像暴力要加一些剪枝？
3、$M=N$，基环外向树，枚举删掉一个点？
4、$M\le N+3$，好像做法差不多？
5、$M=\frac{N(N-1)}{2}$，这不就是取一条边吗。。。
6、Wheel Graph，不懂
7、Random Graph，没啥思路
于是开始刚 $N\le 40$，想着想着想到我的集训队论文上去了，感觉可以只搜极大树形导出子图，用Bron-Kerbosch算法思想，维护两个集合，一个是当前选的点 $S$，一个是剩下的允许加入的点 $U$，每次枚举一个 $U$ 中与 $S$ 相邻的点是否加入 $S$，如果不加入则从 $U$ 中删掉。
这样可以不重不漏枚举所有树形导出子图，然而没法只搜极大……可是这并不像极大独立集那样可以找个点Pivot来优化复杂度……
不管了先写一发，然后和大暴力拍没问题，很好……随机几组 $N=40$ 的数据……啊，跑了4s……
然后想用点度递增序作搜索序什么的，写完发现跑更慢，GG。
不是很会优化，先交吧至少能过第一个数据……卧槽爆0了？！
TLE了。。。算了明天再看什么情况
……
第二天起来，对着代码看了一会儿，加了个优化，把 $U$ 中加入 $S$ 会成环的直接从 $U$ 中删掉，这样剪枝能剪更彻底些，然后不管怎么随机的 $N=40$ 的数据都秒出了，妙。再交……又爆0了？！
WA。。。
论WrongAnswer为什么叫WrongAnswer。。。查了半天的错根本没查出有错，然后判了个如果 $K\le 40$ 就跑搜索，否则直接输出0。然后，就有分了？【虽然只有1.6分并没有什么卵用】
看了下评分方式才知道怎么回事——我TM又没认真读题！评分是按照每个点的答案之和的倒数给的（？），怪不得挂一个点就全WA……【不过我还是想吐槽这种奇葩评分方式】
又打了个完全图的取一条边，分似乎没多的样子……
感觉要多分得先把随机数据搞过去……怎么乱搞呢？就这样：把搜索改成随机贪心，用BFS，每次随机一个能扩展的点扩展，多次随机取最优。尽管我也不知道这样能不能搞到足够优的解……
不过还是得试试。写了一发交上去，竟直接97分了！接着我又打了Wheel Graph和基环外向树，Wheel Graph知道是什么以后就是枚举中心取不取然后环上取最值，很好写，基环外向树统计每个子树的点权和之后删环上最小的。打完交，意料之中地分没变。
然后准备打 $M\le N+3$ 的点，看起来也能用我的论文的做法解决，然后就想怎么DP，并没有好的想法设计DP，不管怎么都处理不了连通的限制。接着开始想缩边，把度为1的点往对面缩，再把度为2的点缩成链，一条链表示成一条边，要在边上记这条链上的点集，然后外面枚举关键点，里面跑个类似MST的东西，细节非常多。。。这东西immaotalCO写过，调了一晚上才调出来。我写了一个多小时以后意识到不太可写，就删了。
看来这题的关键就在怎样做随机数据。
接着继续搞随机图，首先是把多次随机弄了个卡时，效果似乎不错的样子= =接着我试着把卡时的时限改大本机上跑，发现会不断地出更优解，就尝试优化随机化的常数。。。当然是没用的咯，因为没啥可优化的。
根据之前乱搞的经验，贪心经常比随机化优秀——比如CTSC2016D2T1，贪心每个点有3分，随机化基本没有，我考场上两种都试了一下，于是部分分拿满了2333 如果把随机化换成每次加入一个点权最大的能加入的点呢？这样只要把BFS队列换成优先队列。来，std::priority_queue<int> 走起……
测了下发现怎么贪心的答案比随机化要大不少啊，有点惨啊是不是贪心比随机化更劣啊？？索性全删了。
又尝试了几种乱搞姿势还是不给力。接着突然意识到我程序求的是补集，那么更大意味着更优啊？？？我的脑子呢？？？
重新写了一遍优先队列贪心。交上去，分数变低了……为什么？我自己测的数据不都是贪心更优吗？
不管了我两个程序各跑一段时间，交上去分数多了不到1分……但我觉得贪心应该比随机化优很多啊，并不是很懂。
最后还想继续搞点分，并没有想到好的方法。前面一堆人99+分，我怎么都只能排到rank 15……
当然，Challenge最后是有重测的。
重测完我的分数变成了89.918分。
当然，别人分数也变低了，于是我名次上升了。
最后fjzzq2002 990.338分rank 7，我989.918分rank 9，ccz181078 989.907分rank 10，peehs_moorhsum 989.854分rank 11。rank 9~11的分差真是小，果然OI有时候需要运气……
然而再怎么好的运气依旧掩盖不了我不如初中生的事实= =
就要IOI了，再这么弱下去怎么行？刷的题还是太少，多刷题才能积累经验啊。
帖子公开得有点晚。
可以说很失败。
开场看A，感觉二分代码有点奇怪，不知道题目有没问题，就去看B。
B一眼想到一种做法，每个数建一个点，相等的放同一层，得到一个分层图，问有多少种连边方案使得图是一条链。看了下 $n\le 30000$，相同的数不超过 $100$ 个，也就是每层不超过 $100$ 个点，觉得挺靠谱。
然后就开始推，结果被细节恶心到了。我的想法是按一层一层顺序把边加进去，状态 $f(i,j)$ 记前 $i$ 层构成 $j$ 条链的方案数。然而是链不是环，还得记前 $i$ 层有没包含起点和终点，于是搞了个这个玩意：$f(i,j,s,t)$。
然后思博了，中间填边的时候，我以为给 $j$ 条链每条确定一个前继节点一个后继节点就行了，然后发现有环，接着就懵逼了好长时间。
想了好几种解决方法，可惜都是错的。
于是回头看A，看了讨论知道二分代码没错，那一定是我理解错了，我平时的二分习惯相当于代码里面的 $l$ 减掉 $1$，$r$ 加上 $1$ 的。
这样就好理解了。然后又想错了，一开始想到把二分结构的线段树建出来然后DP，发现线段树的节点长度只有 $O(\log n)$ 种，准备写个STL的 map 来大力DP一波。
于是开始写转移，写着写着突然发现不妙，题目求的是 $r=k$ 的概率，我连我要求啥都没搞清楚，靠。
然后继续想，发现DP只有一条路走下去，那就只要乘法原理就行了，没必要DP。接着写完主过程发现要求 $n!$，然而 $n\le 10^9$……
打表大法好，把 $(10^7i)!$ 打出来就做完了。终于在21:30左右过了A。
再去看C，这种题似曾相识的感觉（用myy的话说就是deja vu），好像强上笛卡尔树就行。然而我并不知道两个序列的笛卡尔树怎么弄。
就YY了一个分治算法，$f(l,r)$ 求 $[l,r]$ 内的满足条件的区间个数，如果 $[l,r]$ 内 $A$ 的最大值不等于 $B$ 的最大值，沿着大的那个分成两个区间递归下去，否则，设两个最大值在 $i,j$ 位置（$i < j$），那么 $l\le i,j\le r$ 的 $[l,r]$ 都满足条件，然后加上 $f(l,j-1)+f(i+1,r)-f(i+1,j-1)$，递归下去算。
以为很靠谱，然后准备写，写前想想这玩意儿复杂度是个什么东东。——糟糕，炸了。
如此重要的比赛一定得开个帖写一写。
第二次参加CTSC&APIO，考得不好，我还是太弱了。
练习赛出了NOI2016原题，预示着CTSC2017会出原题？好像是的。
看完三题，感觉T1很可做，T2挺好理解，T3有点复杂。然后发现T1的下发输入库不见了，就在一直看T3，感觉也比较可做。于是等T1的库下发（居然要手打，差评）以后就把T1写掉了。接着研究T2，一开始以为是一道AKF出过校内训练的TC题，然而那题我并不会做，而且复杂度还过不去。当时就写了个 $O(n^2d)$（$d$ 为树的深度）的25分暴力，由于代码能力太糟糕，写了很久。接着觉得似乎能二分，然而对于所有点对的约束并不会判定。后来想到去年IOI题，然后发现题目不太一样，当时以为加边两端点都在直径上是错的，就觉得不一样，扔了。
最后推T3，由于没认真读题就开始想，一开始想成求满足条件的概率，然后写了很久的线段树维护概率，也写了很久。写到快写完时发现不对，是求满足条件下的期望。这时候我有点懵逼，不过把转移看成图，就变成求带重边两点间路径长度的平均值，用线段树维护路径条数和路径长度和就行。
写完T3过掉样例只剩1h-了。感觉精度有点虚，不过出了几组数据都没炸精，也不知道怎么卡，就当得分玄学吧。最后稍微拍了下T1，另两题也没拍就结束了。
出考场fateice说T2结论就是在直径上，哎我好菜啊为什么不出几组数据找找规律。matthew99做出了T2，然后表示T3很容易炸精度，好方啊。
看成绩100+25+100=225。。。这个T3居然过了。。。然后看到matthew99 AK了（原来是matthew99以为数据里有0和1然而实际上题目保证了没有，好像还有别的原因），yjqqqaq 250，还有几个和我同分的。T3好像一点也不卡精，确实直接写就能过。
immortalCO有点惨，T3以为会卡精度改成暴力结果掉了30。。。fateice更惨，好像挂在了和去年wwx一样的地方，一个地方没看long long，T2挂成0分，T3数组开小挂了20，悲伤的故事。当时我非常庆幸我在测T2样例时在后面补了几个0
讲题时听说T2把直径结论搞出来就是IOI原题了，感觉如果我能看出这个结论可能可以多拿25分以上。
感觉今天T1、T3加起来再加上T2暴力分属于大众分吧，没啥好说。
下午开始感觉身体有点乏，开始担心明后天的表现。
答辩自我感觉还行，然而出成绩#13滚粗，让人心碎。也不想说什么了。
晚上和immortalCO一起看了几道题，结果我没想出来一题，immortalCO倒是都做出来了。尽管暂时成绩单上我是#3，但和前后几名的分差相当小，做好了明天被打回原形掉出前6的准备。
和immortalCO一起很早就睡了。
唉……搞了这么久OI还是只会暴力打打，没救了……
最近没有一场比赛打得爽，互测Round 5 GG，校内训练GG，Codechef GG，省选GG。本来想打打51nod出点气，结果TM又崩了。。。
51nod被两道码农数据结构恶心了一脸（应该是我太弱），F题写了个 $O(n\log^2n)$ 的东西被卡常数卡内存，然后才发现做复杂了。最后。。。被9min绝杀，#11滚粗。。。真是不爽。
以下是本人参加51nod算法马拉松24的滚粗过程。
开场看题，A一开始没懂，跳过，看B。
B一开始猜贪心结论，每个尽量往后选，然后随手叉掉了。看 $n\le 20$ 奥妙重重的样子，似乎暴力状压DP可过。
于是10min+的时候把B题过了。
C一开始以为是丧题，感觉数据范围这么大一定有什么性质。先猜足够大的图一定有解，然后发现死活没法把一个格子取反，才发现怎么弄xor和都是0。。。
于是猜想足够大的图有偶数个1就行了。为了验证这个规律，写了个暴力高斯消元观察规律。。。好像确实是这样2333
然后特判了 $n=1$、$m=1$、$n=m=2$ 的情况就切掉了C题，大概30min+？
D目测套路题。。。推下式子 $\sum_{i=1}^n\sum_{j=i+1}^n\sum_{k=1}^{j-i+1}sum_{i,j,k}$，$sum_{i,j,k}$ 为区间 $[i,j]$ 前 $k$ 大和，再推一下变成 $$\sum_{i=1}^n\sum_{j=i+1}^n\sum_{k=i}^ja_k\cdot rank_{i,j}(a_k)=\sum_{i=1}^n\sum_{j=i+1}^n\sum_{k=i}^ja_k\sum_{t=i}^j[a_t\le a_k]$$
$rank_{i,j}(x)$ 表示 $x$ 是 $[i,j]$ 里面第几小的，假设所有数互不相同。于是交换下求和顺序 $$\sum_{k=1}^na_k\sum_{t=1}^n[a_t\le a_k] (\sum_{l=1}^{\min\{k,t\}}\sum_{r=\max\{k,t\}}^n1)=\sum_{k=1}^na_k\left[\sum_{t=1}^k[a_t\le a_k]t(n-k+1)+\sum_{t=k+1}^n[a_t\le a_k] (n-t+1)k\right]$$
两个和式BIT搞搞就 $O(n\log n)$ 做完了。然后在1h左右的时候过掉了。。。
接着开E。然后就进入了SB时间。。。一开始想直接弄个DFS序然后按深度奇偶性分成两个序列，接着发现操作3的LCA询问不会做。然后感觉LCA的条件很不好搞，似乎用距离来做更好做一些？于是作死时间开始。。。$dist(a,b)=dep(a)+dep(b)-2\cdot dep(LCA(a,b))$，通过构造边权使得 $dep(a)=a$，然后变成询问某点到所有黑点的距离和。接着继续作大死。。。树分治一波看看能不能搞出来，接着脑补了好久的树分治发现并不会做= =
浪费了好久，回头考虑别的做法。对于每个询问，如果把 $\sum_{i=1}^nLCA(i,x)$ 换成 $\sum_{a=1}^n\sum_{x=1}^n[LCA(i,x)=a]$ 呢？然后发现 $\sum_{x=1}^n[LCA(i,x)=a]$ 并不是 $a$ 子树内的点数。。。如果强行按子树内的点来算呢？那就把LCA和它的所有祖先全算上了。如果构造点权 $v_a$ 使得 $a$ 到祖先的所有点的点权和等于 $a$ 呢？
好像问题简单了些。。。记 $s(i)$ 为 $i$ 子树内黑点数乘以 $v_i$，查询只要查 $x$ 到根的路径上 $s(i)$ 的和。似乎可以强上树剖线段树，然而信息不是很好维护？又纠结了一会儿无果。
看了下好多人过了A，就回去看A，终于正确理解题意了。列了几个方程发现 $n$ 偶数才有解，有解的时候外圈填 $1,2,\cdots,n-1$ 内圈列个方程，似乎直接解出来了= =然后就过了A。
回去研究E树剖以后怎么维护线段树信息，但搞不清楚，于是准备第二天起来继续研究。
……
鄂公网安备 42010202000505 号Server time: 2024-11-21 14:46:56