2019天梯赛练习题（L2专项练习）

7-2 列出连通集（25 分)

给定一个有

输入样例:

8 6 0 7 0 1 2 0 4 1 2 4 3 5

输出样例:

{ 0 1 4 2 7 } { 3 5 } { 6 } { 0 1 2 7 4 } { 3 5 } { 6 }
思路:先dfs，再bfs即可，但是注意在bfs之前要把vis数组再一次的初始化。

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <queue>
using namespace std; typedef long long LL; const int maxn=15; int n,m; int a,b; int ma[maxn][maxn]; bool vis[maxn]; vector<int>ans; void dfs(int x) { if(vis[x]) return ; vis[x]=true; ans.push_back(x); for(int i=0;i<n;i++) { if(ma[x][i]) dfs(i); } } void bfs(int x) { if(vis[x]) return; queue<int>q; q.push(x); ans.push_back(x); vis[x]=true; while(!q.empty()) { int tem=q.front(); q.pop(); for(int i=0;i<n;i++) { if(ma[tem][i] && !vis[i]) { q.push(i); ans.push_back(i); vis[i]=true; } } } } int main() { cin>>n>>m; memset(vis,false,sizeof(vis)); memset(ma,0,sizeof(ma)); while(m--) { cin>>a>>b; ma[a][b]=ma[b][a]=1; } for(int i=0;i<n;i++) { ans.clear(); dfs(i); int len=ans.size(); if(len!=0) { cout<<"{ "; for(int j=0;j<len;j++) cout<<ans[j]<<" "; cout<<"}"<<endl; } } memset(vis,false,sizeof(vis)); for(int i=0;i<n;i++) { ans.clear(); bfs(i); int len=ans.size(); if(len!=0) { cout<<"{ "; for(int j=0;j<len;j++) cout<<ans[j]<<" "; cout<<"}"<<endl; } } return 0; }

7-3 排序（25 分)

给定

本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下：

数据1：只有1个元素；
数据2：11个不相同的整数，测试基本正确性；
数据3：103个随机整数；
数据4：104个随机整数；
数据5：105个随机整数；
数据6：105个顺序整数；
数据7：105个逆序整数；
数据8：105个基本有序的整数；
数据9：105个随机正整数，每个数字不超过1000。

输入样例:

11 4 981 10 -17 0 -20 29 50 8 43 -5

输出样例:

-20 -17 -5 0 4 8 10 29 43 50 981
思路；可以选择一些nlogn 的排序算法去写，但是这题也可以水过去。

#include<iostream> #include<vector> #include<algorithm>
using namespace std; bool cmp(const int &a,const int &b){ if(a < b) return true; return false; } int main() { int i,j,N,num; vector<int> s; vector<int>::iterator it; cin>>N; for(i=0;i<N;i++){ cin>>num; s.push_back(num); } sort(s.begin(),s.end(),cmp); for(it=s.begin();it!=s.end();it++){ if(it!=s.begin()) cout<<" "; cout<<(*it); } return 0; }

7-4 QQ帐户的申请与登陆（25 分)

实现QQ新帐户申请和老帐户登陆的简化版功能。最大挑战是：据说现在的QQ号码已经有10位数了。

输入样例:

5 L 1234567890 myQQ@qq.com N 1234567890 myQQ@qq.com N 1234567890 myQQ@qq.com L 1234567890 myQQ@qq L 1234567890 myQQ@qq.com

输出样例:

ERROR: Not Exist New: OK ERROR: Exist ERROR: Wrong PW Login: OK
思路：用map存储，然后到对应的情况就在map里面查询即可，不同的情况对应着不同的答案。

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <map>
using namespace std; typedef long long LL; const int maxn=10; int n; int a[maxn]; char c; map<string,string>ma; string s1,s2; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>c; if(c=='L') { cin>>s1>>s2; if(ma.count(s1)==0) cout<<"ERROR: Not Exist"<<endl; else if(ma[s1]==s2) cout<<"Login: OK"<<endl; else cout<<"ERROR: Wrong PW"<<endl; } else { cin>>s1>>s2; if(ma.count(s1)==0) { cout<<"New: OK"<<endl; ma[s1]=s2; } else cout<<"ERROR: Exist"<<endl; } } return 0; }

