周末作业20170508

题解

A - Hotel (POJ3667)
题目详情
题目大意：

一个旅店需要经常对房间进行检查，当输入（1，a）时表示需要入住a个连续房间，输出这几个房间最小的房间号，如房间不够时则输出0；（2，a，b）时，表示a->a+b-1个房间需要办理退房

解题思路：

线段树区间合并，加上lazy标记

AC代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn=50005;
int msum[maxn<<2],lsum[maxn<<2],rsum[maxn<<2],lazy[maxn<<2];
//msum表示 这一节点的总的连续空房间数；lsum表示从左端开始连续的空房间数；rsum表示从右端开始的连续空房间数，lazy表示这个节点是否被标记，如被标记则调用时则需要更新。
void build(int l,int r,int rt){// 建树每个节点的连续空房间总数等于这个区间的房间数
    msum[rt]=lsum[rt]=rsum[rt]=r-l+1;
    lazy[rt]=-1;
    if(l==r) return ;
    int m=(r+l)>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
}
void pushdown(int rt,int len){//标志向下传，延迟标志，简单来说就是先标志，然后等到下次询问或者更新时再去更新线段树
    if(lazy[rt]!=-1){
        lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt];
        msum[rt<<1]=rsum[rt<<1]=lsum[rt<<1]=lazy[rt]?0:len-(len>>1);//如果c为1表示入住，全部置0，否则则恢复则以区间长度
        msum[rt<<1|1]=rsum[rt<<1|1]=lsum[rt<<1|1]=lazy[rt]?0:(len>>1);
        lazy[rt]=-1;//表示这一节点已经处理
    }
}
void pushup(int rt,int len){//将左右子区间合并
    lsum[rt]=lsum[rt<<1];
    rsum[rt]=rsum[rt<<1|1];
    if(lsum[rt]==len-(len>>1))//如果此节点从左边开始房间数恰好等于左子树的长度，则再加上右子树从左边开始的连续房间数
        lsum[rt]+=lsum[rt<<1|1];
    if(rsum[rt]==(len>>1))
        rsum[rt]+=rsum[rt<<1];
    msum[rt]=max(lsum[rt<<1|1]+rsum[rt<<1],max(msum[rt<<1],msum[rt<<1|1]));//在左右子树和区间合并中选取最大
}
void update(int L,int R,int c,int l,int r,int rt){
    if(L<=l&&r<=R){
        msum[rt]=lsum[rt]=rsum[rt]=c?0:r-l+1;
        lazy[rt]=c;
        return ;
    }
    pushdown(rt,r-l+1);//先传递标记
    int m=(r+l)>>1;
    if(L<=m) update(L,R,c,l,m,rt<<1);
    if(m<R) update(L,R,c,m+1,r,rt<<1|1);
    pushup(rt,r-l+1);// 再更新合并区间
}
int  query(int w,int l,int r,int rt){
    if(l==r) return l;
    pushdown(rt,r-l+1);
    int m=(r+l)>>1;
    if(msum[rt<<1]>=w) return query(w,l,m,rt<<1);//左子树
    else if(rsum[rt<<1]+lsum[rt<<1|1]>=w) return m-rsum[rt<<1]+1;//合并区间中考虑
    return query(w,m+1,r,rt<<1|1);//考虑右子树
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    build(1,n,1);
    while(m--){
        int tp,a,b;
        scanf("%d",&tp);
        if(tp==1){
            scanf("%d",&a);
            if(msum[1]<a) printf("0\n");
            else {//表示肯定能找到
                int q=query(a,1,n,1);
                printf("%d\n",q);
                update(q,q+a-1,1,1,n,1);
            }
        }
        else {
            scanf("%d%d",&a,&b);
            update(a,a+b-1,0,1,n,1);
        }
    }
    return 0;
}

B - A Corrupt Mayor's Performance Art（HDU5023）
题目详情

题目大意：

（p，a，b，c）表示（a，b）上c这个颜色；（q，a，b）表示查询（a，b）区间内共有多少中颜色，从颜色升序输出

解题思路：

因为最多只有30种颜色，所以可以用2的幂分别表示一种颜色，然后区间和与每一位进行与运算，则可以算出有多少种颜色，线段树lazy标记

AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int maxn=1000005;
typedef long long  LL;
LL add[maxn<<2],sum[maxn<<2];//sum表示这个节点区间颜色的和，add表示lazy标记
int ans[35];
char s[5];
void pushup(int rt){//合并左右子树颜色种类
    sum[rt]=sum[rt<<1]|sum[rt<<1|1];
}
void build(int l,int r,int rt){//建树
    add[rt]=0;
    if(l==r){
        sum[rt]=2;//先将每一个初始化为2
        return ;
    }
    int m=(r+l)>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    pushup(rt);
}
void pushdown(int rt){
    if(add[rt]){
        add[rt<<1]=add[rt<<1|1]=add[rt];
        sum[rt<<1]=sum[rt<<1|1]=add[rt];
        add[rt]=0;
    }
}
void update(int L,int R,int c,int l,int r,int rt){
    if(L<=l&&r<=R){
        add[rt]=1<<(c-1);//add存贮颜色类别，传递
        sum[rt]=1<<(c-1);
        return ;
    }
    int m=(l+r)>>1;
    pushdown(rt);//先向底层传递
    if(L<=m)  update(L,R,c,l,m,rt<<1);
    if(m<R)  update(L,R,c,m+1,r,rt<<1|1);
    pushup(rt);//再从底层向上更新
}
LL query(int L,int R,int l,int r,int rt){
    LL res=0;
    if(L<=l&&r<=R)
        return sum[rt];
    pushdown(rt);
    int m=(r+l)>>1;
    if(L<=m) res|=query(L,R,l,m,rt<<1);
    if(m<R)  res|=query(L,R,m+1,r,rt<<1|1);
    return res;
}
int main(){
    int n,m,a,b,c,cnt;
    while(~scanf("%d%d",&n,&m)){
        if(n==0&&m==0) break;
        build(1,n,1);
        while(m--){
            scanf("%s",s);
            if(s[0]=='Q'){
                memset(ans,0,sizeof(ans));
                cnt=0;
                scanf("%d%d",&a,&b);
                LL q=query(a,b,1,n,1);
                for(int i=0;i<=30;i++)//一位一位进行位运算
                    if(q&(1<<i)) ans[cnt++]=i+1;
                for(int i=0;i<cnt;i++)
                    printf(i==0?"%d":" %d",ans[i]);
                printf("\n");

            }
            else {
                scanf("%d%d%d",&a,&b,&c);
                update(a,b,c,1,n,1);
            }
        }
    }
    return 0;
}

