2017年校招全国统一模拟笔试(第一场)编程题参考代码汇总

预告：下一场考试10日开启报名，23日考试，请大家注意及时报名参加模拟考试。

本次模拟考试题目练习链接https://www.nowcoder.com/test/4236887/summary

面试算法课程https://www.nowcoder.com/courses/semester/algorithm

好多鱼

分析

直接暴力枚举然后check就好了

参考code

#include <bits/stdc++.h>

using namespace std;

int a[55];
int mi,ma;
int n;
int main(){
    cin >> mi >> ma;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    int ans = 0;
    for(int i = mi; i <= ma; i++){
        int flag = 1;
        for(int j = 0; j < n; j++){
            if( (i >= a[j] * 2 && i <= a[j] * 10) || (i * 2 <= a[j] && i * 10 >= a[j]) ){
                flag = 0;
            }
        }
        if(flag) ans++;
    }
    cout << ans << endl;
}

循环单词

分析

范围比较小,直接暴力求每个串的最小表示。然后丢进set去重就好了

参考code

#include <bits/stdc++.h>

using namespace std;

int n;
string calc(string s){
    vector<string> v;
    for(int i = 0; i < (int)s.length(); i++){
        string tmp = s;
        for(int j = 0; j < (int)s.length(); j++) tmp[j] = s[(j + i) % s.length()];
        v.push_back(tmp);
    }
    sort(v.begin(),v.end());
    return v[0];
}
int main(){
    set<string> s;
    cin >> n;
    for(int i = 0; i < n; i++){
        string x;
        cin >> x;
        s.insert(calc(x));
    }
    cout << s.size() << endl;
}

连续整数

分析

排序之后分别讨论几种可能的情况就OK了

参考code

#include <bit/stdc++.h>

using namespace std;

int n;
int num[55];
int main(){
    cin >> n;
    for(int i = 0 ; i < n; i++) cin >> num[i];
    sort(num,num + n);
    for(int i = 0; i < n - 1; i++){
        if(num[i] == num[i + 1] || num[i + 1] > num[i] + 2){
            cout << "mistake"<< endl;
            return 0;
        }
    }

    int cnt = 0;
    for(int i = 0; i < n - 1; i++){
        if(num[i + 1] == num[i] + 2) cnt++;
    }
    if(cnt > 1){
        cout << "mistake"<< endl;
        return 0;
    }
    for(int i = 0; i < n - 1; i++){
        if(num[i + 1] == num[i] + 2){
            cout << num[i] + 1 << endl;
            return 0;
        }
    }
    if(num[0] == 1){
        cout << num[n-1] + 1 << endl;
    }else{
        cout << num[0] - 1 << " " << num[n-1] + 1 << endl;
    }
    return 0;
}

DNA合成

分析

暴力一遍,统计结果即可。

参考code

#include <bits/stdc++.h>

using namespace std;

int main(){
    string s1,s2;
    cin >> s1 >> s2;
    int ans = 0;
    for(int i = 0; i < s1.size(); i++){
        if(s1[i] == 'A' && s2[i] == 'T') ans++;
        if(s1[i] == 'T' && s2[i] == 'A') ans++;
        if(s1[i] == 'C' && s2[i] == 'G') ans++;
        if(s1[i] == 'G' && s2[i] == 'C') ans++;
    }
    cout << s1.size() - ans << endl;
    return 0;
}

超级素数幂

分析

暴力枚举幂q，然后n开q次幂之后check一下是否相等和p是否是素数。注意一下精度问题就好了

参考code

#include <bits/stdc++.h>

using namespace std;

long long n;
long long calc(long long m, int n){
    return n == 0 ? 1 : calc(m, n-1) * m;
}
bool check(long long n){
    long long tmp = sqrt(n);
    for(long long i = 2; i <= tmp; i++){
        if(n % i == 0) return false;
    }
    return true;
}
int main(){
    cin >> n;
    int flag = 1;
    for(int i = 2;;i++){
        double tmp = pow(n,1.0/i);
        if(tmp < 2.0) break;
        if(calc((long long)(tmp + 0.1),i) == n && check((long long)(tmp + 0.1))){
            flag = 0;
            cout << (int)(tmp + 0.1) <<" "<< i << endl;
        }
    }
    if(flag) cout << "No" << endl;
}

序列和

分析

我们要找连续的一段长度大于等于L小于等于100整数和等于N,容易观察到合法的长度范围很小,于是我们从L开始枚举,然后找到第一个输出即可。

参考code

#include <bits/stdc++.h>

using namespace std;

vector <int> sequence(int S, int L0) {
    vector<int> R;
    for(int L = L0; L <= 100; L++) {
        if (S - L * (L - 1) / 2 >= 0 && (S - L * (L - 1) / 2) % L == 0) {
            int A = (S - L * (L - 1) / 2) / L;
            for (int i = 0; i < L; i++) R.push_back(A + i);
            return R;
        }
    }
    return R;
}
int main() {
    int S,L;
    cin >> S >> L;
    vector<int> ans;
    ans = sequence(S, L);
    if(ans.size() == 0) cout << "No" << endl;
    else {
        for(int i = 0; i < ans.size(); i++) {
            i == 0 ? cout << ans[i] : cout << " " << ans[i];
        }
    }
    return 0;
}

页码统计

分析

一个很经典的问题。会的就直接数位dp好了。 不会的看看《编程之美》P132

参考code

#include <bits/stdc++.h>

using namespace std;

vector<int> solve(int n) {
    vector<int> res(10, 0);
    if(!n) return res;
    if(n % 10 < 9) {
        res = solve(n - 1);
        while(n) {
            res[n % 10]++;
            n /= 10;
        }
        return res;
    }
    res = solve(n / 10);
    for(int i = 0; i < 10; i++) res[i] = res[i] * 10 + n / 10 + (i > 0);
    return res;
}
int main() {
    int n;
    cin >> n;
    vector<int> ans = solve(n);
    for(int i = 0; i < ans.size(); i++) {
        i == 0 ? cout << ans[i] : cout << " " << ans[i];
    }
    return 0;
}

01翻转

分析

这个题应该有多种解法。第一眼看起来很BFS但是复杂度大概是O((A+B)*K),应该需要怎么优化才可以。

参考code

#include <bits/stdc++.h>

using namespace std;


int solve(long long a, long long sum, long long k) {
    long long mx = 0, rest, use;
    if(a == 0) return 0;
    for(int i = 1; i <= 210000; i++) {
        mx += k;

        if(mx < a) continue;
        rest = mx - a;
        use = (sum - a) * (i / 2);
        use += a * ((i - 1) / 2);
        use *= 2;
        if(rest % 2 == 0 && rest <= use) return i;
    }
    return -1;
}
int main() {
    int A , B , K;
    cin >> A >> B >> K;
    int ans = solve(A, A + B, K);
    cout << ans << endl;
}