牛客CSP-S提高组赛前集训营2
预估得分:100+100+40
实际得分:65+80+40
不开long long见祖宗
T1 服务器需求
https://ac.nowcoder.com/acm/contest/1101/A
小多计划在接下来的n天里租用一些服务器，所有的服务器都是相同的。接下来n天中，第i天需要aia_iai台服务器工作，每台服务器只能在这n天中工作m天，这m天可以不连续。
但是计划不是一成不变的，接下来有q次修改计划（修改是永久的），每次修改某一天k的需求量aka_kak。
小多希望知道每次修改之后，最少需要多少台服务器。
这m天可以不连续!
我们从这个角度入手,将每一台服务器抽离出来,记所有的服务器总量为sum,则答案为\frac{sum}{m}\qquad
WA!
可以发现第二个样例过不去,因为这m天可以不连续,并不表示一个人可以在同一天用若干次,所以还有与aia_iai的最大值取max.
T2 沙漠点列
https://ac.nowcoder.com/acm/contest/1101/B
我们称一张无向图是仙人掌，当且仅当这张无向图连通且每条边最多属于一个简单环。我们称一张无向图是沙漠，当且仅当这张无向图中所有连通子图都是仙人掌。
CSP考动态仙人掌
其实我们把所有的割边给抠出来,这样就可以求出有多少个环.对于每一条割边,选择它则会增加1的贡献,对于每一个环,要先断一条边才可以满足割边的性质.我们可以先将所有的割边先删掉,贪心的以环的大小从大到小的选,因为这样可以使选的环尽量的小,则可以让断环需要花费的边尽量的小.由于该图是边仙人掌,两个环之间可能没有变相连,所以要构造一个'拟‘割边连接这两个环,从而隔开两个环.
T3 维护序列
https://ac.nowcoder.com/acm/contest/1101/C
YNOI题,与https://www.luogu.org/problem/P5397 天降之物是一样的.
标签：割边,牛客,https,服务器,集训营,仙人掌,CSP From： https://www.cnblogs.com/zhouhuanyi/p/16983569.html