CF639

2016.04.06 10:49 Wed | 60次阅读 | 旧日oi | 固定链接 | 源码

A. Bear and Displayed Friends

B. Bear and Forgotten Tree 3

构造一颗n个点的以1为根树,满足直径为d,深度为h

构造

搞两条长链,然后别的接成一个菊花就好了。

C. Bear and Polynomials

给出一个多项式,你可以调整某一项的系数,系数的绝对值不能超过k(k<=1e9),使得f(2)=0。问方案数。

数论

把2带入,结果可以变成一个二进制形式,我们可以更改的地方x需要满足条件:
1.x不比二进制表示的答案的最低位高
2.x调整之后在k的范围内。
第一个条件很好维护。
第二个条件,因为k不大,我们不需要存下具体的数,倒着扫一遍,记录最后x位的答案,如果这个答案大于2*k了,那么以后的数也都不可能了。

D.Bear and Contribution

给出一个数列,你可以把某个数花费a的代价加5,b的代价加1,问得到k个相同的数的最小代价。

dp

如果b*5<=a,直接判断下前缀和就好了。
否则,我们枚举每个数x,x+1,x+2,x+3,x+4能否作为答案,可以按照模5来讨论,把其它的数也按照模5分成5组,那么在模5等于x的意义下,每一组数的代价的计算方式是相同的,并且代价按照数从小到大递减。那么我们就可以用类似堆的东西维护出前k小的代价,每次加入一个点,再删掉5组中某一组的末尾,用5个队列就可以维护了。

E.Bear and Paradox

给出n道题,你要某种顺序解决每一题。
每道题有初始分数pi和解题花费时间ti,你在t时间解决问题p可以获得$p(1-c*t/T)$,T是所有ti之和,现在问最大的c,满足任何一种得分最多的做题顺序方式都满足如果pi>pj,那么i题的最终得分比j题多。

排序+

最优方式就是按斜率从大到小,noip知识……
然后二分答案,维护斜率相同的一组中,每个元素的最小可能分数和最大可能分数,然后按分数排序检验一下就好了。
我做的时候一直tm以为是问是否存在一种得分最多的方式满足那个限制……不过我觉得那会是一道好题,然而还不会呢……
复杂度nlogn,官方题解写的什么东西……

F.Bear and Chemistry

初始给出一幅图,问你每次如果添加一些边,能否使一些点两两双连通,强制在线
初始n,m<=300000,添加的n,m之和都<=300000

tarjan+虚树

先tarjan把原图缩成一个树,然后对于每个询问,把虚树建出来,把边连一下,再跑一遍双连通分量就行了。
除了忘清数组能一次写对这题还真是不错……还拿了个rank1……

代码可以在cf上加我好友看,jkxing,紫名狗……