-
http://codeforces.com/contest/602/problem/D 题意:见题目描述。 思路:我们很容易发现,l[h]函数其实就是在求区间斜率的最大值。哦不对,是斜率的绝对值的最大值。而且一个显而易见的结论是,斜率最大值一定是由相邻的点得到。画图可以很容易看出。 具体的证明见这里: In order to prove it properly, we'll consider three numbers A__i, A__j, A__k (i < j < k) and show that one of the numbers _L_1(i, j),_L_1(j, k) is ≥ _L_1(i, k). …
Read More -
http://codeforces.com/problemset/problem/552/A 题意:一个100*100的网格。然后给n个矩形。每个格子中填上包含这个格子的矩形的个数。最后问所有格子的和。 思路:树状数组搞得...然而..直接求所有矩形面积的和就可以啊喂。。o(n)。。。111qqz你个炒鸡大菜鸡。 /* *********************************************** Author :111qqz Created Time :2015年12月14日 星期一 14时01分14秒 File Name :code/cf/problem/552A.cpp …
Read More -
题意:一个长度为l的走廊。两个人站在两端点。互相向对方发射某种魔法。A的魔法速度为p米/秒,B的魔法速度为q米/s,魔法相遇以后会反射。反射会发射人那里会再次发射。问两种魔法第二次相遇的时候距离A的距离。 思路:由于每种魔法的速度保持肯定不变。。所以不管第几次相遇。相遇点都是同一个。。。ans=p*(p+q)/l; /* *********************************************** Author :111qqz Created Time :2015年12月04日 星期五 19时12分56秒 File Name :code/cf/#327/A.cpp …
Read More -
因为每一个正整数可以唯一分解质因数... 要看能猜多少次,只要知道不大于n的质因子数有多少个即可(相同的算多 由于n才是1000.所以素数表随便搞就好....不用筛也行... /************************************************************************* > File Name: code/cf/#319/C.cpp > Author: 111qqz > Email: rkz2013@126.com > Created Time: 2015年09月18日 星期五 20时29分00 …
Read More -
比赛的时候没做出来.这道题需要用到的一个重要的性质是,任意一个自然数可以表示成至多三个三角形数(1,3,6,10,15.....)的和(orz高斯)然后也有推广到任意自然数可以表示成k个k角形数的和的结论(费马提出了猜想,柯西给了证明)然后官方题解说的比较好: **这个题看上去是一个贪心, 但是这个贪心显然是错的. 事实上这道题目很简单, 先判断1个是否可以, 然后判断2个是否可以. 之后找到最小的k (k 2)k(k2), 使得(m - k) mod 6 = 0(m−k)mod6=0即可.** 证明如下: 3n(n-1)+1 = 6(n(n-1)/2)+13n(n−1)+1=6(n∗(n−1)/2)+1, 注意 …
Read More -
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 方程是: …
Read More -
http://codeforces.com/problemset/problem/534/C 题意是说一共有N个骰子,第I个筛子一共有di面...现在知道这些骰子的点数之和,问对于每一个骰子不能取得值有多少个。 乍一看有点不明觉厉...稍微再想下,求取值范围即可。 先把所有di相加,得到所有骰子点数之和的最大值...然后点数之和的最小值当然就是N 对于每个骰子,将最大值和最小值减去这个骰子的对应数值...然后与总和A进行比较。 注意要开long long !!! 比赛的时候我明明写了typedef。。。结果后面还是忘记了。。。真是悲伤。 1 2 /* …
Read More -
http://codeforces.com/problemset/problem/534/B 题意是说一辆车,每秒内的速度恒定...第I秒到第I+1秒的速度变化不超过D。初始速度为V1,末速度为V2,经过时间t,问最远能走多远。 策略就是尽可能加速...加到某个时间,如果在这个时间不开始减速就回不到V2了。 从后往前预处理下每秒钟能达到的最大速度(如果超过这个速度,将不能减回到V2) 1 2 /* *********************************************** 3Author :111qqz 4Created Time :2016年02月22日 星期一 23时49分32秒 5File Name …
Read More -
ACM STEPS里的...这题前面一道是求LCM....结果接下来就是这么一道。。。 朴素会超....筛法会爆....题目顺序真是按照难度来的? 于是想到 Miller-Rabin素数测试....... 这个方法是基于费马小定理 我的理解就是... 如果我要判断n是否为素数 只要取k个数 如果满足 a^(n-1)mod n =1 那么n就很可能为素数。 证明什么的...暂时还是算了吧...论文里貌似扯了一大堆 第一次用,竟然真的A了。。。。 感觉更好的办法也许是先打一个比较小的素数表,然后每次random选取若干个进行判断...那样应该更可靠些? 本来想WA掉之后再改的。。。没想到这么写就A掉了。。。。杭电数据略水? 1 2 /* …
Read More