月度归档:2016年02月

hdu 1003 Max Sum (dp)

传送门

一道很简单的最大连续子序列和的问题,结果在熄灯前赶着敲犯了各种傻逼错误。首先需要注意的是ans起始的值,因为有负数的存在,所以ans要尽可能的小。我一开始根本没看清有负数的情况直接设了个0.= =我还没有看清输出格式。结果WA了n次。。。总之以后敲题目的时候一定不能赶时间。

 

Codeforces 633B. A Trivial Problem(二分)

传送门

题目大意是给你一个数字m输出所有n!阶乘末尾有m个0的数n.如果n的阶乘末尾有0这也就意味着必须得有1对2*5。而且我们知道在1-n中5的数目是远远少于2的,所以我们只需要找到1-n中所有5的个数即可。

我们可以[n/5]+[n/5^2]+[n/5^3]…

因为题目提供了m的范围,可以确定一个上界和下界进行二分。不是很确定每个m有几个符合条件的数,所以我用了vector。

 

Codeforces 633A. Ebony and Ivory (exgcd)

传送门

据说数据很弱,但是我还是按照了exgcd的思路写的。权当复习板子了。

由题意可知ax+by=c的非负整数解(x,y必须都大于等于0)。所以我们只需要求出gcd(a,b)判断是否能被c整除即可。但同时还要注意的是因为要的是非负整数解,所以我们应该求出x或y的其中一个最小非负整数解,判断另一个此时是否大于等于0.如果小于0则还是No。