2018年校招全国统一模拟笔试(第一场)编程题参考题解

密码翻译

分析

根据题意实现就好了

时间复杂度

O(n)

参考代码

#include <bits/stdc++.h>

const int maxn = 100 + 5;

char s[maxn];
int main() {
    gets(s);
    int len = strlen(s);
    for(int i = 0; i < len; i++) {
        if('a' <= s[i] && s[i] <= 'y') s[i]++;
        else if('A' <= s[i] && s[i] <= 'Y') s[i]++;
        else if(s[i] == 'z') s[i] = 'a';
        else if(s[i] == 'Z') s[i] = 'A';
    }
    puts(s);
    return 0;
}

寻宝

分析

最小生成树,保留最大边即可。

时间复杂度

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct Node
{
    int p;
    int q;
    int k;    
}node;

vector<int> pre;
int unionsearch(int index) {
    while (pre[index] != index) {
        pre[index] = pre[pre[index]];
        index = pre[index];
    }
    return index;
}
void join(int x, int y) {
    if (pre[x] != pre[y]) {
        pre[x] = y;
    }
}
bool cmp(const node& vn1, const node & vn2) {
    return vn1.k < vn2.k;
}
int main(void) {
    int N, M;
    scanf("%d %d", &N, &M);
    vector<node> vn;
    for (int i = 0; i < M; i++) {
        node tmp;
        scanf("%d %d %d", &tmp.p, &tmp.q, &tmp.k);
        vn.push_back(tmp);
    }
    // initialize union set;
    for (int i = 0; i <= N; i++) {
        pre.push_back(i);
    }
    sort(vn.begin(), vn.end(), cmp);
    int res = 0;
    for (int i = 0; i < M; i++) {
        int rootA = unionsearch(vn[i].p);
        int rootB = unionsearch(vn[i].q);
        if (rootA != rootB) {
            if (res < vn[i].k) {
                res = vn[i].k;
            }
            join(rootA, rootB);
        }
    }
    cout << res << endl;
    return 0;
}

打车

分析

注意到n很小，直接枚举子集判断是否合法，在所有合法的方案中找size最大。

时间复杂度

O(n^2)

参考代码

#include <bits/stdc++.h>

using namespace std;

int n, s, p[15];
int main() {
    scanf("%d%d", &n, &s);
    for(int i = 0; i < n; i++) scanf("%d", &p[i]);
    int ans = 0;
    for (int x = 0; x < (1 << n); x++) {
        int mi = 10000000;
        int sum = 0;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if ((x & (1 << i)) != 0 ) {
                mi = min(mi, p[i]);
                sum += p[i];
                cnt++;
            }
        }
        if (sum >= s && sum - mi < s) {
            ans = max(ans, cnt);
        }
    }
    cout << ans << endl;

}

美丽的项链

分析

可以通过母函数求解。
比较直接的就直接用背包dp算就行了。

时间复杂度

O(nmr)

参考代码

#include <bits/stdc++.h>
using namespace std;

long long f[2][105];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        memset(f[i & 1], 0, sizeof(f[i & 1]));
        int l, r;
        scanf("%d%d", &l, &r);
        for (int k = l; k <= r; k++)
            for (int j = m; j >= k; j--)
                f[i & 1][j] += f[i + 1 & 1][j - k];
    }
    printf("%lld\n", f[n & 1][m]);
    return 0;
}

排列

分析

如果某个数没有满足错排要求，直接和相邻的位置swap一下，统计次数即可。

时间复杂度

O(n)

参考代码

来源：牛客网

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;

int a[maxn], n;
int main() {
    cin >> n;
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    int res = 0;
    for(int i = 0; i < n - 1; i++) {
        if(a[i] == i + 1) {
            swap(a[i], a[i + 1]);
            res++;
        }
    }
    if(a[n - 1] == n) res++;
    cout << res << endl;
    return 0;
}

勇敢的妞妞

分析

当k >= 5的时，每一维属性都取最大求和即可。
对于k < 5的时，预处理31种情况可能得到的最大的和。然后dfs枚举子集维护最大的答案即可。

时间复杂度

O(32 * 5 * n)

参考代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e4 + 5;

int mx[10];
int num[maxn][10];
int N, K;
int sta[32];
int dfs(int s, int cur) {
    if(cur == K) return 0;
    int tmp = 0;
    for(int i = s; i; i = (i - 1) & s) tmp = max(tmp, sta[i] + dfs(s ^ i, cur + 1));
    return tmp;
}
int main() {
    scanf("%d%d", &N, &K);
    memset(sta, 0, sizeof(sta));
    memset(mx, 0, sizeof(mx));
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < 5; j++) {
            scanf("%d", &num[i][j]);
            mx[j] = max(mx[j], num[i][j]);
        }
        for(int j = 0; j < 32; j++) {
            int res = 0;
            for(int k = 0; k < 5; k++) {
                if(j & (1 << k)) {
                    res += num[i][k];
                }
            }
            sta[j] = max(sta[j], res);
        }
    }
    if(K >= 5) {
        int ans = 0;
        for(int i = 0; i < 5; i++) ans += mx[i];
        printf("%d\n", ans);
    } else {
        printf("%d\n", dfs(31, 0));
    }
    return 0;
}