NOIP2014-5-17模拟赛

Problem 1 双色球(ball.cpp/c/pas)

【题目描述】

    机房来了新一届的学弟学妹，邪恶的chenzeyu97发现一位学弟与他同名，于是他当起了善良的学长233

“来来来，学弟，我考你道水题检验一下你的水平……”

一个栈内初始有n个红色和蓝色的小球，请你按照以下规则进行操作

1. 只要栈顶的小球是红色的，将其取出，直到栈顶的球是蓝色
2. 然后将栈顶的蓝球变成红色
3. 最后放入若干个蓝球直到栈中的球数为n

以上3步骤为一次操作

如栈中都是红色球，则操作停止，请问几次操作后停止

chenzeyu97出完题发现他自己不能AC所以想请你帮忙

【输入格式】

第一行为一个整数n，表示栈的容量为n

第二行为一个字符串，第i个字符表示自顶向下的第i个球的颜色，R代表红色，B代表蓝色

【输出格式】

一个整数表示操作数

【样例输入】

样例1：

3

RBR

样例2：

4

RBBR

【样例输出】

样例1：2

样例2：6

【样例解释】

样例1：

 

样例2：

 

【数据范围】

50%的数据，1<=n<=20

100%的数据，1<=n<=50

Problem 2 魔方(cube.cpp/c/pas)

【题目描述】

ccy（ndsf）觉得手动复原魔方太慢了，所以他要借助计算机。

ccy（ndsf）家的魔方都是3*3*3的三阶魔方，大家应该都见过。

（3的“顺时针”改为“逆时针”，即3 4以图为准。）
ccy（ndfs）从网上搜了一篇攻略，并找人翻译成了他自己会做的方法。现在告诉你他的魔方情况，以及他从网上搜到的攻略，请你求出最后魔方变成什么样子。

【输入格式】
　　　第一行，一串数字，表示从网上搜到的攻略。
　　　下面6*3行，每行3个数字，每三行表示魔方一个面的情况，六个面的顺序是前、后、左、右、上、下。

【输出格式】
　　　6*3行，表示处理后的魔方，形式同输入。

【样例输入】

23
121
221
111
123
321
111
123
321
132
132
231
132
121
112
233
332
111
333

【样例输出】

123
222
113
212
321
113
122
321
132
121
333
121
211
312
113
331
111
331

【样例解释】

 

【数据范围】

40%的数据，攻略的长度小于5且仅有4种操作的其中一种

100%的数据，攻略的长度小于100

Problem 3 czy的后宫(harem.cpp/c/pas)

【题目描述】

czy要妥善安排他的后宫，他想在机房摆一群妹子，一共有n个位置排成一排，每个位置可以摆妹子也可以不摆妹子。有些类型妹子如果摆在相邻的位置（隔着一个空的位置不算相邻），就不好看了。假定每种妹子数量无限，求摆妹子的方案数。

【输入格式】

输入有m+1行，第一行有两个用空格隔开的正整数n、m，m表示妹子的种类数。接下来的m行，每行有m个字符1或0,若第i行第j列为1，则表示第i种妹子第j种妹子不能排在相邻的位置，输入保证对称。（提示：同一种妹子可能不能排在相邻位置）。

【输出格式】

输出只有一个整数，为方案数（这个数字可能很大，请输出方案数除以1000000007的余数。

【样例输入】

2 2

01

10

【样例输出】

7

【样例说明】

七种方案为(空，空)、（空，1）、（1、空）、（2、空）、（空、2）、（1,1）、（2,2）。

【数据范围】

20%的数据，1＜n≤5,0＜m≤10。

60%的数据，1＜n≤200,0＜m≤100。

100%的数据，1＜n≤1000000000，0＜m≤100。

注：此题时限1.5s是因为本评测机跑太慢，大家正常做

但写的太丑可能T一俩个点

Problem 4 mex(mex.cpp/c/pas)

【题目描述】

 

【输入格式】

 

【输出格式】

 

【样例输入】

7 5

0 2 1 0 1 3 2

1 3

2 3

1 4

3 6

2 7

【样例输出】

3

0

3

2

4

【样例解释与数据范围】

 

---

T1:

