2013暑假集训 第三场个人赛总结

　　7月20日，第三场个人赛。这场个人赛应该是最低谷了吧，整场比赛2y了一题以后就再也没出题了。

  IDOriginTitle
  0 / 11 Problem A SPOJ SEGMENTS A
  1 / 94 Problem B SPOJ STRDIST B
26 / 124 Problem C SGU 296 C
  2 / 17 Problem D CodeForces 3D D
    Problem E SPOJ MUSIC E
  1 / 35 Problem F CodeForces 185C F

　　这场比赛没什么好描述的。C题开始的时候贪心的思想错了，以为直接删除最小的数字就行了，结果搞了很久才搞到一组(98919 1)这样的数据，然后才知道是不停地删掉上升序列。然后我就整场比赛卡在A题那里了。原来A就是我这几天做的差分约束加上二分。做的是我还以为是DLX(Dancing Links)结果敲模板敲了好久，改模板也改了好久都改不出结果，然后就知道自己的模板坑了自己了。比赛中其实知道有几题比这题还要简单的，不过状态不是很好，于是就一直卡在A题，D的贪心完全没有想到。

　　好了，这场比赛我能做的题其实是ABCDE，赛后过了这几题。

　　A是差分约束加二分，二分结果，然后不停的更改构图的边权。做的时候将(i)->(i-1)=0的边写成i+1，debug了好久才找到这个问题，居然提交的时候还能过了不少数据。囧！

代码如下，时间780ms：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <map>
 6 
 7 using namespace std;
 8 
 9 const int N = 444;
10 const int INF = 0x11111111;
11 typedef long long LL;
12 struct Edge {
13     int s, t, c;
14     Edge() {}
15     Edge(int s, int t, int c) : s(s), t(t), c(c) {}
16 } edge[N << 2];
17 int ec, rn, dis[N << 1];
18 LL x[N], y[N], rx[N << 1];
19 map<LL, int> xid;
20 
21 bool bellman(int n, int e) {
22     for (int i = 0; i <= n; i++) dis[i] = INF;
23     dis[0] = 0;
24     bool ok;
25     for (int i = 0; i < n; i++) {
26         ok = true;
27         for (int j = 0; j < e; j++) {
28             if (dis[edge[j].t] > dis[edge[j].s] + edge[j].c) {
29                 dis[edge[j].t] = dis[edge[j].s] + edge[j].c;
30                 ok = false;
31             }
32         }
33         if (ok) return true;
34     }
35     return false;
36 }
37 
38 int main() {
39     int n, v;
40     while (cin >> n) {
41         rn = 0;
42         xid.clear();
43         for (int i = 0; i < n; i++) {
44             cin >> x[i] >> y[i] >> v;
45             x[i] <<= 1;
46             y[i] <<= 1;
47             y[i]--;
48             rx[rn++] = x[i];
49             rx[rn++] = y[i];
50         }
51         sort(rx, rx + rn);
52         rn = (int) (unique(rx, rx + rn) - rx);
53         ec = n;
54         for (int i = 0; i < rn; i++) {
55             xid[rx[i]] = i;
56             if (i) edge[ec++] = Edge(i, i - 1, 0);
57         }
58         for (int i = 0; i < n; i++) edge[ec++] = Edge(xid[y[i]], xid[x[i]], -1);
59         int h = 0, t = n + 1, ans = t;
60         while (h <= t) {
61             int m = h + t >> 1;
62             for (int i = 0; i < n; i++) edge[i] = Edge(xid[x[i]], xid[y[i]], m);
63             if (bellman(rn, ec)) ans = m, t = m - 1;
64             else h = m + 1;
65         }
66         cout << ans << endl;
67     }
68     return 0;
69 }
View Code

　　B是一个dp的优化，题目其实敲代码并不难，就是要比较细心才能看到这样的一个细节，最终答案不超过100。这个意味着每一层dp的范围不超过前后100个元素。我们可以从下面的sample得出来的dp矩阵可以看出来。

　　实现的时候要用滚动数组，这样可以防止MLE。

