牛客网模拟笔试 2

https://www.nowcoder.com/discuss/22561

这是牛客网上的官方题解。

1.平衡树，显然小于10的数字不是平衡数，然后把数拆分成个位数，逐个判断是否满足要求。

/*
ID: y1197771
PROG: test
LANG: C++
*/
#include<bits/stdc++.h>
#define pb push_back
#define FOR(i, n) for (int i = 0; i < (int)n; ++i)
#define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
typedef long long ll;
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e3 + 10;
int a[20];
void yes() {
    cout << "YES" << endl;
}
void no() {
    cout << "NO" << endl;
}
void solve() {
    ll x;
    while(cin >> x){
            //cout << "asd " << x << endl;
         int p = 0;
        if(x < 10) {
            no();
            continue;
        }
        while(x > 0) {
            a[p++] = x % 10;
            x /= 10;
        }
        bool f = 0;
        for (int i = 0; i < p - 1; i++) {
            int left = 1, right = 1;
            for (int j = 0; j <= i; j++)
                left *= a[j];
            for (int j = i + 1; j < p; j++)
                right *= a[j];
            if(left == right) {
                yes();
                f = 1;
                break;
            }
            if(f) break;
        }
        if(f) continue;
        no();
    }
}
int main() {
    freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    //ios::sync_with_stdio(0);
    //cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

2. 字符串分类

直接排序，放入set，最后输出个数即可。

/*
ID: y1197771
PROG: test
LANG: C++
*/
#include<bits/stdc++.h>
#define pb push_back
#define FOR(i, n) for (int i = 0; i < (int)n; ++i)
#define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
typedef long long ll;
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e3 + 10;
int n;
set<string> ma;
void solve() {
    string s;
    cin >> n;
    while(n--) {
        cin >> s;
        sort(s.begin(), s.end());
        //cout << s << endl;
        ma.insert(s);
    }
    cout << ma.size() << endl;
}
int main() {
    freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    //ios::sync_with_stdio(0);
    //cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

3. 创造新世界

01串，最多构成多少物品，leetcode原题，dp，01背包，代价为01的个数，价值为物品的个数。dp还是很明显的。

/*
ID: y1197771
PROG: test
LANG: C++
*/
#include<bits/stdc++.h>
#define pb push_back
#define FOR(i, n) for (int i = 0; i < (int)n; ++i)
#define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
typedef long long ll;
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e3 + 10;
int dp[510][510];
int n, m;
int sz;
int a[30], b[30];
void solve() {
    cin >> sz >> n >> m;
    string s;
    int x, y;
    for (int i = 0; i < sz; i++) {
        cin >> s;
        x = y = 0;
        for (char t : s) {
            if(t == '0') x++;
            else y++;
        }
        a[i] = x; b[i] = y;
    }
    for (int k = 1; k <= sz; k++) {
        for (int i = n; i >= a[k - 1]; i--) {
            for (int j = m; j >= b[k - 1]; j--) {
                dp[i][j] = max(dp[i][j], dp[i - a[k - 1] ][j - b[k - 1] ] + 1);
            }
        }
    }
    cout << dp[n][m] << endl;
}
int main() {
    freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    //ios::sync_with_stdio(0);
    //cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

4.优美的回文串

牛牛在书上看到一种字符串叫做回文串,当一个字符串从左到右和从右到左读都是一样的,就称这个字符串为回文串。牛牛又从好朋友羊羊那里了解到一种被称为优美的回文串的字符串,考虑一个长度为N只包含大写字母的字符串,写出它所有长度为M的连续子串(包含所有可能的起始位置的子串,相同的子串也要计入),如果这个字符串至少有K个子串都是回文串,我们就叫这个字符串为优美的回文串。现在给出一个N,牛牛希望你能帮他计算出长度为N的字符串有多少个是优美的回文串(每个位置都可以是'A'~'Z'的一个。) 

这个题目还是比较变态的，根本没思路。没有好办法。答案是枚举+check。

好题，多看几遍，学习解决办法。

每个位置有26种方法，还要满足回文串的个数是k，怎么枚举都不行，那就是枚举所有的进行check，但是这个枚举数字实在是太大了，无法进了。

看题解，真是巧妙的方法，长度为a，至多使用a个字符，然后check生成的字符是否是满足优美的条件，然后采用排列组合的知识进行计算。这个实在是想不出来。

/*
ID: y1197771
PROG: test
LANG: C++
*/
#include<bits/stdc++.h>
#define pb push_back
#define FOR(i, n) for (int i = 0; i < (int)n; ++i)
#define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
typedef long long ll;
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e3 + 10;
int n, m, k;
ll a[15];
ll res;
char ch[20];
void work(int cur, int p) {
    //cout << cur << " " << p << endl;
    if(cur == 0) {
        int t = 0;
        for (int i = 1; i <= n - m + 1; i++) {
            bool f = 1;
            for (int j = 0; j < m / 2; j++) {
                if(ch[i + j] != ch[i + m - 1 - j]) {
                    f = 0; break;
                }
            }
            t += f;
        }
        //cout << t << " asd " << endl;
        if(t >= k)
            res += a[p];
        return;
    }
    for (int i = 0; i < p + 1; i++) {
        ch[cur] = 'a' + i;
        work(cur - 1, max(p, i + 1));
    }
}
void solve() {
    a[0] = 0; a[1] = 26;
    for (int i = 2; i < 15; i++) {
        a[i] = a[i - 1] * (26 - i + 1);
    }
    cin >> n >> m >> k;
    work(n, 0);
    cout << res << endl;
}
int main() {
    freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

其他的二模题目没有看，有时间做一下。

下面是一模的题目。好像之前总结过了，这里就不写了。好像也有一模的所有题目总结，也是没做完，有时间做完总结一下。