NOIP模拟赛20161022

2021-09-17 21:46:51

NOIP模拟赛2016-10-22

题目名

东风谷早苗

西行寺幽幽子

琪露诺

上白泽慧音

源文件

robot.cpp/c/pas

spring.cpp/c/pas

iceroad.cpp/c/pas

classroom.cpp/c/pas

输入文件

robot.in

spring.in

iceroad.in

classroom.in

输出文件

robot.out

spring.out

iceroad.out

classroom.out

时间限制

1000MS

1000MS

1000MS

1000MS

内存限制

64MB

128MB

128MB

128MB

测试点

20

20

10

10

测试点分值

5

5

10

10

Problem 1

东风谷早苗(robot.cpp/c/pas)

题目描述

在幻想乡，东风谷早苗是以高达控闻名的高中生宅巫女。某一天，早苗终于入手了最新款的钢达姆模型。作为最新的钢达姆，当然有了与以往不同的功能了，那就是它能够自动行走，厉害吧（好吧，我自重）。早苗的新模型可以按照输入的命令进行移动，命令包含’E’、’S’、’W’、’N’四种，分别对应四个不同的方向，依次为东、南、西、北。执行某个命令时，它会向着对应方向移动一个单位。作为新型机器人，自然不会只单单执行一个命令，它可以执行命令串。对于输入的命令串，每一秒它会按照命令行动一次。而执行完命令串最后一个命令后，会自动从头开始循环。在0时刻时早苗将钢达姆放置在了(0,0)的位置，并且输入了命令串。她想要知道T秒后钢达姆所在的位置坐标。

输入格式

第1行：一个字符串，表示早苗输入的命令串，保证至少有1个命令

第2行：一个正整数T

输出格式

第1行：两个整数，表示T秒时，钢达姆的坐标

输入样例

NSWWNSNEEWN

12

输出样例

-1 3

数据范围

对于60%的数据：T <= 500,000且命令串长度 <= 5,000

对于100%的数据：T <= 2,000,000,000且命令串长度<= 5,000

注意

向东移动，坐标改变改变为(X+1,Y);

向南移动，坐标改变改变为(X,Y-1);

向西移动，坐标改变改变为(X-1,Y);

向北移动，坐标改变改变为(X,Y+1);

很水的模拟  每一串命令位置变化是一样的

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int N=;

typedef long long ll;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int t,n,sx=,sy=,x=,y=,dx[],dy[];

char s[N];

int main(int argc, const char * argv[]){

    freopen("robot.in","r",stdin);

    freopen("robot.out","w",stdout);

    scanf("%s%d",s+,&t);

     dx['E']=;dy['E']=;

     dx['S']=;dy['S']=-;

     dx['W']=-;dy['W']=;

     dx['N']=;dy['N']=;

     n=strlen(s+);

    for(int i=;i<=n;i++){

        sx+=dx[s[i]];sy+=dy[s[i]];

    }

    int k=t/n,b=t%n;

    while(k--){x+=sx;y+=sy;}

    for(int i=;i<=b;i++){

        x+=dx[s[i]];y+=dy[s[i]];

    }

    printf("%d %d",x,y);

}

Problem 2

西行寺幽幽子(spring.cpp/c/pas)

题目描述

在幻想乡，西行寺幽幽子是以贪吃闻名的亡灵。不过幽幽子可不是只会吃，至少她还管理着亡灵界。话说在幽幽子居住的白玉楼有一颗常年不开花的樱树——西行妖。幽幽子决定去收集人间的春度，聚集起来让西行妖开花。很快，作为幽幽子家园艺师的魂魄妖梦收集到了M个单位的春度。并且在这段时间里，幽幽子计算出要让西行妖开出一朵花需要N个单位的春度。现在幽幽子想要知道，使用所有的春度，能够让西行妖开出多少朵花。

输入格式

第1行：一个正整数M

第2行：一个正整数N

N,M的位数不超过L，L的范围在题目后面给出

输出格式

第1行：一个整数ans，表示能开出花的朵数

输入样例

73861758

12471

输出样例

5922

数据范围

对于60%的数据：L <= 2,000且ans <= 2,000

对于100%的数据：L <= 20,000且ans <= 2,000,000,000

高精度除法 二分答案来试探

没用ll只有60分不开心，因为2e9+2e9还有*2e9都会溢出

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int N=2e4+,INF=2e9;

typedef long long ll;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

struct big{

    ll l,d[N];

    big(){l=;}

};

char s[N];

big a,b,c;

bool check(big &a,big &b){//a>=b

    if(a.l>b.l) return ;

    if(a.l<b.l) return ;

    for(int i=a.l;i>=;i--){

        if(a.d[i]>b.d[i]) return ;

        if(a.d[i]<b.d[i]) return ;

    }

    return ;

}

//void jian(big &a,big &b){

//    int g=0,l=b.l;

//    for(int i=1;i<=l;i++){

//        if(a.d[i]<b.d[i]){

