比赛地址:https://www.nowcoder.com/acm/contest/107#question
牛客网貌似直接复制会变乱码,真的毒瘤。
A:水题直接写
#include<bits/stdc++.h> using namespace std; int main(){ int n; int t; cin>>t; while(t--) { char a[11]; cin>>a; if(a[0]=='z') { cout<<"ling"<<endl; } else if(a[0]=='o') { cout<<"yi"<<endl; } else if(a[0]=='t') { if(a[1]=='w') cout<<"er"<<endl; else if(a[1]=='h') cout<<"san"<<endl; else cout<<"shi"<<endl; } else if(a[0]=='f') { if(a[1]=='o') cout<<"si"<<endl; else cout<<"wu"<<endl; } else if(a[0]=='s') { if(a[1]=='i') cout<<"liu"<<endl; else cout<<"qi"<<endl; } else if(a[0]=='e') { cout<<"ba"<<endl; } else if(a[0]=='n') { cout<<"jiu"<<endl; } } return 0; }
B:记录给定的字母,然后遍历记录求最长。
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; int main() { char c[22]; int s[33]; int n; while(cin>>c) { memset(s,0,sizeof(s)); for(int i=0;c[i];i++) { s[c[i]-'a']++; } cin>>n; int res=0; while(n--) { cin>>c; bool flag=0; for(int i=0;c[i];i++) { if(s[c[i]-'a']) { s[c[i]-'a']--; } else { flag=1; break; } } if(!flag) { int cmp=strlen(c); res=max(res,cmp); } } cout<<res<<endl; } return 0; }
C:直接暴力求出所有值存到数组里,排序后输出第k大的。
#include<bits/stdc++.h> using namespace std; int ans[3333333]; int a[2555]; int main(){ int n; int t; cin>>t; while(t--) { int s=0; cin>>n; int k; cin>>k; for(int i=0;i<n;i++) { scanf("%d",&a[i]); } int js=0; for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { ans[js++]=min(a[i],a[j]); } } sort(ans,ans+js); cout<<ans[js-k]<<endl; } return 0; }
D:去除两个数,加入两个数的平均值,期望为整个数组的平均值
#include<bits/stdc++.h> using namespace std; int main(){ int n; int t; cin>>t; while(t--) { int s=0; cin>>n; for(int i=0;i<n;i++) { int a; cin>>a; s+=a; } int ans=s/n; cout<<ans<<endl; } return 0; }
E:emmm队友写的代码还没看,先po上来。
#include<bits/stdc++.h> using namespace std; long long dp[1111111]; long long dp1[1111111]; long long dp2[1111111]; char s[1111111]; int main(){ while(~scanf("%s",s)) { if(s[0]=='0') { dp[0]=1; dp1[0]=0; dp2[0]=0; } else { dp[0]=0; dp1[0]=1; dp2[0]=0; } int l=strlen(s); for(int i=1;i<l;++i) { if(s[i]=='0') { dp[i]=1+dp[i-1]; dp1[i]=dp2[i-1]; dp2[i]=dp1[i-1]; } else{ dp[i]=dp1[i-1]; dp1[i]=1+dp[i-1]; dp2[i]=dp2[i-1]; } } long long ans=0; for(int i=0;i<l;++i) { ans+=dp[i]; } cout<<ans<<endl; } return 0; }
F:操作系统里面的一道题,查询时如果内存已满,在查询的序列中查找目前内存中要用到最晚的那一页,将其替换出来即可。
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<vector> using namespace std; bool s[50050]; int a[50050]; vector<int>vec; vector<int>::iterator it; int main() { int n,m,q; while(cin>>n>>m>>q) { for(int i=1;i<=m;i++) s[i]=0; for(int i=0;i<q;i++) cin>>a[i]; vec.clear(); int ans=0; for(int i=0;i<q;i++) { if(s[a[i]]) continue; else { ans++; int res=0; int cmp=0; if(vec.size()<n) { s[a[i]]=1; vec.push_back(a[i]); continue; } for(int ii=0;ii<vec.size();ii++) { bool flag=0; for(int j=ii+1;j<q;j++) { if(vec[ii]==a[j]) { flag=1; if(j>cmp) { cmp=j; res=ii; } break; } } if(!flag) { res=ii; break; } } s[vec[res]]=0; vec.erase(vec.begin()+res); s[a[i]]=1; vec.push_back(a[i]); } } cout<<ans<<endl; } return 0; }
G:emmm同样是队友写的,貌似是找质因数有关的规律。
#include<bits/stdc++.h> using namespace std; bool zs[1111111]; int yz[1111111]; int ans[1111111]; void init(){ memset(zs,0,sizeof(zs)); ans[1]=0; zs[1]=1; yz[1]=1; for(long long int i=2;i<=1000000;i++) { if(zs[i]!=1) { ans[i]=i-1; for(long long int j=i*i;j<=1000000;j+=i) { yz[j]=i; zs[j]=1; } } } for(int i=2;i<=1000000;i++) { if(zs[i]==1) { ans[i]=ans[yz[i]]+ans[i/yz[i]]; } } } int main(){ init(); int t; cin>>t; while(t--) { int n; scanf("%d",&n); printf("%d\n",ans[n]); } return 0; }
H:刚开始样例看了好久都没看懂,后来看懂了也不会写。
I:这个时候已经开始挂机了,队友说这道题应该用线段树的,过了的学长说用线段树可以过,不过要用平方和维护一下。
J:瞟了一眼题面就没细看了。。。