[原创]Codeforces Round #404 (Div. 2)
[原创]Codeforces Round #404 (Div. 2)
2017-03-16 11:12:44 Tabris_ 阅读数:354
博客爬取于2020-06-14 22:41:11
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/62418811
# A Anton and Polyhedrons
————————————————————————————————————————————
傻逼题不解释
B Anton and Classes
————————————————————————————————————————————
傻逼题不解释
C Anton and Fairy Tale
————————————————————————————————————————————
就是给你仓库的容积N,最开始每天运来M,但仓库里至多有N,第天被鸟吃,问你至多撑几天,使得仓库里面不为,(先被吃,在运,如果吃完就成了,那么就已经算撑不住了)
首先考虑的情况,最多撑n天,没有问题。
然后考虑其他情况,
开始几天,鸟吃的没有运来的多,所以相当于没有变化,
那么m天后,相当于每天减少1,2,3,4,······。
那么就是 (1+ans)*ans/2>=n-m
最后的结果就是ans+m
计算那个式子可以用不等式开根号,也可以二分,注意下二分的时候别溢出就行了。
D Anton and School - 2
————————————————————————————————————————————
给你一个字符串,问你字串中前半段为’(‘,后半段为’)'的子串有多少个,子串不要求必须连续。
很明显,我们可以枚举每一个’(‘,来计算以这个为前半段结尾的子串有多少个,
首先预处理出前缀’(‘的个数和后缀’)‘的个数,
在遍历一遍母串,每当到’('的时候我们就计算以这个跟为前半段结尾的子串有多少个,
因为前半段的最后一个’('是固定的,所有我们要求
$ \sum_{i=1}^{n} C(n-1,i-1)\times C(m,i)$
然后推导了半天还是不会,最后Q给了个公式
$ when(n\leq m), \ \sum_{i=1}^{n} C(n,i)*C(m,i)\=\sum_{i=1}^{n} C(n,i)*C(m,m-i)\=C(n+m,m)\=\dfrac{(n+m)!}{(n)!\times {(m)}!}$
然后我们就可以计算了.
E Anton and Permutation
————————————————————————————————————————————
不会,待补