2023年中国高校计算机大赛-团队程序设计天梯赛（GPLT）上海理工大学校内选拔赛 题解_中国计算机天梯赛考试内容是什么

总结：本场比赛总共A了两题，主要是因为是在课上做的，老师一直比比个不停，还让关上手机电脑，静不下心去做，做题感觉很差

A A Xor B Problem

两个数异或和为零则两个数相等！！！

思路：使用数组记录每个数的个数，可以先输入，然后再对数组进行逐个遍历，可通过计算得出数对个数等于每个数的平方和。也可以边输入边处理，每输入一个数便更新数对的结果数

赛场AC代码：

#include<cstdio>
#include<iostream>
#define int long long
using namespace std;
 
int a[100005];
int b[114520];
signed main(){
	int n,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		ans-=(b[a[i]]*b[a[i]]);
		b[a[i]]++;
		ans+=(b[a[i]]*b[a[i]]);
	}
	cout<<ans;
	return 0;
} 

另一种思路：

#include<iostream>
#define int long long
using namespace std;
 
const int N=1000005;
int a[N];
signed main(){
	int x,n,ans;
	cin>>n;
    for(int i=0;i<n;i++){
        cin>>x;
        a[x]++;
    }
	for(int i=0;i<=N;i++){
		ans+=a[i]*a[i];
	}
	cout<<ans;
}

B 吃苹果 

思路：贪心算法，计算早上和晚上愉悦值的差并进行排序，差值越小（可能为负值）则代表晚上的愉悦值相对早上的更多，先选晚上的，剩下的则为早上的

注意对结构体的定义和结构体的排序!!!

赛场AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
 
const int N=100005;
 
struct Node{
	int a;
	int b;
	int c;
}ap[N];
 
bool cmp(Node x,Node y){
	return 	x.c<y.c;
}
 
signed main(){
	int n,k,ans=0;
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>ap[i].a>>ap[i].b;
		ap[i].c=ap[i].a-ap[i].b;
	}
	sort(ap,ap+n,cmp);
	for(int i=0;i<k;i++){
		ans+=ap[i].b;
	}
	for(int i=k;i<n;i++){
		ans+=ap[i].a;
	}
	cout<<ans;
	return 0;
} 

另一种思路：(也可以反过来)

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100005;
int a[N];
 
int main(){
	int n,k,x,y;
	cin>>n>>k;
	int ans=0;
	for(int i=1;i<=n;i++){
		cin>>x>>y;
		ans+=x;
		a[i]=y-x;
	} 
	sort(a+1,a+n+1,greater<int>());
	for(int i=1;i<=k;i++){
		ans+=a[i];
	} 
	cout<<ans;
}

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100005;
int a[N];
 
int main(){
	int n,k,x,y;
	cin>>n>>k;
	int ans=0;
	for(int i=0;i<n;i++){
		cin>>x>>y;
		ans+=x;
        a[i]=x-y;;
    }
    sort(a,a+n);
    for(int i=0;i<k;i++){
        ans-=a[i];
    }
    cout<<ans;
    return 0;
}

 C n皇后问题

 思路：用四个数组分别表示横竖左斜右斜

注意超时问题！！！

cin/cout会超时，需要用：   

ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

或者使用scanf！！！

#include<iostream>
#include<cstdio>
using namespace std;
 
const int N=3000005;
bool h[N],l[N],a[N],b[N];
 
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
	cout.tie(0);
	int n,T;
	cin>>n>>T;
	while(T--){
		int x,y;
		cin>>x>>y;
		if(h[x]||l[y]||a[x-y+1000000]||b[x+y]){
			cout<<"No"<<endl;
		}else{
			cout<<"Yes"<<endl;
			h[x]=1;
			l[y]=1;
			a[x-y+1000000]=1;
			b[x+y]=1;	
		}
	}
	
	return 0;
}

D 分苹果 

思路：数学知识，将坐标分别带入直线方程，结果大于零和小于零位于直线两侧

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
 
int ans[5];
signed main(){
	int n,ae,be,ce,ar,br,cr;
	cin>>n;
	cin>>ae>>be>>ce;
	cin>>ar>>br>>cr;
	int x,y,a,b;
	while(n--){
		cin>>x>>y;
		a=ae*x+be*y+ce;
		b=ar*x+br*y+cr;
		if(a>0&&b>0){
			ans[0]++;
		}else if(a>0&&b<0){
			ans[1]++;
		}else if(a<0&&b>0){
			ans[2]++;
		}else{
			ans[3]++;
		}
	}
	sort(ans,ans+4);
	for(int i=0;i<4;i++){
		cout<<ans[i]<<' ';
	}
	return 0;
}

E 完型填空

思路：动态规划，用数组dp[i][j][k][p]分别表示有ijkp道题选ABCD

#include<iostream>
using namespace std;
 
const int N=30;
int dp[N][N][N][N];
int a[105][5];
int main(){
	int n,h;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=4;j++){
			cin>>a[i][j];
		}
	}
	for(int i=0;i<=n/4;i++){
		for(int j=0;j<=n/4;j++){
			for(int k=0;k<=n/4;k++){
				for(int p=0;p<=n/4;p++){
					h=i+j+k+p;
					if(i){
						dp[i][j][k][p]=max(dp[i][j][k][p],dp[i-1][j][k][p]+a[h][1]);
					}
					if(j){
						dp[i][j][k][p]=max(dp[i][j][k][p],dp[i][j-1][k][p]+a[h][2]);
					}
					if(k){
						dp[i][j][k][p]=max(dp[i][j][k][p],dp[i][j][k-1][p]+a[h][3]);
					}
					if(p){
						dp[i][j][k][p]=max(dp[i][j][k][p],dp[i][j][k][p-1]+a[h][4]);
					}
				}
			}
		}
	}
	cout<<dp[n/4][n/4][n/4][n/4];
	return 0;
} 

