Codeforces Round #409(Div 2)做题记录

A. Vicious Keyboard

题意:给出一个只含’V’和’K’的字符串,现在最多改变1次,把‘V’改成K或者K改成V。问最多几出多少个VK。

贪心搞了搞。。。

B. Valued Keys

题意:略。

字符串模拟。。。

C. Voltage Keepsake

题意:有一个充电器,每秒充p能量。一共n个装备,每个装置每秒消耗a[i]能量,起始有b[i]能量。问最多可以坚持多少秒,保证所有装置都可以进行。

二分答案,算出来充电器这段时间内一共能充的电量。然后check一下就好了,但是我偷懒判断无限的方式按照李大爷的写法写了,和一个很大的数比较了一下,结果FST了。。。其实只要p大于a[i]的和就好了。。。。

D. Volatile Kite

题意:给出n个点的坐标的一个凸包,问每个点都任意移动一个最大距离D,仍然保持凸包。求这个D。

其实考虑凸包的最简单的形式:三角形。这个最大距离一定是三条边上的最小的高。而凸包上对于三个点来说,找一个最小的高,一定是三个相邻的点,否则就不可能是凸的。所以O(n)扫一下就好了。

E. Vulnerable Kerbals

题意:现在在0-m-1中选数字,组成一个最长的序列,保证:1.前缀积模m后均不一样。2.不能出现n个不能出现的数字。

被马大爷教育啦。。。

假设我们选择一个前缀积序列a,那么根据题意则有:,转化一下变成这个样子,就是个同余方程,那么也就是说假如,就可以让上面那个式子有解。那么我们按照与m的gcd来分类,把0-m-1个数都分类。也就是缩点。相同gcd一定可以互相到达。然后假如某个gcd值i是j的因子,i向j连边,就形成一个DAG。。。然后dp找出最长路,然后我们就可以得到一个前缀积序列。。。然后两两解出来x就得到我们的序列,最后需要考虑0。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注