排位赛#1题解

浅夏.北朽暖栀

2024-10-15 16:43:07

发布于：安徽

82阅读

0回复

0点赞

您的赞是我们的动力，麻烦动动您发财的手点个赞呗(AC君官方都点赞了，确定不看看吗)

第一题

综上知，第一题要用unsigned long long

long long只有75分

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    unsigned long long a,b;
    cin>>a>>b;
    if(a%2==0||b%2==0){
        cout<<"Yes";
   	}else{
        cout<<"No";
    }
    return 0;
}

第二题

用for循环解决，使用long long即可
AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
long long a[N],b[N];
int main(){
    long long n;
    long long sum=0;
    scanf("%lld",&n);
    for(long long i=1;i<=n;i++)	scanf("%lld",&a[i]);
    for(long long i=1;i<=n;i++)	scanf("%lld",&b[i]);
    for(long long i=1;i<=n;i++){
        sum+=a[i]*b[i];
    }
    printf("%lld",sum);
	return 0;
}

第三题

使用欧几里得公式和曼哈顿距离公式即可
AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,op,x[N],y[N];
int main(){
	scanf("%d%d",&n,&op);
	int a=INT_MIN,b=INT_MAX,c=INT_MIN,d=INT_MAX;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&x[i],&y[i]);
		a=max(a,x[i]+y[i]);
		b=min(b,x[i]+y[i]);
		c=max(c,x[i]-y[i]);
		d=min(d,x[i]-y[i]);
	}
	if(op==1){
		long long ans=0;
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				int u=x[i]-x[j],v=y[i]-y[j];
				ans=max(ans,u*1ll*u+v*1ll*v);
			}
		}
		printf("%lld",ans);
	}else{
		printf("%d",max(a-b,c-d));
	}
	return 0;
}

第四题

深搜即可解决，用一个dfs
AC代码(本题适合学过搜索的食用)

#include<bits/stdc++.h>
using namespace std;
const int N=15;
int n,g[N][N],m,x[N],y[N],w[3];
bool st[N];
int dr[][2]={{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,1},{1,-1},{-1,-1}};
bool check(int x,int y,int k){
	for(int i=0;i<8;i++){
		int xx=x+dr[i][0],yy=y+dr[i][1],cnt=0;
		while(g[xx][yy]==!k){
			xx+=dr[i][0],yy+=dr[i][1],cnt++;
		}
		if(g[xx][yy]==k&&cnt>0){
			return true;
		}
	}
	return false;
}
void work(int x,int y,int k){
	for(int i=0;i<8;i++){
		int xx=x+dr[i][0],yy=y+dr[i][1],cnt=0;
		while(g[xx][yy]==!k){
			xx+=dr[i][0],yy+=dr[i][1],cnt++;
		}
		if(g[xx][yy]==k&&cnt>0){
			xx=x+dr[i][0],yy=y+dr[i][1];
			while(cnt--){
				g[xx][yy]=k,xx+=dr[i][0],yy+=dr[i][1];
			}
		}
	}
}
void dfs(int c,int k,int s){
	if(c==m||s==2){
		int u=0,v=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(g[i][j]==0)	u++;
				else if(g[i][j]==1) v++;
		if(u>v)	w[1]++;
		else if(u<v)	w[0]++;
		else	w[2]++;
		return ;
	}
	int t[N][N];
	bool f=false;
	for(int i=1;i<=m;i++){
		if(!st[i]&&check(x[i],y[i],k)){
			f=true;
			st[i]=true;
			memcpy(t,g,sizeof(g));
			work(x[i],y[i],k);
			g[x[i]][y[i]]=k;
			dfs(c+1,!k,0);
			memcpy(g,t,sizeof(t));
			g[x[i]][y[i]]=-1;
			st[i]=false;
		}
	}
	if(f==false){
		dfs(c,!k,s+1);
	}
}
int main(){
	cin>>n;
	memset(g,-1,sizeof(g));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>g[i][j];
			if(g[i][j]==-1){
				m++,x[m]=i,y[m]=j;
			}
		}
	}
	dfs(0,0,0);
	cout<<w[0]<<" "<<w[1]<<" "<<w[2];
	return 0;
}