7-5 求前缀表达式的值（25 分)

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。前缀表达式指二元运算符位于两个运算数之前，例如2+3*(7-4)+8/4的前缀表达式是：+ + 2 * 3 - 7 4 / 8 4。请设计程序计算前缀表达式的结果值。

输入样例:

+ + 2 * 3 - 7 4 / 8 4

输出样例:

13.0
思路：了解前缀表达式的求值，先把字符串读入进来，然后从后往前，将读取出来的值放到stack 容器里面，如果读到操作符，就取出栈顶的两个元素进行运算，将运算的结果再存储到栈中。注意除数不能为0，以及最后的时候栈不能有数值了。

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <map> #include <stack>
using namespace std; typedef long long LL; const int maxn=10; int n; string s; stack<double>ss; bool flag=0; int main() { getline(cin,s); int len=s.length(); double sum=0; int t=1; for(int i=len-1;i>=0;i--) { if(s[i]>='0'&&s[i]<='9') { sum+=(s[i]-'0')*t; t*=10; } else if(s[i]=='.') { sum=sum/(t*1.0); t=1; } else if((s[i]=='+'||s[i]=='-')&&sum!=0) { if(s[i]=='+') { ss.push(sum); i--; continue; } else { ss.push(-sum); i--; continue; } } else if(s[i]==' ') { ss.push(sum); sum=0;t=1; continue; } else if(s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/') { double a = ss.top(); ss.pop(); double b = ss.top(); ss.pop(); double tt = 0; if(s[i] == '+') tt = a+b; else if(s[i] == '-') tt = a-b; else if(s[i] == '*') tt = a*b; else if(s[i] == '/') { if(b == 0) { flag = 1; break; } tt = a/b; } ss.push(tt); i--; } } if(flag != 1) printf("%.1lf\n",ss.top()); else printf("ERROR\n"); return 0; }

7-8 集合相似度（25 分)

给定两个整数集合，它们的相似度定义为： $/。其中$

输入样例：

3 3 99 87 101 4 87 101 5 87 7 99 101 18 5 135 18 99 2 1 2 1 3

输出样例：

50.00% 33.33%
思路：题意就是找到两个集合相同数值的数的个数，就可以用set 存储一个集合里面的元素，然后用一个set 里面的元素去匹配另一个set，得到相同数值的数的个数就可以了。

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <set>
using namespace std; typedef long long LL; const int maxn=55; int n,m,k,t; int a,b; set<int>s[maxn]; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>m; while(m--) { cin>>k; s[i].insert(k); } } cin>>m; while(m--) { cin>>a>>b; int sa=s[a].size(); int sb=s[b].size(); int same=0; set<int>::iterator it; for(it=s[a].begin();it!=s[a].end();it++) { if(s[b].find(*it)!=s[b].end()) same++; } double ans=same*1.0*100/(sa+sb-same); printf("%.2f%%\n",ans); } return 0; }

7-9 图着色问题（25 分)

图着色问题是一个著名的NP完全问题。给定无向图

但本题并不是要你解决这个着色问题，而是对给定的一种颜色分配，请你判断这是否是图着色问题的一个解。

输入样例：

6 8 3 2 1 1 3 4 6 2 5 2 4 5 4 5 6 3 6 4 1 2 3 3 1 2 4 5 6 6 4 5 1 2 3 4 5 6 2 3 4 2 3 4

输出样例：

