Codeforces Round #332 (Div. 2)

• contest link

    CF#332，Virtual participation，题目整体偏简单，部分题目有些坑。这场比赛耽搁的时间比较久了，晚上下一场都要开战了...不过接下来还是要非正式参赛的，毕竟太晚，熬不下去。

•  599A-Patrick and Shopping

    题意：出发点O,商店A，B，其中OA=d1,OB=d2,AB=d3,要求从O出发，逛了两个商店再回到O走的最短距离。

    解法：四种情况：O-A-B-A-O，O-A-O-B-O，O-B-A-B-O，O-A-B-O。

    code

•  599B-Spongebob and Joke

    题意：已知f[a[i]]=b[i]，给出f序列，b序列，问是否存在唯一确定的a序列。

    解法：需要清楚的是，对于每个b[i]值，它在f序列中出现了多少次，a[i]就有多少可能的值。不过当然不能暴力地扫描啦，可以hash存一下一个数在f中出现的次数，然后只记下任一一个位置；也可以像我那样用链表结构把所有出现的位置都记录下来。如果对于一个b[i]值，它在f中没有出现，那么就是Impossible；如果出现1次以上，就是Ambiguity；如果出现一次，那就把hash记录的位置赋值给a[i]。要注意的是，一定要全部判断完才能下结论——比如b[2]在f中出现3次，b[3]出现0次，那么答案是Impossible，而不是Ambiguity。

    code

•  599C-Day at the Beach

    题意：把给定的序列切成若干连续的段，满足对每一段分别排序后，整体有序。求最多能切多少段。

    解法：n个数共有n-1个位置可以切开，对于某个位置i，如果lmax[i]<=rmin[i]，那么这一位置切开后两侧分别排序的结果和整体排序的结果是相同的（没有逆序对），其中lmax[i]表示第i个位置左侧最大值，rmin[i]表示第i个位置右侧最小值。

    code

•  599D-Spongebob and Squares

    题意：求内含有x个正方形的所有矩形格子。

    解法：假如我们面对一个M*N的矩形，其中M>=N，那么容易得到其中含有的正方形数目如下：

        1*1 ---> m*n
        2*2 ---> (m-1)*(n-1)
        3*3 ---> (m-2)*(n-2)
        ...
        (n-2)*(n-2) ---> (m-n+2)*2
        (n-1)*(n-1) ---> (m-n+1)*1        
		

    换而言之，正方形总数为：

        1*1 ---> m*n  ---> [(m-n)+n]*n
        2*2 ---> (m-1)*(n-1) ---> [(m-n)+n-1]*(n-1)
        3*3 ---> (m-2)*(n-2) ---> [(m-n)+n-2]*(n-2)
        ...
        (n-2)*(n-2) ---> (m-n+2)*2 ---> [(m-n)+2]*2
        (n-1)*(n-1) ---> (m-n+1)*1 ---> [(m-n)+1]*1
        即为：
        sigma{[(m-n)+i]*i} 其中n,m是正整数，1<=i<=n;
        于是乎：
        化简为——(m-n)*n*(n+1)/2+n*(n+1)*(2n+1)/6
    	

    要求的就是这个表达式和x相等能解出的(m,n)点对。此时注意一下n的取值范围，三次方决定其范围最大也就是10^6级别，故简单枚举即可。

    特别注意的是此处规定m>=n，但题目里无此限制，解是对称出现的。当然还要注意m==n的情况。

    code

•  599E-Sandy and Nuts

    题意：

    解法：

    code

Copyright © 2015-2016 zhyack. All Rights Reserved.