2019.08.13【NOIP提高组】模拟 A 组 总结

GG,爆了,心态巨崩。。。

考场:(20 + 15 + 3 = 38)


T1:

神奇拆分+容斥?
正解将(a[i])拆分成(c[i]*m+p[i])
可以得到 (sum{p[i]}) %(m=n)%(m)
(sum{p[i]}) 可能会大于(m),但肯定小于(k*(m-1))!!
我们就可以枚举 。
由于直接用组合数可能会使一些(p[i]>m),所以我们要容斥。
对于每个(sum{p[i]}) ,我们都可以枚举有几个(p[i]>m)。然后容斥。
再将n剩下的m放入这K个数即可。


T2:

神奇OJ连交3次结果CE。
结果是打表找规律?
神奇枚举求递推式最后成功找出?!
tql!!!


T3:

对于(limit1,2)就是使序列(1~n)的排列。
对于(limit3),我们可以将其看做是两个最长上升子序列正好覆盖整个序列,证明显然。
我们可以做一个前缀(max)序列。这样对于(max[i]),保证(max[i]>=i)
而且保证(max[n]=n)
如此,我们可以将问题转化成图。
那么我们可以将问题变成:
求从((1,1))((x,y))再到((n,n))的方案数,途中不能触碰到(y=x-1)的直线(不能使(max[i]<i))。
对于触碰到的方案数用题解说的翻折法即可。
预处理阶乘和逆元(O(n)),询问(O(1))。时间可过。


总结:

不要灰心,不要放弃。。。
交题的时候不要按多次(x>1),否则。。。
对于这种计数题,要认真思考,大胆猜想,小心求证。
要善于将题目转化成其他样子,或许更容易能想到。

现在:(100 + 100 + 100 = 300)

转载需注明出处。
原文地址:https://www.cnblogs.com/jz929/p/11348274.html