滴滴 笔试 两个题目AC
1 分段字符串翻转
#include "bits/stdc++.h"
using namespace std;
int main(){
int i,j,k,m,n;
int num;
cin>>n;
string str;
getchar();
getline(cin,str);
int size = str.size();
num = size/n;
//cout<<"ashdhash";
//cout<<str<<" "<<n;
if(num == 0){
reverse(str.begin() ,str.end());
}
else{
for(i = 0;i < num;i++){
reverse(str.begin() + i*n,str.begin() + (i + 1)*n);
}
reverse(str.begin() + i * n,str.end());
}
cout<<str<<endl;
return 0;
} 2 小岛连接 #include "bits/stdc++.h"
using namespace std;
const int maxn = 1111;
int fa[maxn];
struct node{
int from,to;
int w;
bool operator < (const node & a) const {
return w < a.w;
}
}p[maxn];
void init(int n){
for(int i = 0;i <= n; i++){
fa[i] = i;
}
}
int find_fa(int x){
return fa[x] == x ? fa[x] :fa[x] = find_fa(fa[x]);
}
int kruakal(int n,int num){
int ans = 0;
int cnt = 0;
int i,j,k;
for(i = 0; i < num; i++){
int fx = find_fa(p[i].from);
int fy = find_fa(p[i].to);
if(fx != fy){
fa[fx] = fy;
ans += p[i].w;
cnt ++;
}
if(cnt == n-1)
break;
}
if(cnt < n-1){
return -1;
}
return ans;
}
int main(){
int T;
scanf("%d",&T);
while (T--){
int m,n,k;
cin>>n>>m>>k;
init(n);
int num =0;
int from ,to;
int dis;
for(int i = 0;i < m ; i++){
cin>>from >> to >>dis;
if(dis <= k){
p[num].from = from;
p[num].to = to ;
p[num].w = dis;
num++;
}
}
sort(p, p + num);
int res = kruakal(n,num);
if(res < 0)
cout<<"No"<<endl;
else
cout<<"Yes"<<endl;
}
return 0;
}