Codeforces 371

题目链接代码链接

看到这次Div1是三个2000的(而不是2500),另外看到叉姐在论坛上放出题解,莫名其妙自己也想做一做。。。

Div2A Meeting of Old Friends


题意是给出两个区间,求交集的区间的长度,如果k在这个交集里面,那么结果再减1。

Div2B Filya and Homework


题意是给出n个数,现在能在一些数上(可以是0)上加x,也可以在一些数上减x,问能否最终的值是相等的。

分析可知如果n个数的值只有小于三种的话,那么是一定可以的。如果是等于三种,要形成等差数列。如果是大于三种,那么没可能了。

DIV1A Sonya and Queries


题意是给出一种匹配方法,给出一个01串,将数字从右到左匹配。如果是0,要求该位置是偶数;如果是1,要求该位置是奇数。

每次有三种操作,1.向该集合添加一个数字。2.向该集合删去一个数字。3.给定一个01串,询问该集合中符合该匹配的数字有多少个。

因为这个01串最多是18位,开一个1<<18的数组,暴力记录就可以了。

DIV1B Searching Rectangles


交互题,题意是在n*n(2<=n<=2^16)的格子上有两个矩形,两个矩形不重合。现在叫你找这两个矩形的位置。

每次你可以询问一个矩形,它会回答你里面有多少个完全在里面的矩形(0<=res<=2)。

先二分在横轴上存在把两个矩形分开的x,不存在就找y。

然后分别在分开的矩形内部,二分找四个边。

这个题叉姐写的代码真的很👍。。。

DIV1C Sonya and Problem Wihtout a Legend


题意是给出一个长度为n的序列,可以对每个数加上或减去一个数,将其改造成递增序列,问最小代价。

他们都说这个题烂大街了,然而我没做过。。。POJ 3666CF Round13 C

首先要求递增的话,那么A[i]-=i,将A[i]排好序假设为B[i]。

然后数据是3000的话,O(n^2)的DP也是可以过的,DP[i][j]表示前i个数里面变成单调递增,且最后一个数是B[j]的最小代价。说白了,就是暴力每个数作为一段区间的中位数,考虑其代价(后面的左偏树也是基于这个优化的)。因为如果这个序列单调递增,那么代价为0.单调递减,那么代价就是每个数-中位数的和。

所以能够得到转移方程为
$$
dp[i][j]=min(dp[i-1][k])+|A[i]-B[j]| (k\leq i)
$$
O(nlogn)的方法是用左偏树,有专门的论文,题目接触的也比较少,只知道这个是一个可并堆,可以很方便最大最小值,这个题目维护的是中位数。。。

对于递增的区间,把每一个数看成单独的堆,中位数就是自己。碰到递减的区间,合并这两个区间,维护其中位数。这里面的左偏树是一个最小堆,而不能是最大堆。拿第二个例子来说,如果维护的是最大堆的话,那么中位数到第二个时是4,因为你要处理的是比当前区间中位数小的区间,维护最大堆的话,那么中位数2这个信息就没了,被之前pop掉了。

DIV1D Animals and Puzzle


题意是给出一个n*m的格子,格子上非0即1,现在有q个询问,询问当前矩形里面的最大的都是1的正方形的边长。

首先dp来求当前位置作为正方形的右下角,其最大边长是多少。转移方程为
$$
dp[i][j]=min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1
$$
话说这个dp出来之后没过几天的Google APAC Test也出了这个dp,泪流满面

然后构建一个二维的st表,对于每一个询问,二分答案mid,满足x1+mid-1,y1+mid-1,x2,y2这个区间里面有大于等于mid的值,就OK。否则就没有该边长的正方形。

DIV1E Sonya Partymaker


题意(这个题意给的不好啊。。。不过这个dp倒是又有些神。。。也是见的少,啥都神。。。)给出1到m的环,有n个人坐在相应的位置上,每个人在事先选择好一个方向,顺时针还是逆时针,然后就开始走,每走一步,将所在位置的椅子扔掉,问最少多久之后扔完所有的椅子。

先把这个位置整理成1到n之间空隙最大的位置,然后就像叉姐说的,会发现1和2一定有往左跑的,(假设都向右跑,那么一定不是最优)枚举这个往左跑的,dp[i]表示第i个人能够覆盖的最远位置。

考虑各种情况:

第i个人向右跑,要求dp[i-1]大于等于A[i]-1。dp[i]=max(dp[i],A[i]+x)

第i个人向左跑,可能会是第i-1个人向右跑,为了覆盖该段区间,要求dp[i-1]>=A[i]-x-1,dp[i]=max(dp[i],A[i])

第i个人向左跑,可能会是第i-2向右跑,为了覆盖该段区间,要求dp[i-2]>=A[i]-x-1,dp[i]=max(dp[i],A[i-1]+x)

学习到了rotate函数,rotate(begin,middle,end)把该数组[begin,middle) 与区间[middle,end]内的元素做了交换