欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2020.02.19【NOIP普及组】模拟赛C组8

程序员文章站 2022-06-04 12:30:12
...
题目编号 标题
0 找路(okret)
1 庭作业(zadaca)
2 算法学习(sfxx)
3 友好数对(kompici)

T1

题目描述

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


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


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

输入

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


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

输出

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

提示

2020.02.19【NOIP普及组】模拟赛C组8

这题一种方法是搜索,一种是爆力
(只列举爆力)爆力:如果这里是一个路的话,那上下左右判断,如果有3个X,也就只能从这出,也只能从这进,那就完全死了。
大家会想:如果出毒瘤怎么办?
事实上,这个爆力可以决绝毒瘤
如果有一个点它是路,那和它相邻的路只要能走这个路就能走,那相邻的路又考虑道相邻的相邻……
所以最终会回到原点,那就大功告成了

#include<iostream>
#include<cstdio>
using namespace std;
int m,n,k;
char a[20][20];
int main(){
	freopen("okret.in","r",stdin);
	freopen("okret.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]=='.'){
				k=0;
				if(a[i+1][j]=='.')k++;
				if(a[i][j+1]=='.')k++;
				if(a[i-1][j]=='.')k++;
				if(a[i][j-1]=='.')k++;
				if(k<2){
					cout<<1;
					return 0;
				}
			}
		}
	}
	cout<<0;
	return 0;
}

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位数就可以了。

2020.02.19【NOIP普及组】模拟赛C组8

我们可以两两相约,把约到的最大公因数乘到答案

#include<iostream>
#include<cstdio>
using namespace std;
long long m,n,k=1,x,y,a[10010],b[10010];
long long gcd(long long x,long long b){
	if(b==0)return x;
	return gcd(b,x%b);
}
int main(){
	freopen("zadaca.in","r",stdin);
	freopen("zadaca.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>b[i];
		for(int j=1;j<=n;j++){
			long long t=gcd(a[j],b[i]);
			k=k*t;
			a[j]=a[j]/t;
			b[i]=b[i]/t;
			if(k>=1000000000){
				y=1;
				k=k%1000000000;
			}
		}
	}
	if(y==0)cout<<k;
	else{
		int t=0;
		x=k;
		while(x!=0){
			t++;
			x=x/10;
		}
		for(int i=1;i<=9-t;i++)cout<<0;
		cout<<k; 
	}
	return 0;
}

T3

题目描述

  	自从学习了动态规划后,Famer KXP对动态规划的热爱便一发不可收拾,每天都想找点题做,一天,他找到了一道题,但是不会做,于是,他找到了你。题目如下:给出N个无序不重复的数,再有M个询问,每次询问一个数是否在那N个数中,若在,则ans增加2^K,K为该数在原数列中的位置。
由于ans过大,所以只要求你输出ans mod 10^9+7。

输入

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

输出

  输出最终答案。

样例输入

5 5
1 3 4 6 5
1 8 1 3 6

样例输出

24

数据范围限制

30% 0<N,M<100
50% 0<N,M<10000
100% 0<N,M<100000
输入的数均在2^31 以内

二分+打表
我们先把它的位置记录,然后排序
我们再用二分来找数
把事先打好的表用进去
AC了

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int MAX=1000000007;
long long m,n,k,ans;
long long rp[1000100];
struct node{
	int x,y;
}a[1000100];
bool cmp(node x,node y){
	return x.x<y.x;
}
int main(){
	freopen("sfxx.in","r",stdin);
	freopen("sfxx.out","w",stdout);
	cin>>n>>m;
	rp[0]=1;
	for(int i=1;i<=n;i++){
		rp[i]=rp[i-1]*2%MAX;
		cin>>a[i].x;
		a[i].y=i;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=m;i++){
		cin>>k;
		int l=1,r=n,mid;
		while(l<=r){
			mid=(l+r>>1);
			if(a[mid].x>k)r=mid-1;
			else if(a[mid].x<k)l=mid+1;
			else break;
		}
		if(a[mid].x==k){
			ans=(ans+rp[a[mid].y])%MAX;
		}
	}
	cout<<ans;
	return 0;
}

T4

题目描述

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


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

输入

第一行一个正整数N(1<=N<=1000000)。


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

输出

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

2020.02.19【NOIP普及组】模拟赛C组8

哇!状压+位运算
虽然赛场上一分没得,但讲题时还是觉得挺有趣的(???)
我们把每个数字压成二进制,用N个v来记录每一个二进制数在那位出现过(对,v也是二进制)用 | 运算,再用b数组统计
之后就好办,枚举,当两个数字有一位( & 运算)相同,就乘起来(b数组),到最后还要b[i]*(b[i]-1),最后输出答案杠2

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
long long m,n,k;
long long a[10000100],num[1024];
int wwww(int x,int y){
	return x&y;
}
int main(){
	freopen("kompici.in","r",stdin);
	freopen("kompici.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		long long sum=0;
		while(a[i]>0){
			int x=a[i]%10;
			sum=sum|(1<<x);
			a[i]=a[i]/10;
		}
		num[sum]++;
	}
	for(int i=1;i<=1023;i++){
		if(num[i]==0)continue;
		for(int j=1;j<=1023;j++){
			if(num[j]==0)continue;
			if(wwww(i,j)&&i!=j)
			k=k+num[i]*num[j];
		}
		k=k+num[i]*(num[i]-1);
	}
	cout<<k/2;
	return 0;
}
相关标签: 比赛