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

第二场编程题合集：https://www.nowcoder.com/test/4546329/summary

最长公共子串

分析

注意跟最长公共子序列的区别,还有空格也作为字符在匹配就好了,经典题。

参考code

#include <bits/stdc++.h>

using namespace std;

char s1[55], s2[55];
int main() {  
    gets(s1);
    gets(s2);
    int ans = 0, k;
    for(int i = 0; i < strlen(s1); ++i) { 
        for(int j = 0; j < strlen(s2); ++j) {  
            for(k = 0; s1[i + k] && s2[j + k] && s1[i + k] == s2[j + k]; k++);
            if(k > ans) ans = k; 
        }  
    }
    cout << ans << endl;
    return 0;  
}

找整除

分析

裸暴力不能通过所有数据。所以调整a到一个可以被c整除的位置,然后以c为步长计算就好了。。

参考code

#include <bits/stdc++.h>

using namespace std;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    while(a % c != 0) a++;
    if(a > b)    
        cout << 0 << endl;
    else
        cout << (b - a) / c + 1 << endl;
    return 0;
}

组装三角形

分析

暴力枚举三边,然后check一下就好了。

参考code

#include <bits/stdc++.h>

using namespace std;

int v[55];
int check(int a, int b, int c) {
    return a < b + c && b < a + c && c < a + b;
}
int main() {
    int n, ans = 0;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> v[i];
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            for(int k = j + 1; k < n; k++) {
                if(check(v[i], v[j], v[k])) ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

最小矩阵

分析

维护X,Y坐标最大最小坐标,然后计算一发就好了。

参考code

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    int minx = 10000, maxx = -100000, miny = 100000, maxy = -100000;
    for(int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        minx = min(minx,x);
        maxx = max(maxx,x);
        miny = min(miny,y);
        maxy = max(maxy,y);
    }
    cout << (maxx - minx) * (maxy - miny) << endl;
    return 0;
}

平衡数

分析

枚举断点暴力check一下就好。

参考code

#include <bits/stdc++.h>

using namespace std;

string solve(int number) {
    ostringstream oss;
    oss << number;
    string s = oss.str();
    int n = s.length();
    long long n1, n2;
    for(int i = 1; i < n; i++) {
        n1 = n2 = 1;
        for(int j = 0; j < i; j++)
            n1 *= s[j] - '0';
        for(int j = i; j < n; j++)
            n2 *= s[j] - '0';
        if(n1 == n2)
            return "YES";
    }
    return "NO";
}
int main() {
    int x;
    cin >> x;
    cout << solve(x) << endl;
    return 0;
}

字符串分类

分析

我们可以容易的观察到,两个字符串是同一类当且仅当构成他们的字符集合相同且个数也相同。于是对于每个字符串进行排序,最后再对整个字符串数组排序一下,扫一遍计算个数就好。

参考code

#include <bits/stdc++.h>

using namespace std;

vector<string> v;
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        string x;
        cin >> x;
        sort(x.begin(), x.end());
        v.push_back(x);
    }
    sort(v.begin(), v.end());
    int ans = 0;
    string tmp("");
    for(int i = 0; i < v.size(); i++) {
        if(tmp != v[i]) tmp = v[i], ans++;
    }
    cout << ans << endl;
}

创造新世界

分析

这道题很容易想到使用贪心。。然而。。 一种比较容易想到的贪心是尽量去满足更短的字符串。但是我们考虑2个0和5个1,要组成的字符串是{00, 011, 0111}.这样贪心的答案是1,其实我们可以组成2个。 另外一种贪心是尽量使用更多的1或者0.考虑我们当前有5个0和4个1,组成的字符串是{100000, 110, 110},这样又是不行的。。 这道题的正解是动态规划,首先预处理出需要组成的每个字符串需要0和1的个数,然后dp[i][j]表示使用i个0和j个1能组成的个数,然后对于枚举每个字符串做个转移就行。。详情看代码。 时间复杂度 O(MAX_STRINGS MAX_ZEROES MAX_ONES)

参考code

#include <bits/stdc++.h>

using namespace std;

const int maxn = 500;

vector <string> *l;

int m, n, x;
int solve(int i, int numZeroes, int numOnes) {
    vector<string> &list = *l;
    if(i == list.size()-1) {
        for(int x = 0; x < list[i].size(); ++x) {
            if(list[i][x] == '1') --numOnes;
            if(list[i][x] == '0') --numZeroes;
        }
        if((numOnes | numZeroes) >= 0) return 1; 
        else return 0;
    }
    int a = solve(i+1, numZeroes, numOnes);
    for(int x = 0; x < list[i].size(); ++x) {
            if(list[i][x] == '1') --numOnes;
            if(list[i][x] == '0') --numZeroes;
    }
    if((numOnes | numZeroes) < 0) return a;
    int b = 1 + solve(i+1, numZeroes, numOnes);
    return max(a, b);
}
int main() {
    vector<string> v;
    cin >> x >> n >> m;
    for(int i = 0; i < x; i++) {
        string tmp; cin >> tmp;
        v.push_back(tmp);
    }
    l = &v;
    cout << solve(0, n, m) << endl;
    return 0;
}

优美的回文串

分析

对于一个字符串,我们依次替换掉字符是不影响最后结果的统计的。。 比如AJNFHALJJFJ,我们可以依次替换为a, b, c, d, e 和 f变为abcdeafbbdb,于是我们现在就挨着去生成长度为n的这样的字符串,然后暴力统计出满足条件的个数。最后计算上每个的贡献就行了。。 考虑abcdeafbbdb,第一个a可以换为26个字符的任意一个,b可以换为25个中的一个...... 所以对于一个有k种字符的字符串贡献就是26 × 25 × ... × (26-k+1)。计算出答案即可

参考code

#include <iostream>
#include <algorithm>

using namespace std;

long long cnt[12];
long long res = 0;
int M, K, N;
char s[12];
void solve(int k, int p) {
    if(k == 0) {
        int tmp = 0;
        for(int i = 0; i < N - M + 1; i++) {
            bool ok = true;
            for(int j = 0; j < M / 2; j++) {
                if(s[i + j] != s[i + M - 1 - j]) {
                    ok = false;
                    break;
                }
            }
            if(ok) tmp++;
        }
        if(tmp >= K) {
            res += cnt[p];
        }
        return ;
    }
    for(int i = 0; i < p + 1; i++) {
        s[k - 1] = 'a' + i;
        solve(k - 1, max(p, i + 1));
    }
}
int main() {
    cin >> N >> M >> K;
    cnt[0] = 0; cnt[1] = 26;
    for(int i = 2; i <= N; i++) {
        cnt[i] = cnt[i - 1] * (26 - i + 1);
    }
    solve(N, 0);
    cout << res << endl;
}