TopCoder 649 div1 & div2

最近一场TC，做得是在是烂，不过最后challenge阶段用一个随机数据cha了一个明显错误的代码，最后免于暴跌rating，还涨了一点。TC题目质量还是很高的，非常锻炼思维，拓展做题的视野，老老实实补题吧。

div2

250pts

题意：判断s去掉一个字符后能否和t一样。

代码：

 1 class DecipherabilityEasy {
 2     public:
 3     string check(string s, string t) {
 4         int n = s.size();
 5         int m = t.size();
 6         if(n-1 != m) return "Impossible";
 7         for(int i = 0; i < n; i++){
 8                 string tmp = "";
 9             for(int j = 0; j < i; j++)
10             tmp += s[j];
11             for(int j = i+1; j < n; j++)
12                 tmp += s[j];
13             if(tmp == t) return "Possible";
14         }
15         return "Impossible";
16     }
17 };

View Code

500pts

题意：给定一个长度为n的序列，1 <= n <= 100，可以有两种操作，每次可以将序列从任意位置分成两部分，或者让序列长度减少1，每个操作占1min，每一轮中可以对每个序列进行一次以上操作，问是所有序列消失最短时间，其中split操作的次数不超过k。

分析：dp[n][k]表示对长度为n的序列，最多进行k次split操作时，最短时间。

可以得到以下转移：

dp[n][k] = min(dp[n][k], max(dp[i][j], dp[n-i][k-1-j])+1);

dp[n][k] = min(dp[n][k], n).

代码：

 1 int dp[110][110];
 2 class CartInSupermarketEasy {
 3 public:
 4 
 5     int calc(int N, int K) {
 6         memset(dp, -1, sizeof dp);
 7         for(int i = 0; i <= N; i++)
 8             dp[i][0] = i;
 9         for(int i = 0; i <= K; i++)
10             dp[0][i] = 0;
11 //            cout << dp[0][0] << endl;
12 //            cout << (~0) << endl;
13         return dfs(N, K);
14     }
15     int dfs(int x, int y) {
16 //        if(x == 0) return 0;
17 //        if(y == 0) return x;
18         int &res = dp[x][y];
19 //        cout << dp[x][y] << endl;
20         //        cout << res << endl;
21 //        cout << x << y << endl;
22 //        cout << res << endl;
23         if(~res) return res;
24         res = x;
25         res = min(res, dfs(x-1, y) + 1);
26         y--;
27         for(int i = 1; i < x; i++)
28             for(int j = 0; j <= y; j++) {
29                 res = min(res, max(dfs(i,j), dfs(x-i, y-j))+1);
30             }
31 //        if(res == 0) cout << x << y << endl;
32         return res;
33     }
34 };

View Code

解题关键：发现split操作后得到的子序列问题是原问题的子问题。

1000pts

题意：数组A[i]，长度n <= 50，求C，令B[i] = A[i]^C，使得B[i]中满足i < j，B[i] < B[j]的数对最多，输出这样的最大值。

分析：考虑两个数A[i]，A[j]异或一个数C的大小关系，考虑两数的二进制位，设从第k位开始，A[i]，A[j]二进制位不同，也就是k+1， k+2及高位都完全相同，设k位(x, 1-x)，那么异或后数B[i]，B[j]大小主要与(x，1-x)及C的第k位(记做y)有如下关系：

x = 0，y = 1，B[i] > B[j]; x = 0，y = 0，B[i] < B[j];

x = 1，y = 1，B[i] < B[j]; x = 1，y = 0，B[i] > B[j].

此题n不大，枚举第k位，确定第k位为0,1时，能够根据第k位为0或1确定的满足条件i < j，且B[i] < B[j]的对数，取两者中最大值。

代码：

 1 class XorSequenceEasy {
 2 public:
 3     int getmax(vector <int> A, int N) {
 4         int ans = 0, B = 0;
 5         int n = sz(A);
 6         N = __builtin_popcount(N-1);
 7 //        cout << N << endl;
 8         for(int i = 0; i < N; i++) {
 9             int tmp[2];
10             tmp[0] = tmp[1] = 0;
11             for(int k = 0; k < n; k++)
12                 for(int l = k+1; l < n; l++) {
13                     if(((A[k]^A[l])>=(1<<i)) &&
14                             ((A[k]^A[l])<(1<<(i+1))))
15                         tmp[(A[k]>>i)&1]++;
16                 }
17             if(tmp[0] < tmp[1]) B |= (1<<i);
18         }
19 //        bug(1)
20         for(int i = 0; i < n; i++) A[i] ^= B;
21         for(int i = 0; i < n; i++) for(int j = i+1; j < n; j++)
22                 ans += (A[i] < A[j]);
23         return ans;
24     }
25 };