Yes Yes No No
思路：用二维数组ma[][]存储边，然后按给的颜色去查，如果边相同，且颜色相同就不满足题意。

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #include <stack> #include <vector> #include <set>
using namespace std; typedef long long LL; const int INF=0x3f3f3f3f; const int maxn=505; int n,m,k,q; int ma[maxn][maxn]; int col[maxn]; set<int>s; int main() { scanf("%d %d %d",&n,&m,&k); memset(ma,0,sizeof(ma)); while(m--) { int a,b; scanf("%d %d",&a,&b); ma[a][b]=ma[b][a]=1; } scanf("%d",&q); while(q--) { bool flag=false; for(int i=1;i<=n;i++) { scanf("%d",&col[i]); s.insert(col[i]); } if(s.size()!=k) flag=true; else { for(int i=1;i<=n&&!flag;i++) { for(int j=i+1;j<=n&&!flag;j++) { if(ma[i][j]) { if(col[i]==col[j]) flag=true; } } } } if(flag) printf("No\n"); else printf("Yes\n"); s.clear(); } return 0; }

7-10 出栈序列的合法性（25 分)

给定一个最大容量为

输入样例：

5 7 5 1 2 3 4 5 6 7 3 2 1 7 5 6 4 7 6 5 4 3 2 1 5 6 4 3 7 2 1 1 7 6 5 4 3 2

输出样例：

YES NO NO YES NO
思路：就是走一遍存储的过程，用stack 去模拟出栈的情况，如果能够模拟成功就是YES，否则就是NO。

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <map> #include <stack>
using namespace std; typedef long long LL; const int maxn=1005; stack<int>s; queue<int>q; int a[maxn]; int main() { int m,n,k; cin>>m>>n>>k; while(k--) { stack<int>s; for(int i=0;i<n;i++) { cin>>a[i]; } int i=1,j=0; while(s.size()<m && j<n) { s.push(i);//按开始的顺序push i++; while(!s.empty()&&j<n&&a[j]==s.top())//看给定的出栈顺序，相同则pop { j++; s.pop(); } if(i==n+1) break; } if(i==n+1 && s.empty()) printf("YES\n"); else printf("NO\n"); } return 0; }

7-11 文件传输（25 分)

当两台计算机双向连通的时候，文件是可以在两台机器间传输的。给定一套计算机网络，请你判断任意两台指定的计算机之间能否传输文件？

输入样例 1：

5 C 3 2 I 3 2 C 1 5 I 4 5 I 2 4 C 3 5 S

输出样例 1：

no no yes There are 2 components.
思路：并查集的简单应用，开始没看清题意，只有到最后的时候才需要判断联通集，并不需要在全联通的时候输出The network is connected.

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <map> #include <stack>
using namespace std; typedef long long LL; const int maxn=10005; int n; int fa[maxn]; int cnt[maxn]; char c; int a,b; void init() { for(int i=1;i<=n;i++) { fa[i]=i; cnt[i]=1; } } int findd(int x) { if(fa[x]==x) return fa[x]; else
        return fa[x]=findd(fa[x]); } void join(int x,int y) { int fx=findd(x),fy=findd(y); if(fx!=fy) { fa[fx]=fy; cnt[fy]+=cnt[fx]; cnt[fx]=0; } } int main() { cin>>n; init(); while(cin>>c) { if(c=='S') { int sum=0; for(int i=1;i<=n;i++) { if(cnt[i]) sum++; } if(sum==1) printf("The network is connected."); else printf("There are %d components.\n",sum); break; } else if(c=='C') { cin>>a>>b; if(findd(a)!=findd(b)) cout<<"no"<<endl; else cout<<"yes"<<endl; } else { cin>>a>>b; join(a,b); } } return 0; }

7-12 汉密尔顿回路（25 分)

著名的“汉密尔顿（Hamilton）回路问题”是要找一个能遍历图中所有顶点的简单回路（即每个顶点只访问 1 次）。本题就要求你判断任一给定的回路是否汉密尔顿回路。

输入样例：

6 10 6 2 3 4 1 5 2 5 3 1 4 1 1 6 6 3 1 2 4 5 6 7 5 1 4 3 6 2 5 6 5 1 4 3 6 2 9 6 2 1 6 3 4 5 2 6 4 1 2 5 1 7 6 1 3 4 5 2 6 7 6 1 2 5 4 3 1

输出样例：

YES NO NO NO YES NO
思路：用二维数组ma[][]存边，然后按给的答案顺序判断，当点没访问过并且存在边的时候符合题意，否则就是NO

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <map> #include <stack>
using namespace std; typedef long long LL; const int maxn=205; int n,m,k; int a,b; int ma[maxn][maxn]; bool vis[maxn]; int aa[maxn]; int main() { memset(ma,0,sizeof(ma)); cin>>n>>m; for(int i=1;i<=n;i++) ma[i][i]=1; while(m--) { cin>>a>>b; ma[a][b]=ma[b][a]=1; } cin>>m; while(m--) { memset(vis,false,sizeof(vis)); cin>>k; for(int i=1;i<=k;i++) cin>>aa[i]; if(k!=n+1) cout<<"NO"<<endl; else if(aa[1]!=aa[k]) cout<<"NO"<<endl; else { int flag=1; vis[aa[1]]=true; for(int i=2;i<k;i++) { if(vis[aa[i]] || !ma[aa[i-1]][aa[i]]) { flag=0; break; } vis[aa[i]]=true; } if(!ma[aa[k-1]][aa[k]]) flag=0; if(flag) printf("YES\n"); else printf("NO\n"); } } return 0; }

7-14 与零交换（25 分)

