2023睿抗CAIP-编程技能赛-本科组省赛(c++)

RC-u1 亚运奖牌榜

模拟 AC:

#include<iostream>
using namespace std;
struct nation{int j,y,t;
}a[2];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){int x,y;cin>>x>>y;if(y==1) a[x].j++;if(y==2) a[x].y++;if(y==3) a[x].t++;}cout<<a[0].j<<" "<<a[0].y<<" "<<a[0].t<<endl;cout<<a[1].j<<" "<<a[1].y<<" "<<a[1].t<<endl;if(a[0].j==a[1].j){if(a[0].y==a[1].y){if(a[0].t>a[1].t) puts("The first win!");else puts("The second win!");return 0;}if(a[0].y>a[1].y) puts("The first win!");else puts("The second win!");return 0;}if(a[0].j>a[1].j) puts("The first win!");else puts("The second win!");return 0;
}

RC-u2 出院

答案错误 未AC(13/15): STL map+哈希思想

#include<iostream>
#include<cstring>
#include<map>
using namespace std;
map<string,string>mapp;
int n,m;
int main(){cin>>n>>m;for(int i=0;i<n;i++){string a,b;cin>>a>>b;mapp[a]=b;}while(m--){string in;cin>>in;int lenn=in.size();if(mapp.count(in)) cout<<mapp[in]<<endl;else{int flag=0;string out;for(auto x:mapp){int len=x.first.size();if(len<=lenn&&in.substr(0,len)==x.first&&mapp.count(in.substr(len,lenn))){flag=1;out=x.second+mapp[in.substr(len,lenn)];break;}}if(flag==1) cout<<out<<endl;else cout<<"D"<<endl;}}return 0;
}

借此题型,复习一下c++中的 STL 和 哈希思想:

洛谷 P4305 [JLOI2011] 不重复数字(set+vector)

set 有序不重复集合

set.insert(x) 插入元素x

set.count(x) 查找元素x,存在为1,不存在为0

set.clear()    清空集合

vector 容器

vector.push_back(x) 向容器的末尾添加一个元素x

vector.pop_back()     移除容器中的最后一个元素

vector.clear()             清空容器

#include<iostream>
#include<vector>
#include<set>
using namespace std;
vector<int>ans;
set<int>s;
int T,n;
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>T;while(T--){cin>>n;s.clear();ans.clear();for(int i=0;i<n;i++){int x;cin>>x;if(s.count(x)==0){s.insert(x);ans.push_back(x);}}for(int x:ans) cout<<x<<" ";cout<<endl;}return 0;
}

ACwing 3466. 清点代码库(map+vector)

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
map<vector<int>,int>mapp;
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int n,m;cin>>n>>m;for(int i=1;i<=n;i++){vector<int>num;for(int j=1;j<=m;j++){int x;cin>>x;num.push_back(x);}mapp[num]++;}cout<<mapp.size()<<endl;vector<pair<int,vector<int>>>ans;for(auto p:mapp){ans.push_back({-p.second,p.first});}sort(ans.begin(),ans.end());for(auto x:ans){cout<<x.first*(-1)<<" ";for(auto y:x.second) cout<<y<<" ";cout<<endl;}return 0;
}

 ACwing 138. 兔子与兔子(字符串哈希)

#include<iostream>
#include<cstring>
using namespace std;
const int px=131,N=1e6+5;
unsigned long long h[N],p[N];
char s[N];
int n;
unsigned long long get_vlaue(int l,int r){return h[r]-h[l-1]*p[r-l+1];
}
int main(){scanf("%s",s+1);p[0]=1;int len=strlen(s+1);for(int i=1;i<=len;i++){h[i]=h[i-1]*px+s[i]-'a'+1;p[i]=p[i-1]*px;}scanf("%d",&n);while(n--){int l1,r1,l2,r2;scanf("%d %d %d %d",&l1,&r1,&l2,&r2);if(get_vlaue(l1,r1)==get_vlaue(l2,r2)) puts("Yes");else puts("No");}return 0;
}

 ACwing 4951. 整理账本(map+vector)

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
map<int,int>mapB;
map<int,int>mapS;
typedef pair<int,int> pii;
vector<pii>ansB;
vector<pii>ansS;
int n,m;
int main(){cin>>n>>m;for(int i=0;i<n;i++){char a;int b,c;cin>>a>>b>>c;if(a=='B'){if(mapB.count(b)) {mapB[b]+=c;continue;}mapB[b]=c;}else{if(mapS.count(b)) {mapS[b]+=c;continue;}mapS[b]=c;}}for(auto x:mapB) ansB.push_back({x.first,x.second});for(auto x:mapS) ansS.push_back({x.first,x.second});sort(ansS.begin(),ansS.end());int lenS=mapS.size();for(int i=min(lenS-1,m-1);i>=0;i--) cout<<"S "<<ansS[i].first<<" "<<ansS[i].second<<endl;sort(ansB.begin(),ansB.end());int lenB=mapB.size();for(int i=lenB-1;i>=max(0,lenB-m);i--) cout<<"B "<<ansB[i].first<<" "<<ansB[i].second<<endl;return 0;
}

