UOJ Logo WrongAnswer的博客

博客

退役之战——IOI2017

2017-07-25 08:19:10 By WrongAnswer

退役前的最后一战。

挺紧张的,毕竟我NOI只有#40+,就算把Day2挂掉的66分加上还是只有#20+。不止一题脑抽差一点想出来还是相当不爽的啊。

毕竟还是运气选手唉= =

以及我现在考场心态还是太糟糕。

不过作为国家队的最后一名,我也没有什么太多的梦想吧。保Ag争Au吧。

orz matthew99,xumingkuan,cy。


7月25日

入住酒店。

刷了CEOI2016D2T1。想了一个比较复杂的做法不知道有没更简单的做法。

NOI同步赛成绩单出来了,作为Day2挂成114分的国家队垫底选手,看着被一大堆人虐感觉也是很奇葩的。(然而同步赛FJ Day2最高分居然也就114?大家都考跪了?)

和xumingkuan住一间。

晚上宋老师带全队四人去McDonald吃了点零食,顺便和另外三人聊了些题目怎么做。深刻感觉我水平低得可怜。


7月26日

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题滚粗。我并不能跟上国家队的平均水平。


7月27日

动员会。没什么好说的。


7月28日

在飞机上坐了大概10h,意识模糊。

下午Exhibition,没什么好说的。


7月29日

练习赛。

就是之前做过的题,不过只有2h,来不及AK。

T1用我论文里面的独立集搜索算法拿了70分。虽然说正解更好写但是懒得写了。

T2水题切了。

T3水题切了。

T4提答,暴搜搜出4个点,又搞了4,5两个特殊点,拿了60分。剩下的点没时间搞了。

70+100+100+60=330

明天就是day1了,为自己加油。


7月30日

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到很迟才回宾馆。

现在想想我也已经无所畏惧了。反正国家队最后一名,拿个Ag也没有什么关系。以及FZYZ这么多年都没出过IOI Au,我拿Au岂不是做梦。再说,退役一段时间以后,我拿Au也好,Ag也罢,总是会被遗忘的吧。


7月31日

Exhibition。

本来很好看的,一想到D1T2就没心情了。

如果是实力Ag也不觉得遗憾,然而明明会做的题却因自己作死浪费时间最后来不及调出来导致Ag,就十分遗憾了。


8月1日

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,感觉没有谁同时拿过这三个成就了。


8月2日

上午去water park,以为自己退役了无所畏惧了,还是被某大型水滑梯吓怕了。后来玩了几个小型的。

下午Exhibition。


8月3日

闭幕式。

颁奖按排名从后往前的,然后我是Au上去的第二个。

又开始后悔D1T2了。


8月4日

考挂滚粗回家。

退役了。


CJK猫,CJK强,CJK是FZYZ的红太阳

尽管immortalCO就要上大学了,但immortalCO永远是FZYZ的红太阳。

退役前的最后一个月

2017-07-15 10:52:13 By WrongAnswer

感觉我的高二并没有什么进步唉。。。省选Day2连滚两题被翻,WC提答滚粗,CTSC Day2爆炸,APIO被虐。。。依旧一堆题不会做。。。


LOJ NOI Round

Day 1

和省队集训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

和省队集训Day 2冲突,没时间打。吃完午饭回宾馆想rush一下T1的75分,没rush出来。

期望得分0+0+0=0,实际得分0+0+0=0。

垫底了。

最后两天总分258。Au线364,Ag线283,Cu线216。拿了个Cu。


省队集训

作为非省队选手参加了省队集训。。。果然被屠了。

Day 0

省队互测,大概是15个省队队员加我一个非省队,每人准备一道题完成讲解。(大概是看我去年进了省队但去年没互测于是就给了我这个机会,十分感动。。。于是我成为参加互测的最差选手)

萌萌哒aufeas姐(额好像不能这么称呼。。)第一个上场,dp优化网络流真有趣。虽然她的题我好像不到一小时做出来了。。。

张队长和初三大佬zzq的字符串题也好劲啊。作为不会**自动机的选手在听wrz和张队长题时只能当吃瓜群众。

victbr的原创题也很强。表示我也掉了分块坑。

闫神太巨了,出了一道神级结论题,做法是转成图论问题然后怎么怎么解决。第一步都没看出来的我表示一脸懵逼。。。

