第一部分：选择题20个，每个3分，一共60分；（选择题有几个不会选，难道专门卡100分吗？）
第二部分：2道编程题，每个20分；（AK）
总分：100分；
编程题 AK：
第一题：签到题，给一个字符串，给一个整数k， 每k个进行翻转，最后剩下的不足k个也翻转
思路：直接模拟，一开始不知道输入哪里出问题，总是90%，后来我直接读入两行串，
第一行转换成整数，第二行就是要操作的字符串，详细看代码：
别着急，先看一下截图的一直卡90%，有点泪奔，虽然AC了，但是这个串的输入处理有点闹腾啊！！！
代码：
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("a.txt", "r", stdin);
#endif
int k;
string s;
while(getline(cin, s)) {
stringstream ss(s);
ss >> k;
getline(cin, s);
int n = s.size();
int l = 0;
int r = k - 1;
int i;
int j;
while(r < n) {
i = l;
j = r;
while(i < j) swap(s[i++], s[j--]);
l = r + 1;
r = l + k - 1;
}
if(l < n) {
i = l;
j = n-1;
while(i < j) swap(s[i++], s[j--]);
}
cout << s << endl;
}
return 0;
}
第二题：n个岛屿，m个桥进行连接，桥超过k长度的就不能连接，问最后n个岛屿是否能连通
思路：简单题，最小生成树树 + 并查集，本质就是最小生成树，直接把所有的边存起来，然后一个sort，然后依次检查就行，满足n-1条边就结束
最后根据建成的数量是否等于n-1 直接得出是否能成功
代码：
#include<bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false),cin.tie(0);
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll, ll>;
ll qpow(ll x, ll y) { ll a=1, b=x; while(y){if(y&0x1) a*=b; b*=b; y>>=1;} return a;}
ll qpow(int x, int y) { int a=1, b=x; while(y){if(y&0x1) a*=b; b*=b; y>>=1;} return a;}
template <typename T>
inline void read(T &x) {
char ch=getchar(); int f=1; x=0; while(!isdigit(ch)){if(ch=='-')f *= -1; ch=getchar();}
while(isdigit(ch)) {x = (x<<1) + (x<<3) + (ch^48); ch=getchar();} x*=f;
}
const int maxn = 1005;
int f[maxn];
struct Node {
int u;
int v;
int w;
Node(){u = 0; v = 0;}
Node(int u, int v, int w):u(u),v(v),w(w){}
};
Node edge[maxn];
int n;
int m;
int k;
int find(int x) {
if(x == f[x]) return x;
return f[x] = find(f[x]);
}
void merge(int u, int v) {
int fu = find(u);
int fv = find(v);
f[u] = min(fu, fv);
f[v] = min(fu, fv);
}
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("b.txt", "r", stdin);
#endif
int t;
cin >> t;
while(t--) {
cin >> n >> m >> k;
for(int i = 0; i < m; ++i) cin >> edge[i].u >> edge[i].v >> edge[i].w;
sort(edge, edge + m, [](const Node& l, const Node& r){return l.w < r.w;});
if(edge[0].w > k) {
cout << "No" << endl;
continue;
}
for(int i = 1; i <= n; ++i) f[i] = i;
int cnt = 0;
for(int i = 0; i < m; ++i) {
if(edge[i].w > k) break;
int fu = find(edge[i].u);
int fv = find(edge[i].v);
if(fu == fv) continue;
merge(fu, fv);
cnt++;
if(cnt == n-1) break;
}
if(cnt == n-1) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
全部评论
(5) 回帖