抽两天时间拿了NOI2016原题练习了一遍。
原题见下：（附加文件见下方的uoj链接）
Day1.pdf
Day2.pdf
附加文件整合

Day1 T1：优秀的拆分

Link：优秀的拆分
这部分我一年前就有95分了（捂脸逃）
CCF给此题的暴力还是很良心的（捂脸逃）
正解貌似是后缀数组什么的，反正就5分啊（捂脸逃）
那就简单说下我95分怎么做吧。
对于测试点1，2，3，4，因为所有字符串都相同，我们使用组合数学可以求解啦。
剩下的部分，对原串哈希，然后枚举A，B长度，理论上只要你枚举恰当，甚至都可以过到95分。
我至今仍记得当年我跑过2000的数据时的心情。。。

Day1 T2：网格

Link：网格
这题充分说明了我是个ZZ。
首先自己手玩一下，可以发现答案只有四种情况：-1，0，1，2。
= =
对于-1而言，如果原图只有一只跳蚤或者只有两只跳蚤且是相邻的，那就是无解。
对于0，排除-1的情况后，我们整个并查集判定一下就好。
对于1，枚举填哪一个点，如果填了之后能不联通的话即为答案。
排除以上所有情况之后即为2.
此外，17，18，19貌似可以手玩？如果C超级小的话。
上面的做法，复杂度是$O((nm)^2)$的，可以过前7个点，28分滚粗。。。
下午看题解的时候差点没被气死。
“天杀的我怎么就没往割点上面想啊啊啊啊啊啊啊啊啊啊啊！”

此题如果想到了割点可玩性不就大大提升了吗？？？

那么判断1的情况，就是对网格图跑下tarjan，如果有割点即可。。。
暴力建图可以得52分。。。几乎翻一倍。。。
正解就是在此基础上，把每个点（周围左右两圈）离散化一下。。。
我的天啊…后面的离散化我都想到了…为什么想不到割点啊…
= =

Day1 T3:循环之美

Link：循环之美
哇，这个题要求的东西好玄妙啊。。。
我突然就联想到小学奥数学到过的一个东西：
“如果分母既不含因子2，又不含因子5，那么这个分数是个纯循环小数…只含有2，5为不循环小数…除此都是混循环…”
那个是十进制下的…不含2和5？
貌似是…与10互质？
于是我手玩了2进制，和3进制，发现果真如此。
2/1虽然整除，但是还是按分母与进制互质算，而且符合题意。。。
那题目求的就很简单了（并不），即分子分母互质，然后，分母与进制互质的分子分母数对个数…
表示成公式的话如下：
$1\leq i\leq n$,$1\leq j \leq m$,$gcd(i,j)=1$且$gcd(j,k)=1$的点对个数。
暴力枚举可以过6个点，24分到手。
但是做过SDOI2015数表那个题的话，就会发现这个题与此很相像啊。。。
考虑n比m略小，我们枚举i，求满足条件的j的个数。
对于每个枚举的i，我们求与i*k互质的j的个数即可，两个条件就都顾全了。
做数表时，我还没学过莫比乌斯反演，所以我自己想到了一个容斥原理枚举因数的方法，比如，我要求与20互质的数，它有因子2，5，那就是范围内所有数-2的倍数-5的倍数+10的倍数。
我们需要$O(2^\omega )$枚举因数的子集，由于$\omega$的实际意义是这个数互不相同的因子个数，所以它并不会很大。
2*3*5*7*11*13*17=510510
所以这个系数并不高，整体复杂度$O(n*2^\omega )$。
实测52分，我觉得可能枚举质因数那里复杂度略高，有空可以尝试改进一下。
据说会莫比乌斯反演就可以拿到84分了。。。

Day1 总结

整体来讲，第一天真暴力。。。
感觉最好的就是T3了，感觉最差的是T2（割点想不到真是zz啊）
95+28+52=175

Day2 T1 区间

Link：区间
此题依然说明我是个zz。。。
想了一个多小时都只有60分暴力，最后还因为没有判无解丢了一个点…
其实应该不算太难TAT，我稍后再开贴写个题解？

Day2 T2 国王饮水记

Link：国王饮水记
天啊，我怎么一无所知啊…
于是实际做的时候我就直切过去，干了一小时提交答案题之后再回头处理此题= =
我只会这个题的特判啊。。。
$n\leq 4$的时候暴搜，可以有15分。
$k=10^9$的时候，考虑最优方案应该是贪心地排序，从小到大比一号水箱高的时候依次联通，于是就这么整了，拿到了10分。
$k=1$的时候，还是排序，从大到小枚举，每次取前k大的，然后最优即可。
但是,k=1的时候。。。
1.算平均数不加h[1]
2.这是源程序自己体会我有多2 。。。

int main(){
	scanf("%d%d%d",&n,&k,&p);
	if(n<=4)
	{
		deal1::Main();
		return 0;
	}else if(k==2)deal2::Main();//k==2 2333333
	else deal3::Main();
	return 0;
}

这种对拍三下就可以发现的问题，以后千万不能再犯了TAT
但是，还是有一个很神奇的地方，我其他数据都是按照$k=10^9$来处理，结果多得了16分。。。

真是2333333啊。。。
正解是个好玄学的DP啊…TAT

Day2 T3 旷野大计算

Link：旷野大计算、
真是良心提答题啊，不虐蒟蒻TAT
好多手玩就有好多分了。。。
1：手玩不解释。
2：手玩不解释。
3：把读进来的数乘上个2的300次方，代入到S函数里面，负数变成0，0变成0.5，正数变成1，然后…2333333
4：用3的方法得到负数-1正数1，乘法用一个，得到6分。
5：手玩不解释。
8：是我大开脑洞得到的方法不知怎么就能得8分：

$\frac {a}{10}=\frac {a}{8}-\frac {a}{32}+\frac {a}{128}-\frac {a}{512}+.....$

后来看过题解明白了其奥妙，联想循环之美：

$(0.1)_{10}=(0.0\dot001\dot1)_2$

所以这个式子应该是这么写的…

$\frac {a}{10}=\frac {a}{16}+\frac {a}{32}+\frac {a}{256}+\frac {a}{512}+.....$

其实它们是等价的。。。
真是神奇了啊…233333
54分到手，居然是得分第3高的题目233333

Day2（全部）总结

丧心病狂的演习结束了。
Day2总分：55+41+54=150
总分：175+150=325
那么假设我笔试100分能拿到的话，就是425 。
这是个什么水平呢？
你们自己看吧。。。NOI2016获奖名单
银牌垫底选手啊…要不是那年银牌扩招我还只能Cu收场呢…QAQ
Sengxian去年差不多是这个分数啊QAQ（%%%）
总结来看，发挥的水平应该算是8成吧，该想到的没完全想到，而且还有许多部分分上的失误。
例如D1T2的52分应该想到，估计就是割点部分不熟造成的失误。Day2的T1丢5分很不应该，T2丢掉10分更是活该（谁让你不拍这部分数据的）
如果有这部分的分数，应该发挥的更好才对…
再加上今年应该不会像这样暴力高分的情况…而且今年的实力应该会强很多啊…TAT
总之，接下来应该会是一场硬仗了。。。
（全剧终）