UOJ Logo WrongAnswer的博客

博客

WAer的THU集训

2016-12-04 13:35:37 By WrongAnswer

这里是老是写挂题的WrongAnswer弱渣= =

作为一位无实力选手,当然要直播THU集训是怎么揭露本渣的辣鸡实力的2333


Day 0

很早起来赶飞机,到了以后赶去hotel,最后由于塞车等缘故还是没在报到结束前赶到hotel,啊好惨

尼玛,immortalCO整天都在说我是猫,啊我不是猫啊啊啊


Day 1

上午8:10开考。看了看题。

第一题,居然是TopCoder SRM 561的第二题,我的集训队作业啊= =然而原题数据范围是 $N\le 50$,这题是 $\sum N\le 200000$……

有啥好的性质吗?想了想并没有什么好的思路,敲了个60分暴力去写第二题。

第二题是个题面题……看了好久的题面才知道意思是啥……

发现题目是把 $b$ 求了个 $m$ 维前缀和,直接倒过来对 $c$ 做个差分就做完了,代码好短,让我一度怀疑做法是不是对的。

开始看第三题,怎么有种HNOI的既视感QAQ然而丧多了2333

没思路啊,只会暴力,连只有插入都不会做。那好吧还是写30分暴力,写完了交上去。

这时候10:00,开始研究第一题,准备打表找找规律,手动出了几组数据发现Grundy函数怎么有点奇怪??才发现有个地方vis标记忘了打……

还好查出来了。接着又猜了几个结论都是错的。弃。去检查第二题。

写了个checker对拍,拍了数十组WA了一组,发现有个细节没处理好,及时改对。

想了想我到底该搞第一题呢还是第三题呢,第三题没思路,还是弃第三题搞第一题吧……既然没有啥性质难道就是暴力用个数据结构维护?看到时限2s空间1G似乎明白了什么。

剩1h,开始写Trie合并。

最后10min写完了,结果样例没过不知道哪里狗了……尝试最后几分钟debug出来然而失败了……

出考场估分60+100+30=190。

10分钟后进考场看结果,60+100+0=160。

第三题爆0啦~滚粗啦~然后听说大家都是230,CJK挂了10分,220。似乎挂得最惨的也比我高?

完了要垫底了QAQ退役愉快?

后来和CJK讨论了才知道第1题Trie合并哪里写错了。合并的时候子树大小没有从子树push up而是直接加,于是有重复节点就GG了。另外节点数组没清空。果然我功力不足啊。

下午讲题,果然前2题一堆人A。我的1和3都没到平均分。然后又得知第1题有原题。

惨。

大家都230,而我只有160,少的这70分如何拿回来?没有了,拿不回来了。


Day 2

今天运气比较好。

一开始看了三题,感觉第三题特别麻烦,第一题有点像模板题(?)感觉很多人都会A,第二题是个有趣的Manufactoria提交答案题。

想了想决定先思考第一题。感觉 $f$ 的次数很低的时候可以 $O(1)$,次数很高的时候似乎有和 $m$ 有关的做法?

于是打了个表……$m=1$ 的时候 $Q(f,n,x)=nx$,$m=2$ 的时候不知道是啥,不过是个关于 $n$ 的二次函数……那么 $m=3$ 的时候是个三次函数?一般情况是 $m$ 次函数?

假装这个结论是对的于是插值了一发,发现计算 $Q(f,0,x),Q(f,1,x),...,Q(f,m,x)$ 每个就要 $O(m)$,总共就 $O(m^2)$ 了……看了下数据范围有90分感觉很满足了就不继续想了

写完过了前两个样例,最后一个样例没过=-=仔细一看发现有个地方爆了 int,改完过了样例,感觉90分是稳了。

再看第二题,读了很久的题,试了一会儿怎么搞,发现不太好搞,还是先写第三题暴力回来搞第二题吧QAQ

第三题敲了个不知道复杂度是多少的树形DP,写的时候一堆 for 循环,很怕写错,不过写完样例居然一遍过了?测了下 $n=Q=1000$ 的随机数据,很快就跑出来了。然而还是有点虚。

继续分析了下,似乎正解是加个虚树的优化,然而要处理链上的连通块,细节好多啊,而且还有可能TLE。反正我肯定写不完= =果断弃。

开搞第二题。之前很快把测试点1、2、3搞出来了(2的KMP调了一小会儿,还好调对了),接着搞4发现很麻烦,等会再来搞~测试点5也很水,6呢……?能识别的串没几个?那我就把所有串建个Trie吧(雾)接着发现串长最大可以到 $377$,超过 $300$ 了,靠。

等我搞出测试点6的时候 sim 了一下,发现 a 忘了判- -及时改对。然而由于我太菜了测试点7没想到什么靠谱做法。

测试点8、9、10看起来就觉得很复杂,那好吧我先去考虑测试点4= =b

