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

DNA的片段

分析

挨着扫一遍,维护都是DNA碱基的连续序列的长度最大值即可。

参考代码

#include <bits/stdc++.h>

using namespace std;

string s;

int main() {
    cin >> s;
    int cnt = 0, mx = 0;
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T') {
            cnt++;
            if(mx < cnt) {
                mx = cnt;
            }
        } else {
            cnt = 0;
        }
    }
    cout << mx << endl;
}

彩色瓷砖

分析

分析
因为有4种颜色可以轮转,所以我们直接两个两个的统计是否是相同颜色的个数即可。

参考代码

#include <bits/stdc++.h>

using namespace std;

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

偶串

分析

枚举最后得到的偶串的长度,然后暴力去check是否是偶串。这里是倒着枚举的所以得到的第一个满足条件的即是所求答案。

参考代码

#include <bits/stdc++.h>

using namespace std;

string s;
int main() {
    cin >> s;
    for (int slen = (s.size() - 1) / 2; slen >= 1; slen--) {
        bool is_even_str = true;
        for (int i = 0; i < slen; i++) {
            if (s[i] != s[slen + i]) {
                is_even_str = false;
                break;
            }
        }
        if (is_even_str) {
            cout << (slen * 2) << endl;
            return 0;
        }
    }
    return 0;
}

制造回文

分析

统计每种字符的数量,然后提取一个奇数个数的字符放在第一个回文串中心,对于每个剩下的字符,两个相同字符放在回文串左右,直接用每种字符的数量对2取余即可,如果还有剩下的单一字符都只能单独为一个回文串。

参考代码

#include <bits/stdc++.h>

using namespace std;

string s;
int main() {
    cin >> s;
    vector<int> t(26);
    for(char c : s) {
        t[c - 'a']++;
    }
    int ans = 1;
    for(int i = 0; i < 26; i++) {
        if(t[i] & 1) {
            t[i]--;
            break;
        }
    }
    for(int i = 0; i < 26; i++) {
        t[i] %= 2;
    }
    for(int i = 0; i < 26; i++) {
        if(t[i]) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

猜数游戏

分析

仔细分析我们可以发现一个位置是Y还是N依赖于他的倍数。
考虑若干个素数p0,p1,p2...p3,当他们的乘积那个数确定为Y,那么它们一定也是Y。

例如：
如果27是Y,那么9一定是Y,3也一定是Y,但是81可以是Y或者N。

由于每个数都可以分解为若干素数的乘积。于是我们考虑范围内的素数及其k次幂的位置的情况,其他数字都可以由这些组合而来。
例如：n = 64 考虑2的次幂：
如果64是Y,那么32 16 8 4 2都要是Y;
如果64是N,32是Y,16 8 4 2都要是Y;
如果64 32是N，16是Y，8 4 2都要是Y;
...
依次类推一共有7种情况(因为64 = 2^6)
那么问题就变成计算每个素数p_i^(maxexp) <= n,然后情况数就是每个(maxexp + 1)的乘积

参考代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
int vis[maxn];

int main() {
    int n;
    scanf("%d", &n);
    long long ans = 1;
    for(int i = 2; i <= n; i++) {
        if(vis[i]) continue;
        for(int j = i + i; j <= n; j += i) vis[j] = 1;
        int tmp = n, cnt = 0;
        while(tmp >= i) tmp /= i, cnt++;
        ans = ans * (cnt + 1) % mod;
    }
    printf("%lld\n", ans);
    return 0;
}