Codeforces #330 div2

代码:

https://github.com/HarryGuo2012/ACMCode/tree/worldLine/Codeforces/%23330(Div%202)

A Vitaly and Night

题意:

很简单,自己看。

题解:

直接按照题目的意思统计答案即可。

B Pasha and Phone

题意:

序列$C$长度为$N$,将其分成$K$块,使得第$i$块都能被$a_i$整除,并且第$i$块的开头不是$b_i$,问你有多少种$C$

题解:

按照乘法原理统计答案即可,需要容斥的计算每一块的答案,需要特判$b_i==0$的情况。

C 被吃了,可恶

D Max and Bike

题意:

就有一个奇怪的圆在数轴上滚,上面有个传感器,当这个传感器的横坐标为$s$的时候开始计时,在横坐标变成$f$的时候停止计时,速度恒定,问你最短的时间。

题解:

将整个过程考虑为中间的整数圈和两头非整数圈两部分,那么现在考虑这样一个策略,在时间一定的时候,怎样让圆走得尽量远,很明显,只要让传感器在开始和结束的时候纵坐标一致即可。
感受一下,发现是可以二分的,所以就对$t$二分,然后由上述策略,可以唯一确定当前能走的最长路径,然后check一下就好。