http://codeforces.com/contest/612/problem/D

题意：给出n个线段信息，每个线段以l,r的形式给出。给定k。要求从作到右给出至少有k个线段覆盖的区间的信息。并使得区间数目尽可能少。

思路：很经典的一类问题...又想起了当年在tyvj上海洋兄给我的那个把线段比喻成公路，把两个端点比喻成收费站的比喻了。做法是把所有点的信息按照从小到大排序，并且记录点的类型信息，如果点相同，那么我们规定入口处的优先级高。用pair来搞的话。。可以把入口的type规定成-1，出口规定成1.然后从最左边的点开始扫，遇到-1的点厚度+1，遇到1的点厚度-1.当厚度为k的时候记录区间信息。

http://codeforces.com/contest/327/problem/A 题意：给定一段序列，只由0,1组成。要求选一段非空区间，做翻转操作（0变1,1变0），问变完之后1最多能有多少。 思路：最后的1个个数=初始的1的个数+变换区间的0的个数-变换区间的1的个数。初始的是常数。那么我们只要找到某一个区间内，0的个数-1的个数有最大值即可。如果a[i]==0的时候令b[i]=1，否则b[i]=0,那就是经典了最大连续区间和的问题了。dp的思想o(n)可以解决。

http://codeforces.com/contest/456/problem/C 题意：给出n(1E5)个数（1E5），每次可以选一个数a[k]并删掉a[k],a[k]-1,a[k]+1得到a[k]分，问最多能得到的分数。 思路：裸dp.f[i]表示选到数i的时候能达到的最大分数。开一个计数数组cnt[x]表示数字x出现的次数。那么显然有f[0]=0,f[1]=cnt[1],f[i(i>=2)] = max(f[i-1]，f[i-2]+f[i]*cnt[i]);答案为f[max(a[i])]，注意要开long long

http://codeforces.com/contest/608/problem/B 题意：给定两个字符串a,b，问b中的每个连续的长度为a的子串与a的哈密顿距离的和是多少。哈密顿距离是对应位置的字符的差的绝对值的和。由于是01串，也就是字符不同的位置数。 思路：类似前缀和。0和1分别搞。注意开long long

http://codeforces.com/contest/608/problem/A 题意：一个电梯，从s到0层，单项，给出n个人，每个人在某时间出现在某层，问要花多长时间把所有人运到0。初始电梯在s，每下一层话费时间1，上来人不花时间。 思路：由于电梯只能是单项，那么到达某一层的时候，一定要等到把这层中最晚来的那个接走。所以排序的时候按照楼层高到低为第一关键字，等待时间长到短为第二关键字。对于同一楼层出现的，只考虑第一个即可，也就是最后出现的。需要注意的是最后接完最后一个人以后把电梯运行道0层。

http://codeforces.com/contest/599/problem/D 题意：给出总的方格数x，问有多少种不同尺寸的矩形满足题意，输出方案数和长宽（3,5和5,3算两种） 思路：比赛的时候gg了。。其实稍微在纸上推一下。就会得到对于n,m的矩形，一共会有-nnn+3nnm+n+3n*m的方格。数量级是n3。 我们可以实际跑一遍。发现对于x1E18的数量级，n不会超过1442550，1E6,可以搞。

http://codeforces.com/contest/602/problem/D 题意：见题目描述。 思路：我们很容易发现，l[h]函数其实就是在求区间斜率的最大值。哦不对，是斜率的绝对值的最大值。而且一个显而易见的结论是，斜率最大值一定是由相邻的点得到。画图可以很容易看出。

http://codeforces.com/problemset/problem/602/C 题意：给出n个城镇，m条双向铁路，对于任意不同的x,y，如果x,y之间没有铁路，那么一定有双向公路。train只能走铁路，bus只能走公路。现在一辆火车和一辆bus同时从1出发，要到达n，处于安全考虑，bus和火车不能同时处在除了n以外的点。bus和train不要求同时到达。任意一段道路的时间花费都是1小时。问最少需要多久使得bus和train都到达n。如果存在某个不能到达，那么输出-1. 思路：n才400.一开始打算先按照rail和road建两个图。这两个图互为补。然后在floyd的时候加以判断。但是马上就发现。。不能同时到达同伙一个点这 …

http://codeforces.com/contest/602/problem/B 题意：给定n个数，问最大连续区间长度，满足这段区间内最大值和最小值的差的绝对值小于等于1. 思路：尺取+set。尺取法，由于要时刻得到一段区间的最大值和最小值，而且可能有重复元素，所以用multiset.

http://codeforces.com/contest/604/problem/E 题意：有两个人做游戏，游戏规则如下： 有n堆石子，每次可以对一堆石子进行操作，如果当前石子是偶数，那么可以选择将这2*x个石子分成k堆石子数为x的石子堆，还有一种没有前提的操作是取走当前堆的一个石子，问先手赢还是后手赢，先手和后手都足够聪明的情况下。 思路：博弈论。。不会做。。第一次接触sg函数。。转载一篇题解： http://m.blog.csdn.net/blog/qq_24451605/50154973