因为cf上一堆水题，每个单独开一篇博客感觉不太好，就直接放一起好了。
CF1096D Easy Problem
给定字符串，每个位置删除要代价。求最小代价使之不含子序列"hard"。
设f[i][f]表示前i个删到只匹配f位子序列的最小代价。转移看代码吧。O(n)
#include <bits/stdc++.h> typedef long long LL;
const int N = ; int a[N];
LL f[N][];
char str[N]; int main() {
int n;
scanf("%d", &n);
scanf("%s", str + );
for(int i = ; i <= n; i++) scanf("%d", &a[i]); int tag = ;
for(int i = ; i <= n; i++) {
if(tag == && str[i] == 'h') tag++;
if(tag == && str[i] == 'a') tag++;
if(tag == && str[i] == 'r') tag++;
if(tag == && str[i] == 'd') tag++;
}
if(tag != ) {
printf("0\n");
return ;
} for(int i = ; i <= n; i++) {
f[i][] = f[i - ][] + a[i] * (str[i] == 'h');
f[i][] = f[i - ][] + a[i] * (str[i] == 'a');
f[i][] = f[i - ][] + a[i] * (str[i] == 'r');
f[i][] = f[i - ][] + a[i] * (str[i] == 'd');
if(str[i] == 'h') f[i][] = std::min(f[i][], f[i - ][]);
if(str[i] == 'a') f[i][] = std::min(f[i][], f[i - ][]);
if(str[i] == 'r') f[i][] = std::min(f[i][], f[i - ][]);
} LL ans = std::min(std::min(f[n][], f[n][]), std::min(f[n][], f[n][])); printf("%lld\n", ans);
return ;
}
AC代码
CF1036C Classy Numbers
问[l, r]之间有多少个数满足非0数码不超过三个。
裸数位DP......注意每次读完要把char数组清空...
/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/ #include <bits/stdc++.h> typedef long long LL;
const int N = ; LL f[N][][];
char str[N], str1[N], str2[N]; LL DFS(int k, int cnt, int z) {
if(cnt > ) return ;
if(!k) {
return ;
}
if(f[k][cnt][z] != -) {
return f[k][cnt][z];
}
LL ans = ;
if(cnt < ) {
for(int i = ; i <= ; i++) {
ans += DFS(k - , cnt + , );
}
}
ans += DFS(k - , cnt, z);
return f[k][cnt][z] = ans;
} LL DFS_2(int k, int cnt, int z) {
if(cnt > ) return ;
if(!k) return ;
int lm = str[k] - '';
//printf("k = %d cnt = %d z = %d lm = %d \n", k, cnt, z, lm);
LL ans = DFS_2(k - , cnt + (lm != ), z | (lm != ));
if(lm) {
ans += DFS(k - , cnt, z);
}
for(int i = ; i < lm; i++) {
ans += DFS(k - , cnt + , );
}
return ans;
}
/*
1
29000000000091 29000000000099 */
inline void dec(int &n) {
for(int i = ; i <= n; i++) {
if(str[i] != '') {
str[i]--;
break;
}
else str[i] = '';
}
if(str[n] == '') n--;
return;
} int main() {
memset(f, -, sizeof(f));
LL l, r;
int T;
scanf("%d", &T);
for(int i = ; i <= T; i++) {
scanf("%s%s", str1 + , str2 + );
int n = strlen(str2 + );
memcpy(str + , str2 + , sizeof(char) * n);
std::reverse(str + , str + n + ); /*for(int j = 1; j <= n; j++) {
putchar(str[j]);
}
puts("");*/ LL ans = DFS_2(n, , );
//printf("temp ans = %lld \n", ans);
memset(str2 + , , n * sizeof(char));
n = strlen(str1 + );
memcpy(str + , str1 + , n * sizeof(char));
std::reverse(str + , str + n + );
dec(n); /*for(int j = 1; j <= n; j++) {
putchar(str[j]);
}
puts("");*/ ans -= DFS_2(n, , );
printf("%lld\n", ans);
memset(str1 + , , n * sizeof(char));
} return ;
}
AC代码
CF1132C Painting the Fence
给定n个区间，选出n - 2个区间使它们覆盖的总长度最大。转为删去两个区间。
去重 + 排序。考虑到答案要么相邻要么不相邻，相邻的预处理前后缀覆盖总长之后直接枚举。
预处理出只删每个区间的时候的覆盖减少量为di。当不相邻的时候，考虑到减少总量就是他们两个的di之和。
于是枚举一个区间，拿一个数据结构维护[1, i - 2]之间的最小d值即可。
注意答案不能比总长度还优。复杂度O(nlogn) / O(n)
/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/ #include <bits/stdc++.h> const int N = ; struct Node {
int l, r;
inline bool operator < (const Node &w) const {
if(l != w.l) return l < w.l;
return r > w.r;
}
}node[N], stk[N]; int top; int n, m, sl[N], sr[N], del[N], pw[N], ST[N][]; namespace t1 {
int d[N];
inline void solve() {
for(int i = ; i <= n; i++) {
d[node[i].l]++;
d[node[i].r + ]--;
}
int ans = , now = ;
for(int i = ; i <= m; i++) {
now += d[i];
ans += (now > );
}
printf("%d\n", ans);
return;
}
} namespace t2 {
inline void solve() {
int ans = ;
for(int i = ; i <= n; i++) {
ans = std::max(ans, std::min(sl[i - ] + sr[i + ], sr[]));
}
printf("%d\n", ans);
return;
}
} inline void prework() {
for(int i = ; i <= n; i++) { /// get sl del
sl[i] = sl[i - ] + node[i].r - std::max(node[i].l, node[i - ].r + ) + ;
del[i] = std::min(node[i].r, node[i + ].l - ) - std::max(node[i].l, node[i - ].r + ) + ;
del[i] = std::max(del[i], );
}
for(int i = n; i >= ; i--) { /// get sr
sr[i] = sr[i + ] + std::min(node[i].r, node[i + ].l - ) - node[i].l + ;
}
return;
} inline void prework2() {
for(int i = ; i <= n; i++) {
pw[i] = pw[i >> ] + ;
}
for(int i = ; i <= n; i++) ST[i][] = del[i];
for(int j = ; j <= pw[n]; j++) {
for(int i = ; i + ( << j) - <= n; i++) {
ST[i][j] = std::min(ST[i][j - ], ST[i + ( << (j - ))][j - ]);
}
}
return;
} inline int getMin(int l, int r) {
if(l > r) return 0x3f3f3f3f;
int t = pw[r - l + ];
return std::min(ST[l][t], ST[r - ( << t) + ][t]);
} int main() {
scanf("%d%d", &m, &n);
for(int i = ; i <= n; i++) {
scanf("%d%d", &node[i].l, &node[i].r);
} std::sort(node + , node + n + );
int k = ;
for(int i = ; i <= n; i++) {
if(top && stk[top].r >= node[i].r) {
k--;
continue;
}
stk[++top] = node[i];
}
n = top;
memcpy(node + , stk + , n * sizeof(Node)); if(k <= ) {
t1::solve();
return ;
}
node[n + ].l = node[n + ].r = 0x3f3f3f3f;
prework(); if(k == ) {
t2::solve();
return ;
} /// solve int ans = ;
for(int i = ; i < n; i++) { /// choose i i + 1
ans = std::max(ans, std::min(sl[i - ] + sr[i + ], sr[]));
}
/// not neighbor prework2(); for(int i = ; i <= n; i++) {
ans = std::max(ans, sr[] - del[i] - getMin(, i - ));
}
printf("%d\n", ans);
return ;
}
AC代码
CF1132F Clear the String
给定字符串，一次可以删去连续的一段相同字符，问最少多少次删光。
有一个很直观的想法是f[l][r][k]表示把[l, r]删成k个str[l]的最小代价，发现不好O(1)转移...
然后又考虑f[l][r][k]表示[l, r]右端加上k个str[r]之后删去的最小代价，也不会转移...
尝试n2状态，发现这个k，完全没必要记具体个数，因为无论多少个都是一次删掉。
于是采用CF1025D的套路，fa[l][r]表示把[l, r]删成只剩str[l - 1]的最小代价，fb是str[r + 1]，ans是删光的最小代价。
转移fa的时候考虑str[r]和str[l - 1]是否相同并以此转移。转移ans的时候选出一个位置，左边的fb + 右边的fa转移。
#include <bits/stdc++.h> const int N = ; int fa[N][N], fb[N][N], ans[N][N];
char str[N]; inline void exmin(int &a, const int &b) {
if(a > b) a = b;
return;
} int main() {
memset(fa, 0x3f, sizeof(fa));
memset(fb, 0x3f, sizeof(fb));
memset(ans, 0x3f, sizeof(ans));
int n;
scanf("%d", &n);
scanf("%s", str + );
for(int i = ; i <= n; i++) {
fa[i][i] = (str[i] != str[i - ]);
fb[i][i] = (str[i] != str[i + ]);
ans[i][i] = ;
}
for(int len = ; len <= n; len++) {
for(int l = ; l + len - <= n; l++) {
int r = l + len - ;
/// fa[l][r] fb[l][r] ans[l][r]
if(str[r] == str[l - ]) {
exmin(fa[l][r], fa[l][r - ]);
}
else {
for(int k = l; k < r; k++) {
exmin(fa[l][r], fa[l][k] + ans[k + ][r]);
}
}
if(str[l] == str[r + ]) {
exmin(fb[l][r], fb[l + ][r]);
}
else {
for(int k = l; k < r; k++) {
exmin(fb[l][r], ans[l][k] + fb[k + ][r]);
}
}
for(int k = l + ; k < r; k++) {
exmin(ans[l][r], fb[l][k - ] + fa[k + ][r] + );
}
exmin(ans[l][r], fa[l + ][r] + );
exmin(ans[l][r], fb[l][r - ] + );
exmin(fa[l][r], ans[l][r]);
exmin(fb[l][r], ans[l][r]);
//printf("[%d %d] l = %d r = %d ans = %d \n", l, r, fa[l][r], fb[l][r], ans[l][r]);
}
}
printf("%d\n", ans[][n]);
return ;
}
AC代码
然而本题还有多种简单一点的方法......
就设f[l][r]表示把[l, r]删光的代价，考虑str[l]是如何被删的。显然要么是单独被删，要么是跟某些位置一起删。不妨设一起删的位置中第二个是k。
枚举这个k，于是答案就是f[l + 1][k - 1] + f[k][r]
#include <bits/stdc++.h> const int N = ; int f[N][N];
char str[N]; inline void exmin(int &a, const int &b) {
if(a > b) a = b;
return;
} int main() {
memset(f, 0x3f, sizeof(f));
int n;
scanf("%d", &n);
scanf("%s", str + );
for(int i = ; i <= n; i++) {
f[i][i] = ;
}
for(int len = ; len <= n; len++) {
for(int l = ; l + len - <= n; l++) {
int r = l + len - ;
/// fa[l][r] fb[l][r] ans[l][r]
exmin(f[l][r], f[l + ][r] + );
if(str[l] == str[l + ]) {
exmin(f[l][r], f[l + ][r]);
}
for(int k = l + ; k <= r; k++) {
if(str[k] == str[l]) {
exmin(f[l][r], f[l + ][k - ] + f[k][r]);
}
}
}
}
printf("%d\n", f[][n]);
return ;
}
AC代码
CF1132D Stressful Training
题意：有n个笔记本，一开始有ai格电，每分钟消耗bi格电。你要买一个每分钟充x格点的插头，使得这些笔记本都能撑过k分钟。问x的最小值。
解：不难想到二分。然后check里每天挑最早没电的充电。如果直接用堆的话是nlog2n的，然而我卡过去了...
实际上我们可以考虑把这些笔记本按照没电天来分类，发现同类笔记本我们不需要知道它们的相对大小，于是直接vector。然后从前往后扫一遍，就能做到线性。
注意二分上界是1e12...
#include <bits/stdc++.h> typedef long long LL;
const int N = ; inline char gc() {
static char buf[N], *p1(buf), *p2(buf);
if(p1 == p2) p2 = (p1 = buf) + fread(buf, , N, stdin);
return p1 == p2 ? EOF : *p1++;
} template <class T> inline void read(T &x) {
x = ;
register char c(gc());
bool f(false);
while(c < '' || c > '') {
if(c == '-') f = true;
c = gc();
}
while(c >= '' && c <= '') {
x = x * + c - ;
c = gc();
}
if(f) x = (~x) + ;
return;
} struct Node {
LL now, del;
double x;
Node(LL A = , LL B = ) {
now = A;
del = B;
x = (double)A / B;
}
inline bool operator < (const Node &w) const {
return x > w.x;
}
}node[N]; int n, k;
LL a[N], b[N];
std::priority_queue<Node> Q; inline bool check(LL x) {
while(Q.size()) Q.pop();
for(register int i = ; i <= n; i++) {
Q.push(node[i]);
}
for(register int i = ; i < k; i++) {
Node temp = Q.top();
Q.pop();
if(temp.now - temp.del * i < ) {
return false;
}
temp = Node(temp.now + x, temp.del);
Q.push(temp);
}
Node temp = Q.top();
if(temp.now - temp.del * k < ) {
return false;
}
return true;
} int main() { read(n); read(k);
k--;
for(register int i = ; i <= n; i++) {
read(a[i]);
}
for(register int i = ; i <= n; i++) {
read(b[i]);
}
for(register int i = ; i <= n; i++) {
if(b[i] * k <= a[i]) {
std::swap(a[i], a[n]);
std::swap(b[i], b[n]);
n--;
i--;
}
} if(!n) {
puts("");
return ;
} for(int i = ; i <= n; i++) {
node[i] = Node(a[i], b[i]);
}
std::sort(node + , node + n + ); LL l = , r = 2e12;
while(l < r) {
LL mid = (l + r) >> ;
if(check(mid)) {
r = mid;
}
else l = mid + ;
}
if(r == 2e12) puts("-1");
else {
printf("%lld\n", r);
}
return ;
}
AC代码