RC-u3 骰子游戏

• 如果有5个相同的数字（五个同点数），输出 0 0 1，表示不需要重骰。
• 如果有4个相同的数字（四个同点数），输出 1 1 6，表示重骰1个骰子，概率为1/6。
• 如果有3个相同的数字且有两个相同的数字（葫芦），输出 2 11 36，表示重骰2个骰子，概率为11/36。
• 如果骰子结果为2到6的顺子（六高顺子），输出 4 19 324，表示重骰4个骰子，概率为19/324。
• 如果骰子结果为1到5的顺子（五高顺子），输出 1 1 6，表示重骰1个骰子，概率为1/6。
• 如果有3个相同的数字（三个同点数），输出 2 4 9，表示重骰2个骰子，概率为4/9。
• 如果有两个对子（两对），输出 3 4 9，表示重骰3个骰子，概率为4/9。
• 如果有一个对子（一对），输出 3 13 18，表示重骰3个骰子，概率为13/18。
• 其他情况，输出 2 17 18，表示重骰2个骰子，概率为17/18。

手算+模拟 AC:

#include<iostream>
#include<cstring>
using namespace std;
int n,t,a[10],cnt[10],flag[10];
//a[10]   存储骰子的结果
//cnt[10] 计数每个数字出现的次数
//flag[10]计数出现特定次数的数字的数量
int main(){cin>>n;for(int i=1;i<=n;i++){memset(cnt,0,sizeof cnt);memset(flag,0,sizeof flag);for(int j=1;j<=5;j++){cin>>t;cnt[t]++;}for(int j=1;j<=6;j++)flag[cnt[j]]++;if(flag[5]==1) cout<<0<<" "<<0<<" "<<1;else if(flag[4]==1) cout<<1<<" "<<1<<" "<<6;else if(flag[3]==1&&flag[2]==1) cout<<2<<" "<<11<<" "<<36;else if(flag[1]==5&&cnt[1]==0) cout<<4<<" "<<19<<" "<<324;else if(flag[1]==5&&cnt[6]==0) cout<<1<<" "<<1<<" "<<6;else if(flag[3]==1&&flag[1]==2) cout<<2<<" "<<4<<" "<<9;else if(flag[2]==2) cout<<3<<" "<<4<<" "<<9;else if(flag[2]==1&&flag[1]==3) cout<<3<<" "<<13<<" "<<18;else cout<<2<<" "<<17<<" "<<18;cout<<endl;}return 0;
}

RC-u4 相对论大师

答案错误 未AC (23/25):  STL+BFS

一个有向图, 每两个顶点为一组,要求找到所有同一组内的顶点路径中的最短路径

//RCu4 23
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
using namespace std;
const int N=2e3+5;
map<pair<string,int>,int>mapsii;
map<int,pair<string,int>>mapisi;
vector<int>path;
int n,id,G[N][N],ans=(int)1e9,flag[N],pre[N];
int bfs(int start,int end){memset(flag,0,sizeof(flag));memset(pre,0,sizeof(pre));queue<pair<int,int>>q;q.push({start,0});flag[start]=1;while(q.size()){auto t=q.front();int point=t.first;int step=t.second;if(point==end){if(step<ans){ans=step;return 1;}return -1;}q.pop();for(int i=0;i<id;i++){if(G[point][i]==1&&flag[i]==0){step++;q.push({i,step});pre[i]=point;flag[i]=1;}}}return -1;
}
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;id=0;for(int i=0;i<n;i++){string a,c;int b,d;cin>>a>>b>>c>>d;int x,y;if(mapsii.count({a,b})==0){x=id++;mapsii[{a,b}]=x;}else x=mapsii[{a,b}];if(mapsii.count({c,d})==0){y=id++;mapsii[{c,d}]=y;}else y=mapsii[{c,d}];G[x][y]=1;}for(auto t:mapsii){string a=t.first.first;int b=t.first.second;int start=t.second;mapisi.insert({start,{a,b}});if(mapsii.count({a,b==0?1:0})==0) continue;int end=mapsii[{a,b==0?1:0}];if(bfs(start,end)==1){path.clear();for(int i=end;i!=start;i=pre[i]) path.push_back(i);path.push_back(start);}}for(int i=path.size()-1;i>=1;i--){int t1=path[i];int t2=path[i-1];cout<<mapisi.find(t1)->second.first<<" "<<mapisi.find(t1)->second.second<<" ";cout<<mapisi.find(t2)->second.first<<" "<<mapisi.find(t2)->second.second<<" ";}cout<<"="<<" ";cout<<mapisi.find(path[path.size()-1])->second.first<<" "<<mapisi.find(path[path.size()-1])->second.second<<" ";cout<<mapisi.find(path[0])->second.first<<" "<<mapisi.find(path[0])->second.second;cout<<endl;return 0;
}