View Code

解题关键：发现异或后数的大小关系只和第k位有关。

div1

250pts

题意：字符串s(len <= 50)，从中去掉K个字符之后，能否根据剩下的字符，确定去掉的是哪些字符呢。

分析：去掉K个字符后剩下的字符构成的序列如果不是原s中的唯一序列，那么就不能确定去掉的是哪K个字符，因此，可以枚举s中两个相等的字符s[i]，s[j](i != j)，然后

判断LCS(s[0, i-1], s[0, j-1]) + LCS(s[i+1, len-1], s[j+1, len-1]) + 1 >= len-K么，这样是能判断剩下的序列是否唯一。上面想得略复杂，题解只是判断两个相等字符之间的长度j-i<=K否，因为此时优先移走s[i],s[j]中的一个，然后将i,j之间的字符去掉，剩下的字符已经是相同的了，不论怎么取剩下的字符，最终一定不能确定被移走的是哪些字符。

代码：

 1 const int maxn = 55;
 2 char sa[maxn], sb[maxn];
 3 string str;
 4 int dp[maxn][maxn];
 5 
 6 class Decipherability {
 7 public:
 8     int len;
 9     int LCS(int n, int m, bool rev) {
10         if(n == 0 || m == 0) return 0;
11         if(rev) {
12             for(int i = n-1; i >= 0; i--)
13                 sa[n-1-i] = str[i];
14             for(int i = m-1; i >= 0; i--)
15                 sb[m-1-i] = str[i];
16         } else {
17             for(int i = 0; i < n; i++)
18                 sa[i] = str[len-n+i];
19             for(int i = 0; i < m; i++)
20                 sb[i] = str[len-m+i];
21         }
22         memset(dp, 0, sizeof dp);
23         for(int i = 1; i <= n; i++)
24             for(int j = 1; j <= m; j++)
25                 if(sa[i-1] == sb[j-1]) {
26                     dp[i][j] = dp[i-1][j-1] + 1;
27                 } else {
28                     dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
29                 }
30         return dp[n][m];
31     }
32     string check(string s, int K) {
33         str = s;
34         len = sz(s);
35         if(len == K) return "Certain";
36         int ok = 1;
37         for(int i = 0; i < len; i++)
38             for(int j = i+1; j < len; j++)if(s[i] == s[j]) {
39                     if(LCS(i, j, true)+LCS(len-i-1, len-j-1, false) >= len-K-1) {
40                         ok = 0;
41                         break;
42                     }
43                 }
44         return ok ? "Certain" : "Uncertain";
45     }
46 };

View Code

解题关键：剩下的字符构成的序列在原字符串中不唯一。

550pts

题意：div2 500pts升级版，之前已经知道B[i]，B[j]的大小只和第k位(x,1-x)及C的第k位y有关。

因此当y为0，需要知道A[j]第k位为1时，i < j 且A[i]的第k位为0 的个数；当y为1，A[j]第k位为0时，i < j，且A[i] 第k位为1的个数，注意A[i]，A[j]的k+1位及更高位都应该相同，这样便能够分别统计C的第k位为0,1确定的(i, j)的个数(B[i] < B[j], i < j) 。

对A[i]排序后得到A'[l, r]，从最高位开始，每次统计位于A'[l,r]范围的A[j]，当A[j]的第k位为1或0时,位于A[j]之前且k位为0或1的A[i](i < j)的个数，统计后根据第k位为0 或 1，分成A'[l, mid], A'[mid+1, r]两部分继续统计第k-1位能够确定的数对(i, j)的个数。划分成A'[l, mid], A'[mid+1, r]的目的是为了保证高位都相同，进而对下一位进行统计。具体可以用树状数组实现，为了免去每次都要对数组置零的耗时，可以对数组的每个元素设一个标记。