C - Assignment（HDU 5289）
题目详情
题目大意：

一个连续区间的的最大值和最小值之差小于k，问一个数组这样区间的个数

** 解题思路：**

第一种方法RMQ（适用于重叠区间不会对结果造成影响的（最值，gcd等）），第二种方法单调队列

AC代码：
RMQ

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;
int dp1[100005][30],dp2[100005][30],a[100005],n,m;//dp1表示最大值，dp2表示最小值
void init_rmp(){  //一般的RMQ的写法
    for(int i=1;i<=n;i++){
        dp1[i][0]=a[i];
        dp2[i][0]=a[i];
    }
    for(int j=1;(1<<j)<=n;j++){
        for(int i=1;(i+(1<<j)-1)<=n;i++){
            dp1[i][j]=max(dp1[i][j-1],dp1[i+(1<<(j-1))][j-1]);
            dp2[i][j]=min(dp2[i][j-1],dp2[i+(1<<(j-1))][j-1]);
        }
    }
}
int rmp(int l,int r){
    int k=0;
    while(((1<<(k+1)))<=r-l+1) k++;//找到小于等于这个数的2的次幂
    return max(dp1[l][k],dp1[r-(1<<k)+1][k])-min(dp2[l][k],dp2[r-(1<<k)+1][k]);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%d",a+i);
        init_rmp();
        long long ans=0;
        int tp=1;
        for(int i=1;i<=n;i++){//先固定这个区间的右端点，再找出使最值小于m的左端点的最小值
            while(rmp(tp,i)>=m&&tp<i) tp++;
            ans+=(i-tp+1);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

单调队列

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>

using namespace std;

typedef long long LL;
deque<LL> q1,q2;
LL a[100005];

int main(){// q1降序，q2升序
    int n,T;
    LL ans,k;
    scanf("%d",&T);
    while(T--){
        scanf("%d%lld",&n,&k);
        for(int i=1;i<=n;i++)
            scanf("%lld",a+i);
        ans=0;
        while(!q1.empty()) q1.pop_back();
        while(!q2.empty()) q2.pop_back();
        int i,j=1;
        for(i=1;i<=n;i++){
            while(!q1.empty()&&q1.back()<a[i])
                q1.pop_back();
            q1.push_back(a[i]);//将比a[i]小的值全部去除，对结果不造成影响
            while(!q2.empty()&&q2.back()>a[i])
                q2.pop_back();
            q2.push_back(a[i]);//将比a[i]大的值全部去除，对结果不造成影响
            while(!q1.empty()&&!q2.empty()&&q1.front()-q2.front()>=k){
                ans+=(i-j);//这里表示当i添加到最值大于m，则说明j到i-1满足条件所以ans+=（i-1-j+1）；
                if(q1.front()==a[j]) q1.pop_front();
                if(q2.front()==a[j])  q2.pop_front();
                j++;

            }
        }
        while(j<=n){//此处容易忘记，注意可能并还没有比较完
            ans+=(i-j);
            j++;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

D - GCD HDU 5726
题目详情
题目大意：

求一个区间gcd，并求整个数组等于此gcd的区间个数

解题思路：

一个区间的gcd用RMQ就可以解决，但是求个数就有些麻烦，先固定一个一个左端，再找出等于gcd等于这一点最大右端点（二分，固定左端点往右是非增序列），再求出此左端点与刚才最大右端点+1的端点gcd，再求出一个最大右端点，知道右端点等于n。将左端点固定从1~n则算出所有的gcd的值个数（用map贮存）
AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;

map<int ,long long > mp;
int n,m,T,ncase,dp[100005][30],a[100005];
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
void rmq(){//RMQ
    for(int i=1;i<=n;i++)
        dp[i][0]=a[i];
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            dp[i][j]=gcd(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int findx(int l,int r){
    int k=(int)log2((double)(r-l+1.0));
    return gcd(dp[l][k],dp[r-(1<<k)+1][k]);
}
void settable(){
    mp.clear();
    for(int i=1;i<=n;i++){//遍历左端点
        int g=dp[i][0],j=i;
        while(j<=n){
            int l=j,r=n;
            while(l<r){  //二分求其最大右端点
                int mid=(l+r+1)>>1;
                if(findx(i,mid)==g) l=mid;
                else r=mid-1;
            }//得到此gcd最大右端点
            mp[g]+=(l-j+1);
            j=l+1;//将最大右端点右移一位
            g=findx(i,j);//求一新的gcd；
        }
    }
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",a+i);
        rmq();
        settable();
        int x,y;
        scanf("%d",&m);
        printf("Case #%d:\n",++ncase);
        for(int i=0;i<m;i++){
            scanf("%d%d",&x,&y);
            int tp=findx(x,y);
            printf("%d %lld\n",tp,mp[tp]);
        }
    }
    return 0;
}