RC-u1 亚运奖牌榜
思路
略
代码
点击查看代码
#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x; i<=y; ++i)
using namespace std;
#define int long long
int a[30][30];
signed main(){
int n;
cin>>n;
while(n--){
int x,c;
cin>>x>>c;
a[x][c]++;
}
rep(i,0,1){
rep(j,1,3){
cout<<a[i][j];
if(j<3) cout<<" ";
}
cout<<endl;
}
for(int i=1; i<=3; ++i){
if(a[0][i]>a[1][i]){
puts("The first win!");
break;
}else if(a[0][i]<a[1][i]){
puts("The second win!");
break;
}
}
return 0;
}
RC-u2 出院
思路
说一下坑点，注意题目说的有多种分解方式是指的分解后的结果有多种(列如分解成：AD,CD),而不是有多种方式能分解到一种结果(例如有三种方式分解成DD)
代码
点击查看代码
#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x; i<=y; ++i)
using namespace std;
#define int long long
map<string,string> mp;
signed main(){
int n,m;
cin>>n>>m;
vector<string> ve;
rep(i,1,n){
string s1,s2;
cin>>s1>>s2;
ve.push_back(s1);
mp[s1]=s2;
}
while(m--){
string s;
cin>>s;
if(mp.count(s)!=0) {
cout<<mp[s]<<'\n';
continue;
}
string ans="";
map<string,bool> num;
for(int i=0; i<ve.size(); ++i){
for(int j=0; j<ve.size(); ++j){
if(ve[i]+ve[j]==s){
ans=mp[ve[i]]+mp[ve[j]];
num[ans]=1;
}
}
}
if(num.size()!=1) ans="D";
cout<<ans<<'\n';
}
return 0;
}
RC-u3 骰子游戏
sb
RC-u4 相对论大师
思路
把字符串通过map映射成数字，建图。就是在图上寻找要求的路径即刻，dfs暴力寻找就能过
代码
点击查看代码
#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x; i<=y; ++i)
using namespace std;
#define int long long
#define PSI pair<string,int>
#define pushk push_back
const int N = 1e5+9;
vector<int> g[N];
map<PSI,int> mp;
map<int,PSI> name;
int re[N];
vector<vector<int> > ve;
vector<int> tmp;
bool vis[N];
void dfs(int s,int u){
if(re[s]==u) {
ve.pushk(tmp);
return ;
}
for(auto &it : g[u]){
if(!vis[it]){
tmp.pushk(it);
vis[it]=1;
dfs(s,it);
tmp.pop_back();
}
}
}
bool cmp(const vector<int> &A, const vector<int> &B){
return A.size()<B.size();
}
signed main(){
int n;
cin>>n;
int idx=0;
rep(i,1,n){
string A,B;
int a,b;
cin>>A>>a>>B>>b;
if(!mp[{A,a}]) mp[{A,a}]=++idx;
if(!mp[{A,!a}]) mp[{A,!a}]=++idx;
name[mp[{A,a}]]={A,a};
re[mp[{A,a}]]=mp[{A,!a}];
if(!mp[{B,b}]) mp[{B,b}]=++idx;
if(!mp[{B,!b}]) mp[{B,!b}]=++idx;
name[mp[{B,b}]]={B,b};
re[mp[{B,b}]]=mp[{B,!b}];
g[mp[{A,a}]].push_back(mp[{B,b}]);
}
for(int i=1; i<=idx; ++i){
tmp.clear();
tmp.pushk(i);
vis[i]=1;
dfs(i,i);
memset(vis,0,sizeof vis);
}
sort(ve.begin(),ve.end(),cmp);
auto ans = ve[0];
for(int i=0; i<ans.size(); ++i){
int it = ans[i];
cout<<name[it].first<<" "<<name[it].second<<" ";
if(i!=0&&i<ans.size()-1)cout<<name[it].first<<" "<<name[it].second<<" ";
}
cout<<"= ";
cout<<name[ans[0]].first<<" "<<name[ans[0]].second<<" ";
cout<<name[ans[ans.size()-1]].first<<" "<<name[ans[ans.size()-1]].second;
return 0;
}
RC-u5 相对成功与相对失败
思路
根据题目要求计算出每个人的得分(注意题目的意思00和11等价)，根据题目的要求合理的应该是从小到大的排序。那么我们找出最长的从小到大的子序列（即最长不下降子序列）\(tt\)，再用总长度 \(n\) 减去 \(tt\) 即可
代码
点击查看代码
#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x; i<=y; ++i)
using namespace std;
const int N = 1e5+9;
int a[N],stk[N],b[N],c[N];
signed main(){
int T;
cin>>T;
while(T--){
int n;
cin>>n;
rep(i,1,n) a[i]=c[i]=b[i]=0;
rep(i,1,n){
int x,y;
cin>>x>>y;
if(x==1&&y==0) a[i]=1;
else if(x==0&&y==1) a[i]=3;
else a[i]=2;
}
rep(i,1,n){
cin>>b[i];
c[i]=a[b[i]];
}
int tt=0;
stk[++tt]=c[1];
rep(i,2,n){
if(c[i]>=stk[tt]) stk[++tt]=c[i];
else {
int p = upper_bound(stk+1,stk+tt+1,c[i])-stk;
stk[p]=c[i];
}
}
cout<<n-tt<<'\n';
}
return 0;
}