猫锟强,临场讲了好几题的更优算法。(然而一直说我是猫说yhx是猫说wrz是猫是什么鬼啊。。。

yhx和ct讲的都是猫锟出的模拟赛题。

作为非正式选手的我最后一个讲。。。讲的是我去年出的校内模拟题。做法很sb,没用什么算法,就是打表找规律然后构造。。。感觉我是最菜的出题人。。。

讲题时台下很欢乐。

zzq现场切了我的题,写出来了。

不得不说现在的省队爷都好劲啊,技不如人甘拜下风。整个听讲过程我不是在膜出题人就是在膜锟膜闫神膜zzq,然而只会膜不会提高自己姿势水平有什么卵用呢。就要退役了我还是啥都不会怎么办啊。

Day 1

出题人:猫锟(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。

下场加油吧。

Day 2

出题人: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位数组慢得要死。

Day 3

出题人:叶队长(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分,有毒。

Day 4

出题人:闫神(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了,直接判断一棵树是否可能是点分治树就行了,还面向数据找了那么久的规律,就跪了。想想我到现在还不会分析问题性质,吃枣药丸。

Day 5

出题人: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可做得多,以及我真的很蠢。

Day 6

出题人: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,我花大量时间想搞的题最后没有一题做出来。

不是自己退步了,就是别人进步得更快。

挺后悔自己高二没有认真刷题的。平时总觉得自己已经很努力了,然而一到考试才明白别人比我努力得更多。


CodeM 复赛

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)。感觉我打死也想不到。。。一定是我太弱了。

还是很好奇大家是怎么想出来的。。。

总结

构造题姿势水平不够,要多接触这类问题。


Codeforces Round #424 Div. 1

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题。当然也有可能仅仅是我这次的题我刚好会做。


NOI2017 网上同步赛

Day 1

滚粗。

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了。

Day 2

滚粗更严重了。

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前的一次教训。

Codechef 6月月赛总结

2017-06-12 19:17:15 By WrongAnswer

这次月赛打得不好。传统题难度不大,就是最后一题比较码农。最后区分度主要在Challenge上,然后我Challenge切不动,就滚粗了。

做的时候也几乎是倒着做的。


Cloning(CLONEME)

如果是判断两个序列排序后是否相同,这等价于判断每个数出现的次数是否相同。把每个位置上的数 $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)$。也许有更优做法……?


Persistent oak(OAK)

一道比较裸的数据结构码农题……

树枝之间构成了有根树的结构。用 $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$,感觉卡不掉)

写起来细节好麻烦啊……前后总共花了大概一天才切掉这题。(当然也有可能是我太菜了)

(论连写两题可持久化线段树是一种怎样的体验)


Chef and Prime Queries(PRMQ)

用 $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$,可以接受的。


Pairwise union of sets(UNIONSET)

感觉很迷的一道题,数据范围这么小似乎就是个暴力题?

暴力枚举两个集合 $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$ 就不判,省掉至少一半常数。

什么……这就能过了???


Triplets(SUMQ)

这题感觉很像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)$。


Chef and the Feast(NEO01)

这题我想了挺久的样子,当然也有可能是我太弱了

直接做不好做,先推几个结论。以下用 $(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)$。

(感觉这题有更好的分析方法啊?这题只是第三题啊我怎么做得这么麻烦啊?)


Xenny and Coin Rankings(XENRANK)

水水的纯数学题,不想写题解了。

#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);
}

A Good Set(GOODSET)

水水的智商题,不想写题解了。

#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。看了下题,感觉不太可做。

Euler Sum(ES)

求 $\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了。。。


Saboteur (Challenge)(SBTR)

唉。。。说多了都是泪。。。姿势水平不够最后只有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了,再这么弱下去怎么行?刷的题还是太少,多刷题才能积累经验啊。

失败者的辣鸡本质——记51nod算法马拉松25

2017-06-02 20:26:42 By WrongAnswer

帖子公开得有点晚。

可以说很失败。


开场看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

2017-05-16 22:20:35 By WrongAnswer

如此重要的比赛一定得开个帖写一写。

第二次参加CTSC&APIO,考得不好,我还是太弱了。


CTSC2017

练习赛出了NOI2016原题,预示着CTSC2017会出原题?好像是的。

Day1

看完三题,感觉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一起很早就睡了。

阅读更多……

51nod算法马拉松24 & LYDSY 5月份月赛

2017-05-01 14:25:17 By WrongAnswer

唉……搞了这么久OI还是只会暴力打打,没救了……


51nod算法马拉松24

最近没有一场比赛打得爽,互测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树剖以后怎么维护线段树信息,但搞不清楚,于是准备第二天起来继续研究。

……

阅读更多……

各省省选题完成计划(一)

2017-04-26 10:15:14 By WrongAnswer

最后一次FJOI滚粗,APIO也没考好,让我明白自己技不如人,需要多刷题。

打算先把各省省选题刷完。


SHOI2017(六省联考)

做完之后的感觉是难度偏小,出题人很良心,暴力送了很多分……省队线一定很高……

比较资磁的是数学题比较多。

D1T1:期末考试

数据范围 $t_i,b_i\le 10^5$ 直接告诉我们算法——枚举。

枚举最后结束的时间 $T\le\max\{b_i\}$,那么等待的不愉快度为 $\sum_{t_i\le T}(T-t_i)$。

考虑把所有 $b_i$ 调到不大于 $T$ 的最小不愉快度。假设先进行操作1再进行操作2,那么对 $b_i\le T$ 的操作没意义,所以操作2只对 $b_i>T$ 的 $b_i$ 减到 $T$ 有意义。假设先进行操作2再进行操作1,设 $b_i'$ 为操作后的 $b_i$,由于操作1不改变总和,故需要满足 $$\sum_ib_i'\le mT$$

即 $$\sum_{b_i'>T}(b_i'-T)\le \sum_{b_i'\le T}(T-b_i')$$