实现的代码如下，注释部分是用map来做的，不过超时了。用数组直接hash存放，9s左右通过：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <map>
 6 
 7 using namespace std;
 8 
 9 const int N = 111111;
10 const int INF = 0x11111111;
11 const int DIF = 111;
12 const int SZ = 1 << 8;
13 char A[N], B[N];
14 //map<int, int> dp[4];
15 int dp[1 << 2][SZ];
16 
17 int main() {
18 //    freopen("in", "r", stdin);
19     int n, m;
20     while (cin >> n >> m) {
21 //        for (int i = 0; i < 4; i++) dp[i].clear();
22         memset(dp, 0, sizeof(dp));
23         cin >> A + 1 >> B + 1;
24         dp[0][0] = 0;
25         for (int i = 0; i <= n; i++) {
26             int ti = i & 3;
27 //            dp[ti].clear();
28             for (int s = max(0, i - DIF), t = min(m, i + DIF), j = s; j <= t; j++) {
29                 if (i || j) dp[ti][j & SZ - 1] = INF;
30                 if (i > 0) dp[ti][j & SZ - 1] = min(dp[ti][j & SZ - 1], dp[(i - 1) & 3][j & SZ - 1] + 1);
31                 if (j > s) dp[ti][j & SZ - 1] = min(dp[ti][j & SZ - 1], dp[ti][j - 1 & SZ - 1] + 1);
32                 if (i > 0 && j > 0) {
33                     if (A[i] == B[j]) dp[ti][j & SZ - 1] = min(dp[ti][j & SZ - 1], dp[(i - 1) & 3][j - 1 & SZ - 1]);
34                     else dp[ti][j & SZ - 1] = min(dp[ti][j & SZ - 1], dp[(i - 1) & 3][j - 1 & SZ - 1] + 1);
35                 }
36                 if (i > 1 && j > 1 && A[i] == B[j - 1] && A[i - 1] == B[j]) dp[ti][j & SZ - 1] = min(dp[ti][j & SZ - 1], dp[(i - 2) & 3][j - 2 & SZ - 1] + 1);
37             }
38         }
39         cout << dp[n & 3][m & SZ - 1] << endl;
40     }
41     return 0;
42 }
View Code

开始的时候没有想到上面这样的一个方法，于是就搞了如下的滚动数组：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 
 8 const int N = 111111;
 9 const int INF = 0x11111111;
10 const int MID = 222;
11 char A[N], B[N];
12 int dp[1 << 3][MID + 5 << 1];
13 
14 int main() {
15     int n, m;
16     while (cin >> n >> m) {
17         memset(dp, 0, sizeof(dp));
18         cin >> A + 1 >> B + 1;
19         dp[0][MID] = 0;
20         for (int i = 0; i <= n; i++) {
21             for (int s = max(0, i - MID), t = min(m, i + MID), j = s; j <= t; j++) {
22                 int ti = i & 7, tj = j - i + MID + 5;
23                 if (i || j) dp[ti][tj] = INF;
24                 if (i > 0) dp[ti][tj] = min(dp[ti][tj], dp[(i - 1) & 7][tj + 1] + 1);
25                 if (j > 0) dp[ti][tj] = min(dp[ti][tj], dp[ti][tj - 1] + 1);
26                 if (i > 0 && j > 0) {
27                     if (A[i] == B[j]) dp[ti][tj] = min(dp[ti][tj], dp[(i - 1) & 7][tj]);
28                     else dp[ti][tj] = min(dp[ti][tj], dp[(i - 1) & 7][tj] + 1);
29                 }
30                 if (i > 1 && j > 1 && A[i] == B[j - 1] && A[i - 1] == B[j]) dp[ti][tj] = min(dp[ti][tj], dp[(i - 2) & 7][tj] + 1);
31             }
32         }
33         cout << dp[n & 7][MID + 5 - n + m] << endl;
34     }
35     return 0;
36 }
View Code

　　C题就是那题数字的贪心，我的做法跟找最大上升序列差不多：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 
 8 const int N = 1111;
 9 char buf[N];
