首页 > 腾讯笔试部分ac代码
头像
关键句v
编辑于 2020-08-23 22:44
+ 关注

腾讯笔试部分ac代码

1. 第一题,比较简单
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

    int tmp;
    k -= 1;
    for (int i = 0; i < n; i++) {
        scanf("%d", &tmp);
        if (k != 0) {
            printf("%d ", tmp);
        }
        k--;
    }
}
2. 第二题,求字符串字串的字典序第k小,因为就五个,所以可以直接暴力

#include <bits/stdc++.h>
using namespace std;
int main(void)
{
    //freopen("data.txt", "r", stdin);
    char str[5000 + 10];
    scanf("%s", str);
    int k;
    scanf("%d", &k);
    map<string, int> ms;
    string s(str);
    for (int i = 1; i < 6; i++) {
        for (int j = 0; j < s.size() && j + i < s.size(); j++) {
            ms[s.substr(j, i)] = 1;
        }
    }
    for (auto it = ms.begin(); it != ms.end(); it++) {
        k--;
        if (k == 0) {
            cout << it->first << endl;
            return 0;
        }
    }
    return 0;
}

3 . 暴力a了40,用dfs写了一半没时间了

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int dfs(string str) {
    if (str.empty()) return 0;
    int tmp = 0;
    if (str.size() > 1) {
        if (str[0] != '9') {
            tmp += 10 + str[0] - '0';
            str[1] -= 1;   // 需要考虑1000的情况,
        }
        else {
            tmp += 9;
        }
        tmp += dfs(str.substr(1, str.size() - 1));
    }
    else {
        tmp += str[0] - '0';
    }
    return tmp;
}

int main() {
    int T;
    freopen("data.txt", "r", stdin);
    scanf("%d", &T);
    while (T--) {
        ll n;
        scanf("%lld", &n);
        string str = to_string(n);
        reverse(str.begin(),str.end());
        cout << dfs(str) << endl;
    }
    return 0;
}

4. 求最少粉刷次数,递归+分治,分治的思路,就是每次按照最小的位置进行切分,比如2 2 1 2 1可以分成 2 2 和 2

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
vector<vector<int>> dp;
int dfs(vector<ll> v, int s, int e) {
    if (s > e) return 0;
    if (dp[s][e]) return dp[s][e];
    ll min_v = LLONG_MAX;
    for (int i = s; i <= e; i++) {
        min_v = min(v[i], min_v);
    }
    int cnt = min_v;
    int pre_pos = s;
    for (int i = s; i <= e; i++) {
        v[i] -= min_v;
        if (v[i] == 0) {
            cnt += dfs(v, pre_pos, i-1);
            pre_pos = i + 1;
        }
        v[i] += min_v;
    }
    cnt += dfs(v,pre_pos, e);
    dp[s][e] = min(cnt,e-s+1);
    return dp[s][e];
}
int main() {
    int n;
    scanf("%d", &n);
    vector<ll> v(n);
    dp.resize(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        scanf("%lld", &v[i]);
    }
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }
    cout << dfs(v, 0, v.size() - 1) << endl;
    return 0;
}

5. 动态规划,dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j])

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

int check(string& str, int i, int j) {
    int p = j - i + 1;
    while (i < j) {
        if (str[i] != str[j]) {
            return p;
        }
        i++;
        j--;
    }
    return 1;
}
int main() {
    string str;
    cin >> str;
    vector<vector<int>> dp;
    dp.resize(str.size(), vector<int>(str.size()));
    for (int i = 0; i < str.size(); i++) {
        for (int j = 0; j < str.size(); j++) {
            dp[i][j] = check(str, i, j);
        }
    }
    // dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j])
    for (int i = 0; i < str.size(); i++) {
        for (int j = i + 1; j < str.size(); j++) {
            for (int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
            }
        }
    }
    int Q;
    scanf("%d", &Q);
    int l, r;
    while (Q--) {
        scanf("%d %d", &l, &r);
        printf("%d\n", dp[l - 1][r - 1]);
    }
    return 0;
}




全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