2024睿抗机器人开发者大赛CAIP编程赛题解（c++）_2024caip

题目地址(补题)

PTA | 程序设计类实验辅助教学平台

RC-u1 热҈热҈热҈

简单模拟题，没什么好说的 : 

#include<bits/stdc++.h>
using namespace std ;
const int N = 55 ;
 
int a[N] ;
 
int main(){
	int n , w ; cin >> n >> w ;
	for(int i=1;i<=n;i++) cin >> a[i] ;
	int t = w ;
	int x = 0 , y  = 0 ;
	for(int i=1;i<=n;i++){
		if(a[i]>=35){
			if(t!=4) x++ ;
			else y++ ;
		}
		t  = (t + 8) % 7 ;
	}
	cout << x << " " << y << endl ;
}

RC-u2 谁进线下了？

简单模拟题，没什么好说的 : 

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int yss[21] = {0, 12, 9, 7, 5, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0};
 
int get(int x){
	return yss[x] ;
}
 
int main(){
	int n ; cin >> n ;
	vector<int> a(21,0) ;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=20;j++){
			int p , k ; cin >> p >> k ;
			a[j] += k + get(p) ;
		}
	}
	for(int i=1;i<=20;i++){
		cout << i << " " << a[i] << endl ;
	}
	return 0;
}

RC-u3 暖炉与水豚

简单模拟题，没什么好说的 (注意看清题目就ok): 

#include<bits/stdc++.h>
using namespace std ;
const int N = 1010 ;
 
int n , m ; 
char a[N][N] ;
bool st[N][N] ;
 
/**
wm....mw
.w..ww..
..wm.wwm
w.w....w
.m.c.m..
w.....w.
*/
 
void f(int i , int j){
	for(int x=-1;x<=1;x++){
		for(int y=-1;y<=1;y++){
			int xx = i+x , yy = j + y ;
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m) {
				st[xx][yy] = true ;
			}
		}
	}
}
 
bool pd(int i , int j){
	for(int x=-1;x<=1;x++){
		for(int y=-1;y<=1;y++){
			int xx = i+x , yy = j + y ;
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[xx][yy]=='c') {
				return false ;
			}
		}
	}
	return true ;
}
 
int main(){
	cin >> n >> m ;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin >> a[i][j] ;
			if(a[i][j]=='m') f(i,j) ;
		}
	}
	int cnt = 0 ;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]=='w' && !st[i][j]){
				for(int x=-1;x<=1;x++){
					for(int y=-1;y<=1;y++){	
						int xx = i+x , yy = j + y ;
						if(a[xx][yy]=='.'&&pd(xx,yy)){
							cout << xx << " " << yy << '\n' ;
							cnt ++ ;
						}
					}
				}
			}
		}
	}
	if(cnt==0){
		cout << "Too cold!" ;
	}
	return 0 ;
}

RC-u4 章鱼图的判断

1 . 先用并查集求每一个连通块的环的个数 : 

        ps : 对于每一对点 ， 如果祖先相同 ， 那么必定存在环，环数++ ， 不同，进行union操作

2 . 对于输出yes的答案 ， 记录环中一对相邻点 ， 用bfs求两点距离 ，则为环的大小 ；

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) ;
using namespace std ;
const int N = 1e5+10 ;
#define endl '\n'
 
vector<int> e[N] ;
int n , m ;
int p[N]; //存储每个点的祖宗节点
int sz[N] ;// 维护联通图中环的数量 
int find(int x) {return x == p[x] ? x : p[x] = find(p[x]);}
int a , b ;
int d[N] ;// 存距离 
 
// 所在连通图只有一个环的时候才满足题意 
// 假设只有一个章鱼环 ， a , b为环中相邻的两个点 
 
inline void solve(){
	cin >> n >> m ;
	for(int i=1;i<=n;i++) e[i].clear() , p[i] = i , d[i] = 0 , sz[i] = 0 ;
	for(int i=1;i<=m;i++){ 
		int u , v ; cin >> u >> v ;
		e[u].push_back(v) ; e[v].push_back(u) ;
		int fu = find(u) , fv = find(v) ;
		if(fu==fv) sz[fu]++ , a = u , b = v ; // 必定存在环 
		else p[fu]=fv ,sz[fv]+=sz[fu] ;// union两个点 
	}	
	int ans = 0 ; // 求章鱼环的数量 
	for(int i=1;i<=n;i++) if(find(i)==i&&sz[i]==1) ans ++ ;
	if(ans != 1) {
		cout << "No" << " " << ans << endl ;
		return ;
	}
	// 求a->b中这个环中点的数量-->题目所求
	// 章鱼子图 点数>=3 , 直接bfs来求 a->b的距离(不是直接两点两边的距离，这个用continue跳过)
	queue<int> q ;
	q.push(a) ;
	while(!q.empty()){
		int u = q.front() ; q.pop() ;
		for(int v : e[u]){
			if(u==a&&v==b) continue ;
			if(!d[v]) d[v] = d[u] + 1,q.push(v) ;
		}
	}
	cout << "Yes" << " " << d[b]+1 << endl ;
}
 
int main(){
	IOS
	int _ ; 
	cin >> _ ;
	while(_--) solve() ;
	return 0 ;
}

RC-u5 工作安排

先看赛时代码   : 

先按截止时间排序 ，然后dp ;

dp[i][j] 代表前i个任务，截止时间为j的最大值 ;

转移方程 : dp[i][j] = max(dp[i][j],dp[i-1][k]+a[i].p) ;

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) ;
using namespace std ;
#define endl '\n'
int n ;
struct Node{
	int t,d,p ;
};
bool cmp(Node& x , Node& y){
	return x.d < y.d ;
}
 
inline void solve(){
	cin >> n ;
	int ma = 0 ;
	int tx = 1 ;
	vector<Node> a(n+1) ;
	for(int i=1;i<=n;i++){
		int x , y , z ; cin >> x >> y >> z ;
		if(x>y) continue ;
		a[tx].t = x ;
		a[tx].d = y ;
		a[tx++].p = z ;
		ma = max(ma , y) ;
	}
	tx -= 1 ;
//	cout << tx << endl ;
	sort(a.begin()+1,a.begin()+1+tx,cmp) ;
	vector<vector<int>> dp(tx+1,vector<int>(ma+1,0)) ;
	for(int i=1;i<=tx;i++){
		for(int j=1;j<=a[i].d;j++){
			dp[i][j] = max(dp[i-1][j] , dp[i][j-1]) ;
			int k = j - a[i].t ;
			if(k>=0){
				dp[i][j] = max(dp[i][j],dp[i-1][k]+a[i].p) ;
			}
		}
	}
	cout << dp[tx][ma] << endl ;
}
 
int main(){
	IOS
	int _ ; 
	cin >> _ ;
	while(_--){
		solve() ;
	}
	return 0 ;
}

ps : 这个代码爆空间了 ， 丢了5分 ， 正解应该是一个01背包 ； 

欢迎交流!