PKUSC2018题解

当时太菜了没有去,题解合集

CF1204E Natasha, Sasha and the Prefix Sums

请先思考后再展开

这题不是PKUSC2018的,但有兴趣的可以看看
$$
考虑在第一个max处计数,f(a,b)表示前缀 \le0,g(a,b)表示后缀>0的方案数 \\
f(a>b)=0,f(a,b)=C_{a+b}^a-C_{a+b}^{b+1},类似卡特兰数的推导方式 \\
g(0,0)=g(a<b)=0,在后面先放一个1,g(a,b)=C_{a+b-1}^{a-1}-C_{a+b-1}^a \\
然后枚举前缀mx,前面g后面f拼接起来,O(n^2),g和f也可以dp计算
$$
code
$$
k(a,b)=a个1,b个-1下f<0的方案数 \\
k(a>b)=0,k(a<b)考虑从后面添加=k(a-1,b)+k(a,b-1) \\
其实用类似卡特兰数的推导方式可知 k(a<b)=C_{a+b}^a-C_{a+b}^{a-1} \\
f(a,0)=a,f(0,b)=0,考虑从前面添加(奇妙的思路) \\
f(a,b)=(f(a-1,b)+C_{a+b-1}^b)+(f(a,b-1)-(C_{a+b-1}^a-k(a,b-1)))
$$
code

线性做法:就是求一个至少i+1,可以看【OI之路】03数学-7组合数学中Catalan数拓展部分

1
2
3
4
5
6
7
for(int i=0;i<=n;i++)
{
int x=n,y=m+i+1;//注意要这样比大小
if(min(x,n+m-x)<min(y,n+m-y)) continue;
cnt[i]=C[n+m][x]-C[n+m][y];
}
ll ans=0;for(int i=1;i<=n;i++) ans+=(cnt[i]-cnt[i-1])*i,ans%=MOD;write((ans+MOD)%MOD);

最大前缀和

请先思考后再展开

和上题做法类似,不过需要注意一个细节,整个S的和不算是后缀和的一部分,否则前缀和可能取在题面中i=0
code

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/71bd.html
转载请注明出处,谢谢!