最近一场TC，做得是在是烂，不过最后challenge阶段用一个随机数据cha了一个明显错误的代码，最后免于暴跌rating，还涨了一点。TC题目质量还是很高的，非常锻炼思维，拓展做题的视野，老老实实补题吧。
div2
250pts
题意：判断s去掉一个字符后能否和t一样。
代码：
class DecipherabilityEasy {
public:
string check(string s, string t) {
int n = s.size();
int m = t.size();
if(n- != m) return "Impossible";
for(int i = ; i < n; i++){
string tmp = "";
for(int j = ; j < i; j++)
tmp += s[j];
for(int j = i+; j < n; j++)
tmp += s[j];
if(tmp == t) return "Possible";
}
return "Impossible";
}
};
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).
代码：
int dp[][];
class CartInSupermarketEasy {
public: int calc(int N, int K) {
memset(dp, -, sizeof dp);
for(int i = ; i <= N; i++)
dp[i][] = i;
for(int i = ; i <= K; i++)
dp[][i] = ;
// cout << dp[0][0] << endl;
// cout << (~0) << endl;
return dfs(N, K);
}
int dfs(int x, int y) {
// if(x == 0) return 0;
// if(y == 0) return x;
int &res = dp[x][y];
// cout << dp[x][y] << endl;
// cout << res << endl;
// cout << x << y << endl;
// cout << res << endl;
if(~res) return res;
res = x;
res = min(res, dfs(x-, y) + );
y--;
for(int i = ; i < x; i++)
for(int j = ; j <= y; j++) {
res = min(res, max(dfs(i,j), dfs(x-i, y-j))+);
}
// if(res == 0) cout << x << y << endl;
return res;
}
};
解题关键：发现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]的对数，取两者中最大值。
代码：
class XorSequenceEasy {
public:
int getmax(vector <int> A, int N) {
int ans = , B = ;
int n = sz(A);
N = __builtin_popcount(N-);
// cout << N << endl;
for(int i = ; i < N; i++) {
int tmp[];
tmp[] = tmp[] = ;
for(int k = ; k < n; k++)
for(int l = k+; l < n; l++) {
if(((A[k]^A[l])>=(<<i)) &&
((A[k]^A[l])<(<<(i+))))
tmp[(A[k]>>i)&]++;
}
if(tmp[] < tmp[]) B |= (<<i);
}
// bug(1)
for(int i = ; i < n; i++) A[i] ^= B;
for(int i = ; i < n; i++) for(int j = i+; j < n; j++)
ans += (A[i] < A[j]);
return ans;
}
};
解题关键：发现异或后数的大小关系只和第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之间的字符去掉，剩下的字符已经是相同的了，不论怎么取剩下的字符，最终一定不能确定被移走的是哪些字符。
代码：
const int maxn = ;
char sa[maxn], sb[maxn];
string str;
int dp[maxn][maxn]; class Decipherability {
public:
int len;
int LCS(int n, int m, bool rev) {
if(n == || m == ) return ;
if(rev) {
for(int i = n-; i >= ; i--)
sa[n--i] = str[i];
for(int i = m-; i >= ; i--)
sb[m--i] = str[i];
} else {
for(int i = ; i < n; i++)
sa[i] = str[len-n+i];
for(int i = ; i < m; i++)
sb[i] = str[len-m+i];
}
memset(dp, , sizeof dp);
for(int i = ; i <= n; i++)
for(int j = ; j <= m; j++)
if(sa[i-] == sb[j-]) {
dp[i][j] = dp[i-][j-] + ;
} else {
dp[i][j] = max(dp[i-][j], dp[i][j-]);
}
return dp[n][m];
}
string check(string s, int K) {
str = s;
len = sz(s);
if(len == K) return "Certain";
int ok = ;
for(int i = ; i < len; i++)
for(int j = i+; j < len; j++)if(s[i] == s[j]) {
if(LCS(i, j, true)+LCS(len-i-, len-j-, false) >= len-K-) {
ok = ;
break;
}
}
return ok ? "Certain" : "Uncertain";
}
};
解题关键：剩下的字符构成的序列在原字符串中不唯一。
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]的目的是为了保证高位都相同，进而对下一位进行统计。具体可以用树状数组实现，为了免去每次都要对数组置零的耗时，可以对数组的每个元素设一个标记。
代码：
const int maxn = + ; int order[maxn], A[maxn];
LL ma[][];
LL res[maxn][];
int cnt; bool cmp(const int &x, const int &y) {
return A[x] < A[y];
} class XorSequence {
public: void add(int x, int v) {
while(x < maxn) {
if(res[x][] != cnt) {
res[x][] = ;
res[x][] = cnt;
}
res[x][] += v;
x += lowbit(x);
}
}
LL query(int x) {
LL ans = ;
while(x > ) {
if(res[x][] != cnt){
res[x][] = ;
res[x][] = cnt;
}
ans += res[x][];
x -= lowbit(x);
}
return ans;
}
void dfs(int l, int r, int dep) {
if(l > r || dep < ) return;
int mid = l-;
while(mid+ <= r) {
if(!(A[order[mid+]]&(<<dep)))
mid++;
else break;
} if(mid >= l && mid < r) {
cnt++;
//memset(res[dep], 0, sizeof(res[dep]));
for(int i = l; i <= mid; i++)
add(order[i], );
for(int i = mid+; i <= r; i++) {
ma[dep][] += query(order[i]);
}
// memset(res[dep], 0, sizeof(res[dep]));
cnt++;
for(int i = mid+; i <= r; i++)
add(order[i], );
for(int i = l; i <= mid; i++)
ma[dep][] += query(order[i]);
}
dfs(l, mid, dep-);
dfs(mid+, r, dep-);
}
long long getmax(int N, int sz, int A0, int A1, int P, int Q, int R) {
A[] = A0;
A[] = A1;
for (int i = ; i <= sz; i++) {
A[i] = (1LL*A[i - ] * P%N + 1LL*A[i - ] * Q%N + R) % N;
}
int n = __builtin_popcount(N-);
// for(int i = 1; i <= sz; i++)
// printf("%d ", A[i]);
// cout << endl; for(int i = ; i <= sz; i++)
order[i] = i;
sort(order + , order + sz + , cmp);
cnt = ;
memset(ma, , sizeof ma);
memset(res, , sizeof res); dfs(, sz, n-);
LL ans = ;
for(int i = ; i < n; i++)
ans += max(ma[i][], ma[i][]);
TL
return ans;
}
};
解题关键：排序后根据第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。
代码：
class CartInSupermarket {
public:
int calcmin(vector <int> a, int b) {
int low = , high = (int)1e9;
while(low < high) {
int mid = (low+high)/;
if(possible(a, mid, b)) high = mid;
else low = mid+;
}
return low;
}
private:
bool possible(vector<int> a, int timeLimit, int b) {
LL sum = ;
for(int x: a) sum += numSplits(x, timeLimit);
return sum <= b;
}
int numSplits(int x, int timeLimit) {
int low = , high = x;
while(low < high) {
int mid = (low+high)/;
if(possible(x, mid, timeLimit)) high = mid;
else low = mid + ;
}
if(low == x) return (int)1e9 + ;
return low;
}
bool possible(LL x, LL numSplits, int timeLimit) {
LL numParts = ;
int tl = ;
while(numParts <= numSplits){
numSplits -= numParts;
numParts *= ;
tl++;
}
x = max(0LL, x-(numParts-numSplits));
return (tl + ) + (x + numParts + numSplits - ) / (numParts + numSplits) <= timeLimit;
}
};
解题关键：二分时间，并二分split次数，确定的splits次数下，最优化进行操作的过程。