首页 > 2020.08.23 腾讯研发岗笔试A~E题解
头像
业余选手キライ!
编辑于 2020-08-23 22:49
+ 关注

2020.08.23 腾讯研发岗笔试A~E题解

误操作删帖了,惨。

1. 白给
#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;
using LL = long long;

const int maxn = 1001000;
int n, k, val;

signed main() {
  // freopen("in", "r", stdin);
  // freopen("out", "w", stdout);
  while (~scanf("%d%d",&n,&k)) {
    int x;
    for (int i = 1; i <= n; i++) {
      scanf("%d", &x);
      if (i == k) continue;
      printf("%d ", x);
    }
    printf("\n");
  }
  return 0;
}

2. top k的k小于等于5,所以需要维护一个数据结构保留字典序最小的5个,但是要考虑去重。n^2logn惨遭卡常,于是我把内层的循环砍掉一半竟然hack过去了。。。
#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;
using LL = long long;

const int maxn = 5050;
char s[maxn];
int n, k;
vector<int> pos[257];

signed main() {
  // freopen("in", "r", stdin);
  // freopen("out", "w", stdout);
  while (~scanf("%s", s + 1)) {
    scanf("%d", &k);
    n = strlen(s + 1);
    set<string> vis;
    for (int i = 1; i <= n; i++) {
      string tmp;
      for (int j = i; j <= min(n, 2500); j++) {
        tmp += s[j];
        if (vis.find(tmp) != vis.end()) continue;
        vis.emplace(tmp);
        if (vis.size() > k) vis.erase(*vis.rbegin());
      }
    }
    printf("%s\n", vis.rbegin()->c_str());
  }
  return 0;
}

3. 贪心,令一个数的形式为999...999,另一个数就无所谓了,不过不会证明。
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

LL n;

LL gao(LL x) {
  LL ret = 0;
  while (x) {
    ret += x % 10;
    x /= 10;
  }
  return ret;
}

signed main() {
  // freopen("in", "r", stdin);
  // freopen("out", "w", stdout);
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%lld", &n);
    LL a = 0;
    while (a <= n) {
      a = a * 10 + 9;
    }
    a /= 10;
    printf("%lld\n", gao(a) + gao(n - a));
  }
  return 0;
}

4. 一开始想区间dp,维护f(l,r)为粉刷区间[l,r]内的最少步数,转移的时候直接考虑每一个都竖着刷(r-l+1次)以及横着刷min{a[k]}次,发现是n^3,其实每次如果横着刷这个区间肯定都被刷完了,所以直接刷掉就行,于是这个问题就不用区间dp了。
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int maxn = 5050;
int n;
int a[maxn];
int f[maxn][maxn];

int dfs(int l, int r) {
  if (l > r) return 0;
  if (~f[l][r]) return f[l][r];
  int k = l;
  for (int i = l + 1; i <= r; i++) {
    if (a[i] < a[k]) k = i;
  }
  int ret = a[k];
  for (int i = l; i <= r; i++) {
    a[i] -= ret;
  }
  return f[l][r] = min(r - l + 1, dfs(l, k - 1) + dfs(k + 1, r) + ret);
}

signed main() {
  // freopen("in", "r", stdin);
  // freopen("out", "w", stdout);
  while (~scanf("%d", &n)) {
    for (int i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
    }
    memset(f, -1, sizeof f);
    printf("%d\n", dfs(1, n));
  }
  return 0;
}

5. 维护f(l,r)表示字符串从l起始,并且长度为r时所能构成的最少回文串数,每次枚举l,在以l为起点的后缀串做DP,当[i,j]为一个回文串时更新f[i] = min(f[i], f[j - 1] + 1). 判字符串回文可以用字符串哈希,也可以马拉车。整体复杂度为n^3
#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;
using LL = long long;
using ULL = unsigned long long;

const ULL M = 1145141919810;
const int maxn = 440;
int n, q;
string s;
vector<vector<int>> f;

void gao(const string& s, vector<int>& f) {
  int n = s.length();
  for (int i = 0; i <= n; i++) {
    f[i] = i;
  }
  vector<ULL> h1(n + 1, 0), h2(n + 1, 0), mul(n + 1, 0);
  mul[0] = 1, mul[1] = M;
  for (int i = 2; i <= n; i++) {
    mul[i] = mul[i - 1] * M;
  }
  for (int i = 0; i < n; i++) {
    h1[i + 1] = h1[i] * M + s[i] - 'a';
    h2[i + 1] = h2[i] * M + s[n - i - 1] - 'a';
  }

  auto ok = [&](int i, int j) {
    int len = j - i + 1;
    ULL a = h1[j + 1] - h1[i] * mul[len];
    ULL b = h2[n - i] - h2[n - j - 1] * mul[len];
    return a == b;
  };

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
      if (ok(j - 1, i - 1)) {
        f[i] = min(f[i], f[j - 1] + 1);
      }
    }
  }
}

signed main() {
  // freopen("in", "r", stdin);
  // freopen("out", "w", stdout);
  while (cin >> s) {
    n = s.length();
    for (int i = 0; i <= n; i++) {
      f.emplace_back(vector<int>(n + 1, 1E6));
    }
    for (int k = 1; k <= n; k++) {
      string t;
      for (int i = k; i <= n; i++) {
        t += s[i - 1];
      }
      gao(t, f[k]);
    }
    scanf("%d", &q);
    while (q--) {
      int l, r;
      scanf("%d %d", &l, &r);
      printf("%d\n", f[l][r - l + 1]);
    }
  }
  return 0;
}


全部评论

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

推荐话题

相关热帖

近期热帖

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

近期精华帖

热门推荐