IT校招全国统一模拟笔试（秋招备战专场) 编程题参考代码汇总

题目https://www.nowcoder.com/test/5217106/summary     

变换次数

分析

暴力计算即可.

参考code

#include <bits/stdc++.h>

using namespace std;

int n, ans, tmp;
int main() {
    cin >> n;
    while(n > 9) {
        tmp = 1;
        for(; n; n /= 10) tmp *= n % 10;
        n = tmp;
        ans++;
    }
    cout << ans << endl;
}

神奇数

分析

枚举区间内的数,然后check一下要求的性质即可。

参考code

#include <bits/stdc++.h>

using namespace std;

bool isprime(int x) {
    for(int i = 2; i * i <= x; i++) {
        if(x % i == 0) return false;
    }
    return true;
}
bool check(int x) {
    int cnt[10];
    memset(cnt, 0, sizeof(cnt));
    while(x) {
        cnt[x % 10]++;
        x /= 10;
    }
    for(int i = 1; i < 10; i++) {
        for(int j = 1; j < 10; j++) {
            if(i != j && cnt[i] && cnt[j]) {
                if(isprime(i * 10 + j)) return true;
            }else if(i == j && cnt[i] >= 2) {
                if(isprime(i * 10 + j)) return true;
            }
        }
    }
    return false;
}
int main() {
    int a, b, ans = 0;;
    cin >> a >> b;
    for(int i = a; i <= b; i++) {
        if(check(i)) ans++;
    }
    cout << ans << endl;
    return 0;
}

添加字符

分析

分为A长度小于B的情况和等于的情况。
小于就枚举B串的一个偏移量,然后枚举维护最小的不相等的位数。
等于就直接对比就好了。

参考code

#include <bits/stdc++.h>

using namespace std;

int main() {
    string a, b;
    cin >> a >> b;
    int la = a.size(), lb = b.size();
    if(la < lb) {
        int ans = 1e9;
        for(int i = 0; i + la <= lb; i++) {
            int cnt = 0;
            for(int j = 0; j < la; j++) {
                if(a[j] != b[i + j]) cnt++;
            }
            if(cnt < ans) {
                ans = cnt;
            }
        }
        cout << ans << endl;
        return 0;
    } else {
        int cnt = 0;
        for(int j = 0; j < la; j++) {
            if(a[j] != b[j]) ++cnt;
        }
        cout << cnt << endl;
    }
    return 0;
}

数组变换

分析

对于每个数一直除2,然后最后check是否相等即可。

参考code

#include <bits/stdc++.h>

using namespace std;

int a[55];
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    string res = "YES";
    for(int i = 0; i < n; i++) {
        while(!(a[i] & 1)) a[i] >>= 1;
    }
    for(int i = 1; i < n; i++) {
        if(a[i] != a[0]) res = "NO";
    }
    cout << res << endl;
}

排序子序列

分析

考虑序列A_1, A_2, . . . , A_i是一个单调的序列.显然如果对于j < i把序列分为A_1, A_2. . . A_j 和 A_j+1, A_j+2, . . . , A_i 两个部分不会使问题变得更优.

于是我们可以贪心的去重复下面过程:
1、 从序列中找出最长的单调连续子序列
2、 删除找出的最长的单调连续子序列

这里的单调序列包括非递增和非递减,而判断子序列是否单调的时候,注意处理等于的情况。

参考code

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector <int> A;
    int ans = 1;
    for(int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if(A.size() <= 1)
            A.push_back(x);
        else {
            if(A[0] <= A.back() && A.back() <= x)
                A.push_back(x);
            else if(A[0] >= A.back() && A.back() >= x)
                A.push_back(x);
            else {
                ans++;
                A.clear();
                A.push_back(x);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

组队竞赛

分析

对于所有参赛队员,我们把他们的水平值进行逆序排序,然后逐一挨着安排每个队伍,然后计算出队伍水平值总和,即为所求。对于a1 >= a_2 >= a_3... >= a{3N}, 我们可以容易观察出答案就是a2 + a_4 + a_6 +...+ a{2N}

参考code

#include <bits/stdc++.h>

using namespace std;

const int maxn = 300100;

int a[maxn];

int main() {
    int n; scanf("%d", &n);
    for(int i = 0; i < 3 * n; i++) scanf("%d", &a[i]);
    sort(a, a + 3 * n);
    long long ans = 0;
    for(int i = 0; i < n; i++) ans += a[n + 2 * i];
    printf("%lld\n", ans);
    return 0;
}

训练部队

分析

可以考虑把新兵分为两种类型。
一种战斗型(战斗值大于潜力值的),一种潜力型(相当于打了他可以获得潜力值),对潜力型的新兵进行战斗力值排序。
然后一种情况是潜力型中战斗值最高的牛牛去打完剩余的潜力型,因为战斗力值会越大越多,另一种情况考虑打完所有潜力型获得值是固定的,那么在攻击型中找一个能打完所有的潜力型的牛牛,并且战斗力值和潜力值要最大。
实现就是用的前缀和和二分

参考code

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int maxn = 100005;
int n;
int goodn,badn;
LL sum[maxn],MAX[maxn];
struct Node {
    LL x,y;
    Node() {}
    Node (const LL &_x,const LL &_y) { x=_x; y=_y; }
    bool operator < (const Node &t) const {
        if(x ^ t.x) return x < t.x;
        return y < t.y;
    }
}good[maxn],bad[maxn];
int search(int L, int R, LL x) {
    while(L < R) {
        int mid = (L + R + 1) >> 1;
        if(MAX[mid] < x) L = mid;
        else R = mid - 1;
    }
    return L;
}
LL solve() {
    LL ans = 0;
    ans = max(ans, sum[search(0, goodn - 1, good[goodn].x)] + good[goodn].x + good[goodn].y);
    for(int i = 1; i <= badn; i++) {
        int pos = search(0, goodn, bad[i].x);
        ans = max(ans, sum[pos] + bad[i].x + bad[i].y);
    }
    return ans;
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        LL x, y;
        scanf("%lld%lld",&x, &y);
        if(x < y) good[++goodn] = Node(x,y);
        else bad[++badn] = Node(x,y);
    }
    sort(good + 1, good + goodn + 1);
    MAX[0] = 0; sum[0] = 0;
    for(int i = 1; i <= goodn; i++) {
        sum[i] = sum[i-1] + good[i].y - good[i].x;
        MAX[i] = max(MAX[i-1], good[i].x - sum[i-1]);
    }
    LL ans = solve();
    printf("%lld\n", ans);
    return 0;
}

牛牛的数列

分析

正着枚举记录一下当前位置的连续上升子序列长度,倒着也做一遍。
最后枚举一个连接点即可。

参考code

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100000 + 5;
const int INF = 0x3f3f3f3f;

int a[maxn], n;
int pre[maxn], suf[maxn];
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", a + i);
    a[0] = INF, a[n + 1] = INF;
    for(int i = 1; i <= n; i++) pre[i] = a[i - 1] < a[i] ? pre[i - 1] + 1 : 1;
    for(int i = n; i >= 1; i--) suf[i] = a[i] < a[i + 1] ? suf[i + 1] + 1 : 1;
    int ans = 1;
    for(int i = 1; i <= n; i++) {
        ans = max(ans, pre[i - 1] + 1);
        ans = max(ans, suf[i + 1] + 1);
        if(a[i + 1] - a[i - 1] >= 2) ans = max(ans, pre[i - 1] + suf[i + 1] + 1);
    }
    printf("%d\n", ans);
    return 0;
}