CF集萃1
因為cf上一堆水題，每個單獨開一篇博客感覺不太好，就直接放一起好了。
CF1096D Easy Problem
給定字符串，每個位置刪除要代價。求最小代價使之不含子序列"hard"。
設f[i][f]表示前i個刪到只匹配f位子序列的最小代價。轉移看代碼吧。O(n)
1 #include <bits/stdc++.h> 2 3 typedef long long LL; 4 const int N = 100010; 5 6 int a[N]; 7 LL f[N][5]; 8 char str[N]; 9 10 int main() { 11 int n; 12 scanf("%d", &n); 13 scanf("%s", str + 1); 14 for(int i = 1; i <= n; i++) scanf("%d", &a[i]); 15 16 int tag = 0; 17 for(int i = 1; i <= n; i++) { 18 if(tag == 0 && str[i] == 'h') tag++; 19 if(tag == 1 && str[i] == 'a') tag++; 20 if(tag == 2 && str[i] == 'r') tag++; 21 if(tag == 3 && str[i] == 'd') tag++; 22 } 23 if(tag != 4) { 24 printf("0\n"); 25 return 0; 26 } 27 28 for(int i = 1; i <= n; i++) { 29 f[i][0] = f[i - 1][0] + a[i] * (str[i] == 'h'); 30 f[i][1] = f[i - 1][1] + a[i] * (str[i] == 'a'); 31 f[i][2] = f[i - 1][2] + a[i] * (str[i] == 'r'); 32 f[i][3] = f[i - 1][3] + a[i] * (str[i] == 'd'); 33 if(str[i] == 'h') f[i][1] = std::min(f[i][1], f[i - 1][0]); 34 if(str[i] == 'a') f[i][2] = std::min(f[i][2], f[i - 1][1]); 35 if(str[i] == 'r') f[i][3] = std::min(f[i][3], f[i - 1][2]); 36 } 37 38 LL ans = std::min(std::min(f[n][0], f[n][1]), std::min(f[n][2], f[n][3])); 39 40 printf("%lld\n", ans); 41 return 0; 42 } AC代碼CF1036C?Classy Numbers
問[l, r]之間有多少個數滿足非0數碼不超過三個。
裸數位DP......注意每次讀完要把char數組清空...
1 /** 2 * There is no end though there is a start in space. ---Infinity. 3 * It has own power, it ruins, and it goes though there is a start also in the star. ---Finite. 4 * Only the person who was wisdom can read the most foolish one from the history. 5 * The fish that lives in the sea doesn't know the world in the land. 6 * It also ruins and goes if they have wisdom. 7 * It is funnier that man exceeds the speed of light than fish start living in the land. 8 * It can be said that this is an final ultimatum from the god to the people who can fight. 9 * 10 * Steins;Gate 11 */ 12 13 #include <bits/stdc++.h> 14 15 typedef long long LL; 16 const int N = 25; 17 18 LL f[N][5][2]; 19 char str[N], str1[N], str2[N]; 20 21 LL DFS(int k, int cnt, int z) { 22 if(cnt > 3) return 0; 23 if(!k) { 24 return 1; 25 } 26 if(f[k][cnt][z] != -1) { 27 return f[k][cnt][z]; 28 } 29 LL ans = 0; 30 if(cnt < 3) { 31 for(int i = 1; i <= 9; i++) { 32 ans += DFS(k - 1, cnt + 1, 1); 33 } 34 } 35 ans += DFS(k - 1, cnt, z); 36 return f[k][cnt][z] = ans; 37 } 38 39 LL DFS_2(int k, int cnt, int z) { 40 if(cnt > 3) return 0; 41 if(!k) return 1; 42 int lm = str[k] - '0'; 43 //printf("k = %d cnt = %d z = %d lm = %d \n", k, cnt, z, lm); 44 LL ans = DFS_2(k - 1, cnt + (lm != 0), z | (lm != 0)); 45 if(lm) { 46 ans += DFS(k - 1, cnt, z); 47 } 48 for(int i = 1; i < lm; i++) { 49 ans += DFS(k - 1, cnt + 1, 1); 50 } 51 return ans; 52 } 53 /* 54 1 55 29000000000091 29000000000099 56 57 */ 58 inline void dec(int &n) { 59 for(int i = 1; i <= n; i++) { 60 if(str[i] != '0') { 61 str[i]--; 62 break; 63 } 64 else str[i] = '9'; 65 } 66 if(str[n] == '0') n--; 67 return; 68 } 69 70 int main() { 71 memset(f, -1, sizeof(f)); 72 LL l, r; 73 int T; 74 scanf("%d", &T); 75 for(int i = 1; i <= T; i++) { 76 scanf("%s%s", str1 + 1, str2 + 1); 77 int n = strlen(str2 + 1); 78 memcpy(str + 1, str2 + 1, sizeof(char) * n); 79 std::reverse(str + 1, str + n + 1); 80 81 /*for(int j = 1; j <= n; j++) { 82 putchar(str[j]); 83 } 84 puts("");*/ 85 86 LL ans = DFS_2(n, 0, 0); 87 //printf("temp ans = %lld \n", ans); 88 memset(str2 + 1, 0, n * sizeof(char)); 89 n = strlen(str1 + 1); 90 memcpy(str + 1, str1 + 1, n * sizeof(char)); 91 std::reverse(str + 1, str + n + 1); 92 dec(n); 93 94 /*for(int j = 1; j <= n; j++) { 95 putchar(str[j]); 96 } 97 puts("");*/ 98 99 ans -= DFS_2(n, 0, 0); 100 printf("%lld\n", ans); 101 memset(str1 + 1, 0, n * sizeof(char)); 102 } 103 104 return 0; 105 } AC代碼CF1132C?Painting the Fence
給定n個區間，選出n - 2個區間使它們覆蓋的總長度最大。轉為刪去兩個區間。
去重 + 排序。考慮到答案要么相鄰要么不相鄰，相鄰的預處理前后綴覆蓋總長之后直接枚舉。
預處理出只刪每個區間的時候的覆蓋減少量為di。當不相鄰的時候，考慮到減少總量就是他們兩個的di之和。
于是枚舉一個區間，拿一個數據結構維護[1, i - 2]之間的最小d值即可。
注意答案不能比總長度還優。復雜度O(nlogn) / O(n)
1 /** 2 * There is no end though there is a start in space. ---Infinity. 3 * It has own power, it ruins, and it goes though there is a start also in the star. ---Finite. 4 * Only the person who was wisdom can read the most foolish one from the history. 5 * The fish that lives in the sea doesn't know the world in the land. 6 * It also ruins and goes if they have wisdom. 7 * It is funnier that man exceeds the speed of light than fish start living in the land. 8 * It can be said that this is an final ultimatum from the god to the people who can fight. 9 * 10 * Steins;Gate 11 */ 12 13 #include <bits/stdc++.h> 14 15 const int N = 5010; 16 17 struct Node { 18 int l, r; 19 inline bool operator < (const Node &w) const { 20 if(l != w.l) return l < w.l; 21 return r > w.r; 22 } 23 }node[N], stk[N]; int top; 24 25 int n, m, sl[N], sr[N], del[N], pw[N], ST[N][20]; 26 27 namespace t1 { 28 int d[N]; 29 inline void solve() { 30 for(int i = 1; i <= n; i++) { 31 d[node[i].l]++; 32 d[node[i].r + 1]--; 33 } 34 int ans = 0, now = 0; 35 for(int i = 1; i <= m; i++) { 36 now += d[i]; 37 ans += (now > 0); 38 } 39 printf("%d\n", ans); 40 return; 41 } 42 } 43 44 namespace t2 { 45 inline void solve() { 46 int ans = 0; 47 for(int i = 1; i <= n; i++) { 48 ans = std::max(ans, std::min(sl[i - 1] + sr[i + 1], sr[1])); 49 } 50 printf("%d\n", ans); 51 return; 52 } 53 } 54 55 inline void prework() { 56 for(int i = 1; i <= n; i++) { /// get sl del 57 sl[i] = sl[i - 1] + node[i].r - std::max(node[i].l, node[i - 1].r + 1) + 1; 58 del[i] = std::min(node[i].r, node[i + 1].l - 1) - std::max(node[i].l, node[i - 1].r + 1) + 1; 59 del[i] = std::max(del[i], 0); 60 } 61 for(int i = n; i >= 1; i--) { /// get sr 62 sr[i] = sr[i + 1] + std::min(node[i].r, node[i + 1].l - 1) - node[i].l + 1; 63 } 64 return; 65 } 66 67 inline void prework2() { 68 for(int i = 2; i <= n; i++) { 69 pw[i] = pw[i >> 1] + 1; 70 } 71 for(int i = 1; i <= n; i++) ST[i][0] = del[i]; 72 for(int j = 1; j <= pw[n]; j++) { 73 for(int i = 1; i + (1 << j) - 1 <= n; i++) { 74 ST[i][j] = std::min(ST[i][j - 1], ST[i + (1 << (j - 1))][j - 1]); 75 } 76 } 77 return; 78 } 79 80 inline int getMin(int l, int r) { 81 if(l > r) return 0x3f3f3f3f; 82 int t = pw[r - l + 1]; 83 return std::min(ST[l][t], ST[r - (1 << t) + 1][t]); 84 } 85 86 int main() { 87 scanf("%d%d", &m, &n); 88 for(int i = 1; i <= n; i++) { 89 scanf("%d%d", &node[i].l, &node[i].r); 90 } 91 92 std::sort(node + 1, node + n + 1); 93 int k = 2; 94 for(int i = 1; i <= n; i++) { 95 if(top && stk[top].r >= node[i].r) { 96 k--; 97 continue; 98 } 99 stk[++top] = node[i]; 100 } 101 n = top; 102 memcpy(node + 1, stk + 1, n * sizeof(Node)); 103 104 if(k <= 0) { 105 t1::solve(); 106 return 0; 107 } 108 node[n + 1].l = node[n + 1].r = 0x3f3f3f3f; 109 prework(); 110 111 if(k == 1) { 112 t2::solve(); 113 return 0; 114 } 115 116 /// solve 117 118 int ans = 0; 119 for(int i = 1; i < n; i++) { /// choose i i + 1 120 ans = std::max(ans, std::min(sl[i - 1] + sr[i + 2], sr[1])); 121 } 122 /// not neighbor 123 124 prework2(); 125 126 for(int i = 1; i <= n; i++) { 127 ans = std::max(ans, sr[1] - del[i] - getMin(1, i - 2)); 128 } 129 printf("%d\n", ans); 130 return 0; 131 } 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轉移。
然而本題還有多種簡單一點的方法......
就設f[l][r]表示把[l, r]刪光的代價，考慮str[l]是如何被刪的。顯然要么是單獨被刪，要么是跟某些位置一起刪。不妨設一起刪的位置中第二個是k。
枚舉這個k，于是答案就是f[l + 1][k - 1] + f[k][r]
1 #include <bits/stdc++.h> 2 3 const int N = 510; 4 5 int f[N][N]; 6 char str[N]; 7 8 inline void exmin(int &a, const int &b) { 9 if(a > b) a = b; 10 return; 11 } 12 13 int main() { 14 memset(f, 0x3f, sizeof(f)); 15 int n; 16 scanf("%d", &n); 17 scanf("%s", str + 1); 18 for(int i = 1; i <= n; i++) { 19 f[i][i] = 1; 20 } 21 for(int len = 2; len <= n; len++) { 22 for(int l = 1; l + len - 1 <= n; l++) { 23 int r = l + len - 1; 24 /// fa[l][r] fb[l][r] ans[l][r] 25 exmin(f[l][r], f[l + 1][r] + 1); 26 if(str[l] == str[l + 1]) { 27 exmin(f[l][r], f[l + 1][r]); 28 } 29 for(int k = l + 2; k <= r; k++) { 30 if(str[k] == str[l]) { 31 exmin(f[l][r], f[l + 1][k - 1] + f[k][r]); 32 } 33 } 34 } 35 } 36 printf("%d\n", f[1][n]); 37 return 0; 38 } AC代碼CF1132D?Stressful Training
題意：有n個筆記本，一開始有ai格電，每分鐘消耗bi格電。你要買一個每分鐘充x格點的插頭，使得這些筆記本都能撐過k分鐘。問x的最小值。
解：不難想到二分。然后check里每天挑最早沒電的充電。如果直接用堆的話是nlog2n的，然而我卡過去了...
實際上我們可以考慮把這些筆記本按照沒電天來分類，發現同類筆記本我們不需要知道它們的相對大小，于是直接vector。然后從前往后掃一遍，就能做到線性。
注意二分上界是1e12...
1 #include <bits/stdc++.h> 2 3 typedef long long LL; 4 const int N = 200010; 5 6 inline char gc() { 7 static char buf[N], *p1(buf), *p2(buf); 8 if(p1 == p2) p2 = (p1 = buf) + fread(buf, 1, N, stdin); 9 return p1 == p2 ? EOF : *p1++; 10 } 11 12 template <class T> inline void read(T &x) { 13 x = 0; 14 register char c(gc()); 15 bool f(false); 16 while(c < '0' || c > '9') { 17 if(c == '-') f = true; 18 c = gc(); 19 } 20 while(c >= '0' && c <= '9') { 21 x = x * 10 + c - 48; 22 c = gc(); 23 } 24 if(f) x = (~x) + 1; 25 return; 26 } 27 28 struct Node { 29 LL now, del; 30 double x; 31 Node(LL A = 0, LL B = 0) { 32 now = A; 33 del = B; 34 x = (double)A / B; 35 } 36 inline bool operator < (const Node &w) const { 37 return x > w.x; 38 } 39 }node[N]; 40 41 int n, k; 42 LL a[N], b[N]; 43 std::priority_queue<Node> Q; 44 45 inline bool check(LL x) { 46 while(Q.size()) Q.pop(); 47 for(register int i = 1; i <= n; i++) { 48 Q.push(node[i]); 49 } 50 for(register int i = 0; i < k; i++) { 51 Node temp = Q.top(); 52 Q.pop(); 53 if(temp.now - temp.del * i < 0) { 54 return false; 55 } 56 temp = Node(temp.now + x, temp.del); 57 Q.push(temp); 58 } 59 Node temp = Q.top(); 60 if(temp.now - temp.del * k < 0) { 61 return false; 62 } 63 return true; 64 } 65 66 int main() { 67 68 read(n); read(k); 69 k--; 70 for(register int i = 1; i <= n; i++) { 71 read(a[i]); 72 } 73 for(register int i = 1; i <= n; i++) { 74 read(b[i]); 75 } 76 for(register int i = 1; i <= n; i++) { 77 if(b[i] * k <= a[i]) { 78 std::swap(a[i], a[n]); 79 std::swap(b[i], b[n]); 80 n--; 81 i--; 82 } 83 } 84 85 if(!n) { 86 puts("0"); 87 return 0; 88 } 89 90 for(int i = 1; i <= n; i++) { 91 node[i] = Node(a[i], b[i]); 92 } 93 std::sort(node + 1, node + n + 1); 94 95 LL l = 1, r = 2e12; 96 while(l < r) { 97 LL mid = (l + r) >> 1; 98 if(check(mid)) { 99 r = mid; 100 } 101 else l = mid + 1; 102 } 103 if(r == 2e12) puts("-1"); 104 else { 105 printf("%lld\n", r); 106 } 107 return 0; 108 } AC代碼?
轉載于:https://www.cnblogs.com/huyufeifei/p/10618055.html
《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀總結
- 上一篇： java1.8之supplier
- 下一篇： Greenplum添加mirror步骤