CF 344 Div. 2

CF #344 Div. 2

When I am Coding , only God and I know this .
After soon that , only God know this .
                                        ----Someone I don't know

A.Interview

给两个数组,定义函数 f(x,l,r)=xlxl+1...xrf(x,l,r)=x_l|x_{l+1}|...|x_r |的意思是按位或,xix_i是x数组中第i个数,现在要求

L=1nR=Lnmax(f(a,L,R)+f(b,L,R))\sum_{L=1}^{n}\sum_{R=L}^{n}max(f(a,L,R)+f(b,L,R))

1n10001\leq n \leq 10000ai,bi1090 \leq a_i,b_i \leq 10^9

.
.
.
.
.
.
.
.
.
.
.
因为范围很小,直接枚举就行

//author: CHC
//First Edit Time:	2016-03-05 09:08
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=1e+4;
const int MAXM=1e+5;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
int A[MAXN],B[MAXN];
int main()
{
    int n;
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++)scanf("%d",&A[i]);
        for(int i=1;i<=n;i++)scanf("%d",&B[i]);
        int ans=0;
        for(int i=1;i<=n;i++){
            int r1=A[i],r2=B[i];
            for(int j=i;j<=n;j++){
                r1|=A[j];r2|=B[j];
                ans=max(ans,r1+r2);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

扩展

如果1n1000001 \leq n \leq 100000怎么处理?如果不仅想求得最大值,而且还想求得L,R这两个值(必须满足L尽可能的大并且R尽可能的小)?
直接套用上面那个方法复杂度得爆炸O(n2)O(n^2)
唔。。。做法?把每个数字拆分二进制,然后从高到低枚举处理?
二分,先求得[1,n]的值,先固定左端点二分右端点得RR',然后再固定右端点二分左端点得LL'。得到[L,R][L',R']?唔。。有时间看下能不能证明。。
如果以上这种方法不行的话试试这样,枚举固定左端点,二分求最小右端点。复杂度大概是这样O(1log1+2log2+3log3+...+nlogn)O(1log1+2log2+3log3+...+nlogn)
唔。复杂度太高,还是拆分二进制,枚举二进制从最高位到最低位,找坐标,然后范围就出来了。

B.Print Check

有一个n*m大小的画版(n行m列),现在有k个以下的操作
1riai1 r_i a_i把第rir_i行染为aia_i
2ciai2 c_i a_i把第cic_i列染为aia_i
经过k个操作后把这个染色版n行m列输出
1n,m50001 \leq n,m \leq 5000nm100000nm\leq 100 0001k1000001 \leq k \leq 100000
.
.
.
.
.
.
.
.
.
.
.
.
如果每进行一次操作就完全执行一次,效率实在太低。
用两个哈希数组表示某行是什么颜色或者某列是什么颜色,然后对于每次操作有个权值,输出的时候比较一下权值就知道某行某列是哪个颜色了。

//author: CHC
//First Edit Time:	2016-03-05 09:16
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=10000;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
struct Tx {
    int x,val;
}R[MAXN],C[MAXN];
int main()
{
    int n,m,k;
    while(~scanf("%d%d%d",&n,&m,&k)){
        memset(R,0,sizeof(R));
        memset(C,0,sizeof(C));
        int op,t1,x;
        for(int i=1;i<=k;i++)
        {
            scanf("%d%d%d",&op,&t1,&x);
            if(op==1){
                R[t1].x=x;R[t1].val=i;
            }
            else {
                C[t1].x=x;C[t1].val=i;
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<m;j++){
                if(R[i].val>C[j].val)printf("%d ",R[i].x);
                else printf("%d ",C[j].x);
            }
            if(R[i].val>C[m].val)printf("%d\n",R[i].x);
            else printf("%d\n",C[m].x);
        }
    }
    return 0;
}

C.Report

有n个数,m个操作,操作有两种:
1ri1 r_i 把这个数组的[1,ri][1,r_i]区间按非递减排序
2ri2 r_i 把这个数组的[1,ri][1,r_i]区间按非递增排序
1n,m2000001 \leq n,m \leq 200000 , 这n个数aia_i的范围ai109|a_i| \leq 10^9
.
.
.
.
.
.
.
.
.
.
.
如果按照题意所叙述的来操作,每次操作来次排序。。复杂度要爆表了。。O(mnlogn)O(mnlogn),明显不可行也不能采取。
求一个特殊的子序列,在开始到某次操作的区间,只需要考虑最大的rir_i所进行的排序方式就行,因为在这次操作之前的排序都无意义。
所以。。思路来了。。(我就懒得画流程图了)

第一步
求这么一个特殊的最大子序列:
假设数列长度为100000,有1000个操作
400号的r400r_{400}最大,说明400之前的操作都是无用功,记录这个操作。然后从第401~1000次操作中找最大的rir_i,401i1000401 \leq i \leq 1000,然后依次迭代以上过程,求出这个特殊的子序列。
第二步
将取到的这个特殊子序列去重
因为获得到的这个特殊子序列可能存在某种相同方式的排序
比如获取到的子序列是这个样子的:
升 升 降 降 升 降
10 9 8 6 3 2
将它去重成这样:
升 降 升 降
10 8 3 2
第三步
对于数组重赋权值重排序,模拟操作过程,假设是以上四次操作
1 2 3 4 5 6 7 8 9 10 11
1:l1=11:l_1 = 1r1=10r_1 = 10curpos=1curpos=1,把1~10都赋值为max,排序方式为升
2:l2=12:l_2 = 1r2=8r_2 = 8curpos=8curpos=8,把1~8赋值为max-1,排序方式为降
3:l3=63:l_3 = 6r3=8r_3 = 8curpos=6curpos=6 ,把6~8赋值为max-2,排序方式为升

权值的重赋,排序方式可以和权值融在一个int中,占用一个二进制位就行
两颗线段树。。其实第一步可以用st算法
太久没敲算法题了。。犯了好多愚蠢的代码错误。。。

//author: CHC
//First Edit Time:	2016-03-05 09:51
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=200000 + 1000;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
#define lson L,mid,rt<<1
#define rson mid+1,R,rt<<1|1
struct Tree {
    int v,tpye,pos;
}tr[MAXN<<4];
void pushup(int rt){
    if(tr[rt<<1].v>tr[rt<<1|1].v){
        tr[rt]=tr[rt<<1];
    }
    else {
        tr[rt]=tr[rt<<1|1];
    }
}
struct TT{
    int t,r;
}A[MAXN];
void build(int L,int R,int rt){
    tr[rt].v=tr[rt].tpye=0;
    if(L==R){
        tr[rt].v=A[L].r;
        tr[rt].tpye=A[L].t;
        tr[rt].pos=L;
        return ;
    }
    int mid=(L+R)>>1;
    build(lson);
    build(rson);
    pushup(rt);
}
Tree querymaxpos(int L,int R,int rt,int l,int r){
    if(l<=L&&R<=r){
        return tr[rt];
    }
    int mid=(L+R)>>1;
    Tree t1,t2;
    t1.tpye=t2.tpye=0;
    if(l<=mid)t1=querymaxpos(lson,l,r);
    if(r>mid)t2=querymaxpos(rson,l,r);
    pushup(rt);
    if(t1.tpye==0)return t2;
    if(t2.tpye==0)return t1;
    if(t1.v>t2.v)return t1;
    return t2;
}
//区间更新,单点查询
struct Tree2{
    int x,flag,val;
}tr2[MAXN<<4];
void pushdown2(int rt){
    if(tr2[rt].flag){
        tr2[rt<<1]=tr2[rt];
        tr2[rt<<1|1]=tr2[rt];
        tr2[rt].flag=0;
    }
}
void build2(int L,int R,int rt){
    memset(&tr2[rt],0,sizeof(tr2[rt]));
    if(L==R){
        return ;
    }
    int mid=(L+R)>>1;
    build2(lson);build2(rson);
}
void update2(int L,int R,int rt,int l,int r,int val){
    //printf("update2 %d %d %d\n",L,R,val);
    //while(l>r);
    if(l<=L&&R<=r){
        tr2[rt].val=tr2[rt].x=val;
        tr2[rt].flag=1;
        return ;
    }
    pushdown2(rt);
    int mid=(L+R)>>1;
    if(l<=mid)update2(lson,l,r,val);
    if(r>mid)update2(rson,l,r,val);
    return ;
}
int C[MAXN];
void query2(int L,int R,int rt){
    if(L==R){
        C[L]=tr2[rt].x;
        return ;
    }
    pushdown2(rt);
    int mid=(L+R)>>1;
    query2(lson);query2(rson);
}
int n,m;
int B[MAXN];
Tree res[MAXN],res1[MAXN];
//升
int cmp1(int x,int y){
    return x<y;
}
//降
int cmp2(int x,int y){
    return x>y;
}
int (*cmp[2])(int,int)={cmp1,cmp2};
int D[MAXN];
int cmp3(int x,int y){
    int tx=C[x]>>1,ty=C[y]>>1;
    if(tx==ty){
        if(C[x]&1)return B[x]>B[y];
        else return B[x]<B[y];
    }
    else {
        return tx<ty;
    }
}
int main()
{
    while(~scanf("%d%d",&n,&m)){
        for(int i=1;i<=n;i++){
            scanf("%d",&B[i]);
        }
        for(int i=1;i<=m;i++){
            scanf("%d%d",&A[i].t,&A[i].r);
        }
        build(1,m,1);
        int tot=0;
        int l=1,r=m;
        while(l<=r){
            Tree mid=querymaxpos(1,m,1,l,r);
            res[tot++]=mid;
            l=mid.pos+1;
        }
        sort(B+1,B+res[0].v+1,cmp[res[0].tpye-1]);
        int tot1=0;
        res1[tot1++]=res[0];
        for(int i=1;i<tot;i++){
            if(res[i].tpye!=res[i-1].tpye)
                res1[tot1++]=res[i];
        }
        int tflag=res1[0].tpye-1;
        int tval=m+5;
        build2(1,res1[0].v,1);
        update2(1,res1[0].v,1,1,res1[0].v,(tval<<1)|tflag);
        l=1,r=res1[0].v;
        int curpos=1;
        for(int i=1;i<tot1;i++){
            if(l==curpos){
                int t=curpos;
                curpos+=res1[i].v-1;
                l=t;r=curpos;
            }
            else if(r==curpos){
                int t=curpos;
                curpos-=res1[i].v-1;
                l=curpos;r=t;
            }
            tflag=!tflag;
            --tval;
            update2(1,res1[0].v,1,l,r,(tval<<1)|tflag);
        }
        for(int i=1;i<=n;i++)D[i]=i;
        query2(1,res1[0].v,1);
        sort(D+1,D+1+res1[0].v,cmp3);
        for(int i=1;i<n;i++)printf("%d ",B[D[i]]);
        printf("%d\n",B[D[n]]);
    }
    return 0;
}
/*
#1 把C数组和D数组搞混淆了
#2 把tr数组和tr2数组搞混淆了
#3 if(l==curpos) 和 if(r==curpos)分开判断 这是错的,加个else
#4 去重遍历的上限变量名打错,m->tot
#5 去重代码变量名写错
 * */

D. Messenger

有个很长很长的字符串。为了简便,把它缩写成这这种格式。。
3-a 2-b 4-c 3-a 2-c
这个代表的字符串为aaabbccccaaacc
给两个字符串t和s,求s在t中出现的次数。
t和s有n和m部分,1n,m2000001\leq n,m \leq 200000,字符都为小写字符
比如下面两个样例:

输入
6 1
3-a 6-b 7-a 4-c 8-e 2-a
3-a
输出
6
s:aaa
t:aaabbbbbbaaaaaaacccceeeeeeeeaa
字符串s在字符串t中出现了三次

输入
5 3
3-a 2-b 4-c 3-a 2-c
2-a 2-b 1-c
输出
1
s:aabbc
t:aaabbccccaaacc
字符串s在字符串t中出现了一次

.
.
.
.
.
.
.
.
.
.
.
.
。。把相邻相同格式的给合并,然后对于字符串s特殊考虑
如果只有一部分,两部分,大于两部分的情况。
对于大于两部分的情况,除去头和尾选择中间部分,找匹配中间部分的在t字符串的起点坐标,然后对比s的头部和尾部。。
kmp可以搞。。