ZZXYY's blog

最后一个赛季了。。。

DAY-？

突然想到曾经忘记SAP怎么写的悲剧然后重温了一遍模版，然后突然想到有一个叫做平衡树的东西，然后简单复习了一下（然而）。

DAY1

哇纸质题目好评！

然后

第一题看不懂、第三题看不懂。。。。。。

第一题一堆错别字、第二题一堆错别字、第三题一堆错别字、第四题一堆错别字。。。。。。

出题人是不是今天凌晨想到今天是GZOI然后临时出的题啊！！！

好吧不管了，做题吧

t1:用半个小时一个逗号一个逗号的读题，总算是弄明白了，题目大意是给个a，求有多少个k<=n满足4(a+k)和a^2+k^2不是互质的。然后想推推公式试试吧。。。。。。然而十分钟后除了知道a如果是奇数，对一切奇数k都是成立的，如果a是偶数，对一切偶数k都是成立的，然后就没有然后了。于是想试试暴力，然后尝试输出了一下所有成立的k，当然我过滤掉了和a奇偶性相同的k。然后输入了个5 100，输出了这堆东西：

10 20 30 40 50 60 70 80 90 100

啊哈！

然后连蒙带猜归纳猜想出如果a是奇数，那么除了奇数的k，有且只有a的整数倍的k是成立的。

然后偶数也是类似情况。

那么分解质因数再来个容斥原理就搞定了，简单和暴力拍一下就ok了。（哇t1就说了这么多）

t2:题目挺好理解（然而在我正在写这东西的时候大家在讨论这题是算人数还是人次=_=），然后脑补了一下能不能DP，发现好像用f[i,j]表示前i+1个站点之间的空间放了j个设备的最大人次是有后效性的。但发现减去重复的人数只需要知道前面放了设备的空格是哪个站就可以了。然后暴力预处理是O(N^4)的。。。于是想预处理方法就用了十几分钟。然后DP的方法其实一开始就想到了，发现空间复杂度是O(N^3)的，500*500*500会爆空间。。。然后盯了题目十几分钟发现直接滚动数组不就可以了吗。。。

t3:看题又用了半个小时，然后想到了用字典树，然后纠结了好久题意，才发现样例的最优方案是先读b结局的。。。出题人就不能给个样例解释吗！！！！！！然后被题意纠结着错过了正解，最后也没弄清楚自己写了什么就交上去了。

t4:题目还算能看懂，然后又是DP，一开始没有想到要乘上组合数，然后弄了半天，在x位置想了好久都没弄出来，然后就没时间了，暴力好像勉强正确？应该弄不到分了。

然后上午就愉快的挂掉了ggg，也不想说什么了，出题人啊。

DAY1.5

中午会教室象征性的写了点作业，然后就继续比赛了。

LOL乱入。。。不过题意起码是看的懂的了。

t1:一开始想是贪心，考虑到每种高度的花只需要考虑是从左到右浇花还是从右到左就行了，就想到贪心。然后觉得不太对，于是找到了反例。然后似乎是可以DP的：用f[i,j]表示浇完高度为i的花之后，j=0表示在高度为i的花的最左边，j=1表示最右边的最小时间，然后预处理出每种高度的花最左和最右的位置就可以了，为了方便还加了个离散化。

t2:嗯数据结构题，想了一会想到分解质因数，但是似乎时间不是很够用。想了很久也只想到只能单点修改的O(N√N)的方法，于是随便弄了个线段树，很可能会超时。出来后才想到为什么不用树状数组，用线段树被卡常无误。

t3:这题目简直丧心病狂，超级概率DP，然后尝试推公式，弄了好久好像弄出一个O(N^2)的递推，高兴了好一会，开始打的时候发现好像这只有30分。。。然后就30分弃疗。

t4:完全没有想法，于是弄了个暴力。

下午发挥还好，只是t2用了线段树是个不小的失误。

最终还是差一点点呢。。。我果然还是太弱了，不出意外的话还有三十多天就退役了，我也只能寄希望dwjed和肘子了，总之加油吧。

退役倒计时：36天。