将 { 0, 1, 2, ..., N-1 } 的任意一个排列进行排序并不困难，这里加一点难度，要求你只能通过一系列的 Swap(0, *) —— 即将一个数字与 0 交换 —— 的操作，将初始序列增序排列。例如对于初始序列 { 4, 0, 2, 1, 3 }，我们可以通过下列操作完成排序：

Swap(0, 1)
Swap(0, 3)
Swap(0, 4)

本题要求你找出将前 N 个非负整数的给定排列进行增序排序所需要的最少的与 0 交换的次数。

输入样例：

10 3 5 7 2 6 4 9 0 8 1

输出样例：

9
思路：找循环节。（3,0,7,2），（5,1,9,6,4），（8）三个
第一个节（包含0）需要循环节长度-1次操作，即可把其它元素移到对应的位置
第二个节（不包含0）需要循环节长度+1次操作，可以看成向循环节中加入0（操作次数加1），
那么循环节长度加1（交换时次数要加1），总共比包含0的情况多操作两次
第三个节是一个元素，那么不需要任何操作。

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <map> #include <stack>
using namespace std; typedef long long LL; const int maxn=100005; int n; int a[maxn],b[maxn]; int vis[maxn]; map<int,int>ma; void dfs(int x,int t) { if(vis[x]) return ; vis[x]=t; dfs(b[x],t); } int main() { memset(vis,0,sizeof(vis)); cin>>n; for(int i=0;i<n;i++) { cin>>a[i]; b[a[i]]=i; } int cnt=1; for(int i=0;i<n;i++) { if(!vis[i]) { dfs(a[i],cnt); cnt++; } } for(int i=0;i<n;i++) ma[vis[i]]++; int ans=0; for(int i=1;i<cnt;i++) { if(ma[i]==1) continue; if(i==vis[0]) ans+=ma[i]-1; else ans+=ma[i]+1; } printf("%d\n",ans); return 0; }

秒客网

2019天梯赛练习题（L2专项练习）

输入样例:

输出样例:

输入样例:

输出样例:

输入样例:

输出样例:

输入样例:

输出样例:

输入样例：

输出样例：

输入样例：

输出样例：

输入样例：

输出样例：

输入样例 1：

输出样例 1：

输入样例：

输出样例：

输入样例：

输出样例：

相关文章