代码：

 1 const int maxn = 131072 + 10;
 2 
 3 int order[maxn], A[maxn];
 4 LL ma[33][2];
 5 LL res[maxn][2];
 6 int cnt;
 7 
 8 bool cmp(const int &x, const int &y) {
 9     return A[x] < A[y];
10 }
11 
12 class XorSequence {
13 public:
14 
15     void add(int x, int v) {
16         while(x < maxn) {
17             if(res[x][1] != cnt) {
18                 res[x][0] = 0;
19                 res[x][1] = cnt;
20             }
21             res[x][0] += v;
22             x += lowbit(x);
23         }
24     }
25     LL query(int x) {
26         LL ans = 0;
27         while(x > 0) {
28             if(res[x][1] != cnt){
29                 res[x][0] = 0;
30                 res[x][1] = cnt;
31             }
32             ans += res[x][0];
33             x -= lowbit(x);
34         }
35         return ans;
36     }
37     void dfs(int l, int r, int dep) {
38         if(l > r || dep < 0) return;
39         int mid = l-1;
40         while(mid+1 <= r) {
41             if(!(A[order[mid+1]]&(1<<dep)))
42                 mid++;
43             else break;
44         }
45 
46         if(mid >= l && mid < r) {
47             cnt++;
48             //memset(res[dep], 0, sizeof(res[dep]));
49             for(int i = l; i <= mid; i++)
50                 add(order[i], 1);
51             for(int i = mid+1; i <= r; i++) {
52                 ma[dep][0] += query(order[i]);
53             }
54             // memset(res[dep], 0, sizeof(res[dep]));
55             cnt++;
56             for(int i = mid+1; i <= r; i++)
57                 add(order[i], 1);
58             for(int i = l; i <= mid; i++)
59                 ma[dep][1] += query(order[i]);
60         }
61         dfs(l, mid, dep-1);
62         dfs(mid+1, r, dep-1);
63     }
64     long long getmax(int N, int sz, int A0, int A1, int P, int Q, int R) {
65         A[1] = A0;
66         A[2] = A1;
67         for (int i = 3; i <= sz; i++) {
68             A[i] = (1LL*A[i - 2] * P%N + 1LL*A[i - 1] * Q%N + R) % N;
69         }
70         int n = __builtin_popcount(N-1);
71 //        for(int i = 1; i <= sz; i++)
72 //            printf("%d ", A[i]);
73 //        cout << endl;
74 
75         for(int i = 1; i <= sz; i++)
76             order[i] = i;
77         sort(order + 1, order + sz + 1, cmp);
78         cnt = 0;
79         memset(ma, 0, sizeof ma);
80         memset(res, 0, sizeof res);
81 
82         dfs(1, sz, n-1);
83         LL ans = 0;
84         for(int i = 0; i < n; i++)
85             ans += max(ma[i][0], ma[i][1]);
86         TL
87         return ans;
88     }
89 };

View Code

解题关键：排序后根据第k位对数组进行分组，统计。

850pts

题意：div2 500pt升级版，范围更大，且开始给定的n ( n <= 50)个序列，长度len及能够进行的split操作总次数<=1e9。

分析：官方题解是采用二分时间，然后在确定时间下单独考虑消除每个序列，二分需要的最少split次数，最后判断总的split次数是否<=splits。

难点在于怎么二分确定需要的最少split次数，题解里面给出了一系列证明，总结起来就是：先进行split操作，然后进行remove操作，这样结果肯定是更优的；

split的次数越多，结果更优。因此首先进行split操作，一个序列能够split成两个时，则split，如果满足split次数，能够继续将两个序列split成四个时，则split，继续split直到不能split所有序列，那么利用剩余的split次数对部分序列split，对没有split的其他部分序列进行remove操作，此时时间记做T1。剩余部分需要的时间T2和剩下的序列总长度，n'有关，即T2 = ，判断T1+T2 <= timeLimit。

代码：

 1 class CartInSupermarket {
 2 public:
 3     int calcmin(vector <int> a, int b) {
 4         int low = 1, high = (int)1e9;
 5         while(low < high) {
 6             int mid = (low+high)/2;
 7             if(possible(a, mid, b)) high = mid;
 8             else low = mid+1;
 9         }
10         return low;
11     }
12 private:
13     bool possible(vector<int> a, int timeLimit, int b) {
14         LL sum = 0;
15         for(int x: a) sum += numSplits(x, timeLimit);
16         return sum <= b;
17     }
18     int numSplits(int x, int timeLimit) {
19         int low = 0, high = x;
20         while(low < high) {
21             int mid = (low+high)/2;
22             if(possible(x, mid, timeLimit)) high = mid;
23             else low = mid + 1;
24         }
25         if(low == x) return (int)1e9 + 100;
26         return low;
27     }
28     bool possible(LL x, LL numSplits, int timeLimit) {
29         LL numParts = 1;
30         int tl = 0;
31         while(numParts <= numSplits){
32             numSplits -= numParts;
33             numParts *= 2;
34             tl++;
35         }
36         x = max(0LL, x-(numParts-numSplits));
37         return (tl + 1) + (x + numParts + numSplits - 1) / (numParts + numSplits) <= timeLimit;
38     }
39 };

View Code

解题关键：二分时间，并二分split次数，确定的splits次数下，最优化进行操作的过程。