//            a.d[i+1]--;

//            a.d[i]+=10;

//        }

//        a.d[i]-=b.d[i];

//    }

//    l++;

//    while(a.d[l]<0){a.d[l]+=10;a.d[l+1]--;l++;}

//    while(a.d[a.l]==0) a.l--;

//}

void cheng(big &a,ll b){

    ll g=,l=a.l;

    for(int i=;i<=l;i++){

        ll t=a.d[i]*b+g;

        a.d[i]=t%;

        g=t/;

    }

    l++;

    while(g){

        a.d[l]=g%;

        g/=;

        l++;

    }

    a.l=l-;

}

void cpy(big &a,big &b){//a<---b

    a.l=b.l;

    for(int i=b.l;i>=;i--) a.d[i]=b.d[i];

}

int main(){

    freopen("spring.in","r",stdin);

    freopen("spring.out","w",stdout);

    scanf("%s",s+);

    int len=strlen(s+);

    for(int i=;i<=len;i++) a.d[len-i+]=s[i]-'';

    a.l=len;               //printf("l %d\n",a.l);for(int i=a.l;i>=1;i--) printf("%c",a.d[i]+'0);

    scanf("%s",s+);

    len=strlen(s+);

    for(int i=;i<=len;i++) b.d[len-i+]=s[i]-'';

    b.l=len;

    if(!check(a,b)) printf("");

    else{

        ll l=,r=INF,ans=-;

        while(l<=r){//printf("%d %d\n",l,r);

            ll m=(l+r)/;

            cpy(c,b);

            cheng(c,m);   //printf("new\nl %d m %d\n",c.l,m);for(int i=c.l;i>=1;i--) printf("%c",c.d[i]+'0');cout<<"\n";

            if(check(a,c)){ans=max(ans,m);l=m+;}

            else r=m-;

        }

        printf("%d",ans);

    }

}

Problem 3

琪露诺(iceroad.cpp/c/pas)

题目描述

在幻想乡，琪露诺是以笨蛋闻名的冰之妖精。某一天，琪露诺又在玩速冻青蛙，就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多，在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙。小河可以看作一列格子依次编号为0到N，琪露诺只能从编号小的格子移动到编号大的格子。而且琪露诺按照一种特殊的方式进行移动，当她在格子i时，她只会移动到i+L到i+R中的一格。你问为什么她这么移动，这还不简单，因为她是笨蛋啊。每一个格子都有一个冰冻指数A[i]，编号为0的格子冰冻指数为0。当琪露诺停留在那一格时就可以得到那一格的冰冻指数A[i]。琪露诺希望能够在到达对岸时，获取最大的冰冻指数，这样她才能狠狠地教训那只青蛙。但是由于她实在是太笨了，所以她决定拜托你帮它决定怎样前进。开始时，琪露诺在编号0的格子上，只要她下一步的位置编号大于N就算到达对岸。

输入格式

第1行：3个正整数N, L, R

第2行：N+1个整数，第i个数表示编号为i-1的格子的冰冻指数A[i-1]

输出格式

第1行：一个整数，表示最大冰冻指数。保证不超过2^31-1

第2行：空格分开的若干个整数，表示琪露诺前进的路线，最后输出-1表示到达对岸

输入样例

5 2 3

0 12 3 11 7 -2

输出样例

11

0 3 -1

数据范围

对于60%的数据：N <= 10,000

对于100%的数据：N <= 200,000

对于所有数据 -1,000 <= A[i] <= 1,000且1 <= L <= R <= N

注意

此题采用Special Judge

改了一下题目不要求路径

很明显DP，暴力的话n^2不行，然后想到了单调队列

对于i，用单调队列维护[i-r,i-l]，然后入队i-l+1

因为只要超过n，所以最优解最远到N+r-1

f[i]表示到i的话有一个问题，不知道i这个店能不能从0到达，所以倒着来，答案就是f[0]

比赛时直接把w序列给倒过来了

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int N=4e5+;

typedef long long ll;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,l,r,w[N];

int f[N],q[N],head=,tail=;

void dp(){

    n=n+r-;

    for(int i=;i<=n/;i++) swap(w[i],w[n-i+]);

    for(int i=;i<=n+;i++){

        while(head<=tail&&q[head]<i-r) head++;

        if(head>tail) f[i]=w[i];

        else f[i]=f[q[head]]+w[i];

        int nw=i-l+;

        if(nw>=) while(head<=tail&&f[q[tail]]<f[nw]) tail--;

        q[++tail]=nw;

        //printf("%d %d  %d   %d %d\n",i,w[i],f[i],q[head],q[tail]);

    }

}

int main(){

    freopen("iceroad.in","r",stdin);

    freopen("iceroad.out","w",stdout);

    n=read();l=read();r=read();

    for(int i=;i<=n;i++) w[i]=read();

    dp();

    printf("%d",f[n+]);

}

Problem 4

上白泽慧音(classroom.cpp/c/pas)

题目描述

