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

 

		ID	Origin	Title
	/	Problem A
	/	Problem B
	/	Problem C
	/	Problem D
		Problem E
	/	Problem F

 

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

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

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

代码如下，时间780ms：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
         
        
       
      

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

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

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

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
         
        
       
      

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

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           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 }
         
        
       
      

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

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           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 }
         
        
       
      

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

代码如下：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6  7 using namespace std; 8  9 typedef long long LL;10 typedef pair
           
             PII;11 const int N = 55555;12 char str[N];13 priority_queue
            
              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 }
            
           
          
         
        
       
      

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

代码如下：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           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\n", ans);40         else puts("-1");41     }42     return 0;43 }
         
        
       
      

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

——written by Lyon