10 bool vis[N];
11 int main() {
12     int k;
13     while (cin >> buf >> k) {
14         int n = strlen(buf), mk = 0, t;
15         k = n - k;
16         memset(vis, 0, sizeof(vis));
17         while (k > 0) {
18             t = mk;
19             for (int i = mk; i <= n - k; i++) {
20                 if (buf[t] < buf[i]) t = i;
21             }
22             vis[t] = true;
23             mk = t + 1;
24             k--;
25         }
26         for (int i = 0; i < mk; i++) if (vis[i]) putchar(buf[i]);
27         puts("");
28     }
29     return 0;
30 }
View Code

　　D题是括号匹配的贪心，做法是用一个优先队列存放A和B的差值，我们每次扫到问号的时候就直接讲它变成')'右括号，因为对于一个右括号过多的序列，可以任意挑选一个A和B的差最小的右括号来换成左括号，之前合法的状态依然继续合法。不合法的，例如前面存在固定的右括号过多，就可以直接调出循环了。

代码如下：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <queue>
 6 
 7 using namespace std;
 8 
 9 typedef long long LL;
10 typedef pair<int, int> PII;
11 const int N = 55555;
12 char str[N];
13 priority_queue<PII> Q;
14 
15 int main() {
16     int a, b;
17     while (~scanf("%s", str)) {
18         while (!Q.empty()) Q.pop();
19         char *p = str;
20         int lf = 0;
21         LL sum = 0;
22         bool noans = false;
23         while (*p) {
24             if (*p == '(') lf++;
25             if (*p == ')') lf--;
26             if (*p == '?') {
27                 scanf("%d%d", &a, &b);
28                 if (noans) { p++; continue;}
29                 *p = ')';
30                 lf--;
31                 sum += b;
32                 Q.push(PII(b - a, p - str));
33             }
34             while (!Q.empty() && lf < 0) {
35                 PII t = Q.top();
36                 sum -= t.first;
37                 *(str + t.second) = '(';
38                 lf += 2;
39                 Q.pop();
40             }
41             if (lf < 0) noans = true;
42             p++;
43         }
44         if (noans || lf) puts("-1");
45         else {
46             cout << sum << endl;
47             cout << str << endl;
48         }
49     }
50     return 0;
51 }
View Code

　　然后就是E了，E的做法，首先是要看得出每次的修改都是将一段的和S变成了-S，这时候就可以想到求前缀和的操作了。求出前缀和以后，就是一个最小交换次数的题了，计算最少要多少次交换才能对数组排好序。因为每次修改的操作都是将两个前缀和交换而已，所以就能直接就散最小交换次数。

代码如下：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 
 8 const int N = 111111;
 9 int rec[N], sum[N], p[N];
10 bool vis[N];
11 
12 bool cmp(int a, int b) { return sum[a] < sum[b];}
13 
14 int main() {
15     //freopen("in", "r", stdin);
16     int n;
17     while (~scanf("%d", &n)) {
18         sum[0] = 0;
19         bool ok = true;
20         for (int i = 1; i <= n; i++) {
21             scanf("%d", rec + i);
22             sum[i] = sum[i - 1] + rec[i];
23             p[i] = i;
24             if (sum[i] <= 0) ok = false;
25         }
26         sort(p + 1, p + n + 1, cmp);
27         memset(vis, 0, sizeof(vis));
28         int ans = n;
29         for (int i = 1; i <= n; i++) {
30             //cout << p[i] << endl;
31             if (sum[p[i - 1]] == sum[p[i]]) ok = false;
32             if (!vis[i]) {
33                 int t = i;
34                 while (!vis[t]) vis[t] = true, t = p[t];
35                 ans--;
36             }
37             //for (int i = 1; i <= n; i++) cout << vis[i] << ' '; cout << endl;
38         }
39         if (ok) printf("%d
", ans);
40         else puts("-1");
41     }
42     return 0;
43 }
View Code

　　最后还有一题F，这个真不会了。以后研究懂了dp的时候再说吧。

——written by Lyon

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/LyonLys/p/2013_07_20_Lyon.html