2020.09.13滴滴秋招笔试（2简单编程题 AK）

第一部分：选择题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;
}

#笔经##滴滴##笔试题目#