第二题
考虑到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;
} 
全部评论
(2) 回帖