同时,满足上述条件一定能通过每次选一对小于 $T$ 和大于 $T$ 的 $b_i'$ 总共进行 $\sum_{b_i'>T}(b_i'-T)$ 次操作1完成。所以:

(1)如果 $A>B$,那么只用操作2最优,否则可以把所有操作1换成对减小的 $b_i$ 进行操作2,不愉快度为 $$B\sum_{b_i>T}(b_i-T)$$

(2)否则,如果 $\sum_{b_i>T}(b_i-T)\le \sum_{b_i\le T}(T-b_i)$,那么只需要做操作1,不愉快度为 $$A\sum_{b_i>T}(b_i-T)$$

(3)否则,需要先对 $b_i>T$ 的 $b_i$ 做 $\sum_{b_i>T}(b_i-T)-\sum_{b_i\le T}(T-b_i)$ 次操作2,再做 $\sum_{b_i\le T}(T-b_i)$ 次操作1,不愉快度为 $$B[\sum_{b_i>T}(b_i-T)-\sum_{b_i\le T}(T-b_i)]+A\sum_{b_i\le T}(T-b_i)$$

预处理前缀和可以 $O(1)$ 计算不愉快度和。复杂度 $O(n+m+\max\{b_i\})$。

阅读更多……

FJOI2017滚粗记

2017-04-23 18:25:41 By WrongAnswer

这场省选毁掉了所有我对好成绩的梦想。

8:00开场看题,T1貌似是可持久化Treap裸题,T2字符串DP似乎挺可做,T3居然是去年原题扩大数据范围,做过。

感觉这场很容易拿高分的样子,想想能A两题再写一题高分就稳了。

于是开场先做T2,求两个长度 $n\le 500$ 的字符串的最长公共回文子序列。一开始以为直接写就行了,结果发现复杂度 $O(n^4)$,还10组数据,没救。

想了想直接上序列自动机似乎复杂度很不满的样子,虽然是 $O(n^5)$ 不过好像能有很多分。

于是花了半个多小时码完过了样例,自己出了几组数据没问题。

再做T3,写了十几分钟过了样例测了几组大数据就不管了。

这时候自信T2拿到高分T3 AC了,觉得只要再AC T1就rank 1稳了。这时候9:00,然而FJOI是4h所以还剩3h= =

最后决定放弃后两题的对拍开始搞T1。T1的意思是这样的,维护一个序列,支持插入、区间翻转、区间第 $\lceil\frac{m}{2}\rceil$ 个最大值下标查询、区间满足 $a_i>a_{i+1}$ 的 $i$ 之和查询、区间满足 $a_i< a_{i+1}$ 的 $i$ 之和查询。这种和两侧有关的信息似乎很难维护。

不过还是硬着头皮开始写了,先码个可持久化Treap……嗯,要维护哪些信息呢?结点的值,子树的最大值以及最大值个数,前驱的值,后继的值,子树中满足 $a_i>a_{i+1}$ 的下标之和,子树中满足 $a_i< a_{i+1}$ 的下标之和,以及翻转标记。

然后写 pushup,写写写……写完了。

然后写 mergesplit,写写写……写完了。这时候代码已经100行了。

然后在前面加了个翻转 revpushdown,每次操作 pushdown。接着开始写修改,写着觉得常数好大,不过 $n$ 范围是 $50000$ 可能不虚。

……

终于写完修改、翻转、查询了~已经11:00了,然而FJOI是4h所以只剩1h了= =

嗯我测一下样例,果然……没过……

把树打出来看,发现几个地方写炸了,改改改,改了好久,终于调过了样例。

11:30。不知道会不会出事情。

于是赶紧写了T1的暴力拍,一拍就错。

手算了下发现暴力写挂了,还好。

改完暴力继续拍,又拍出错了,而且错在十几行。

这回真的是正解写挂了。

阅读更多……

关于UOJ上奇怪的RE问题

2017-04-18 17:33:40 By WrongAnswer
int f[100][500000];
int main(){return 0;}

这段代码在UOJ#1的自定义测试上,程序有一定概率正常结束,有一定概率Runtime Error。

感觉这个问题很奇怪啊,理论上没爆内存的吧。而且有时候正常有时候RE是为什么?

2017年4月比赛记录

2017-04-03 11:46:44 By WrongAnswer

马上就要FJOI二试和CTSC了。然而FJOI二试迷之延时至下旬。CTSC就是下个月的事情。比较紧张。


51nod算法马拉松23

这场比赛做得很不及时。

4月1日听到同学讨论才想起有51nod比赛,然后点进去看已经有9个AK了……赚钱基本是没戏了。那就试着做一下呗。点进去第一题,觉得是结论题,然后自信有解就把 $x=\frac{\pi}{6}$ 代入,直接找出循环节,然后写了几个 if 不检查直接交就A掉了……挺送分。那么再看第二题,好像推个式子就行了然而 $m\le 10^7$?输入有点爆炸唉我先码个输入优化,码码码,OK了,然后推了个 $\frac{1}{m}\sum_ia_i$ 的式子交上去结果只过了第一个点……囧……

这么短代码要错肯定是结论错咯。看下题发现题意理解错,每次生成都要加进答案,再推了一波让人难以置信的是答案居然和输入的 $a_i$ 无关。。。???然后读入两个 $n,m$ 输出 $\frac{n(n-1)}{2m}$ 就过了?就过了?输入优化都没删。。。怎么都是纯数学题啊2333【讲道理这种题出在数学考试都是可以的

然后看第三题,一开始理解错以为要枚举小的对大的分段,好像还得分块,还不能处理图的情况,觉得做不了。immortalCO问我答案是不是就是次大值,我当时想到某道CF题觉得不太可能吧看了下那道CF题,发现一个条件 $a_i > a_j$。。。靠,读错题了。那看来真的是严格次大值无误。然而想了很久还是搞不清楚怎么对每个点 $v$ 求能到 $v$ 的点权中比 $v$ 的值小的最大值,好难啊先扔了。

这时候dick32165401他们好像在刚D题,就去看D。

一开始觉得状态要记原点到6个点的最短路,这样状态数至少 $O(m^6)$ 了……思考了一会儿明白了相邻两格最短路差不超过1,那就是 $100^2\times 3^5$ 级别的状态数了挺能接受,转移的时候就枚举下一列的状态,总共 $100^2\times 3^5\times 2^6$ 好像能过,就写了一会儿写完了。交上去WA掉。发现 $n,m$ 又打反,尼玛我怎么老是犯这种毛病啊QAQ第二次就过了。

这时候好像有10人AK了。惨。

E题一开始想分治之类的东西结果毫无进展,一定是我想复杂了。然后看着式子联想到一道自己出过(其实是我出完以后在BZOJ看到一模一样的题)的区间逆序数,好像只能分块搞,不过这题离线所以写个莫队+BIT好像能卡过去……然后写了一会儿写出来,接着你们懂的本SB又是过了样例WA飞了,为啥?immortalCO:你输出的时候 unsigned long long 开了没?我:没……

感觉正式比赛出这种情况就真的毁前途。看F。一开始想了想暴力怎么写,然后写完交上去想验证暴力正确性结果除了第一个点全是大数据,我去。。。不过样例和第一个点过了应该就没错了。接着开始用莫比乌斯反演推式子,推了一会儿推出一个 $\sum_{i=1}^n\sum_{j=1}^n[(i,j)=1]$ 状物,我想这应该就是 $2\varphi(n)-1$ 吧,验证了下好像是对的。接着式子就变成了分段求区间次大因数和以及区间 $\varphi$ 和,后一个好像有原题上个杜教筛容斥就行,$O(n^\frac{2}{3})$,问题是前一个怎么求不是很会= =

然后想暴力该怎么写,就是埃氏筛法,好像和筛法函数长得很像?接着就开始推筛法函数的DP,推了几步发现中间某一步要求 $\sum_{i=1}^ni^K$,$n$ 又很大,好像只能强上插值了……于是目前的想法是“插值+容斥+DP”三合一,感觉会很难写很难调。

然而好像拉格朗日插值没逆元,还是写 $O(K^2)$ 的牛顿插值吧,然而并不会牛顿插值的式子,上网搜了一堆资料结果半懂不懂的,决定自己推,然后推对了……RP不错,接着开始写,写完一测发现萎了。。。怎么回事?调调调。。。卧槽我的方法用到了除以阶乘然而阶乘不一定有逆元,日。。。

最后还是只好质因数分解保平安了2333写完以后开始写容斥求 $\varphi(x)$ 前缀和,由于一开始忘记预处理 $\varphi(1)=1$ 导致怎么都是错,也费了好多时间。终于开始写筛法函数了,一开始还把定义搞错把质数也筛掉了,后来觉得不妙才改了,然而还是出一堆问题。接着两三个小时发现一堆bug,一个个改完以后终于过样例了,然后第一个点WA了,又调了一下发现丢了一个 pow

结局是艰难地过掉了F。。。感觉这种难度的题我还得折腾这么久我这迟早要完啊。。。

然后C还是不会做。。。4月2日起来继续想,想了很久一直往强连通分量去想,结果不知道怎么提取第一个比自己小的权值,还是做不出来。最后想出枚举权值区间floodfill再把这个权值的点去掉,求出每个点能到达它的不等于自己的最大权值,又想想觉得不对= =于是改成floodfill搞出每个点能到达它的最大和次大权值,这样就靠谱了。于是12点多把C题过了。论最后想出来的是C题是一种怎样的体验2333

最后rank14 GG,可能我早点开始打也不太能进前10。

看完题解之后

C题原来缩强连通分量以后直接递推一发就做完了,不知道我当时在想什么

E题分块做好像就能不带log了,当然莫队把BIT换成分块维护好像也能优化掉log(不过好像更难写就懒得优化了)

F题居然可以多设几个函数来搞,不用插值了……不过不知道常数会不会大


集训队互测 Round 1

开场看T1,感觉得推什么复杂的式子,不知道有没结论,于是先写个随机模拟打个表再说,然后发现 $k=1$ 时答案全是 $0$。看下子任务居然有 $k\le 1$ 的部分分,难道是我写错了?再看 $k=2$ 的,发现是 $\frac{m(n-1)}{n^2}$,这个应该有分……好我写一写,交。

交上去居然是 Invisible,这不科学啊一定是OJ的问题……于是OJ修了一会儿看到结果,才5分= =然而怎么右边显示了标准输出?趁着工作人员修OJ的时候调代码,然后发现期望忘记除以方案总数了。。。接着又看了看表看出 $k=3$ 是 $\frac{m(n-1)(n-2)}{n^3}$ 感觉挺稳,觉得答案应该就是 $\frac{m(n-1)(n-2)\cdots(n-k+1)}{n^k}$,接着发现 $k\ge 4$ 就挂了……

算了先交 $k=3$。看到得了45分就放心了。然后试着推通用的式子,然而每次计算是 $O(m)$ 的,而且怎么都化简不了。先放一边。

接着去看T2,这题不出意外一定是JOHNKRAM的题,联想到WC时的仙人掌计数……已经不打算想正解了,那就写 $O(n^2)$ 吧。

推了一下好像得预处理 $i$ 个点的强连通图个数?然后就开始想,想到后面以为只要求这个了,又想到清华集训2014的主旋律,然而我并没有A。。。然后又是线上比赛,不如找一份std对着写?点开以后意识到问题并不是这么简单……

继续推,发现主旋律做法还是有用的,然而接着处于掉坑状态,想了非常久还是没想出怎么做。后来干脆考虑每种图会被枚举到多少次,接着就好像会 $O(n^2)$ 了,只要DP出每种点数的和合法图个数,然后枚举源点集合大小加起来就是答案了。

写到210min的时候终于写完,居然对了。70分到手,有点开心。

最后看T3,好像是个比较麻烦的题,感觉我不可能做出来了,就写了个15分暴力交上去。交完以后发现 $K\le 5000$ 可以离散化啊= =就写了离散化交上去,发现前面WA掉了。。。原来是数组开小了2333

改完以后想多捞点分,就想 $q=0$ 可不可做,似乎只要找出每一列最后一次被染色的时刻然后按这个顺序做一遍,不需要什么复杂的数据结构就搞定了,不过不太确定能否写对。不过还是试着写写吧……

最后10min终于调过样例,交上去。后来看到自己这题得了50分,挺满意的了。

然后还想rush一下T1的另外15分,结果没时间了。

最后45+70+50=165,出榜以后发现我这一堆暴力加起来居然有rank 2……有点爽。再看下其他人,好多大爷都是刚某道题没时间做别的题,然后送了我这个机会……所以我实力还是不行的。

看完题解之后

xumingkuan的T1好神奇啊。题解里讲了“有可能出现的情况是找出 $k=3$ 的答案公式,与 $k=2$ 时的答案公式形式相似,试图推出一个普适的规律,然而发现 $k=4$ 时这个规律就挂了”,这不就是我的情况吗2333

也许学过stirling相关知识这题就能多做一些分?我的姿势水平还需要提高。。。

JOHNKRAM的T2我可能需要多花一些时间理解。

zsyzssoft的T3可能细节偏多?然而场上2人AC,可能我还是没跟上大家的水平啊。


集训队互测 Round 2

还是开场看T1,以为直接状压就行了,结果 $O(3^nn^2)$ 写完一交才4分,好气啊,暴力分真少。优化一发,好像只要考虑包含某个点的集合就行了,再交,20分。分数这么低一定是我想偏了。

然后发现这题 $p=17$ 居然是给出的,一定是有什么很妙的算法,想到了Codechef的BIKE。那就只要一开始把所有式子DFT一下,乘的时候只要 $O(p)$,最后IDFT回来就行了。不过不太确定能否AC。

当然由于时间效率是 $3^{16}\times 17=7.3\times 10^8$,$3\texttt{s}$ 还是跑出来了……$O(3^np)$ 能过看来这题肯定大家都会。接着看T2。

然后就说明了我有多弱……一开始没注意到对 $M$ 取模,然后觉得好像可以网络流,正在想怎么建图的时候发现了要对 $M$ 取模,于是瞬间不会了。原本想二分贪心,结果发现二分也是错的。脑补了好几种贪心,结果全是错的,然后一点思路都没有了。

接着放弃T2去想T3了。一开始觉得条件有点复杂,不过如果枚举了 $m$ 就可以压位高斯消元了,$O(\frac{n^4}{w})$,这大概有30分。不过要跑 $n$ 次高斯消元,可能我有些性质没用上?

于是仔细分析了一下性质,发现 $m$ 每增加 $1$,就少一个约束,多一个变量,好像处理起来不方便。如果 $m$ 减少 $1$,就多一个约束,少一个变量,直接把最后一列删掉,然后用前面的行消这一行,这样复杂度就优化到 $O(\frac{n^3}{w})$ 了?不知道能不能60分的说。。。

接着开始写,写了挺久的,写完过了两个样例交上去,一直Waiting,就继续想第二题,还是没想出来。

测出来了,0分。点进去一看,全都是WA和TLE。

样例怎么这么弱啊,怎么过了两个样例都能爆0。。。难道是系统差?自定义测试一发,过了。

那肯定是我写挂了。写了个 $O(2^nn^2)$ 暴力拍,拍了一会儿拍出一个问题,改完以后过了对拍。交。继续想第二题,还是没想出来。

测出来了,0分。点进去一看,全都是WA和TLE。

这就尴尬了……无论如何都拍不出错怎么交上去就是0分?难道是我题目理解错了?

把 $O(2^nn^2)$ 暴力特判 if(n>20)return 0; 交上去。

测出来了,0分。点进去一看,全都是WA,而且都是0s。不可能跑这么快啊?难道是……数据……犹豫了一会儿把暴力的 gets(a) 换成 scanf("%s",a),交上去,10分了。估计是毛爷爷用Windows造的数据导致文件末有多余字符 gets 会挂,惨啊= =

再把原来的代码交上去,40分,中间TLE了。好像被卡常数了,开始优化。接着发现我数组开的 $50000\times 782$ 于是 memcpy 炸复杂度了……改完交了两发(有一发优化错了)一共经过7次提交终于过60分了,真是艰难。

最后1个多小时继续刚T2,然而除了 $K=1$ 的特判和答案小于 $M$ 的网络流以外都不会,我好菜啊……最后还是写了这两档一共25分,然而不明原因得了40分,而且9~11测试点还是WA的。好玄学,不过也没时间做什么了。

结果是GG了,100+40+60=200,rank 7。一看怎么大家都会T2,惨啊……果然T1大家都会,T3也有很多60。

于是就成了T2最低分选手。。。我做的题还是太少啊。。。

看完题解之后

cy的T1正解是 $O(2^nn^2p)$ 的,好像比较麻烦。。。(反正我没去想就是了)不过似乎 $3^{17-1}$ 和 $2^{17}\times 17^2$ 运行效率差不多的样子?

yjqqqaq表示他的T2是NOI第一题难度,想想我NOI2016 D2T1的分数……

T2正解是贪心+结论,最后一步用数据结构优化。然而我不仅没看出只要判断连续 $K$ 个数的结论,还没看出有解时答案为最大值的结论,更没有看出答案不超过 $2M$……可以说我是完全不会。另外好像直接输出最大值好像就有很多分???

matthew99的T3竟然真的是WC讲的Berlekamp-Massey算法……yyt16384 AC了好劲啊。

有空的时候我也学一学这个算法。


Codechef APRIL17

难得参加了一场Codechef。感觉这场比往常的都水啊,最后都是比谁Challenge分数高。

除了最后一题以外几乎是倒着往前做的。

Chef and Digits(DGTCNT)

一眼看觉得是个数位DP?仔细看下,原来是带了 $10$ 个约束的计数,约束这么少感觉容斥一波就行了= =先把 $[L,R]$ 转成 $[1,R+1)$ 和 $[1,L)$ 的差,求 $[1,N)$ 有多少个 $x$ 满足时,枚举 $x$ 和 $N$ 的LCP和第一个不同的数,然后容斥,枚举数字集合 $S$,要求 $\forall i\in S$,$i$ 在 $x$ 中恰好出现 $a_i$ 次,组合数算算就好,再乘上 $(-1)^{|S|}$ 就行了?于是一下子码完,肉眼调了几个SB错误,就过了第一个样例。

然后第二个样例一直过不去。自己出了几组小数据都没问题。

对着代码想了好一会儿终于发现哪里错了,我的做法假设 $x$ 和 $N$ 位数相同,于是把前导零算进去了!改……先强制最高位不能是 $0$……然后把之前的代码强制复制一遍,枚举一下 $x$ 的长度再搞搞……

然后过了两个样例,用暴力和正解拍了几组大数据就交了,一发AC。爽。

Bear and Random Grid(RNDGRID)

点进来就看到数据随机生成,题意大概是给一个有障碍的矩阵和一个操作序列,求从每个格子出发按这个操作序列走第一次碰到障碍或出界的时刻,粗略感觉随机走的话走几步就碰到障碍了,于是直接模拟2333然后发现不对劲,如果矩阵是空的就挂了- -

再想想这个做法期望复杂度是 $O(\frac{N^2}{P})$,$P$ 小的时候会跪。

不过 $P=0$ 的话没有障碍,就可以预处理每个点第一次出界的时刻。那么 $P$ 很小做法应该也类似。又想了想就明白只要对每个障碍和每个 $i$ 找出从哪个点出发走操作序列长度为 $i$ 的前缀能到它就能更新答案了,这么搞复杂度是 $O(N^2PL)$。

那就把 $P$ 以 $\frac{1}{\sqrt L}$ 分界一下就能做到期望 $O(N^2\sqrt L)$……然而我本机上调参用的是二分,于是二分出 $P=1.2\%$ 两个做法都是 $3.8\texttt{s}$ 左右,好像可以过就交了……

事实证明Codechef的运行效率比本机快得多,交上去一个点还不到 $1\texttt{s}$ 就AC了。

Stable market(SMARKET)

首先想到了游程编码一发,然后问一个区间的时候把两个端点所在的段取出来,判一判是否大于等于 $k$,查一下区间里有多少个不小于 $k$ 的段就行了吧。

整个思路无比显然。。查区间不小于 $k$ 的数先想到了可持久化线段树,然后发现这题可以离线,就用个BiT搞= =挺好写的。

然而我居然TLE了一发。。。??什么鬼,原来是数组忘清空了= =b想到去年NOI有些大佬D1T1本来高我5分因为这个错误炸成比我少85分感觉我还是RP选手= =

Chef and Divisor Tree(CHEFDIV)

一看 $B-A < 10^5$ 就知道可以枚举整数 $n\in[A,B]$ 然后求 $n$ 的答案 $f(n)$,一开始打了个表没看出熟悉的东西,就质因数分解一下 $n=\prod_{i=0}^{k-1}p_i^{c_i}$,$f(n)$ 就是每次把一个正的 $c_i$ 减掉 $1$,过程中 $\prod_{i=0}^{k-1}(1+c_i)$ 的和。联想到自己以前给NOIP组出的一道题就猜了个结论每次找个最大的 $c_i$ 减,再用之前打的表验证了一下感觉没问题。

然后懒得优化直接写了个 $O((B-A)\log^2B)$(可能有更好的上界?反正跑的挺快),结果过完样例交上去后面的点挂了。然后发现我犯了两个错误,一个是存质因数的数组用了 int,于是用 $\sqrt n$ 以内的质数分解完以后如果大于 $1$ 再把剩下的数加进数组就溢出了……另一个就不说了

for(int i=2;i<1000;i++)if(!a[i]){ // 于是1000~1000000的质数都没被考虑进去
    for(int j=i*i;j<=1000000;j+=i)a[j]=1;
    for(long long j=(L+i-1)/i<i?i*i:(L+i-1)/i*i;j<=R;j+=i)f[j-L][c[j-L]++]=i;
}

改完两个bug过了……

Bear and Clique Distances(CLIQUED)

把团上的点和一个附加结点都连上边以后就是裸的最短路咯,写写写,写完了,测样例,过了,交,AC。

Bear and Row 01(ROWSOLD)

一开始看错题以为是最小化的SB题,再想想原来是最大化,不过好像也很简单,猜个结论每次把最左边能右移的右移,好像没错,试试,写完,测样例,过了,交,AC。

Dish Of Life(DISHLIFE)

水水的模拟,先统计每个数出现次数,有 $0$ 次就是 sad,没有的话枚举删哪一个看看有没哪个次数会变 $0$。偷懒直接上了 vector

Similar Dishes(SIMDISH)

水水的模拟,然而偷懒直接上了 stringsortlower_boundupper_bound

Heavy-Light Decomposition(HLD)

终于来做最后一题了,不过比想象中要简单。

一开始瞎猜了几个贪心,每次取个深度最大的连重链,然后凭借多年写树链剖分的经验这样只要弄一条链然后从下往上依次在每个点挂长度为 $1,2,3,\cdots$ 的链就能叉掉。又猜是不是按子树大小贪心,发现在某个结点上瞎挂一堆叶结点就能卡掉。看来直接贪心会炸。

那就树形DP。一开始的想法是记 $f(i,j)$ 为 $i$ 上方的重链长度为 $j$,$i$ 子树内的最大cost。转移的时候枚举重链连向哪个子结点,好像能转移。一看数据范围 $N\le 100,000$……

于是又在想更靠谱的状态设计,如果 $j$ 改成定义为 $i$ 下方的重链长度呢?如果能够不遍历深度最大的子结点的DP数组复杂度就对了。链的长度怎么搞呢?那就令距离链的顶端 $1,2,3,5,9,\cdots,2^i+1$ 的重边和所有轻边长度为1,其它为0。接着开始想递推方程。

如果所有子结点 $c_1,c_2,\cdots,c_k$ 中,重链连的是 $c_m$,那么

$$f(i,j)=\max\{g(c_1),g(c_2),\cdots,f'(c_m,j-1)+[d=1\lor\exists k\in\mathrm{N},d=2^k+1],\cdots,g(c_k)\}$$

其中 $g(i)=\max\{f(i,j)\}$。至于 $f'$ 呢,是个好像有后效性的玩意。。。不太好做?

看了下AC人数感觉这题肯定不难,一定是我没想到点子上。

脑补了一下,发现 $c_m$ 肯定是 $g$ 值最大的子结点,那么只要记 $g(c_1),\cdots,g(c_k)$ 中的最大值 $g(c_m)$ 和次大值 $v$ 就OK了,一边DFS一边方案就确定了,$j$ 这一维都不需要了。接着就只剩快速计算 $i$ 到 $m$ 子树的点 $v$ 的最大cost了,因为只有当 $v$ 往上第一次到 $i$ 所在重链到达的点到 $i$ 的cost是 $1,2,3,5,9,\cdots$ 的时候才会加1,所以只要每个点 $i$ 维护这个点往下的轻边子树到它的最大深度 $d_i$,然后把 $O(\log n)$ 个点 $d_i$ 加1,就解决了。

看起来确实挺简单,就开始码了。因为懒得写不定长数组所以用了 vector,不过空间复杂度是 $O(n)$ 的,不虚。过样例就一遍AC了挺开心。

(CH) Serejs and Billiards(SEABIL)

体现我近似算法水平低的时候到了。

看完题,先想分数为正的有什么好的搞法,一开始想把球一个个打进洞,这样步数上界是 $2M$ 的。在想能不能先把球打到对角线上,然后一次全打进洞,就想到每列打一次把这一列的球全打到主对角线上,再把所有球一次打进洞,步数上界 $N+1$,不错的样子。写完得了60分。

再搞搞分数有负数的吧,感受了下如果不考虑球的分数正负的话实际得分期望是负的,不爽,得把负的都搞掉。然而把负的打到一个边角可能会把影响正的,经过思考,打算这么构造:负的球打到相邻偶数列,正的球打到相邻奇数列,接着把正的打到对角线上,再一次打进洞。这样步数上界期望大概 $\frac{M+N}{2}$ 吧,好像没什么优化余地了,就写了。

写完一交得了98.5分,以为这分数应该不错,结果一看榜怎么全是99+分的。。。GG。。。

最后1h还是没能搞出更高的分。。。最后rank 24滚粗,再见。。。


集训队互测 Round 3(围观)

因为这场由immortalCO、fateice和我出题,所以我不是参赛者而是观察者……

我出的是T3,一道槽点一大堆的提交答案题。

其实也没什么想说的吧。当然这场被很多人当成辣鸡比赛= =

不少人整场疯狂交T2(10个点,时限8s的题),有一段时间评测队列卡了五六个Waiting,卡评测严重。主要原因是这题 $n\le 20,000$,数据组数 $t\le 5$,$\sum n\le 70,000$,于是大家都想用 $O(n^2)$ 卡常数过掉……

由于我的T3下发的checker直接告诉了分数,于是大家不怎么提交,一般都是最后再交。不过悲催的是yyt16384最后没交上去,惨。。。

最后就是我的题估分大爆炸。当时给fateice验题的时候,fateice一小时做了6个点,当时还觉得现场好几个小时大家应该很容易上60的,结果。。。没人上60。。。【一定是fateice太强啦!

不知道会不会给人一种“FJ卡常队”的印象……去年AKF的集训队互测也有人被卡常数,今年呢,T1没人写正解就不说了,T2卡常数,T3也有人被卡了常数……T3 57分(最高分)xumingkuan有的点被卡了些结点个数的常数,于是少了点分,惨……

选个时间把这场放到UOJ上让大家玩一玩?


集训队互测 Round 4

开场看了下三题,觉得T1好像很可做,先跑一遍Manacher在每次指针右移的时候记下区间,就可以转化成每次询问右下角有多少个点。。。开始写的时候突然发现这个做法是错的。。。

然后开始fix,脑补了各种回文串的性质无果;转成后缀数组的每个后缀维护一个集合,区间插入一个数,发现集合难合并;考虑维护所有不同回文串的最左出现位置,不断删第一个字母,看起来很靠谱结果复杂度是错的……总之一共想了2个多小时还是一无所获。哎。

算了去想后面的题,第二题一开始想到 $[a,b]$ 的一个左子结点 $[a,c]$ 被覆盖的条件是 $l\le a\le c\le r < b$,写了个暴力交上去只有10分,原来我 $type=0$ 的也异或上一次答案了。。。算了我想想稍微不暴力点的做法。

发现这是个三维偏序,不资磁!不过 $a\le b < c$ 是个好性质,我们转化一下,答案是满足 $1\le a\le c\le r$ 的个数减去满足 $1\le a\le b\le r$ 的个数,再转化一下就是区间长度($r-l+1$)减去 $l\le a\le b\le r$ 的非叶结点 $[a,b]$ 个数,就变成了二维偏序了。写了一下发现结论没错,好像能做。

然而又要在线又要带修改……强上两个log吧。线段树套线段树?不资磁,空间是 $O(n\log^2 n)$ 的。那就线段树套……平衡树?虽然时间还是 $O(n\log^2n)$ 但空间只有 $O(n\log n)$ 了,效果也许不错?

于是就陷入了深坑。

15点多开始线段树套平衡树,到16点半的时候调出来了,交上去,60分。一看,被卡了8个点的内存。

惨。

我就在想,$64\texttt{MB}$ 可以开 $1.6\times 10^7$ 个 int,$200000\times 20$ 个结点,每个节点大概长这样:

struct snode{
    int val,siz;
    snode*fa,*ch[2];
};

如果每个节点是 $8$ 个 int 大小,那就起码 $128\texttt{MB}$,有点崩。然而明明只要查后缀区间为什么要写线段树?写个树状数组就行了啊期望还能省一半内存= =

于是又花了20多分钟改成了树状数组套平衡树,交上去,还是60分。。。

想了好久还是不知道怎么优化。至今不明白为什么连 $64\texttt{MB}$ 都卡不进去。

一看比赛只剩1h了,得赶紧写掉剩下两题暴力。

于是先写了T3的 $O(n\min\{n,m\})$ 暴力,一开始写错了一次,调了一会儿过了35。

又写了T1的 $O(n^2\log n+qn\log n)$ 暴力,20分。

最后又想多rush T3的分又想优化T2的内存,结果都没成功。

于是20+60+35=115滚粗。。。T2一堆100,只有我一个60。。。然而T2分这么低居然还有rank 4。。。

immortalCO T2标算AC,太强啦!

fateice T2神奇算法AC,太强啦!

看完题解之后

philipsweng的T1正解是回文树+分块,然而我不会回文树,哎我怎么这么菜啊

srwudi的T2确实带给选手们无与伦比的卡内存做题体验啊……不过说到底还是我自己的问题,我还!是!不!会!分!析!问!题!性!质!推了个二维偏序就不管了,最后GG……

线段树结点和普通区间相比有明显的规律啊,覆盖区间的结点一定是一段递增一段递减,然而我怎么就把问题给一般化了,问题一般化就丢性质了。。。immortalCO教导得是啊。

yyt16384的T3看起来不可做,当然也可能是我太弱了。


集训队互测 Round 5

血崩。

由于晚上熬夜出题,状态不好,看到题啥思路都没有。于是想想T1,好像是后缀自动机,然而我不会,于是写了后缀Trie的35分。又想想T2,好像可以FWT,结果细节考虑不清楚,怎么都是错的,最后调来调去弄了30分,不知道为什么2、3过了4没过。然后又去看T3,觉得是三合一的恶心题,没啥写的欲望。然后花了很久才写掉了第一个subtask。回头准备试着写SAM,然而考场上确实不应该写不熟悉的算法,还是放弃了。T2感觉造数据很麻烦,就盯着代码看,没看出问题。。。GG。。。T3的第二个subtask好像可以均摊搞搞,写着写着开始怀疑人生,觉得复杂度爆炸,于是不写了。。。最后还是把subtask3的裸暴力写了,然而前面的点莫名其妙地WA了,又没法Rejudge,就只剩25分了。

结果#9滚大粗。。。35+30+25=90。。。膜immortalCO 170分#1。

最后一次互测考成这样我对自己已经没什么信心了。大概我就只有rank 9的水平吧。况且最近也没时间刷题了,只能CTSC坐等GG同时围观immortalCO怒拿rank 1进国家队了。

看完题解之后

SkyDec的T1是继sone3之后的又一道神字符串题,不想做。然而把我的后缀Trie换成后缀自动机就有60分了啊……我一定要想办法学会后缀自动机。

qiaoranliqu的T2感觉自己状态好的话完全是可以想出来的,因为我前段时间学过FWT了。。。然而自己傻逼到盯着50分一直码写挂了还懒得调感觉我心态实在太糟糕。。。(也可能是晚上睡太少了)

sunyaofeng的T3后两个subtask正解好复杂啊,可是immortalCO说敢写暴力就能AC,orz……我纠结了好久的错误复杂度光荣滚粗……


FJOI2017 二试

一场挂得心碎的省选。

http://wronganswer.blog.uoj.ac/blog/2565

NOIP和省选一试优势全部浪没。失去了所有对好成绩的梦想。


51nod算法马拉松24

见另外的博客。

又好久没打Codeforces了,CTSC前如果有不在半夜的CF还是挺想打一打的。尽管打了有可能掉rating,但不掉rating怎么涨rating?

共 37 篇博客