ACwing 847. 图中点的层次

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int N=1e5+5;
int n,m;
vector<int>G[N];
bool flag[N];
int bfs(int a,int b){memset(flag,0,sizeof flag);queue<pair<int,int>>q;q.push({a,0});flag[a]=1;while(!q.empty()){auto t=q.front();int point=t.first;int step=t.second;if(point==b) return step;q.pop();for(int i=0;i<G[point].size();i++){int nextpoint=G[point][i];if(flag[nextpoint]==0){flag[nextpoint]=1;q.push({nextpoint,step+1});}}}return -1;
}
int main(){cin>>n>>m;while(m--){int a,b;cin>>a>>b;G[a].push_back(b);}cout<<bfs(1,n)<<endl;return 0;
}

RC-u5 相对成功与相对失败

最后的排序是根据若分数不上升的排列的

令参加比赛得一分,不玩手机游戏得一分

最少有多少人撒谎,就是最多有多少人没有撒谎,即最多有多少人是符合分数不上升排列的

所以本题的本质是:最长不上升子序列长度,即动态规划

因此最终 答案 == n - 下降子序列长度

超时 未AC(17/30): 暴力法求下降子序列

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+5;
int T,n,a[N],b[N],dp[N];
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++){int x,y;cin>>x>>y;if(x==1&&y==0) a[i]=2;else if(x==0&&y==1) a[i]=0;else a[i]=1;}for(int i=1;i<=n;i++){int x;cin>>x;b[i]=a[x];dp[i]=1;}for(int i=1;i<=n;i++) for(int j=1;j<i;j++) if(b[j]>=b[i]) dp[i]=max(dp[i],dp[j]+1);sort(dp+1,dp+1+n);cout<<n-dp[n]<<endl;}return 0;
}

优化AC: 单调贪心+二分优化查找

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=1e5+5;
int T,n,a[N],b[N];
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++){int x,y;cin>>x>>y;if(x==1&&y==0) a[i]=2;else if(x==0&&y==1) a[i]=0;else a[i]=1;}for(int i=1;i<=n;i++){int x;cin>>x;b[i]=a[x];}vector<int>stk;stk.push_back(b[1]);for(int i=2;i<=n;i++){if(stk.back()>=b[i]) stk.push_back(b[i]);else{int l=0,r=stk.size()-1;while(l<r){int mid=(l+r)/2;if(stk[mid]>=b[i]) l=mid+1;else r=mid;}stk[l]=b[i];}}cout<<n-stk.size()<<endl;}return 0;
}

ACwing 895. 最长上升子序列

//O(n^2)
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e3+5;
int n,a[N],dp[N];
int main(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i],dp[i]=1;for(int i=1;i<=n;i++)for(int j=1;j<=i-1;j++)if(a[j]<a[i])dp[i]=max(dp[i],dp[j]+1);sort(dp+1,dp+1+n);cout<<dp[n]<<endl;return 0;
}//O(nlongn)
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+5;
int n,a[N];
vector<int>stk;//模拟堆栈
int main(){cin>>n;for(int i=0;i<n;i++) cin>>a[i];stk.push_back(a[0]);for(int i=1;i<n;i++) {//如果该元素大于栈顶元素,将该元素入栈if(a[i]>stk.back()) stk.push_back(a[i]);//否则替换掉第一个>=这个数字的那个数else *lower_bound(stk.begin(),stk.end(),a[i])=a[i];}cout<<stk.size()<<endl;return 0;
}