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

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,可以搞。 需要注意的是，一个是会爆int,所以记得用long long 另一个是如果两个数相等，记得只输入一组，并且方案数-1 我是用set +pair存的答案。。反向遍历set的时候要用reserve_iterator... /* …

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). …

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. 需要注意的是，set里最小值是se.begin() ，最大值是se.rbegin()这样比较好。。不要用se.end()之类。。。 另一个需要注意的是，multiset里用erase的时候。如果se.erase(x)会把集合里所有的x都删除掉。如果指向删除一个，那么应该写成se.erase(se.find(x)) /* …

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

http://codeforces.com/contest/604/problem/D 题意：一个恒等式 f(kx%p)=kf(x)%p ,k,p为常数，且满足x对于定义域为0..p-1的p的整数，值域也在0..p-1范围（不一定一一对应）。问满足题意的f有多少个。 思路： f(0)=0,对于其他的值，当f（x）确定时，f（kx%p）也随之确定，那么把kx%p看做新的x,f（kkx%p）也随之确定...相当于【1，p-1】被分为r个小环，确定每个环可以任选一个数字，ans=p^r。环的个数可以用dfs跑一遍得到r. 注意当k=1的时候是特殊情况，f(x)恒等于f(x)那么答案应该有p的p次方种。因为对于p个f(0..p-1)，每一个 …

http://acm.hdu.edu.cn/showproblem.php?pid=1221 题意：问圆和矩形是否相交 思路：主要特殊的包含情况，然后判断与线段相交。 /* *********************************************** Author :111qqz Created Time :2015年12月21日 星期一 21时38分22秒 File Name :code/hdu/rr1221.cpp ************************************************ */ #include <iostream> #include …

http://poj.org/problem?id=3687 题意：给定几个标签球的重量大小关系，求每个球是第几重的(即每个球在所有球的重量中由小到大排名是多少)。 （输出是每个球第几重，而不是几号球比几号球重！）。一开始理解错了QAQ 思路：反向拓扑+优先队列。因为正向不好用。。。所以我们连边的时候由重的指向轻的。。这样最先出队的就是最重的。。和上道题差不多？ /* *********************************************** Author :111qqz Created Time :2015年12月19日 星期六 16时32分59秒 File Name :code/poj/3687.cpp …

http://poj.org/problem?id=3660 题意：给定n个奶牛，m个奶牛的关系，a,b表示a比b强...问能确定多少个奶牛的排名。 思路：最重要的一点是。。能确定奶牛i的排名的条件是。。知道奶牛i和其他n-1个奶牛的关系。。不管是能打败奶牛i也好。。会被奶牛i打败也好。。只要不是不确定就行。。所以我们跑一遍floyd做传递闭包。得到任何两个点之间的联系。然后对于每一个点。看其他n-1个点是否和他有关系。 /* *********************************************** Author :111qqz Created Time :2015年12月17日 星期四 21时31分05 …