8.23腾讯开发笔试

第二题

考虑到k就5，枚举长度<=10的全部子串（我枚举5wa掉了不知道为啥）

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
#define fir first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define ull unsigned long long
#define cl(a, b) memset(a, b, sizeof(a))
#define quickio(a) ios::sync_with_stdio(a)
#define datatest() freopen("data.in", "r", stdin)
#define makeans() freopen("data.out", "w", stdout)
#define makedata() freopen("data.in", "w", stdout)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
using namespace std;
const int maxn = 1e6 + 10;
const int maxm = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxblock = sqrt(maxn) + 10;
const double eps = 1e-7;
const ll INF = 1e16;
char str[maxn];
int k;

int main() {
  scanf("%s", str);
  scanf("%d", &k);
  vector<string> v;
  int n = strlen(str);
  for (int i = 0; i < n; i++) {
    string temp;
    for (int cnt = 0; cnt < 5; cnt++) {
      if (i + cnt >= n) break;
      temp.push_back(str[i + cnt]);
      v.push_back(temp);
    }
  }
  sort(v.begin(), v.end());
  auto it = unique(v.begin(), v.end());
  v.erase(it, v.end());
  for (int i = 0; i < v[k - 1].size(); i++) {
    printf("%c", v[k][i]);
  }
  printf("\n");
  return 0;
}

第三题

答案的一个数肯定是999999....，枚举一下就可以了

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
#define fir first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define ull unsigned long long
#define cl(a, b) memset(a, b, sizeof(a))
#define quickio(a) ios::sync_with_stdio(a)
#define datatest() freopen("data.in", "r", stdin)
#define makeans() freopen("data.out", "w", stdout)
#define makedata() freopen("data.in", "w", stdout)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
using namespace std;
const int maxn = 1e6 + 10;
const int maxm = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxblock = sqrt(maxn) + 10;
const double eps = 1e-7;
const ll INF = 1e16;
int sum(ll n) {
  ll res = 0;
  while (n) {
    res += n % 10;
    n /= 10;
  }
  return res;
}

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    ll n;
    scanf("%lld", &n);
    if (n < 9) {
      int Max = 0;
      for (int i = 0; i <= n; i++) {
        Max = max(Max, sum(i) + sum(n - i));
      }
      printf("%d\n", Max);
    } else {
      ll now = 0;
      int Max = 0;
      while (now <= n) {
        // cout << "now=" << now << endl;
        Max = max(Max, sum(now) + sum(n - now));
        now = now * 10 + 9;
      }
      printf("%d\n", Max);
    }
  }
  return 0;
}

第四题

考虑当前要刷的区间[l,r]，如果最小值MIn>最小值个数肯定一个一个刷

不是的话把最小值刷掉然后一个一个连续非0区间刷

最后过了95% 没想到写区间dp。。。。。。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
#define fir first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define ull unsigned long long
#define cl(a, b) memset(a, b, sizeof(a))
#define quickio(a) ios::sync_with_stdio(a)
#define datatest() freopen("data.in", "r", stdin)
#define makeans() freopen("data.out", "w", stdout)
#define makedata() freopen("data.in", "w", stdout)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
using namespace std;
const int maxn = 1e6 + 10;
const int maxm = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxblock = sqrt(maxn) + 10;
const double eps = 1e-7;
const ll INF = 1e16;

int n;
int a[maxn];
int res = 0;
void solve(int l, int r) {
  int Min = mod;
  for (int i = l; i <= r; i++) Min = min(Min, a[i]);
  int num = 0;
  for (int i = l; i <= r; i++) {
    if (a[i] == Min) num++;
  }
  if (num < Min) {
    res += r - l + 1;
  } else {
    for (int i = l; i <= r; i++) {
      a[i] -= Min;
    }
    res += Min;
    vector<int> v;
    for (int i = l; i <= r; i++) {
      if (a[i] == 0) {
        if (v.size() != 0) {
          solve(v[0], v[v.size() - 1]);
        }
        v.clear();
      } else {
        v.push_back(i);
      }
    }
    if (!v.empty()) {
      solve(v[0], v[v.size() - 1]);
    }
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  solve(1, n);
  printf("%d\n", res);
  return 0;
}

第五题

区间dp处理出每个区间是否为回文串在区间dp处理每个区间的答案就可以了

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
#define fir first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define ull unsigned long long
#define cl(a, b) memset(a, b, sizeof(a))
#define quickio(a) ios::sync_with_stdio(a)
#define datatest() freopen("data.in", "r", stdin)
#define makeans() freopen("data.out", "w", stdout)
#define makedata() freopen("data.in", "w", stdout)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
using namespace std;
const int maxn = 500 + 10;
const int maxm = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxblock = sqrt(maxn) + 10;
const double eps = 1e-7;
const ll INF = 1e16;
char str[maxn];
int dp[maxn][maxn];
int is[maxn][maxn];
int main() {
  scanf("%s", str + 1);
  int n = strlen(str + 1);
  for (int len = 1; len <= n; len++) {
    for (int l = 1; l + len - 1 <= n; l++) {
      int r = l + len - 1;
      if (len == 1)
        is[l][r] = 1;
      else if (len == 2) {
        if (str[l] == str[r]) is[l][r] = 1;
      } else {
        if (str[l] == str[r] && is[l + 1][r - 1]) is[l][r] = 1;
      }
    }
  }
  // cout << is[1][4] << endl;
  for (int len = 1; len <= n; len++) {
    for (int l = 1; l + len - 1 <= n; l++) {
      int r = l + len - 1;
      dp[l][r] = inf;
      if (is[l][r])
        dp[l][r] = 1;
      else {
        for (int k = l; k < r; k++) {
          dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 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;
}

#腾讯##笔试题目#