2025年(RAICOM)睿抗机器人开发者大赛CAIP国赛题解
RC-u1 谁拿冠军了？
很久没敲代码，第一题写法太唐了，花的时间也很多。
利用结构体和map，存储每一天的操作，使用数组也可以。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m,a1,a2,b1,b2,b3;
int ans1,ans2;
struct nod{
int c1;
int c2;
int c3;
};
unordered_map<int,nod> mp;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
cin>>a1>>a2>>b1>>b2>>b3;
for(int i=1;i<=n;i++){
int d,op;cin>>d>>op;
if(op==1) mp[d].c1++;
else if(op==2) mp[d].c2++;
else mp[d].c3++;
}
for(int i=1;i<=m;i++){
int t,op;cin>>t>>op;
int tmp1=0,tmp2=0;
if(op==1&&mp[t].c1!=0){
tmp1=mp[t].c1*a1;
tmp2=mp[t].c1*b1;
tmp2/=2;
ans1+=tmp1,ans2-=tmp2;
mp[t].c1=0;
}else if(op==2&&mp[t].c2!=0){
tmp2=mp[t].c2*b2;
tmp2/=2;
ans2-=tmp2;
mp[t].c2=0;
}else if(op==3&&mp[t].c3!=0){
tmp1=mp[t].c3*a2;
tmp2=mp[t].c3*b3;
tmp2/=2;
ans1-=tmp1,ans2-=tmp2;
mp[t].c3=0;
}
}
unordered_map<int,nod>::iterator it=mp.begin();
for(;it!=mp.end();it++){
nod d=(*it).second;
int tmp1,tmp2;
if(d.c1!=0){
tmp1=d.c1*a1;
tmp2=d.c1*b1;
ans1+=tmp1,ans2-=tmp2;
}
if(d.c2!=0){
tmp2=d.c2*b2;
ans2-=tmp2;
}
if(d.c3!=0){
tmp1=d.c3*a2;
tmp2=d.c3*b3;
ans1-=tmp1,ans2-=tmp2;
}
}
cout<<ans1<<" "<<ans2;
return 0;
}
RC-u2 理包
一开始思路错了，等想到正确思路时，已经过去二十分钟了。
我使用一个c数组存储每次输入图形，再去除掉周围空白的，压缩到b数组中，再一个个点尝试放入a数组中。代码还可以更简单。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int N,M,n,m,q,sh,sl,zz,yy,ss,xx;
int a[55][55],b[55][55],c[55][55];
bool pan(int x,int y){
for(int i=1;i<=xx-ss+1;i++){
for(int j=1;j<=yy-zz+1;j++){
if(x+i-1>N||y+j-1>M) return 0;
if(b[i][j]==1&&a[x+i-1][y+j-1]==1) return 0;
}
}
return 1;
}
void cha(int x,int y){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(b[i][j]) a[x+i-1][y+j-1]=1;
}
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>N>>M>>q;
while(q--){
yy=xx=sh=sl=0;
zz=ss=0x3f3f3f3f;
cin>>n>>m;
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char ch;cin>>ch;
if(ch=='*'){
c[i][j]=1;
if(sh==0){sh=i,sl=j;}
zz=min(zz,j),yy=max(yy,j),ss=min(ss,i),xx=max(xx,i);
}
}
}
for(int i=1;i<=xx-ss+1;i++)
for(int j=1;j<=yy-zz+1;j++)
b[i][j]=c[ss+i-1][zz+j-1];
sh-=ss-1,sl-=zz-1;
int f=0;
for(int i=1;i<=N;i++){
if(f) break;
for(int j=1;j<=M;j++){
if(f) break;
if(pan(i,j)){
cha(i,j);
f=1;
cout<<i+sh-1<<" "<<j+sl-1<<"\n";
}
}
}
if(!f) cout<<"-1 -1\n";
}
return 0;
}
RC-u3 删除屏蔽词
这题应该是国赛签到题。
下面首先是我赛时愚蠢代码，再是AC代码。
赛时我没看到第一个字符串长度为2的条件，想骗点分赶快去写第4题，因此直接循环find，总共耗时几分钟就跳了。只拿到15分，亏麻了。
#include<bits/stdc++.h>
using namespace std;
string s,str;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>s>>str;
int tmp=str.find(s),ans=0;
while(tmp!=-1){
string s1=str.substr(0,tmp);
string s2=str.substr(tmp+s.size());
str=s1+s2;
ans++;
tmp=str.find(s);
}
cout<<ans<<" "<<str;
return 0;
}
赛后队友刘神说AC了，讨论了一下发现我眼瞎。
#include<bits/stdc++.h>
using namespace std;
char s[2],str[1000001],x;
int len,ans;
int main(){
cin>>s[0]>>s[1];
str[0]=' ';
while(cin>>x){
if(x==s[1]&&str[len]==s[0]){
ans++,len--;
}else{
str[++len]=x;
}
}
str[len+1]='\0';
cout<<ans<<str;
return 0;
}
RC-u4 穷游
首先说明，我下面代码只拿到28分，有一个特例没拿到，没时间改bug，想AC的自己找找。
因为题目要求路径最贵城市的费用尽可能少，所以我们从费用低的城市到费用高的城市一个个找，当起点到终点出现路径时，此时这个路径的最贵城市费用最低。我们再利用比这个费用低的所有城市找出最短路径即可。
我首先利用结构体排序，得到费用从低到高，再利用并查集，一个个加入直至得到起点终点联通，再通过最短路板子得到最短路径即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10,M=3e4+10;
struct edge{
int v,w;
};
struct nod{
int len,v;
friend bool operator > (nod a,nod b){
return a.len>b.len;
}
};
vector<edge> vt[N];
int n,m,s,dis[N],vis[N],S,T,tmpz;
int f[N];
int bfind(int x){
if(f[x]!=x) f[x]=bfind(f[x]);
return f[x];
}
struct cs{
int id,cc,gd;
}c[N];
bool cmp(cs a,cs b){
if(a.cc!=b.cc) return a.cc<b.cc;
return a.id<b.id;
}
unordered_map<int,int> ump;
priority_queue<nod,vector<nod>,greater<nod> > q;
void dijkstra(){
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[S]=0;
q.push({0,S});
while(!q.empty()){
int u=q.top().v;q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=0;i<vt[u].size();i++){
int v=vt[u][i].v,z=vt[u][i].w;
if(v>tmpz) continue;
if(dis[v]>dis[u]+z){
dis[v]=dis[u]+z;
q.push({dis[v],v});
}
}
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>c[i].cc;
c[i].id=i;
f[i]=i;
}
sort(c+1,c+n+1,cmp);
for(int i=1;i<=n;i++) ump[c[i].id]=i;
for(int i=1;i<=m;i++){
int v3,v4,t;cin>>v3>>v4>>t;
int v1=ump[v3],v2=ump[v4];
vt[v1].push_back({v2,t});
vt[v2].push_back({v1,t});
}
cin>>S>>T;
S=ump[S],T=ump[T];
//1.从小到大扩展并查集，直到st出现路径
for(int i=1;i<=n;i++){
for(int j=0;j<vt[i].size();j++){
if(vt[i][j].v<=i){
int fi=bfind(i),fj=bfind(vt[i][j].v);
if(f[fi]!=f[fj]) f[fj]=f[fi];
}
}
if(bfind(S)==bfind(T)){
tmpz=i;
break;
}
}
//2.st的连通块中找出最短路
dijkstra();
cout<<c[tmpz].cc<<" ";
cout<<dis[T]<<"\n";
return 0;
}
RC-u5 工序优化
最后时间不够了，这题花了10min不到，写了个贪心拿到14分也差不多了。按照往年最后一题，这题正解应该是DP。（向天再借20min我应该能写个DP出来分更高）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10;
int n,k,tmp;
ll t[N],p[N],c[N],ans1,ans2;
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>t[i]>>p[i]>>c[i];
}
ans1=t[1]*p[1];
for(int i=2;i<=n;i++){
ll tmp1=t[i-1]*p[i],tmp2=t[i]*p[i];
if(tmp1<tmp2&&k){
ans1+=tmp1;
ans2+=c[i];
k--;
t[i]=t[i-1];
}else ans1+=tmp2;
}
cout<<ans1<<" "<<ans2<<"\n";
return 0;
}
总结，这写代码写完后，晚上被子里都是甜的，太唐了。
相较于去年，第三题纯亏麻了，第四题比去年拿分更多，第五题比去年拿分更少。
京公网安备 11010502036488号