天梯赛赛前模拟赛补题

本文主要是介绍天梯赛赛前模拟赛补题—2020，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、畅通工程之最低成本建设问题

这道题是用最小生成树做的，之前最小生成树练的很少，比赛时没写出来，也没考虑用最小生成树，还是练得少。

这个题可以用Kruskal算法做，先将每条路的花费从小到大排序，然后再从头开始加每条边花费的价格，从头开始用并查集判断两个点的根节点是否相同，如果相同说明出现了环，就continue；否则就加上两点之间修一条路的价格。
最后用并查集判断一下是否只有一个连通分量。

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define ll long long
using namespace std;
const ll inf = 0x3f3f3f3f;
const int maxn = 2e5+10;
int vis[maxn],start;
int g[1005][1005];
int p,n,k,val[1005][1005],m;
int f[1005];
struct node
{int u,v,p;
}e[maxn];bool cmp(node a,node b)
{return a.p<b.p;
}int Find(int x)
{if(x!=f[x]){f[x] = Find(f[x]);}return f[x];
}bool Union(int u,int v)
{u = Find(u);v = Find(v);if(u!=v){f[v]=u;return true;}return false;
}int main()
{cin>>n>>m;for(int i=1; i<=n; i++)f[i] = i;for(int i=1; i<=m; i++){cin>>e[i].u>>e[i].v>>e[i].p;}sort(e+1,e+m+1,cmp);int cnt=0;int sum=0;for(int i=1; i<=m; i++){if(Union(e[i].u,e[i].v)){cnt++;sum+=e[i].p;}if(cnt==n-1)break;}int num=0;for(int i=1; i<=n; i++){f[i]==i?num++:num;}if(num>1||!num)//没有通路，不是完全图printf("Impossible\n");elseprintf("%d\n",sum);return 0;
}

二、进制转换

这个题不是很难，有一个测试点没过，因为没有判断结果是0时的输出情况，如果等于0，就不用输出符号，如果大于零就不用输出’+‘。

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define ll long long
using namespace std;
const ll inf = 0x3f3f3f3f;
const int maxn = 3e5+10;int main()
{map<char,int>mp;mp['0'] = 0;mp['1'] = 1;mp['2'] = 2;mp['3'] = 3;mp['4'] = 4;mp['5'] = 5;mp['6'] = 6;mp['7'] = 7;mp['8'] = 8;mp['9'] = 9;mp['a'] = 10;mp['A'] = 10;mp['b'] = 11;mp['B'] = 11;mp['c'] = 12;mp['C'] = 12;mp['d'] = 13;mp['D'] = 13;mp['e'] = 14;mp['E'] = 14;mp['f'] = 15;mp['F'] = 15;string str;char ch;while(cin>>ch){if(ch!='#')str+=ch;elsebreak;}int len = str.size();int flag=0;char op;stack<ll>s;for(int i=0; i<len; i++){if(!flag&&(str[i]=='+'||str[i]=='-')){op = str[i];}if((str[i]>='0'&&str[i]<='9')||(str[i]>='a'&&str[i]<='f')||(str[i]>='A'&&str[i]<='F')){s.push(mp[str[i]]);flag=1;}}ll base=1;ll ans=0;while(!s.empty()){ans+=base*s.top();s.pop();base*=16;}if(ans==0)cout<<0<<endl;else{if(op!='+')cout<<op;cout<<ans<<endl;}return 0;
}

三、说反话-加强版

感觉当时做这个题的时候真憨，用的十分暴力的方法，样例还全没过…后来换了种方法.

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define ll long long
using namespace std;
const ll inf = 0x3f3f3f3f;
const int maxn = 3e5+10;int main()
{string str;vector<string>ans;while(cin>>str){ans.push_back(str);if(getchar()=='\n')break;}for(int i=ans.size()-1; i>=0; i--){if(i==ans.size()-1)cout<<ans[i];elsecout<<' '<<ans[i];}cout<<endl;return 0;
}

四、列车厢调度

if语句中有多个判断条件时，先按照运算符的优先级来，同级的从左到右依次。如果是 && 运算，前面的有一个不满足，后面的不会再判断；如果是|| 运算，前面的有一个满足，后面的也不会再判断。
在这个题中，我因为将s_.empty() 放在了s1.top()==s2.top()后面，导致了段错误。

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define ll long long
using namespace std;
const ll inf = 0x3f3f3f3f;
const int maxn = 2e5+10;int main()
{string str1,str2;stack<char>s1,s2,s3;vector<string>ans;cin>>str1;cin>>str2;for(int i=str1.size()-1; i>=0; i--){s1.push(str1[i]);}for(int i=str2.size()-1; i>=0; i--){s2.push(str2[i]);} int flag=1;while(!s2.empty()){if(!s1.empty()&&s1.top()==s2.top()){s1.pop();s2.pop();ans.push_back("1->2");}else if(!s3.empty()&&s3.top()==s2.top()){s3.pop();s2.pop();ans.push_back("3->2");}else if(!s2.empty()&&s1.empty()&&s3.top()!=s2.top()){flag=0;break;}else{s3.push(s1.top());s1.pop();ans.push_back("1->3");}}if(!flag){printf("Are you kidding me?\n");}else{for(int i=0; i<ans.size(); i++){cout<<ans[i]<<endl;}}return 0;
}