F 坐火车 （最短路改编）不是很懂，老是卡在9分！！！

最好从头开始学一遍最短路！！！

推荐Dijkstra链式前向星优化：算法小讲堂之最短路算法(Floyd+bellman+SPFA+Dijkstra)

关键是考虑如何求经过城市的数量的最小值!

#include<iostream>
#include<cstring>
#include<queue>
#define int long long
using namespace std;
 
typedef pair<int,int> PII;
const int N=1e5+10;
const int M=4*N;
const int inf=0x3f3f3f3f;
int n,m;
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
int cnt[N];
bool vis[N];
 
void init(){
	memset(dist,inf,sizeof(dist));
	memset(cnt,inf,sizeof(cnt));
	memset(h,-1,sizeof(h));
	cnt[1]=1;
	dist[1]=0;
}
 
void add(int a,int b,int c){
	e[idx]=b;
	w[idx]=c;
	ne[idx]=h[a];
	h[a]=idx++;
}
 
void dij(){
	priority_queue<PII,vector<PII>,greater<PII> > q;
	q.push({0,1});
	while(q.size()){
		PII t=q.top();
		q.pop();
		int ver=t.second;
		if(vis[ver]){
			continue;
		} 
		vis[ver]=1;
		for(int i=h[ver];i!=-1;i=ne[i]){
			int j=e[i];
			if(cnt[j]>cnt[ver]+1){
				cnt[j]=cnt[ver]+1;
				dist[j]=dist[ver]+w[i];
				q.push({cnt[j],j});
			}else if(cnt[j]==cnt[ver]+1){
				if(dist[j]>dist[ver]+w[i]){
					dist[j]=dist[ver]+w[i];
					q.push({cnt[j],j});
				}
			}
		}
	}
}
 
signed main(){
	cin>>n>>m;
	init();
	while(m--){
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
		add(b,a,c);
	}
	dij();
	cout<<cnt[n]<<' '<<dist[n];
	return 0;
}

9分代码： 啊啊啊啊——

#include<iostream>
#include<cstring>
#include<queue>
#define int long long
using namespace std;
 
const int inf=0x3f3f3f3f;
const int N=100005;
const int M=4*N;
int n,m,cnt;
int head[N],dis[N],sum[N];
bool vis[N];
typedef pair<int,int>Pll;
 
struct Edge{
	int next;
	int to;
	int w;
}edge[M];
 
void init(){
	memset(vis,0,sizeof(vis));
	memset(dis,inf,sizeof(dis));
	memset(head,-1,sizeof(head));
	memset(sum,inf,sizeof(sum));
	cnt=0;
	dis[1]=0;
	sum[1]=1;
}
 
void add(int u,int v,int w){
	edge[cnt].to=v;
	edge[cnt].w=w;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}
 
void dij(){
	priority_queue<Pll,vector<Pll>,greater<Pll> > q;
	q.push(Pll(0,1));
	Pll temp;
	while(!q.empty()){
		temp=q.top();
		q.pop();
		int u=temp.second;
		if(vis[u]){
			continue;
		}
		vis[u]=1;
		int t,len;
		for(int i=head[u];i!=-1;i=edge[i].next){
			t=edge[i].to;
			len=edge[i].w;
			if(sum[t]>sum[u]+1){
				sum[t]=sum[u]+1;
				dis[t]=dis[u]+len;
				q.push(Pll(dis[t],t)); 
			}else if(sum[t]==sum[u]+1){
				if(dis[t]>dis[u]+len){
					dis[t]=dis[u]+len;
				}
			}
		}
	}
}
 
signed main(){
	init();
	cin>>n>>m;
	int u,v,w;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	dij();
	cout<<sum[n]<<' '<<dis[n];
	return 0;
}

G A Xor B Problem again   位运算问题，不懂！！！

学习位运算~~~

#include<iostream>
#define int long long
using namespace std;
 
const int N=300005;
int n,pre[N],a[N];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
    	cin>>a[i];
    	pre[a[i]]++;//记录每一个数出现的次数
	}
	//枚举每一个位数（变成二进制之后）
	for(int i=0;i<18;i++){
		//二进制枚举每（1-1e5）
		for(int j=0;j<262144;j++){
			// 如果这个数与这个二进制数一样那么
			if(j&(1<<i)){
				pre[j]+=pre[j^(1<<i)];
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		int x=a[i]^((1<<18)-1);
		ans+=pre[x];
	}
	cout<<ans;
	return 0;
}

H  摘苹果

思路：正常思路，模拟，玄学问题，g++编译器超时，clang++编译器能过

可以考虑其他做法进行时间优化！！！

#include<iostream>
#include<cmath>
#define int long long
using namespace std;
 
const int N=100005;
int a[N];
signed main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	while(m--){
		int op,l,r,ans;
		scanf("%lld%lld%lld",&op,&l,&r);
		if(op==1){
			for(int i=l;i<=r;i++){
				if(a[i]>=10){
					a[i]-=((a[i]-1)/3+1);
				}
			}
		}
		if(op==2){
			ans=0;
			for(int i=l;i<=r;i++){
				if(a[i]<100){
					ans++;
				}
			}
			printf("%lld\n",ans);
		}
		if(op==3){
			ans=0;
			for(int i=l;i<=r;i++){
				ans+=a[i];
			}
			printf("%lld\n",ans);
		}
	}
	
	return 0;
}