GDOI 2020 赛前两周模拟总结

2020.6.9:

今天是LL的题。

  • T1推出了个式子,没想把它继续化简,这样可以更好算,或者换个思路直接用概率推也可以很好算,正式赛时可以想宽点。

  • T2跟着部分分很容易想到正解,挺好的。

  • T3是绝妙生成函数题,卡在了那一步。

  • 改题写ln、exp求快速幂时忘记把多项式的第0项化为1了,这个必须要化ln才有意义(虽然省选考的概率不高)。

  • 还把次数界开小了,多项式这些操作还要多开大一倍。

  • 今天没有挂分,因为全是计数,也对拍了。

2020.6.10:

今天是常高的LJ的题。

  • T1是集训队作业里的sb几何题,我没有做到。

  • 其实挺简单的,但我因为做法没有那么优美而爆long long了,在本机调了好久才过。

  • T2是傻逼trie树题,我因为有一步扩展时忘记标父亲而近乎爆0了(刚好对拍忘记测全1的数据),而且写复杂了许多。

  • 还因为传lazy标记时没有先判lazy不为0才xor下传而导致常数颇大而T了一个包。

  • T3是个打块题,弃了。

2020.6.11:

今天是sz的题。

  • T1是个线段树合并煞笔题,因为做法和题解不一样卡了好久空间才碾过去。

  • T2是个睿智贪心题,其实我做过转换后的问题,但是第一步转换错了,打出GG。

  • 得想想更加显然的转换。

  • T3发现单调后是个SAM+启发式的无脑码农题,因为太久没写SAM而写了1.5h,退步了。

  • 今天没有挂分,因为拍了,而且样例比较良心。

2020.6.12:

今天是zjk的题。

  • T1做过的任意长度FFT忘了。

  • T2第一步没想着合并,就想着分开做,结果做不出来,合并之后的部分是我做过的。

  • T3是个几何题,因为干T2所以没做,事实上(O(n^3))超显然,是我的水平可以做出来的。

  • 感觉今天精神不是很好,得调整调整。

2020.6.13:

今天是???的题

  • T1、T2傻逼题,T3神仙题。

  • T3没发现单调,不会做(k le 10^5).

  • (n le 10)是JOISC那种类似的思想,就是成了基环内向树(事实上最后的结论可以得到只有一条非环边),倍增或二分即可,然后写了,对拍了。

  • 结果有个算次数的地方没有(/m)能过对拍???

  • 后来发现是值域没有设对,(m>>h)导致起点不会绕圈,看来不能完全信任对拍,或者对拍造数据要认真想范围。

2020.6.15:

  • T1是个cf原题,再写了一遍。

  • T2是个字符串题,因为没有想到本质上是前面加一段、后面加一段,就可以SAM随便做做,就只有50分。

  • T3是个傻逼dp题,但是卡常很辛苦,最后加了个MTT才过。结果发现题目里漏写P是个质数,就可以直接插值就不用卡常了。

  • 因为今天的题是三题计数,T1又做过,所以不太能挂分。

2020.6.16:

今天打得和shit一样。

  • 第一题想过最优策略就是预先定一个阈值序列,但觉得这个太简单把它×了,又写不出暴力,没有好的样例,就GG了。

  • 第二题是图的点染色问题,缩二度点就很好写,但是我没见过,就写了5k容斥,最后一个地方忘记二项式逆展开,只有80分。

  • 还写挂了,实在是调不出来,待会儿看看。

  • 真相告破:1<<k写成了1<<n,虽然大样例的n很大,但是1<<(n)等于1<<(n%32),大样例n%32=20,刚好不会数组越界,大了答案不会错。

  • 第三题是个傻逼数据结构,时间花在第二题上了,没怎么看,其实好好想想45min就能敲完的,唉……

  • 注意三题都不太有思路时的时间分配策略吧,还有要抓住思路的一点点灵感。

2020.6.17:

  • 一看T1好神,T2是个简单题,T3没思路。

  • 但T2卡常的很,最后忘记逆元可以放到一起处理而导致常数颇大。

  • 写完T2回头看T1,想到一个判断方法,然后好像dp套dp就可以计数了?

  • 最后对着T3搞,关键性质没有推出来(感觉状态不好),推出来之后的就是一个经典分块+hash表的问题。

  • 最后几天调整一下精神状态。

2020.6.18:

  • T1是sb奇偶题。

  • T2没得想法,最后蒙了个(2^n)的做法,但却没发现(=2)就是个二元关系最小割。

  • T3忘了链可以直接点-边,事实上正解也是点-边改过来的。

  • 最后一场结束了

原文地址:https://www.cnblogs.com/coldchair/p/13073503.html