codeforces #327 A. Flipping Game

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)可以解决。

codeforces 456 C. Boredom

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

codeforces #336 div 2 B. Hamming Distance Sum

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

codeforces #336 div 2 A. Saitama Destroys Hotel

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

codeforces #332 div 2 D. Spongebob and Squares

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

需要注意的是,一个是会爆int,所以记得用long long

另一个是如果两个数相等,记得只输入一组,并且方案数-1

我是用set +pair存的答案。。反向遍历set的时候要用reserve_iterator…

 

 

codeforces #333 div 2 D. Lipshitz Sequence

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

具体的证明见这里:

In order to prove it properly, we’ll consider three numbers Ai, Aj, Ak (i < j < k) and show that one of the numbers L1(i, j),L1(j, k) is  ≥ L1(i, k). W.l.o.g., we may assume Ai ≤ Ak. There are 3 cases depending on the position of Aj relative to Ai, Ak:

  • Aj > Ai, Ak — we can see that L1(i, j) > L1(i, k), since |Aj - Ai| = Aj - Ai > Ak - Ai = |Ak - Ai| and j - i < k - i; we just need to divide those inequalities
  • Aj < Ai, Ak — this is similar to the previous case, we can prove that L1(j, k) > L1(i, k) in the same way
  • Ai ≤ Aj ≤ Ak — this case requires more work:
    • we’ll denote d1y = Aj - Ai, d2y = Ak - Aj, d1x = j - i, d2x = k - j
    • then, L1(i, j) = d1y / d1x, L1(j, k) = d2y / d2x, L1(i, k) = (d1y + d2y) / (d1x + d2x)
    • let’s prove it by contradiction: assume that L1(i, j), L1(j, k) < L1(i, k)
    • d1y + d2y = L1(i, j)d1x + L1(j, k)d2x < L1(i, k)d1x + L1(i, k)d2x = L1(i, k)(d1x + d2x) = d1y + d2y, which is a contradiction

We’ve just proved that to any L1 computed for two elements A[i], A[k] with k > i + 1, we can replace one of i, j by a point jbetween them without decreasing L1; a sufficient amount of such operations will give us k = i + 1. Therefore, the max. L1can be found by only considering differences between adjacent points.

这样子就好做了很多。由于斜率绝对值的最大值一定在由相邻的两个点得到。而相邻两个点的横坐标差1,所以斜率的绝对值就变成了相邻元素差的最大值。因此我们可以预处理一个数组b,表示相邻元素的差的绝对值。

接下来的问题就变成了如何求b的一段区间里的所有子区间的最大值的和。我们的思路是考虑这个区间里每个元素对答案的贡献。显然,对于b中越大的元素,它对答案的贡献会越多,因为会有更多包含它的区间以它为最大值。具体来讲,对于这个区间的每一个元素,我们可以分别向左和右边扩展,看最大能到哪里。

比如3 4 3 8 2 7 1,对于8,左边可以到达3,与8的距离为3,右边可以到达1,与8的距离为3,那么8对答案的贡献为(3+1)*(3+1)*8,也就是说一共有4*4个区间的最大值为8.对于7,左边可以到2,距离7为1,右边可以到1,距离7长度为1,那么7对答案的贡献就是(1+1)×(1+1)*7,也就是有4个区间的最大值为7.分别为{2},{2,7},{7,1},{2,7,1}

由于q不算很大,可以直接搞…用两个数组right和left代表能到达的右边和左边的最远位置。

 

 

 

codeforces #333 div 2 C. The Two Routes

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的时候加以判断。但是马上就发现。。不能同时到达同伙一个点这个条件其实不会影响。。因为按照题意,一定存在一条1到n的路,不是公路就是铁路。那么就让有路的花费1的代价到n,然后剩下的求一个一到n的最短路即可。由于n才400.。最短路怎么搞都行。。我偷懒就用floyd了。

codeforces #333 div 2B. Approximating a Constant Range

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

 

codeforces #334 div 2 E. Lieges of Legendre

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

codeforces #334 div 2 D.Moodular Arithmetic

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

hdu 1221 Rectangle and Circle

http://acm.hdu.edu.cn/showproblem.php?pid=1221
题意:问圆和矩形是否相交
思路:主要特殊的包含情况,然后判断与线段相交。

poj 3687 Labeling Balls

http://poj.org/problem?id=3687
题意:给定几个标签球的重量大小关系,求每个球是第几重的(即每个球在所有球的重量中由小到大排名是多少)。
输出是每个球第几重,而不是几号球比几号球重!)。一开始理解错了QAQ
思路:反向拓扑+优先队列。因为正向不好用。。。所以我们连边的时候由重的指向轻的。。这样最先出队的就是最重的。。和上道题差不多?

 

poj 3660 Cow Contest (floyd,传递闭包)

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

 

 

hdu 2647 rewards

http://acm.hdu.edu.cn/showproblem.php?pid=2647
题意:老板要给很多员工发奖金, 但是部分员工有个虚伪心态, 认为自己的奖金必须比某些人高才心理平衡; 但是老板很人道, 想满足所有人的要求, 并且很吝啬,想画的钱最少
输入若干个关系
a b
a c
c b
意味着a 的工资必须比b的工资高 同时a 的工资比c高; c的工资比b高

当出现环的时候输出-1

思路:因为点的个数比较多。。。用数组存点的关系存不下。。于是用set存边。。和用vector差不多。。。窝一开始的大思路错了。。以为会是一条链。。也就是没一个钱数只对应一个人。。。但实际上可以是889,888,888,这样。。。只要不矛盾。。然后要反向建图。。因为只知道最少的钱数是888,不知道最多的钱数是多少。。所以最先出来的,也就是入度为0的点应该为工资最少的。。。所以如果a应该比b工资高,那么连一条b指向a的边。

 

 

hdu 3342 Legal or Not

http://acm.hdu.edu.cn/showproblem.php?pid=3342
裸题。
注意有重边。