Round #276 (Div 1) 总结

codeforces

---

A.Bits

来源

http://codeforces.com/contest/484/problem/A

题目

给出N次询问(N<=10^4)。每次询问一个区间[L,R] (1<=L<=R<=10^18)，问区间内二进制1个数最多的数是几？多种答案输出最小的。

解答

因为要二进制最多的数最小，所以最优答案的二进制低位是连续的1。我的做法是从高位枚举，枚举到二进制的第k位，如果上限R这一位是1，而下限L这一位是0，这时候我们令x=R，分两种情况。
情况一，如果x中比k低位的含有0，则把x的第k位变成0，比k低位的变成1，就可以得到1最多并且小于R大于等于L的数。
情况二，x中比k低位的全是1，那么x的第k位的1就可保留，答案其实就是R。
注意还有L=R的情况。

总结

做这题的时候打表发现规律，但是一开始漏了情况二，直接把第k位变成0，低位的变成1，同时也漏了L=R的情况，导致WA了两发。
关于数位的题目，经验不足。

---

B.Maximum Value

来源

http://codeforces.com/contest/484/problem/B

题目

给出N个数(N<=2*10^5)，每个数大于0不超过10^6。任意选两个数ai和aj，当满足ai>=aj，求出ai mod aj。问最大的ai mod aj是多少？

解答

由于数不大，可以对读入用桶排序。然后将桶扫一遍，预处理一个pre[]数组，记录桶排后每个位置的前一个数是多少(不包括该位置的数)。比如，读入两个数2和4，预处理的pre[1]=0(代表没有)，pre[2]=0，pre[3]=2，pre[4]=2，pre[5]=4...
然后枚举除数aj，遍历k=aj的2倍，3倍，...，MAX/aj的上取整倍(MAX是读入的最大的数，pre[]预处理的时候可以预处理到pre[2*MAX])，每次遍历用pre[k]做被除数，求出最大的pre[k] mod aj。
由于重复的aj可以不枚举，所以时间复杂度平均起来是$O(N*ln(MAX))$。

总结

这题一开始想的比较复杂，想到方法后写错了，遍历aj的倍数时，本来应该写成k+=a[j]，我却写成了k++，导致TLE一次。

---

C.Strange Sorting

来源

http://codeforces.com/contest/484/problem/C

题目

给出一个长度为N的字符串s，要将字符串进行M次操作，每次操作给出两个数k和d。首先对s[0..k-1]进行变换，然后对变换后的字符串s[1..k]进行变换，以此类推，直到对s[N-k..N-1]变换为止。对每次变换s[i..i+k-1]，把k个字符取出，放入r[0..k-1]，对0..k-1分别mod d，以mod d后的余数对r[0..k-1]进行稳定排序，排序后的结果按顺序放回s[i..i+k-1]。M次操作，输出每次操作后的s。(1<=N*M<=10^6,1<=d<=k<=N)
例：
qwerty进行一次k=4,d=2的操作
qwerty -> qewrty -> qerwty -> qertwy 输出qertwy
若再进行一次k=6,d=3的操作
qertwy -> qtewry 输出qtewry

解答

这是一道数学题目，也是本场比赛目前过的最少的题目。其实并不难，就是用到了置换群的快速幂而已。
对每次操作，我们构造三个置换群。L代表全部元素左移一位(0移到N-1)，P代表前k位[0..k-1]进行关于mod d的变换并且后N-k位[k..N-1]不变，R代表全部元素右移一位(N-1移到0)。那么每次操作就可以表示为：

$$P*(L*P)^{N-k}*R^{N-k}$$
由于置换群满足结合律，所以我们可以用快速幂求出变换后的置换群，每次操作的时间复杂度是$O(N*log(N-k))$。
总时间复杂度是$O(M*N*log(N))$。

总结

1.此题跟字符串算法无关

2.关于位置的变换可以构造置换群

3.置换群满足结合律，可以快速幂

4.这道题不想写错，就要多举例子，不要想当然地写

---

D.Kindergarten

来源

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

题目

给出N个正数A[i](N<=10^6)，你可以将它们分成若干个连续的区间，每个区间的价值等于这个区间最大的数减去最小的数。问：所有区间总价值的最大值是多少？

解答