一开始想到了在模意义下做,于是设计了一个模 $m$ 从 $m-1$ 到 $0$ 的时候cricket一个 [,从 $0$ 到 $m-1$ 的时候cricket一个 ]的做法,结果发现复杂度是错的——如果在 $m-1$ 和 $0$ 附近一直转移就呵呵了,看了下离比赛结束只有1h左右了,好虚啊要是搞不出来真的要GG了……然后经过思考,想了一个把 $m$ 个节点扩展成 $2m$ 个节点的做法,令 $m=100$ 然后把这个结构复制 $3$ 份就做完了?然后发现节点数爆了,就令 $m=20$ 然后把这个结构复制了 $5$ 份……测了一下数据990000+。好险。

这时候时间不多了就把第二题交了。交了以后继续看发现表达式和括号序列一样做法= =就把测试点4的结构稍微调整了一下得到测试点8的答案,再把测试点8的答案原样复制了一份作为测试点9的答案就交了,想想81分也不错了,就不继续搞了。

最后十分钟在检查,对拍了第三题感觉没什么问题,比赛就结束了。

n+e过来说我今天206,过了一会儿看到成绩果然是95+81+30=206。第一题 $m^2$ 居然多过了一个点?(虽然标程也是 $m^2$ 的)第二题搞的点全A了。终于没有挂了。

问题是,昨天少了70分,今天多20分仍然翻不回来啊QAQAQAQ

immortalCO是猫!WrongAnswer不是猫!


Day 3

只剩两天了,希望能不留遗憾吧。

一开始看了下三个题。

第一题:我会暴力!很快把暴力码完了,然而……暴力才10分……

第二题:我会暴力!很快把暴力码完了,然而……暴力也才10分……

第三题:字典序最大……这不是个最大生成树吗?看起来有反例的样子,如果不是简单路径的话……题目意思应该是简单路径,那就是个加边维护MST?可是我不会啊TAT

于是码了个MST的暴力,看子任务,有一部分数据是 find 都在 move 之前的,这样的话只要把MST建出来,转成子树加深度来搞?看起来很有道理,于是就花了大概1h写LCA+树状数组。看了下也有70分了,剩下的感觉是LCT之类的麻烦东西,实在搞不动。(感觉CJK这题要AC了)

拍了下感觉没问题。回去搞前两题。

第一题可以矩阵乘法,可惜也才20分。剩下的 $3^m$ 有点大感觉很恶心,不太会。

感觉第二题似乎更可做一点?那好我就搞第二题吧。想了下如果枚举了特殊牌的顺序接着怎么搞?看起来就是每个元素都有一个最右边的位置,然后问有多少种排列方法。这个似乎可以用一个多项式复杂度的递推完成,然而要枚举排列……经过思考决定改成状压DP,然而复杂度实在太糟糕还是只有30分……

接着开始考虑优化状压DP,结果是越想掉坑越深,更可怕的是我并没有意识到想法方向错误。决定换个思路想想:答案会不会是关于 $w_1,w_2,...,w_n$ 的多项式呢?好像有道理,来我推个式子,好像式子有一定对称性?接着想用一个递推来计算系数。接着意识到由 $w_i$ 构成项的个数也是指数级的,弃疗了。

11点多回头搞第一题。由于花了一个多小时搞第二题却只得了30分,心态不好,有点急躁,于是推第一题的时候很紧张,就怕是个水题,然而我时间不够了啊QAQ

通过打表找规律,发现矩阵中不同的数好像只有 $\frac{(m+1)(m+2)}{2}$ 项,而且好像有循环性质。再分析了一下意识到矩阵只要存第一行。以为这样能多不少分(虽然后来发现只多了15分),于是花了一会儿把第一题改成只存矩阵第一行,再交。接着在想能不能把矩阵优化到 $\frac{(m+1)(m+2)}{2}$?然后就做完了?

果然我还是太naive。缩完矩阵以后似乎要做个奇怪的求和变换,不会了。

最后滚回去检查第3题,和暴力拍了好几组 $n=1,001$,$m=3,001$ 的数据没出问题,接着出了一组大数据RE,于是非常感人地发现我改暴力的时候有个 $3,000$ 的数组忘了改成 $300,000$,及时改好。好险啊差点70分就没了。

看了一下今天只有35+30+70=135,哎好惨要滚粗了啊。

最后就这么135分滚粗了。出考场CJK说第3题不就是个裸的LCT吗?卧槽,看来要被甩30分了=-=接着看到第2题被yjqqqaq想了个线性做法A过去了

rank1 yjqqqaq 240,rank2 HalfSummer11 195,还有一堆170+、160+……看了下榜连前15都没进TAT

讲题的时候发现我真是无比傻逼。第1题我没搞出来的那一步是个FWT,然而我并没有深入研究。

更可惜的是,第2题!我!后!来!的!想!法!是!对!的!——唯一不对的!就是以为指数级一定过不了!实际上40的划分数很少!

一个多小时的努力,已经十分接近正解,却在最后弃疗了,失去了得70分的机会。

(UPD:据说这个做法会被卡常数成50分,看来丢的分没那么多)

不过也没什么好说的了,毕竟自己确实没有前15的实力,也许考场上就算想到这一步也不一定能写对。


Day 4

最后一天。希望能不留遗憾吧。

