[原创]Codeforces Round #404 (Div. 2)

Tabris

CSDNcodeforces套题

发布于：2017年3月16日

次浏览

[原创]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，第i天被鸟吃i，问你至多撑几天，使得仓库里面不为 $0$,(先被吃，在运，如果吃完就成 $0$ 了，那么就已经算撑不住了)

首先考虑n<=m的情况，最多撑 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)}!}

然后我们就可以计算了。

ans \\= \sum_{i=1}^{n} C(n-1,i-1)\times C(m,i) \\= \sum_{i=1}^{n}\big[ C(n,i)-C(n-1,i)\big]\times C(m,i)\\ =\sum_{i=1}^{n} C(n,i)\times C(m,i)-\sum_{i=1}^{n}C(n-1,i)\times C(m,i) \\=C(n+m,m)-C(n-1+m,m) \\ =\dfrac{(n+m)!}{(n)!\times {(m)}!}-\dfrac{(n+m-1)!}{(n-1)!\times {(m)}!}