由于A和B错的太多，后面的题目估计想不到，导致我萌生水水的想法，没有认真思考题目。看了题解后，才发现此题并不难。
可以证明的是，存在一种最优划分，使得划分出来的所有区间一定都是单调的(非递减或非递增)，所以我们可以对单调区间的端点进行dp。
首先对连续相同的数去重，只保留两个(其它的都不会影响结果)。然后通过严格的单调性，找出单调区间的两个端点，i和j(i<j)，F[j]=max(F[i]+abs(A[i+1]-A[j]),F[i-1]+abs(A[i]-A[j]))，转移中用到了F[i-1]，所以为了下一次转移，得求出F[j-1]，F[j-1]=max(F[i]+abs(A[i+1]-A[j-1]),F[i-1]+abs(A[i-1]-A[j-1]))，然后令i=j，j=i+1，继续找下一个区间端点。

总结

1.区间内的最大最小差，划分在端点最优

2.处理非严格的单调区间，可以去重的话会方便一点，CF还有一题也是处理非严格单调区间的端点来做的:http://codeforces.com/problemset/problem/279/C (这题我做复杂了，用了离散话加树状数组处理区间覆盖，其实可以预处理好后给每一合法段一个编号(端点处可以有两个编号)，在线查询询问区间的端点是否具有相同编号来完成，时间是线性的)

---

E.Sign on Fence

来源

http://codeforces.com/contest/484/problem/E

题目

给出N个宽度为1，高度为H[i]的矩形，从1到N连续挨着排。有M次询问，每次询问一段区间[L,R]中组成宽度为wid的矩形的最高高度是多少？(N,M<=10^5, H[i]<=10^9)

解答

题解是二分答案+可持久化线段树。
假设二分答案是k，那么我们对每个H[i]>=k标记为1，H[i]<k标记为0，那么问题就转化为询问区间[L,R]内最长连续1的长度，如果这个长度>=wid就合法，否则就不合法。
对一个k，可以构造一个线段树来维护。记录四个值：pref该区间左边连续1的个数，suf该区间右边连续1的个数，len该区间长度，maxf该区间最大连续1的个数。具体合并维护如下：

struct Tnode
{
    Tnode *l,*r;   // 左右孩子区间
    int pref,suf,len,maxf;
    Tnode() { l=r=NULL; pref=suf=len=maxf=0; }
    void init(int x) { l=r=NULL; pref=suf=maxf=0; len=x; } //线段树区间长度固定，可以一开始就处理好
    void up()
    {
        maxf=max(l->suf + r->pref,max(l->maxf,r->maxf));
        suf=r->suf + (r->len==r->suf ? l->suf : 0);
        pref=l->pref + (l->len==l->pref ? r->pref : 0);
    }
};

由于有N个k，所以我们不可能全部构造，要用可持久化。假设一开始k为无穷大，[1..N]全部位置为0。然后从大到小加入H[i]，每次单点修改第i位为1并可持久化维护。这样就可以$O(4*N+N*log(N))$预处理好所有答案k的线段树。
最后每次询问，二分答案，判断区间[L,R]的最大连续1是否>=wid即可。
由于我可持久化是用指针写的，但询问的时候得返回结构体，得写一个类似上面的结构体合并。如下：

Tnode Ans_up(Tnode &l,Tnode &r)
{
    Tnode ret;
    ret.maxf=max(l.suf + r.pref,max(l.maxf,r.maxf));
    ret.suf=r.suf + (r.len==r.suf ? l.suf : 0);
    ret.pref=l.pref + (l.len==l.pref ? r.pref : 0);
    ret.len=l.len + r.len; //这个一定要加，不同于线段树区间的长度固定
    return ret;
}

时间复杂度是$O(4*N+N*log(N)+M*log^{2}(N))$

总结

1.复杂的找最值可用二分答案简化

2.区间达到要求最长宽度可转化为连续1最大

3.可持久化的对象不止是区间，也可以是高度

4.区间第k大也可以用二分答案+可持久化线段树(或树状数组)做，但没有直接用对区间的可持久化线段树优

5.我想这题的时候，只想了从小到大预处理每一块高度的最远区间范围，如果询问的区间都是[1,N]才能做，不能处理任意区间。没有想到高度从大到小的预处理，当然也没想到连续1的线段树。

6.总结下此题的思路:先二分、判断合法(询问区间连续1最大)、对高度可持久化

补充一点，此题还可以用整体二分离线做(cdq分治，所有询问一起二分)，数据结构不用可持久化，但要多维护一个“1变成0”的操作

---

魏子卿
2015年11月29日