2020.08.23腾讯秋招第一场笔试（2h 5题）
第一题：打印链表，有一个元素删除了。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define ios ios::sync_with_stdio(false),cin.tie(0);
template <typename T>
inline void read(T &x) {char ch=getchar(); int f=1; x=0; while(!isdigit(ch)){if(ch=='-')f *= -1; ch=getchar();} while(isdigit(ch)) {x = (x<<1) + (x<<3) + (ch^48); ch=getchar();} x*=f;}
ll qpow(ll x, ll y) { ll a=1, b=x; while(y){if(y&0x1) a*=b; b*=b; y>>=1;} return a;}
const int maxn = 1000005;
int a[maxn];
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("a.txt", "r", stdin);
#endif
int n, k;
while(cin >> n >> k) {
for(int i = 1; i <= n; ++i) cin >> a[i];
for(int i = k+1; i <= n; ++i) a[i-1] = a[i];
n--;
for(int i = 1; i <= n; ++i) {
if(i == 1) cout << a[i];
else cout << " " << a[i];
}
cout << endl;
}
return 0;
}
第二题：找到第k小的子符串，1 <= k <= 5, 理论上最长只需要5个字符的长度就好了。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define ios ios::sync_with_stdio(false),cin.tie(0);
template <typename T>
inline void read(T &x) {char ch=getchar(); int f=1; x=0; while(!isdigit(ch)){if(ch=='-')f *= -1; ch=getchar();} while(isdigit(ch)) {x = (x<<1) + (x<<3) + (ch^48); ch=getchar();} x*=f;}
ll qpow(ll x, ll y) { ll a=1, b=x; while(y){if(y&0x1) a*=b; b*=b; y>>=1;} return a;}
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("b.txt", "r", stdin);
#endif
int k;
string s;
while(cin >> s >> k) {
set<string> heap;
int n = s.size();
for(int len = 1; len <= min(n, k); ++len) {
for(int i = 0; i+len <= n; ++i) {
heap.insert(s.substr(i, len));
if(heap.size() > k) heap.erase(next(heap.begin(), k));
}
}
cout << *heap.rbegin() << endl;
}
return 0;
} 第三题：数字被拆解后，能构成的最大的数位值是多少？例子：35，最大被拆为16 + 19： 1 + 6 + 1 + 9 = 17,17就是最大值
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define ios ios::sync_with_stdio(false),cin.tie(0);
template <typename T>
inline void read(T &x) {char ch=getchar(); int f=1; x=0; while(!isdigit(ch)){if(ch=='-')f *= -1; ch=getchar();} while(isdigit(ch)) {x = (x<<1) + (x<<3) + (ch^48); ch=getchar();} x*=f;}
ll qpow(ll x, ll y) { ll a=1, b=x; while(y){if(y&0x1) a*=b; b*=b; y>>=1;} return a;}
int getVal(int x) {
int s = 0;
while(x > 0) {
s += x%10;
x /= 10;
}
return s;
}
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("c.txt", "r", stdin);
#endif
int t, n;
cin >> t;
while(t--) {
cin >> n;
if(n == 1) {cout << 1 << endl; continue;}
int x = 0;
while(x <= n) x = x*10 + 9;
x /= 10;
cout << getVal(x) + getVal(n - x) << endl;
}
return 0;
} 第四题：用刷子刷板子，每个板子高度不一样，可以横刷或者竖着刷，算一次，最少刷几次？
代码：
第五题：给一个字符串，并且给出一个区间[l, r]，问该区间进行拆分成所有的子串都是回文的最少数量是多少？
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define ios ios::sync_with_stdio(false),cin.tie(0);
template <typename T>
inline void read(T &x) {char ch=getchar(); int f=1; x=0; while(!isdigit(ch)){if(ch=='-')f *= -1; ch=getchar();} while(isdigit(ch)) {x = (x<<1) + (x<<3) + (ch^48); ch=getchar();} x*=f;}
ll qpow(ll x, ll y) { ll a=1, b=x; while(y){if(y&0x1) a*=b; b*=b; y>>=1;} return a;}
const int maxn = 500;
bool f[maxn][maxn];
int dp[maxn][maxn];
int dfs(int l, int r) {
if(l == r || f[l][r]) return 1;
if(dp[l][r]) return dp[l][r];
int t = maxn;
for(int i = l; i < r; ++i) {
t = min(t, dfs(l, i) + dfs(i+1, r));
}
return dp[l][r] = t;
}
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("e.txt", "r", stdin);
#endif
int n;
string s;
while(cin >> s) {
memset(f, 0, sizeof(f));
memset(dp, 0, sizeof(dp));
int n = s.size();
for(int i = n-1; i >= 0; --i) {
f[i][i] = true;
for(int j = i+1; j < n; ++j) {
if(s[i] == s[j] && (j-i == 1 || f[i+1][j-1])) {
f[i][j] = true;
}
}
}
int q;
cin >> q;
while(q--) {
int l, r;
cin >> l >> r;
l--;
r--;
if(f[l][r]) {
cout << 1 << endl;
continue;
}
int ans = r - l + 1;
cout << dfs(l, r) << endl;
}
}
return 0;
}
