【纪中2020.2.19日】模拟赛题解-白红宇

【纪中2020.2.19日】模拟赛题解

阅读量：319 次

发布时间：2019-03-03

本文共 4378 字，大约阅读时间需要 14 分钟。

正题：

T1：找路

题目描述

Mirko 刚开始学车，因此他还不会在一个很狭窄的地方掉头，所以他想找一个不需要掉头的地方学车。Mirko马上发现他想找的地方必须没有死胡同，因为死胡同是不可能出来的，除非掉头（假设Mirko也不会倒车）。现在，你需要写一个程序，来分析一个地方的地图，研究是否这个地方适合Mirko练习开车。

这张地图是包含R*C个单元格的，单元格中的“X”代表一个建筑物，单元格中的“.”代表路面。从一个路面单元格，Mirko可以向旁边上下左右四个方向的单元格开去，只要开过去的地方同样也是路面。

最后，我们要得出这个地图是否包含死胡同，假如从任意一个路面单元格出发，沿着任何一个可以行驶的方向，我们可以不用掉头就能返回到出发点，那么这个地图就是没有死胡同的。

输入

第一行包括两个整数R和C（3<=R,C<=10),表示这个地图的大小。

接下来R行，每行有C个字符，每个字符可能是“X”和“.”。地图中至少有两个路面单元格，并且所有的路面都是相连的（相互可达的）。

输出

输出只有一行，输出0表示这个地图没有死胡同，输出1表示这个地图存在死胡同。

在这里插入图片描述

分析：

这道题很简单。

就是遍历整个地图，如果有一个点四周是‘.’，就计数。

如果有<2个这样的点，就说明没有死胡同。

CODE：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;char a[12][12];int m,n;bool f=true;int main(){   	freopen("okret.in","r",stdin);	freopen("okret.out","w",stdout);	memset(a,'X',sizeof(a));	scanf("%d%d",&m,&n);	for (int i=1;i<=m;i++)	{   		for (int j=1;j<=n;j++)		{   			scanf(" %c",&a[i][j]);  //读入		}	}	for (int i=1;i<=m;i++)	{   		for (int j=1;j<=n;j++)		{   			int t=0;  //计数器			if (a[i][j]=='X') continue;  //不是'.'			if (a[i-1][j]=='.') t++;			if (a[i][j-1]=='.') t++;			if (a[i+1][j]=='.') t++; //判断上下左右			if (a[i][j+1]=='.') t++;			if (t<2)  //小于2个			{   				f=false;			}		}	}	if (f) printf("0");  //没有死胡同	else printf("1"); //有死胡同}

T2：家庭作业

题目描述

Mirko最近收到了一个家庭作业，作业的任务是计算两个数A和B的最大公约数。由于这两个数太大了，我们给出了N个数，他们的乘积是A，给出M个数，他们的乘积是B。

Mirko想要验算自己的答案，所以他想找你写一个程序来解决这个问题。如果这个最大公约数超过了9位数，那么只需要输出最后9位就可以了。

输入

第一行包含一个正整数N，范围是1到1000。第二行是N个用空格隔开的正整数(小于10亿），他们的乘积是A。第三行包含一个正整数M，范围是1到1000。第四行是M个用空格隔开的正整数（小于10亿），他们的乘积是B。

输出

输出有且只有一行，表示A和B的最大公约数，如果结果超过了9位数，输出最后9位数就可以了。

分析：

这道题要求最大公约数。

如果最大公约数>题目要求，做个标记，最后判断一下，printf("%09ld",ans)，就是输出后9位。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long long LL;int n,m;LL k,ans=1,a[1001],x,f;int euclid(int y,int x){ if(x==0) return y; //求最大公约数函数 return euclid(x,y%x);}int main(){ //freopen("zadaca.in","r",stdin); //freopen("zadaca.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); scanf("%d",&m); for(int i=1; i<=m; i++) { scanf("%lld",&x); for(int j=1; j<=n; j++) { k=euclid(a[j],x); //找两个数列中的最大公约数 if(ans*k>=1000000000) f=1; //标记 ans=ans*k%1000000000; //取后9位 a[j]/=k; x/=k; } } if(f==1) //有标记 printf("%09ld",ans); //输出后9位 else printf("%lld",ans);}

T3：算法学习

题目描述

自从学习了动态规划后，Famer KXP对动态规划的热爱便一发不可收拾，每天都想找点题做，一天，他找到了一道题，但是不会做，于是，他找到了你。题目如下：

给出N个无序不重复的数，再有M个询问，每次询问一个数是否在那N个数中，若在，则ans增加2^K,K为该数在原数列中的位置。

由于ans过大，所以只要求你输出ans mod 10^9+7。

输入

第一行，两个数N,M，第二行N个数，第三行M个数。

输出

输出最终答案。

样例输入

5 51 3 4 6 51 8 1 3 6

样例输出

分析：

很多做法。

一种正解为二分查找+快速幂。

两个函数打好后带到主函数就ok。

CODE：

#include 
   
    #include 
    
     using namespace std;long long k,n,m,ans,z,a[100001],b[100001],c[100001];void fast(long long l,long long r){      //快排    if (l>=r) return;    int i=l,j=r;    long long mid=a[(l+r)/2];    do    {           while(a[i]
     
      mid) j--;        if(i<=j)        {               a[0]=a[i];a[i]=a[j];a[j]=a[0];            b[0]=b[i];b[i]=b[j];b[j]=b[0];            i++;j--;        }    }    while(i<=j);    fast(l,j);    fast(i,r);}int search_(long long x,long long y){     //二分查找    int m=x+(y-x)/2;    if(a[m]==k)        return m;    if(a[m]>k)        return search_(x,m-1);    if(a[m]
      
       >n>>m;    b[0]=1;     for(int i=1; i<=n; i++)    {           cin>>a[i];        b[i]=(b[i-1]*2)%1000000007;     }    fast(1,n);    for(int i=1; i<=m; i++)    {           cin>>k;        if((k>=a[1])&&(k<=a[n]))        {               ans=(ans+b[search_(1,n)])%1000000007;  //带入再%        }    }    cout<
       
        <

T4：友好数对

题目描述

在顺利完成家庭作业以后，Mirko感到非常的厌倦。所以，他列出了N个数，这些数中有些数对他是喜欢的，有些数对他是不喜欢的。

他喜欢的数对叫做友好数对，如果两个数至少有一个相同的数字(不要求在相同的位置），那么这两个数就是友好数对。请帮助Mirko在这N个数找出有多少友好数对。

输入

第一行一个正整数N（1<=N<=1000000）。

接下来N行，每行一个正整数,范围在1到1018之间。N个数中任意两个数都是不同的。

输出

只有一行一个整数，表示友好数对的个数。

在这里插入图片描述

分析：

刚看这道题，~~感觉不可做~~ 。

听完我们学校一位dalao的讲解后，得：

先把输入的数在二进制下判断两个数有没有相同一位都为1，也就是都有一个相同的数，然后标记当前位，最后判断合法，累加答案。

CODE：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long long LL;LL ans,b[10001];LL i,n,t,s,j,k,x;int main(){ //freopen("kompici.in","r",stdin); //freopen("kompici.out","w",stdout); scanf("%lld",&n); for(i=1;i<=n;i++) { t=0;s=0; scanf("%lld",&x); while(x>0) { t=x%10; x=x/10; s=s|(1<