第四次双周赛
目录L1-2 日期格式化
-
当时写的时候忘记补0咋写了用if硬加的
printf("%02d",m); //输出m宽度为2,不足前面补0 printf("%-4d",m); //输出n宽度为4,不足后面补空格 printf("%4d",m); //输出m宽度为4,不足前面补空格
L1-6 正整数A+B(getline)
-
考点应该是输入B的时候可能中间会有空格,这里用getline
string b; getline(cin,b);
L2-1 排座位(并查集)
-
并查集问题
-
思路:因为朋友的朋友也是朋友,把所有朋友都并到一起
#include<bits/stdc++.h> using namespace std; int n,m,k; map<int,int> mp; int gx[110][110]; int findroot(int a) { if(mp[a]==a) return a; else findroot(mp[a]); } //这里好像写得有点问题,改成这个 //int findRoot(int x) //{ // if(mp[x]!=x) // mp[x]=findRoot(mp[x]); // return mp[x]; //} void unionr(int a,int b) { int f1=findroot(a); int f2=findroot(b); if(f1==f2) return ; if(f1>f2) swap(f1,f2); //让大的为根 mp[f1]=f2; } int main() { cin>>n>>m>>k; for(int i=1;i<=n;i++) mp[i]=i; while(m--) { int a,b,x; cin>>a>>b>>x; gx[a][b]=x; gx[b][a]=x; if(x==1) { unionr(a,b); } } while(k--) { int a,b; cin>>a>>b; if(gx[a][b]!=-1&&findroot(a)==findroot(b)) cout<<"No problem"<<endl; if(gx[a][b]!=-1&&findroot(a)!=findroot(b)) cout<<"OK"<<endl; if(gx[a][b]==-1&&findroot(a)==findroot(b)) cout<<"OK but..."<<endl; if(gx[a][b]==-1&&findroot(a)!=findroot(b)) cout<<"No way"<<endl; } return 0; }
L2-2 名人堂与代金券
- 注意细节脑子别晕
#include<bits/stdc++.h>
using namespace std;
int n,g,k,sum;
struct Student{
string id;
int score,pm;
}stu[10005];
bool cmp(Student a,Student b)
{
if(a.score ==b.score )
{
int len1=a.id .length();
int len2=b.id .length();
int len=min(len1,len2);
for(int i=0;i<len;i++)
{
if(a.id[i] !=b.id[i] ) //注意1
return a.id[i]<b.id[i];
}
return len1>len2;
}
return a.score >b.score ;
}
int main()
{
cin>>n>>g>>k;
for(int i=0;i<n;i++)
{
cin>>stu[i].id >>stu[i].score ;
if(stu[i].score >=g&&stu[i].score <=100)
{
sum+=50;
}
if(stu[i].score >=60&&stu[i].score <g)
sum+=20;
}
sort(stu,stu+n,cmp);
cout<<sum<<endl;
if(k<=0)
return 0;
stu[0].pm =1;
for(int i=1;i<n;i++)
{
if(stu[i].score ==stu[i-1].score)
stu[i].pm =stu[i-1].pm;
else
stu[i].pm =i+1; //注意2
}
for(int i=0;i<n;i++)
{
if(stu[i].pm <=k)
cout<<stu[i].pm <<" "<<stu[i].id <<" "<<stu[i].score <<endl;
}
return 0;
}
L2-3 包装机(栈和队列)
-
栈和队列的应用
#include<bits/stdc++.h> using namespace std; int n,m,s,k; queue<char> wp[1010]; stack<char> st; int main() { cin.tie(0); cout.tie(0); cin>>n>>m>>s; for(int i=1;i<=n;i++) { string x; cin>>x; for(int j=0;j<m;j++) { wp[i].push(x[j]); } } while(cin>>k) { if(k==-1) break; if(k==0) { if(!st.empty()) { cout<<st.top(); st.pop(); } continue; } if(!wp[k].empty()) { if(st.size()==s) { cout<<st.top(); st.pop(); } st.push(wp[k].front()); wp[k].pop(); } } return 0; }
L2-4 愿天下有情人皆是失散多年的兄妹
-
用vector存图,搜索两人五代以内的亲属,如果有重复则不能结婚
#include<bits/stdc++.h> using namespace std; const int N=1e5+5; vector<int> vec[N]; bool vis[N]; char sex[N]; bool flag; void Dfs(int x,int num) { if(num>=4) return; for(int i=0;i<vec[x].size();i++) { if(!vis[vec[x][i]]) { vis[vec[x][i]]=1; Dfs(vec[x][i],num+1); } else flag=1; } } int main() { int T; cin>>T; while(T--) { int t,fa,ma; char ch; scanf("%d ",&t); sex[t]=getchar(); scanf(" %d %d",&fa,&ma); if(fa!=-1) { vec[t].push_back(fa); sex[fa]='M'; } if(ma!=-1) { vec[t].push_back(ma); sex[ma]='F'; } } cin>>T; while(T--) { int x,y; scanf("%d %d",&x,&y); if(sex[x]==sex[y]) cout<<"Never Mind"<<endl; else { memset(vis,0,sizeof(vis)); vis[x]=1; vis[y]=1; flag=0; Dfs(x,0); Dfs(y,0); if(flag) cout<<"No"<<endl; else cout<<"Yes"<<endl; } } return 0; }