http://codeforces.com/contest/602/problem/D 题意:见题目描述。 思路:我们很容易发现,l[h]函数其实就是在求区间斜率的最大值。哦不对,是斜率的绝对值的最大值。而且一个显而易见的结论是,斜率最大值一定是由相邻的点得到。画图可以很容易看出。
阅读更多http://codeforces.com/problemset/problem/552/A 题意:一个100*100的网格。然后给n个矩形。每个格子中填上包含这个格子的矩形的个数。最后问所有格子的和。 思路:树状数组搞得...然而..直接求所有矩形面积的和就可以啊喂。。o(n)。。。111qqz你个炒鸡大菜鸡。
阅读更多题意:一个长度为l的走廊。两个人站在两端点。互相向对方发射某种魔法。A的魔法速度为p米/秒,B的魔法速度为q米/s,魔法相遇以后会反射。反射会发射人那里会再次发射。问两种魔法第二次相遇的时候距离A的距离。 思路:由于每种魔法的速度保持肯定不变。。所以不管第几次相遇。相遇点都是同一个。。。ans=p*(p+q)/l;
阅读更多比赛的时候没做出来.这道题需要用到的一个重要的性质是,任意一个自然数可以表示成至多三个三角形数(1,3,6,10,15.....)的和(orz高斯)然后也有推广到任意自然数可以表示成k个k角形数的和的结论(费马提出了猜想,柯西给了证明)然后官方题解说的比较好:
阅读更多http://codeforces.com/problemset/problem/535/C
题读了好几遍才读懂。 题意是给出一个等差数列,操作严格要求从最左边不为零的连续m个数减去1,最多执行t次后问离最左边最远的位置在哪里。 有两个限制条件...一个是本身的si不能大于t,否则无法吃完。 还有一个是从sl到sr的和不能超过m*t (比赛的时候考虑的不周到。。实际上只有当r-l+1比m大的时候才是m,也就是说要取min(m,l-r+1)) 这题正解应该是二分....直接Lower_bound。。。看到也有人用前缀和搞的。 我是解方程了(貌似是个傻逼做法).... 可以列出一个关于r的一元二次方程。。。然后求根公式2333 方程是:
阅读更多http://codeforces.com/problemset/problem/534/C
题意是说一共有N个骰子,第I个筛子一共有di面...现在知道这些骰子的点数之和,问对于每一个骰子不能取得值有多少个。
乍一看有点不明觉厉...稍微再想下,求取值范围即可。
阅读更多http://codeforces.com/problemset/problem/534/B
题意是说一辆车,每秒内的速度恒定...第I秒到第I+1秒的速度变化不超过D。初始速度为V1,末速度为V2,经过时间t,问最远能走多远。
策略就是尽可能加速...加到某个时间,如果在这个时间不开始减速就回不到V2了。
阅读更多ACM STEPS里的...这题前面一道是求LCM....结果接下来就是这么一道。。。 朴素会超....筛法会爆....题目顺序真是按照难度来的? 于是想到 Miller-Rabin素数测试....... 这个方法是基于费马小定理 我的理解就是... 如果我要判断n是否为素数 只要取k个数 如果满足 a^(n-1)mod n =1 那么n就很可能为素数。 证明什么的...暂时还是算了吧...论文里貌似扯了一大堆 第一次用,竟然真的A了。。。。 感觉更好的办法也许是先打一个比较小的素数表,然后每次random选取若干个进行判断...那样应该更可靠些? 本来想WA掉之后再改的。。。没想到这么写就A掉了。。。。杭电数据略水?
阅读更多