校招全国统一模拟笔试（七月场）编程题参考代码

膨胀的牛牛

分析

根据题意遇到跟当前大小一样的草料大小翻倍即可。

参考code

#include <bits/stdc++.h>

using namespace std;

const int maxn = 200 + 5;

int a[maxn], n, A;
int main() {
    scanf("%d%d", &n, &A);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    for(int i = 0; i < n; i++) {
        if(a[i] == A) A += A;
    }
    printf("%d\n", A);
    return 0;
}

黑化的牛牛

分析

一个做法是枚举去除掉的字符然后去重一下。
其实我们仔细观察对于相邻的两个字符如果一样去除掉后一个是不会产生新的字符串的,于是问题就转化为计算字符串当前字符是否和前面字符相同,特殊处理下长度等于1的情况即可。

参考code

#include <bits/stdc++.h>

using namespace std;

string s;
int main() {
    cin >> s;
    int ans = 0;
    for(int i = 1; i < s.size(); i++) {
        if(s[i] != s[i - 1]) ans++;
    }
    if(s.size() == 1) ans = 0;
    ans++;
    cout << ans << endl;
    return 0;
}

黑白卡片

分析

考虑最终的状态只有两种,然后分别比较之后取最小值即可。

参考code

#include <bits/stdc++.h>

using namespace std;

string s;
int main() {
    cin >> s;
    int cnt1 = 0, cnt2 = 0;
    for(int i = 0; i < s.size(); i++) {
        if(i % 2 == 0) {
            if(s[i] != 'W') cnt1++;
        } else {
            if(s[i] != 'B') cnt1++;
        }
    }
    for(int i = 0; i < s.size(); i++) {
        if(i % 2 == 0) {
            if(s[i] != 'B') cnt2++;
        } else {
            if(s[i] != 'W') cnt2++;
        }
    }
    cout << min(cnt1, cnt2) << endl;
    return 0;
}

序列交换

分析

用vector存序列,枚举交换之后丢进set去重得到个数即可。

参考code

#include <bits/stdc++.h>

using namespace std;

int n;
set<vector <int> > s;
vector<int> x;
int main() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        x.push_back(tmp);
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(i != j) {
                swap(x[i], x[j]);
                s.insert(x);
                swap(x[i], x[j]);
            }
        }
    }
    cout << s.size() << endl;
    return 0;
}

丑陋的字符串

分析

前缀都是'?'部分都是有方案可以抵消掉的。。后面的部分遇到'?'考虑前一个是什么贪心放就好了。

参考code

#include <bits/stdc++.h>

using namespace std;

string str;
int calc(string s, int j) {
    int res = 0;
    for(int i = j + 1; i < s.size(); i++) {
        if(s[i] == s[i - 1]) res++;
    }
    return res;
}
int main() {
    cin >> str;
    int pos = 0;
    while(pos < str.size() && str[pos] == '?') pos++;
    for(int i = pos + 1; i < str.size(); i++) {
        if(str[i] == '?') {
            if(str[i - 1] == 'A') str[i] = 'B';
            else str[i] = 'A';
        }
    }
    cout << calc(str, pos) << endl;
    return 0;
}

庆祝61

分析

枚举排列来计算肯定是不可行的。。
考虑我们已经将身高升序排序了,然后对于前k个小朋友组成队形的身高差的最大值的最小值为f(k),并且第k个和第(k-1)个小朋友是相邻的。现在我们加入第(k+1)个小朋友,考虑到第(k + 1)个小朋友身高是大于等于前面的小朋友,插入队形之后,第(k + 1)个小朋友一定与两个小朋友相邻, 所以当我们将第(k + 1)个小朋友插入到第k个和第(k - 1)个小朋友中间可以得到f(k + 1)的下界一定是max(f(k), h[k] - k[k - 2]),我们又注意到这样插入之后第(k + 1)个和第k个小朋友还是相邻的,于是这样可以一直推广下去。考虑最初3个小朋友的时候这样也是可行的, 于是问题变成了求max(h[i] - h[i - 2])。可以写出很简洁的代码。

参考code

#include <bits/stdc++.h>

using namespace std;

const int maxn = 20 + 5;

int n;
int h[maxn];
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &h[i]);
    sort(h, h + n);
    int ans = 0;
    for(int i = 2; i < n; i++) ans = max(ans, h[i] - h[i - 2]);
    cout << ans << endl;
}

随机的机器人

分析

考虑dp[i % 2][j][k]表示走了i步之后恰好有j个红色格子,并且此时机器人正好站在第k个红色格子上的概率。最后求一个可能的状态的带权和就是所求期望。时间复杂度O(n ^ 3)

这个题应该还有很多做法,甚至可以做到O(n^2),O(n),欢迎讨论.

参考code

#include <bits/stdc++.h>

using namespace std;

const int maxn = 500 + 5;

double dp[2][maxn][maxn];
int n ;
int main() {
    cin >> n;
    double ans = 0;
    dp[0][1][0] = 1.0;
    for(int i = 1; i <= n; i++) {
        int cur = i % 2, old = 1 - (i % 2);
        for(int j = 1; j <= i + 1; j++) for(int k = 0; k < j; k++) dp[cur][j][k] = 0;
        for(int j = 1; j <= i; j++) for(int k = 0; k < j; k++) {
            if(dp[old][j][k] > 0) {
                int pos1 = j, pos2 = k + 1;
                if(pos1 == pos2) ++pos1;
                dp[cur][pos1][pos2] += 0.5 * dp[old][j][k];
                int pos3 = j, pos4 = k - 1;
                if(pos4 == -1) {pos3++,pos4++;}
                dp[cur][pos3][pos4] += 0.5 * dp[old][j][k];
            }
        }
    }
    for(int i = 1; i <= n + 1; i++) {
        for(int j = 0; j < i; j++) {
            ans += i * dp[n % 2][i][j];
        }
    }
    printf("%.1f\n", ans);
    return 0;
}

逃离农场

分析

考虑dp[i][k][sum]表示前i个奶牛中选取k个他们的编号和为sum的方案数,于是有:
dp[i][k][sum] = dp[i - 1][k][sum] + dp[i - 1][k - 1][(sum - i + n) % n]
然后可以滚动优化或者压缩一维空间。

参考code

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
int n, k;
int dp[55][1005];
int main() {
    cin >> n >> k;
    dp[0][0] = 1;
    for(int i = 0; i < n; i++) {
        for(int j = k; j >= 1; j--) {
            for(int x = 0; x < n; x++) {
                dp[j][x] = (dp[j][x] + dp[j - 1][x - i < 0 ? x - i + n : x - i]) % mod;
            }
        }
    }
    cout << dp[k][0] << endl;
    return 0;
}