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

牛牛的游戏

分析

模拟，判断。

时间复杂度分析

O(1)

参考代码

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string a,b,c;
    cin >> a >> b >> c;
    if (*a.rbegin() == *b .begin() && *b.rbegin() == *c.begin()) puts("YES");
    else puts("NO");
    return 0;
}

艰难的抉择

分析

贪心。
由于第一种操作之后必须是整数，那么可以进行的条件是序列中至少存在一个数是2的倍数，于是每一次的操作中，对n-1个数乘3，对一个可以被2整除的数除以2。所以最多的次数就是每个数字分解出的2的幂的和。

时间复杂度分析

O(nlogx)

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        while (x % 2 == 0) {
            cnt++;
            x /= 2;
        }
    }
    printf("%d\n", cnt);
    return 0;
}

数字比较

分析

取对数进行比较。

时间复杂度

O(1)

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int x, y;
    scanf("%d%d", &x, &y);
    if (x == y) puts("=");
    else {
        long double a = 1.0 * y * log2(x);
        long double b = 1.0 * x * log2(y);
        if (fabs(a-b) < 1e-15) puts("=");
        else if (a > b) puts(">");
        else puts("<");
    }
    return 0;
}

序列最小化

分析

贪心，枚举1的相对位置，把序列分割为前半段和后半段，每次最多替换k - 1个数字，前半段的次数加后半段的次数，每次更新答案。

时间复杂度

O(n)

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int a[N];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    if (k >= n) return puts("1") * 0;
    int ma = -1;
    for (int i = 1;i <= n;i++) {
        if (a[i] == 1) ma = i;
    }
    int ans = N;
    for (int i = 0;i < k;i++) {
        int cnt = 0;
        int pre = ma - i - 1;
        int sub = pre + k;
        sub = n - sub;
        if (pre > 0 && pre <= n)
        {
            cnt += pre / (k-1);
            if (pre % (k-1)) cnt++;
        }
        if (sub > 0)
        {
            cnt += sub / (k-1);
            if (sub % (k-1)) cnt++;
        }
        ans = min(cnt,ans);
    }
    printf("%d\n", ++ans);
    return 0;
}

括号匹配

分析

对于每个字符串，用栈判断是否合法，每次栈为空或者栈中只有一种类型的括号，那么就是合法的，否则不合法。
统计完后，用乘法原理累加即可。

时间复杂度

O(n*logn)

参考代码

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

typedef long long ll;
const int N = 3e5 + 10;

char s[N];
map<int,int> l;
map<int,int> r;
stack<char> S;
int main() {
    int n;
    scanf("%d", &n);
    int com = 0;
    for (int i = 0; i < n; i++) {
        scanf("%s", s);
        while (!S.empty()) S.pop();
        int sz = strlen(s);
        for (int i = 0;i < sz; i++) {
            if (s[i] == '(') {
                S.push(s[i]);
            }
            else {
                if (S.empty()) {
                    S.push(s[i]);
                }
                else
                {
                    if (S.top() == '(') S.pop();
                    else S.push(s[i]);
                }
            }
        }
        int ln = 0,rn = 0;
        if (S.empty()) {
            com++;
            continue;
        }
        while (!S.empty()) {
            char t = S.top();
            if (t == '(') ln++;
            else rn++;
            S.pop();
        }
        if (ln == 0) {
            r[rn]++;
        }
        else if (rn == 0) {
            l[ln]++;
        }
    }
    ll ans = (ll)com * com;
    for (auto it = l.begin();it != l.end();++it) {
        int tmp = it -> first;
        int num = it -> second;
        ans += 1LL * num * r[tmp];
    }
    printf("%lld\n", ans);
    return 0;
}