首先看了下三道题。第一题NOIP加强版,裸数位DP,估计全场AC。第二题看起来像个点分治,估计半场都要AC。第三题是个几何题,看起来是个要么基本没分要么拿高分的题。

于是先切了第一题,由于实力实在太菜,写错了好几个地方,调了好久才对。

犹豫了一下到底第二题和第三题要先写哪题,觉得第二题部分分比第三题简单些?先敲了第二题的20分暴力。打算先写完第三题再看情况是写第二题100分做法还是部分分做法。

写的时候感觉很有压力,毕竟几何题容易挂。大致整理了一下就是 $S$ 和 $T$ 连边,$S,T$ 和每个圆连切线的边,每两个圆连公切线的边,每个圆的切点按顺序连成一个环,求最短路。随后感觉没那么简单,因为切线不能和别的圆相交。

所以还要和圆判交,暴力是 $O(n^3)$……算了就写这个吧反正就算不能A应该还是有很多分的。

开始写。先定义了点和边的 struct,定义了几个基本函数,敲了输入部分(经过思考决定把所有几何量开 double),敲了个Dijkstra最短路,然后把主过程一个个打好。打到一半的时候发现我的线段和圆判交写成了直线和圆判交,日哦……改改改,改完了。

全写完后测一发样例,什么鬼第一个样例WA了?有点慌,把图打出来看,发现一个 y 打成 x……过了第一个样例,再测第二个,尼玛又WA了?好紧张啊都10:30了……没时间做第二题了啊……

还是把样例一的图再打出来看看吧,接着对着样例说明的图看了看,发现外公切线求对了,内公切线求错了- -调好以后过了样例二。交上去了。

这时候只剩1h+,开始研究第二题,推出一种做法:二分一个 $M$,判断是否存在一条路径满足 $|\frac{sum}{len}-k|< M$,即

$$(k+M)\cdot len-sum>0$$

$$sum+(M-k)\cdot len>0$$

就把每条边的权值 $w_i$ 改成两个权值 $(k+M-w_i,w_i+M-k)$,判断有没有两个权值都为正的路径。接着想到了用点分治解决,对每个点记到根的路径上的两个权值和 $a_i.b_i$,把权值序列取相反数以后和原来的权值序列归并排序,转化为对每个原序列 $i$ 判断是否有 $j < i$ 且 $j$ 属于相反数序列且不在 $i$ 同一个子树内,以及 $b_j < b_i$。每个子树记一下 $b_i$ 最小值。也不知道有没问题。

然而点分治写不动啊……曾经在省选的时候花了3h写了一道点分治导致时间不够于是爆炸,UR14第一题也掉坑花了90+min写了点分治导致时间不够挂了第二题,前段时间打Codeforces写点分治也写了好久没写出来。看着只有1h的时间,决定放弃正解,写几个部分分。

先写了 $(i,i+1)\in E$ 的点,二分完就是个离散化树状数组。交上去之后又写了 $(1,i)\in E$ 的点,做法差不多。写完后和暴力拍了若干组没啥问题,交了。

最后检查了下第一题,又检查了下第三题样例构的图没问题,就弃疗了。

最后出成绩——尼玛我第二题怎么才40?!炸了呀,点开一看发现只A了前8个点,后面那一档部分分全WA了……

还好T3数据水送了我90分。于是今天就100+40+90=230了。

出考场发现大家分数都比我高,immortalCO 260,philipsweng 235……然后听说C_SUNSHINE大爷AK了。

这是滚粗的节奏啊……

看了总榜,前6名分别是C_SUNSHINE、matthew99、philipsweng、yjqqqaq、syf、immortalCO。

immortalCO FJ全省rank1,全国rank6,劲啊。

还好我由于Day2的优势并没有掉出前15。希望WC能稳一点吧。


回去调Day4的第二题,测了几组数据没问题,为啥会挂?

难道是我数组没开够?

……果然,我把 $a$ 和 $a$ 的相反数放在一起离散化一共 $100,000$ 个数,然而有个数组只开了 $50,000$,于是挂了……

附一段对话:

WrongAnswer:问题是没有RE而是WA……

JOHNKRAM & yjqqqaq:正常

JOHNKRAM:你开的数组刚好是连续的

再调Day1的第三题,看了一会儿还出了几组小数据都觉得没啥问题,怎么就爆0了呢?

仔细一看我的暴力求LCA是这么写的:

while(dep[i]!=dep[j]){ // 正确应该是 while(i!=j)
    if(dep[i]>dep[j])i=fa[i];
    else j=fa[j];
}

while(dep[i]!=dep[j])!!!我怎么连暴力找LCA都写狗了啊QAQ

最后打算把这几天把集训的题都搞懂。希望UOJ能加上清华集训题。

评论

lkmcfj
前排%%%
chentong
前排%%%
ruanxingzhi
前排%%%
Menci
前排%%%
Sengxian
一刷新就更新了233333333
fjzzq2002
中排%%%
dick32165401
中排%%%
wyh2001
到底谁是猫
ppfdd
d3T2写正解可能会被卡常数成50分(雾
matthew99
mathhew99是谁,难道比matthew99还菜吗
AntiLeaf
后排%%%
cxzxxjd
前排%%%

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。