这题一开始看数据范围这么小，于是乎直接模拟，T5个点

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define MAXN 55
using namespace std;
int stack[MAXN],top=0;
int cnt;
int n;
int ans=0;
int main()
{
    scanf("%d",&n);
    // 1 red 2 blue;
    for(int i=n;i>=1;i--){
        char c;
        scanf(" %c",&c);
        if('R'==c){
            stack[i]=1;
            cnt++;
        }
        else{
            stack[i]=2;
        }
    }
    top=n;
    while(1){
        ans++;
        while(1==stack[top]&&top){
            top--;
            cnt--;
        }
        if(2==stack[top]&&top){
            stack[top]=1;
            cnt++;
        }
        for(int i=top+1;i<=n;i++){
            stack[i]=2;
        }
        top=n;
        if(cnt==n){
            break;
        }
    }
    printf("%d
",ans);
    return 0;
}

后来发现其实是找规律的：

对于一个栈，我们只考虑从栈顶到第一个blue，即RRRRB，因为所有操作不可能干到这个B底下，

我们姑且无视B下面的东西吧

然后发现操作1次为BBBBR，再次无视这个R，变成了BBBB

然后发现操作分别变成RBBB BRBB RRBB ……

如同0000 1000 0100 1100 ……

规律出来了，对于栈中自上向下第i个B，把它变成R需要2^(i-1)，然后依次处理即可

 注意：用long long的时候就不可以把int类型的i直接(1<<(i-1))，会炸的

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
int n;
ll ans;
ll Power(int p){
    ll ret=1;
    for(int i=1;i<=p;i++){
        ret*=2;
    }
    return ret;
}
int main()
{
    char c;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf(" %c",&c);
        if('B'==c){
            ans+=Power(i);
        }
    }
    printf("%lld
",ans);
    return 0;
}

---

T2:

这题可以用一些技巧，比如操作2等价于操作1三次，

左旋一次等价于右旋三次等等

另外传址的函数可以在很大程度上简化程序

拼的是基本功啊

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#define REP(x,y) for(int x=1;x<=y;x++)
using namespace std;
void move(int s1[4][4],int s2[4][4],int s3[4][4],int s4[4][4],int x1,int y1,int x2,int y2){
    int t[4][4]={0};
    memcpy(t,s1,sizeof(t));
    for(int i=x1;i<=x2;i++){
        for(int j=y1;j<=y2;j++){
            s1[i][j]=s2[i][j];
            s2[i][j]=s3[i][j];
            s3[i][j]=s4[i][j];
            s4[i][j]=t[i][j];
        }
    }
}
void Lx(int ss[4][4]){
    int t[4][4]={0};
    for(int i=1;i<=3;i++){
        t[i][1]=ss[1][4-i];
        t[1][i]=ss[i][3];
        t[i][3]=ss[3][4-i];
        t[3][i]=ss[i][1];
    }
    t[2][2]=ss[2][2];
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            ss[i][j]=t[i][j];
        }
    }
}
void Rx(int ss[4][4]){
    Lx(ss),Lx(ss),Lx(ss);
}
int s[7][4][4];
char c[105];
void P2(){
    //1qian 2hou 3zuo 4you 5shang 6xia
    move(s[1],s[5],s[2],s[6],1,3,3,3);
    Lx(s[4]);    
}
void P1(){
    P2(),P2(),P2();
}
void P3(){
    //1qian 2hou 3zuo 4you 5shang 6xia
    move(s[1],s[3],s[2],s[4],1,1,1,3);
    Rx(s[5]);
}
void P4(){
    P3(),P3(),P3();
}
int main()
{
//    freopen("data.in","r",stdin);
//    freopen("my.out","w",stdout);
    scanf("%s",c+1);
    
    REP(k,6){
        REP(i,3){
            char p[4]={0};
            scanf("%s",p+1);
            REP(j,3){
                s[k][i][j]=p[j]-'0';
            }    
        }     
    } 
    int len=strlen(c+1);
    for(int p=1;p<=len;p++){
        
        if('1'==c[p]){
            P1();
        }
        else if('2'==c[p]){
            P2();
        }
        else if('3'==c[p]){
            P3();
        }
        else{
            P4();
        }
//printf("p=%d
",p);
//REP(k,6){
//    printf("k=%d
",k);
//    REP(i,3){
//        REP(j,3){
//            printf("%d",s[k][i][j]);
//        }
//        printf("
");
//    }     
//    printf("
");
//} 
    }
    
    REP(k,6) REP(i,3){
        REP(j,3){
            printf("%d",s[k][i][j]);
        }
        printf("
");
    } 
    return 0;
}

---

T3:

设f[i][j]表示i个座位，必须以第j个妹子为结尾的方案

然后f[i][j]=∑f[i-1][k] (j,k不矛盾)

当然矩阵快速幂优化即可，详见代码

 注意：

1，妹子可以为空，那么直接m++即可，多出来的矩阵用1补足

2，输入的01矩阵和转移矩阵正好反的

3，对于矩阵较大的内存，最好不要用递归快速幂，直接用循环即可

4，切记要开long long！！！

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<iostream>
#define MAXN 105
#define MOD 1000000007
#define ll long long
using namespace std;
struct Mat{
    int len;
    ll s[MAXN][MAXN];
    Mat(){
        len=0;
        memset(s,0,sizeof(s));
    } 
    void operator *= (const Mat &A){
        Mat t;
        len=A.len;
        for(int i=1;i<=len;i++){
            for(int j=1;j<=len;j++){
                for(int k=1;k<=len;k++){
                    t.s[i][j]=(t.s[i][j]+(s[i][k]*A.s[k][j])%MOD)%MOD;
                }
            }
        }
        for(int i=1;i<=len;i++){
            for(int j=1;j<=len;j++){
                s[i][j]=t.s[i][j];
            }
        }
    }
    void operator = (const Mat &A){
        len=A.len;
        for(int i=1;i<=len;i++){
            for(int j=1;j<=len;j++){
                s[i][j]=A.s[i][j];
            }
        }
    }
};
int n,m;
Mat Power(Mat A,int p){
    Mat ret;
    ret.len=m+1;
    for(int i=1;i<=ret.len;i++){
        ret.s[i][i]=1;
    }
    Mat t; t=A;
    for(;p;p>>=1){
        if(p&1){
            ret*=t;
        }
        t*=t;
    }
    return ret;
}
int main()
{
//    freopen("harem2.in","r",stdin);
    Mat A;
    scanf("%d%d",&n,&m);
    if(1==n){
        printf("%d
",m+1);
    }
    char ch[MAXN]={0};
    for(int i=1;i<=m;i++){
        scanf("%s",ch+1);
        for(int j=1;j<=m;j++){ 
            if('0'==ch[j])
            A.s[i][j]=1;
        }
    }
    A.len=m+1;
    for(int i=1;i<=m+1;i++){
        A.s[m+1][i]=A.s[i][m+1]=1;
    }
    Mat t=Power(A,n-1);
    ll ans=0;
    int len=t.len;
    for(int i=1;i<=len;i++){
        for(int j=1;j<=len;j++){
            ans=(ans+t.s[i][j])%MOD;
        }
    }
    cout<<ans<<endl;
    return 0;
}

---

T4:

我当时用莫队算法+暴力，60分

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#define MAXN 200005
using namespace std;
struct Ask{
    int L,R;
    int lb,id;
    int ans;
    Ask(){
        L=R=lb=ans=0;
    }
};
bool comp1(const Ask &p1,const Ask &p2){
    if(p1.lb!=p2.lb){
        return (p1.lb<p2.lb);
    }
    else{
        return (p1.R<p2.R);
    }    
}
bool comp2(const Ask &p1,const Ask &p2){
    return (p1.id<p2.id);
}
Ask s[MAXN];
int n,T;
int b[MAXN];
int a[MAXN];
int main()
{
//    freopen("data.in","r",stdin);
    scanf("%d%d",&n,&T);
    int size=sqrt(n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=T;i++){
        scanf("%d%d",&s[i].L,&s[i].R);
        s[i].lb=s[i].L/size;
        s[i].id=i;
    }
    sort(s+1,s+T+1,comp1);
    int x=1,y=0;
    int t=0;
    for(int i=1;i<=T;i++){
        int L=s[i].L,R=s[i].R;
        if(x<L){
            for(int j=x;j<L;j++){
                b[a[j]]--;
                if(!b[a[j]]){
                    t=min(t,a[j]);
                }
            }
        }
        else if(x>L){
            for(int j=x-1;j>=L;j--){
                if(!b[a[j]]&&t==a[j]){
                    for(t++;;t++){
                        if(!b[t]){
                            break;
                        }
                    }
                }
                b[a[j]]++;
            }
        }
        if(y<R){
            for(int j=y+1;j<=R;j++){
                if(!b[a[j]]&&t==a[j]){
                    for(t++;;t++){
                        if(!b[t]){
                            break;
                        }
                    }
                }
                b[a[j]]++;
            }
        }
        else if(y>R){
            for(int j=y;j>R;j--){
                b[a[j]]--;
                if(!b[a[j]]){
                    t=min(t,a[j]);
                }
            }
        }
        x=L,y=R;
        s[i].ans=t;
    }
    sort(s+1,s+T+1,comp2);
    for(int i=1;i<=T;i++){
        printf("%d
",s[i].ans);
    }
    return 0;
}

其实这题并不好写，原因这些数据都是离散的，搞不出来连续的，用数据结构不好维护

于是可以构造出连续的数据：Next[i]=j (a[i]==a[j]&&i<j)

然后按左节点从左到右依次解决，当左节点变化时，相应的j~Next[j]-1用线段树进行更新即可

这样可以用离线算法解决了，转化为典型的离线问题

另:线段树切记开4倍啊QAQ

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define MAXN 200005
#define INF 0x7f7f7f7f
using namespace std;
int mex[MAXN];
int n,m;
int dat[MAXN*4],tag[MAXN*4];

void build(int k,int L,int R){
//build:L+1==R return
    if(L+1==R){
        dat[k]=mex[L];
        return ;
    }
    build(k<<1,L,(L+R)>>1);
    build(k<<1|1,(L+R)>>1,R);
}
void pushdown(int k){
    int lc=(k<<1),rc=(k<<1|1);
    dat[lc]=min(dat[lc],tag[k]);
    dat[rc]=min(dat[rc],tag[k]);
    tag[lc]=min(tag[lc],tag[k]);
    tag[rc]=min(tag[rc],tag[k]);
    tag[k]=INF;
}
void update(int a,int b,int k,int L,int R,int t){
    if(b<=L||R<=a){
        return;
    }
    else if(a<=L&&R<=b){
        dat[k]=min(dat[k],t);
        tag[k]=min(tag[k],t);
    }
    else{
        if(tag[k]!=INF){
            pushdown(k);
        }
        update(a,b,k<<1,L,(L+R)>>1,t);
        update(a,b,k<<1|1,(L+R)>>1,R,t);
    }
}
int find(int x,int k,int L,int R){
    if(L+1==R){
        return dat[k];
    }
    int mid=(L+R)>>1;
    if(tag[k]!=INF){
        pushdown(k);
    }
    if(x<mid){
        return find(x,k<<1,L,mid);
    }
    else{
        return find(x,k<<1|1,mid,R);
    }
}
struct Ask{
    int L,R;
    int id,ans;
    Ask(){
        L=R=id=ans=0;
    }
}s[MAXN];
bool comp1(const Ask &p1,const Ask &p2){
    return (p1.L<p2.L);
}
bool comp2(const Ask &p1,const Ask &p2){
    return (p1.id<p2.id);
}
int a[MAXN],b[MAXN];
int Next[MAXN],first[MAXN];

int main()
{
//    freopen("T1.in","r",stdin);
//    freopen("my.out","w",stdout);
    memset(dat,0x7f,sizeof(dat));
    memset(tag,0x7f,sizeof(tag));
//    freopen("data.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&s[i].L,&s[i].R);
        s[i].id=i;
    }
    int k=0;
    for(int i=1;i<=n;i++){
        b[a[i]]=1;
        while(b[k]){
            k++;
        }
        mex[i]=k;
    }
    build(1,1,n+1);
    for(int i=n;i>=1;i--){
        Next[i]=first[a[i]];
        first[a[i]]=i;
        if(!Next[i]){
            Next[i]=n+1;
        }
    }
    sort(s+1,s+m+1,comp1);
    int nL=1;
    for(int i=1;i<=m;i++){
        if(nL<s[i].L){
            for(int j=nL;j<s[i].L;j++){
                update(j,Next[j]-1+1,1,1,n+1,a[j]);
            }
            nL=s[i].L;
        }
//        for(int j=1;j<=n;j++){
//            printf("%d ",find(j,1,1,n+1));
//        }
//        printf("
");
        s[i].ans=find(s[i].R,1,1,n+1);
    }
    sort(s+1,s+m+1,comp2);
    for(int i=1;i<=m;i++){
        printf("%d
",s[i].ans);
    }
    return 0;
}