雅礼集训2018-1

Jan 15, 2018 12:59 · 54 words · 1 minute read stuffs DP

D1

上午讲题,下午练习赛T1和T3都是我见过的题。T1考虑prufer编码随意dp一下,T2是个博弈大讨论,注意不要漏情况,T3是个玄妙的dp。

我那台机的键盘真是让人无比不爽,退格键得要准确地敲中正中间才能按下去,而且其实敲中了还是比较费劲,有的时候甚至要两根手指发力。

D2

考得挺不满意的……看了一遍题之后马上觉得T3很可做就去BB,但实际上我并不擅长这种博弈大讨论。T1是一个结论题,我推结论的时候用到了去年WC的时候jc(?)讲的一个结论,可是一开始记错结论了,还好后来想起正确的结论然后成功AC。T2是我做过的一个题目的模型的加强版,可惜我掌握得还不够熟练所以没想出来,可能也有一部分原因是做题顺序不对导致T3浪费太多时间。

总的来讲今天的题目不算太难,我的发挥还是欠缺稳定。

D3

讲字符串,发现自己还是过于naive。fft不止可以算$\sum (a_i-b_i)^2$这样的东西,有必要的话可以算$\sum a_i b_i(a_i-b_i)^2$。

我写的hash屡次被卡自然溢出/被卡常数/卡自然溢出也卡常数,于是我终于下定决心学了一下倍增……

D4

t2和t3都不难,结果变成了拼t1……

我已开始也想到应该是要IDA*什么的,然而想不到好的估价函数,后来BB出来一个巨恶心的$O(n^{??})$的DP,完全没有调试的勇气,所以我也不知道它对不对……

D5

讲仙人掌和线性代数。仙人掌只是讲了圆方树,嘴巴起来还是不太难的。线性代数讲得其实挺友好的,学习到了bzoj3569这样给边赋随机权值这样的技巧,以及如何在线性基里面删去一个数。求积和式是一个np的问题,所以以后如果想做法的时候发现可以规约到积和式,那可能就得观察特殊性质/考虑换一个做法了……

D6

炸了炸了……

t1注意到转移的时候需要快速计算差分,据此想到把k次幂拆成下降幂。可是……我没有想到……

t2正解是树套树,因为正解常数比较大,放到dfs树上做一个在线莫队也是可以的。然而我没想到把颜色也分块,以为过不了,最后写了个kdtree……于是我得到了比标算更大的常数!

我:我的程序在本机跑了3s,不过我的本机是奔腾的。

出题人:没关系我的也是。

我:!!??

后来跑了下测试数据发现最慢的要12s……

D7

肠胃炎

D8

再次爆炸……

t1这种区间覆盖关键点的问题,可以把区间的端点都离散到关键点上面。标算的思路是按左端点排序然后依次考虑每个区间对dp数组的贡献。hsz的做法是容斥,f[i]表示钦定i不被覆盖前面不一定后面一定不被覆盖的方案数,然后$f_i=-\sum_{???} f_j$。感觉这两种思路都挺妙的可以学习一下。据说多做做atcoder可能可以提升dp水平?

t2我都想到鹦鹉那道题了我居然还没想到做法。$C_{2n}^{n}$增长得很快所以可以用2n个元素的n元集来编码一些东西。

t3是个贪心。如果想到要考虑权值最小的点,剩下想起来是不难的。我一开始就像对于任意一个点,它下面的节点要按什么顺序,自然就想不出来了……以后想不出来的时候一定要记住试试从极特殊的情况开始考虑。

D9

讲数论,感觉讲得还是不太难的。什么时候认真学一学类欧几里得算法。

下午练习题的t1挺有启发性的。莫队算法中,因端点变化造成的修改有$O(n\sqrt{n})$次,但查询只有$O(n)$次,所以莫队要套一个数据结构的话,$O(1)$修改,$O(\sqrt{n})$查询的分块往往比都是$O(\log n)$的数据结构要好。同样的思路也可以运用到在线莫队/带修改莫队/强制在线带修改莫队上。

D10

肠胃炎各种想吐,于是开场就决定战略性放弃一题,然后就放弃了据说最简单的t3……

后来看了看发现我并不会??研究了一下发现一个东西。在dp里面,其实答案也可以看做以为状态,以此题为例,就有了三维状态:a卡到多少位,b卡到多少位,还有c串长度。发现前两维的变化都比较复杂,而第三位的变化比较简单,选择较简单的两个作为状态表示,剩下一个作为答案。

D11

讲数据结构,感觉不难。

D12

今天我的发挥真的很差,题目本身是不难的,但是我总是差一点点才能想到。

T1我的思维方向是完全正确的,但是最后统计两端贡献的时候,大概是因为太心急之类的原因,我没有注意到那个式子可以拆成T个数的和乘上T个数的和,而不是T^2个积的和。另外就是set的常数比较大需要手写个链表什么的。

T2我已经成功地证出了竞赛图在不强连通的时候一定是一个全序集,但是没有想到原图可以强连通缩点。缩点之后还需要一个很强的结论,就是强连通的竞赛图一定有长为3,4,5,…,n的环(n为点数),这个其实挺好猜的,我的证明思路,也就是归纳,也是正确的。这说明我对竞赛图的处理技巧还不够熟悉,以后多注意注意吧。另外如果无环的时候有一些比较强的结论的话,要考虑一般情况可以试试缩点。

T3我已经证出了所有需要的结论,我已经意识要到把左端点看成1,右端点看成-1,而且1和-1一定构成括号序列,题目对于l,r单增的条件是为了保证每个括号序列与操作序列一一对应。这个时候直接dp就可以了,但我偏偏在想用组合数直接解决,最后还是没推出来。以后做题的时候,推出一些结论的时候,要看看它有没有什么“计划之外”的作用,因为一开始的思考方向、一开始希望这个结论起到的作用不一定是对的,说不定这个结论就可以用在别的方向上从而解决问题。

加油吧……

D13

被题面坑了……很多时间被我拿去想所谓的“不太难”实际上最难的题目……

t1黑白点分开考虑贡献,都是可算的。

t3利用分治来dp的思路挺妙的,因为c直接处理非常不方便,接着发现从小到大排序之后就可以保证一些性质,所以每次选择c最大的点分治。

D14

传说中最难的一天?emmmmm……