在幻想乡，上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞，使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够聚集最多人数的村庄作为新的教学地点。人间之里由N个村庄（编号为1..N）和M条道路组成，道路分为两种一种为单向通行的，一种为双向通行的，分别用1和2来标记。如果存在由村庄A到达村庄B的通路，那么我们认为可以从村庄A到达村庄B，记为(A,B)。当(A,B)和(B,A)同时满足时，我们认为A,B是绝对连通的，记为<A,B>。绝对连通区域是指一个村庄的集合，在这个集合中任意两个村庄X,Y都满足<X,Y>。现在你的任务是，找出最大的绝对连通区域，并将这个绝对连通区域的村庄按编号依次输出。若存在两个最大的，输出字典序最小的，比如当存在1,3,4和2,5,6这两个最大连通区域时，输出的是1,3,4。

输入格式

第1行：两个正整数N,M

第2..M+1行：每行三个正整数a,b,t, t = 1表示存在从村庄a到b的单向道路，t = 2表示村庄a,b之间存在双向通行的道路。保证每条道路只出现一次。

输出格式

第1行： 1个整数，表示最大的绝对连通区域包含的村庄个数。

第2行：若干个整数，依次输出最大的绝对连通区域所包含的村庄编号。

输入样例

5 5

1 2 1

1 3 2

2 4 2

5 1 2

3 5 1

输出样例

3

1 3 5

数据范围

对于60%的数据：N <= 200且M <= 10,000

对于100%的数据：N <= 5,000且M <= 50,000
     

第一眼，并查集、

第二眼，有向？！强连通分量.........完了tarjan完全忘了

打了一下暴力不太好做就弃疗了

60：floyd传递闭包+并查集维护

应该想到的

PS：字典序最小就是集合中最小点最小

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int N=,M=5e4+;

typedef long long ll;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,m,a,b,flag,d[N][N];

void floyd(){

    for(int k=;k<=n;k++)

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

                d[i][j]=d[i][j]||(d[i][k]&&d[k][j]);

}

int fa[N],mn[N],size[N];

inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

int main(int argc, const char * argv[]){

    freopen("classroom.in","r",stdin);

    freopen("classroom.out","w",stdout);

    n=read();m=read();

    for(int i=;i<=m;i++){

        a=read();b=read();flag=read();

        if(flag==) d[a][b]=;

        else d[a][b]=d[b][a]=;

    }

    floyd();

    for(int i=;i<=n;i++) fa[i]=mn[i]=i,size[i]=;

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

            if(d[i][j]&&d[j][i]){//printf("%d %d\n",i,j);

                int x=find(i),y=find(j);

                if(x!=y){

                    fa[y]=x;

                    mn[x]=min(mn[x],mn[y]);

                    size[x]+=size[y];//printf("f %d %d %d\n",x,y,size[x]);

                }

            }

    int mx=,ans;

    for(int i=;i<=n;i++){

        if(size[i]>mx){mx=size[i];ans=i;}

        if(size[i]==mx&&mn[i]<mn[ans]) ans=i;

    }

    printf("%d\n",size[ans]);

    for(int i=;i<=n;i++) if(d[i][ans]&&d[ans][i]) printf("%d ",i);

}

100分：tarjan求强连通分量

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int N=,M=5e4+;

typedef long long ll;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

struct edge{

    int v,ne;

}e[M<<];

int h[N],cnt=;

inline void add(int u,int v){

    cnt++;

    e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;

}

int n,m,a,b,flag;

int dfn[N],low[N],belong[N],size[N],dfc,scc;

int st[N],top=;

void dfs(int u){//printf("dfs %d\n",u);

    dfn[u]=low[u]=++dfc;

    st[++top]=u;

    for(int i=h[u];i;i=e[i].ne){

        int v=e[i].v;

        if(!dfn[v]){

            dfs(v);

            low[u]=min(low[u],low[v]);

        }else if(!belong[v])

            low[u]=min(low[u],dfn[v]);

    }

    if(low[u]==dfn[u]){

        scc++;

        while(true){

            int x=st[top--];

            belong[x]=scc;

            size[scc]++;

            if(x==u) break;

        }

    }

}

int main(int argc, const char * argv[]){

    freopen("classroom.in","r",stdin);

    //freopen("classroom.out","w",stdout);

    n=read();m=read();

    for(int i=;i<=m;i++){

        a=read();b=read();flag=read();

        if(flag==){add(a,b);}

        else {add(a,b);add(b,a);}

    }

    for(int i=;i<=n;i++) if(!belong[i]) dfs(i);

    int mx=,ans;

    for(int i=;i<=n;i++) if(size[belong[i]]>mx){

        mx=size[belong[i]];ans=belong[i];

    }

    printf("%d\n",mx);

    for(int i=;i<=n;i++) if(belong[i]==ans) printf("%d ",i);

}
上一篇：（十七）迭代器模式详解（foreach的精髓）


下一篇：微信小程序开发系列教程三：微信小程序的调试方法