差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:too_low:cfedu92hj [2020/07/31 17:20]
jim [B.Array Walk]
+++ 2020-2021:teams:too_low:cfedu92hj [2020/07/31 17:37] (当前版本)
jim [E.Segment Intersections]
@@ 行 37: / 行 37: @@
 题意：给定一个数组，起始位置在下标1处，可以选择向左走与向右走，不可重复向左走，向左走总次数不得超过p，总共走k次，求经过路径上数组元素值和的最大值。
 贪心。对于1-x范围内的路径，三种情况可能为最优值：
-找到相邻两项和的最大值，在这相邻两项间重复走min(p, k-p/2)次。
-找到相邻两项和的最大值，在这相邻两项间重复走min(p, k-p/2)次, 再在结尾向左走1次。
+找到相邻两项和的最大值，在这相邻两项间重复走min(p, k-p/2)次。
+找到相邻两项和的最大值，在这相邻两项间重复走min(p, k-p/2)次, 再在结尾向左走1次。
 ->x->x-1
@@ 行 88: / 行 91: @@
 =====  C.Good String =====
-**  [[https://codeforces.com/contest/1389/problem/A]]
-** 题意：找到[l, r]范围内的两个数x, y使得其最小公倍数也在[l, r]范围内。
+题意：长度为n的good string是s[i] = s[(i+2) % n] 的字符串
+给定一个0-9构成的字符串，求使其变为good string需要删除的最少字符数
+直接暴力枚举，在0-9中选2个数字构成good string，计算每次选择需要删除的字符数，找到最小的答案。
@@ 行 96: / 行 103: @@
 <code cpp>
+#include <bits/stdc++.h>
+using namespace std;
+typedef long long LL;
+int main() {
+    int t = 0;
+    cin >> t;
+    while (t--) {
+        string s;
+        cin>>s;
+        int l = s.length();
+        int ans = INT32_MAX;
+        for (int i = '0'; i <= '9'; ++i) {
+            for (int j = '0'; j <= '9'; ++j) {
+                int e = 0;
+                bool rev = 0;
+                for (int k = 0; k < l && e < ans; ++k) {
+                    char c = rev ? j : i;
+                    if(s[k] != c) e++;
+                    //else if(k == l - 1 && i != j && (l & 1))e++;
+                    else rev = !rev;
+                }
+                if(rev && (i != j))e++;
+                ans = min(ans, e);
+            }
+        }
+        cout<<ans<<endl;
+    }
+}
 </code>
 </hidden>
@@ 行 101: / 行 138: @@
 =====  D.Segment Intersections =====
-**  [[https://codeforces.com/contest/1389/problem/A]]
-** 题意：找到[l, r]范围内的两个数x, y使得其最小公倍数也在[l, r]范围内。
+题意：给定2种区间，每种区间有n个，2种不同区间为一组。每次操作可以将区间向左/右扩展一个单位。求使各组区间重叠长度达到k的最小步数。
+最优情况下，扩展时有3个过程：不相邻->相邻->区间完全重叠->继续扩展
+三个过程的重叠数收入分别为0，扩展数、扩展数/2
+记录每个过程的扩展长度，枚举选i组区间扩展到重叠k次需要的扩展数，取最小值。
+需要注意已经重叠的情况
 <hidden>
 <code cpp>
+#include <bits/stdc++.h>
+using namespace std;
+typedef long long LL;
+int main() {
+    int t = 0;
+    cin >> t;
+    while (t--) {
+        LL n, k;
+        cin>>n>>k;
+        int l1, r1, l2, r2;
+        cin>>l1>>r1>>l2>>r2;
+        LL pre = max(0, max(l1, l2) - min(r1, r2));
+        LL most = max(r1, r2) - min(l1, l2);
+        LL ist = max(0, min(r1, r2) - max(l1, l2) )* (LL)n ;
+        k -= ist;
+        if(k <= 0){
+            cout<<0<<endl;
+            continue;
+        }
+        LL ans = INT32_MAX;
+        for (int i = 1; i <= n; ++i) {
+            LL cur = pre * i;
+            cur += min((LL)k, most * i);
+            if(k > most * i){
+                cur += 2 * (k - most * i);
+            }
+            ans = min(ans, cur);
+        }
+        cout<<ans<<endl;
+    }
+}
 </code>
 </hidden>
-=====  E.Segment Intersections =====

CVBB ACM Team

用户工具

站点工具

差别

页面工具