正文
2019天梯赛练习题（L2专项练习）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
7-2 列出连通集 （25 分)
给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。
输入样例:
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=;
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=;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=;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,,sizeof(ma));
while(m--)
{
cin>>a>>b;
ma[a][b]=ma[b][a]=;
}
for(int i=;i<n;i++)
{
ans.clear();
dfs(i);
int len=ans.size();
if(len!=)
{
cout<<"{ ";
for(int j=;j<len;j++)
cout<<ans[j]<<" ";
cout<<"}"<<endl;
}
}
memset(vis,false,sizeof(vis));
for(int i=;i<n;i++)
{
ans.clear();
bfs(i);
int len=ans.size();
if(len!=)
{
cout<<"{ ";
for(int j=;j<len;j++)
cout<<ans[j]<<" ";
cout<<"}"<<endl;
}
}
return ;
}
7-3 排序 （25 分)
给定N个（长整型范围内的）整数，要求输出从小到大排序后的结果。
本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下：
- 数据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=;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 ;
}
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=;
int n;
int a[maxn];
char c;
map<string,string>ma;
string s1,s2;
int main()
{
cin>>n;
for(int i=;i<=n;i++)
{
cin>>c;
if(c=='L')
{
cin>>s1>>s2;
if(ma.count(s1)==)
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)==)
{
cout<<"New: OK"<<endl;
ma[s1]=s2;
}
else
cout<<"ERROR: Exist"<<endl;
}
}
return ;
}
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=;
int n;
string s;
stack<double>ss;
bool flag=;
int main()
{
getline(cin,s);
int len=s.length();
double sum=;
int t=;
for(int i=len-;i>=;i--)
{
if(s[i]>=''&&s[i]<='')
{
sum+=(s[i]-'')*t;
t*=;
}
else if(s[i]=='.')
{
sum=sum/(t*1.0);
t=;
}
else if((s[i]=='+'||s[i]=='-')&&sum!=)
{
if(s[i]=='+')
{
ss.push(sum);
i--;
continue;
}
else
{
ss.push(-sum);
i--;
continue;
}
}
else if(s[i]==' ')
{
ss.push(sum);
sum=;t=;
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 = ;
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 == )
{
flag = ;
break;
}
tt = a/b;
}
ss.push(tt);
i--;
}
}
if(flag != )
printf("%.1lf\n",ss.top());
else
printf("ERROR\n");
return ;
}
7-8 集合相似度 （25 分)
给定两个整数集合，它们的相似度定义为：/。其中Nc是两个集合都有的不相等整数的个数，Nt是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。
输入样例：
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=;
int n,m,k,t;
int a,b;
set<int>s[maxn];
int main()
{
cin>>n;
for(int i=;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=;
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*/(sa+sb-same);
printf("%.2f%%\n",ans);
}
return ;
}
7-9 图着色问题 （25 分)
图着色问题是一个著名的NP完全问题。给定无向图G=(V,E)，问可否用K种颜色为V中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色？
但本题并不是要你解决这个着色问题，而是对给定的一种颜色分配，请你判断这是否是图着色问题的一个解。
输入样例：
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=;
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,,sizeof(ma));
while(m--)
{
int a,b;
scanf("%d %d",&a,&b);
ma[a][b]=ma[b][a]=;
}
scanf("%d",&q);
while(q--)
{
bool flag=false;
for(int i=;i<=n;i++)
{
scanf("%d",&col[i]);
s.insert(col[i]);
}
if(s.size()!=k)
flag=true;
else
{
for(int i=;i<=n&&!flag;i++)
{
for(int j=i+;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 ;
}
7-10 出栈序列的合法性 （25 分)
给定一个最大容量为 M 的堆栈，将 N 个数字按 1, 2, 3, ..., N 的顺序入栈，允许按任何顺序出栈，则哪些数字序列是不可能得到的？例如给定 M=5、N=7，则我们有可能得到{ 1, 2, 3, 4, 5, 6, 7 }，但不可能得到{ 3, 2, 1, 7, 5, 6, 4 }。
输入样例：
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=;
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=;i<n;i++)
{
cin>>a[i];
}
int i=,j=;
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+)
break;
}
if(i==n+ && s.empty())
printf("YES\n");
else
printf("NO\n");
}
return ;
}
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=;
int n;
int fa[maxn];
int cnt[maxn];
char c;
int a,b;
void init()
{
for(int i=;i<=n;i++)
{
fa[i]=i;
cnt[i]=;
}
}
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]=;
}
}
int main()
{
cin>>n;
init();
while(cin>>c)
{
if(c=='S')
{
int sum=;
for(int i=;i<=n;i++)
{
if(cnt[i])
sum++;
}
if(sum==)
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 ;
}
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=;
int n,m,k;
int a,b;
int ma[maxn][maxn];
bool vis[maxn];
int aa[maxn];
int main()
{
memset(ma,,sizeof(ma));
cin>>n>>m;
for(int i=;i<=n;i++)
ma[i][i]=;
while(m--)
{
cin>>a>>b;
ma[a][b]=ma[b][a]=;
}
cin>>m;
while(m--)
{
memset(vis,false,sizeof(vis));
cin>>k;
for(int i=;i<=k;i++)
cin>>aa[i];
if(k!=n+)
cout<<"NO"<<endl;
else if(aa[]!=aa[k])
cout<<"NO"<<endl;
else
{
int flag=;
vis[aa[]]=true;
for(int i=;i<k;i++)
{
if(vis[aa[i]] || !ma[aa[i-]][aa[i]])
{
flag=;
break;
}
vis[aa[i]]=true;
}
if(!ma[aa[k-]][aa[k]])
flag=;
if(flag)
printf("YES\n");
else
printf("NO\n");
}
}
return ;
}
7-14 与零交换 （25 分)
将 { 0, 1, 2, ..., N-1 } 的任意一个排列进行排序并不困难，这里加一点难度，要求你只能通过一系列的 Swap(0, *) —— 即将一个数字与 0 交换 —— 的操作，将初始序列增序排列。例如对于初始序列 { 4, 0, 2, 1, 3 }，我们可以通过下列操作完成排序：
- Swap(0, 1) ⟹ { 4, 1, 2, 0, 3 }
- Swap(0, 3) ⟹ { 4, 1, 2, 3, 0 }
- Swap(0, 4) ⟹ { 0, 1, 2, 3, 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=;
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,,sizeof(vis));
cin>>n;
for(int i=;i<n;i++)
{
cin>>a[i];
b[a[i]]=i;
}
int cnt=;
for(int i=;i<n;i++)
{
if(!vis[i])
{
dfs(a[i],cnt);
cnt++;
}
}
for(int i=;i<n;i++)
ma[vis[i]]++;
int ans=;
for(int i=;i<cnt;i++)
{
if(ma[i]==)
continue;
if(i==vis[])
ans+=ma[i]-;
else
ans+=ma[i]+;
}
printf("%d\n",ans);
return ;
}
