8.23腾讯后台&综合开发笔试题解

Problem A

题意

给一个长度为n的链表，挖掉第k个元素，问挖掉元素后的序列。

做法

其实可以拿个数组存，下标为k不输出就可以了，代码也很短。

AC代码

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

const int N = 1e6 + 7;
int a[N];
int main() {
    int n, m; scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++)if(i != m)printf("%d ", a[i]);
    return 0;
}

Problem B

题意

给一个长度为n（n在5000内）的字符串，问字典序第k（k在5以内）小的子串是什么。

做法

k长度只有5，那答案的长度也不会超过5，只要把长度为5以内的所有子串抠出来排个序就可以了，AC代码中开了个set。

AC代码

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

int main() {
    set<string> s;
    string str;
    cin >> str;
    int n = str.length();
    for(int i = 0; i < n; i++) {
        string tmp;
        for(int j = 0; j < 5; j++)if(i + j < n) {
            tmp += str[i + j];
            s.insert(tmp);
        }
    }
    set<string>::iterator it = s.begin();
    int k; cin >> k;
    while(--k)it++;
    cout << *it << endl;
    return 0;
}

Problem C

题意

给一个数n，把它拆成a+b=n，要求a和b的数位和最大，求这个数位和。

做法

可以很容易想到一种贪心的方法，假设n是个x位数，那么我们可以让a为x-1个9组成的数，b为n-a。这个也比较容易想到以及证明。

AC代码

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

ll solve(ll n) {
    ll sum = 0;
    while(n) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
int main() {
    int T; scanf("%d", &T); while(T--) {
        ll n; scanf("%lld", &n);
        ll a = 0;
        while(a <= n)a = a * 10 + 9;
        a /= 10;
        cout << solve(a) + solve(n - a) << endl;
    }
    return 0;
}

Problem D

题意

有n（n在5000内）块木板，宽度是1，长度不固定，这些小木板拼接起来一块大木板。

给一个宽度为1的刷子，每刷一次可以选择横着刷和竖着刷，过程中都不能离开木板。

问最少要刷几次能把木板完全刷一遍。

做法

动态规划题，表示当前完全刷完了前块木板，横着刷的部分能延伸到之后木板的部分高度为的最小代价，显然不会超过，因为所有木板竖着刷答案就是了，不存在横着刷高度超过的情况。

我们枚举所有的状态，转移情况如下：

1. 竖着刷

   此时代价是1，能延伸的部分是和当前木板高度取最小值。

2. 横着刷

   如果当前木板高度小于，则没有代价，否则要补上他们之间的差值，能延伸的部分是当前木板的高度。

AC代码

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

const int N = 5e3 + 7;
int dp[N][N];
int a[N];
int main() {
    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = 0;
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; i++)scanf("%d", &a[i]);
    for(int i = 0; i < n; i++)for(int j = 0; j <= n; j++) {
        int high;
        //竖着刷
        high = min(j, a[i + 1]);
        dp[i + 1][high] = min(dp[i + 1][high], dp[i][j] + 1);
        //横着刷
        if(a[i + 1] < n) {
            if(j >= a[i + 1])dp[i + 1][a[i + 1]] = min(dp[i + 1][a[i + 1]], dp[i][j]);
            else dp[i + 1][a[i + 1]] = min(dp[i + 1][a[i + 1]], dp[i][j] + a[i + 1] - j);
        }
    }
    int ans = n;
    for(int i = 0; i <= n; i++)ans = min(dp[n][i], ans);
    printf("%d\n", ans);
    return 0;
}

Problem E

题意

给定一个字符串，再给出若干个询问，问对应的子串最少可以由多少个回文串拼接而成。

做法

动态规划题再放送，表示区间的子串最少可以由多少个回文串拼接而成。

那么如果区间本身是回文串，就是1，否则我们枚举分割点x，计算 + ，在其中取一个最小，这是个经典区间dp的题目，转移先枚举区间长度（很显然转移方向是区间短的往区间长的转移），再枚举左端点，再枚举分割点。

最后对于所有的询问，直接访问dp数组下标输出即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 400 + 7;
char str[N];
int dp[N][N];
int main() {
    memset(dp, 0x3f, sizeof dp);
    scanf("%s", str + 1);
    int n = strlen(str + 1);
    for(int i = 1; i <= n; i++) {
        int l = i, r = i;
        while(1) {
            dp[l][r] = 1;
            l--, r++;
            if(l <= 0 || r > n)break;
            if(str[l] != str[r])break;
        }
    }
    for(int i = 1; i < n; i++) {
        int l = i, r = i + 1;
        if(str[l] != str[r])continue;
        while(1) {
            dp[l][r] = 1;
            l--, r++;
            if(l <= 0 || r > n)break;
            if(str[l] != str[r])break;
        }
    }
    for(int len = 1; len < n; len++)for(int i = 1; i <= n - len; i++) {
        int l = i, r = i + len; 
        for(int j = l; j < r; j++)dp[l][r] = min(dp[l][r], dp[l][j] + dp[j + 1][r]);
    }
    int q; scanf("%d", &q); while(q--) {
        int l, r; scanf("%d%d", &l, &r);
        printf("%d\n", dp[l][r]);
    }
    return 0;
}