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;
}
