D题补了一天...
B. Maximum Strength
题意
给定两串数字，在这两串数字之间找两串数字，要求每一数位之差的绝对值之和最大，求最大值为多少。
思路
对较少的那串数字添加前导零，使两串数字长度一样。
要使所求值最大，就要尽可能使两数字串上相同数位的值分别为0和9。容易证明，从高位向低位，第一次两个数字不同的数位的后面所有数位均可分别设为0和9。第一次两个数字不同的数位的则保持不变。
代码
void solve() {
string l, r;
cin >> l >> r;
int n = r.size();
l = string(n - l.size(), '0') + l;
int k = -1;
for(int i = 0; i < r.size(); i++) {
if(l[i] != r[i]) {
k = i;
break;
}
}
if(k == -1) {
cout << "0\n";
} else {
cout << (r[k] - l[k]) + 9 * (n - k - 1) << "\n";
}
}
C. Game with Reversing
题意
给定两个字符串，Alice可以修改其中一个字符串中的一个字符，Bob可以使其中一个字符串翻转。两人分别进行操作，Alice先手，两个字符串相等后停止操作。Alice向要最小化操作数，Bob可以想要最大化操作数，求最小的操作次数为多少。
思路
统计最初两个字符串正向和反向不同的字符数，再计算更改这些不同字符所用的最少次数，比较得出答案。
对于修改正向不同的字符使两个字符串相等，翻转操作的次数要为偶，而对于反向，翻转的次数要为奇数。总操作次数就是要修改的字符数和翻转数。但要注意，正向的最小的可能总操作数为0，反向的最小的可能总操作数为2。
当不同的字符数量为奇数和偶数时，总操作的计算方法也是不同的，详情见代码。
代码
void solve() {
int n;
string a, b;
cin >> n >> a >> b;
int cnt1 = 0, cnt2 = 0;
for(int i = 0; i < n; i++) {
if(a[i] != b[i]) {
cnt1++;
}
if(a[n-i-1] != b[i]) {
cnt2++;
}
}
if(cnt1 & 1) {
cnt1 = 2 * cnt1 - 1;
} else {
cnt1 = 2 * cnt1;
}
if(cnt2 & 1) {
cnt2 = 2 * cnt2;
} else {
cnt2 = 2 * cnt2 - 1;
}
cout << min(max(cnt1, 0), max(cnt2, 2)) << "\n";
}
D. Survey in Class
题意
给定几个区间，然后询问一个数，如果这个数在某个区间内，那么这个区间的值加1，其它不包含这个数的区间的值减1。所有区间的初始值都为0，且每次询问的数都不同。求若干次询问后，值最大的区间和最小的区间之差最大为多少。
思路
要使一个区间和另一个区间的值之差最大，那么每次询问的值要使一个区间增加，另一个区间减少，即询问的值在其中一个区间中，而不在另一个区间中。
对于任意两个区间，有三种情况：
1. 大区间包含小区间：要使这两个区间的值之差最大，询问在小区间以外大区间以内的所有数。
2. 两个区间不包含：要使值之差最大，询问其中较大的那个区间的所有数。
3. 两个区间相交：要使值之差最大，询问不相交的两个部分之中较大的那部分的所有数。
先求出所有区间中最大的区间和最小的区间，这两者之差乘以2就是第一种情况的最大可能。不用担心这两个区间是否包含，因为如果不包含，那么答案会在后面的操作中更新。
再求出所有区间最左边的右端点minr，和最右边的左端点maxl，然后遍历每个区间维护答案。把每个区间的右端点减去minr，maxl减去左端点。如果这两者的值有小于等于区间的长度，那么就是第三种情况，如果都大于，就为第二种情况。
代码
void solve() {
int n, m;
cin >> n >> m;
vector<int> l(n), r(n), len(n);
for(int i = 0; i < n; i++) {
cin >> l[i] >> r[i];
l[i]--;
len[i] = r[i] - l[i];
}
int mx = *max_element(len.begin(), len.end());
int mn = *min_element(len.begin(), len.end());
int ans = mx - mn;
int minr = *min_element(r.begin(), r.end());
int maxl = *max_element(l.begin(), l.end());
for(int i = 0; i < n; i++) {
ans = max(ans, min(len[i], max(r[i] - minr, maxl - l[i])));
}
cout << ans * 2 << "\n";
}
E. MEX of LCM
题意
给定一个序列，可以得到所有子序列的最小公倍数，再求出所有最小公倍数的最小不存在正值mex。
思路
可以证明\(n\)个数的mex最大为\(n+1\)，当\(n\)个数中的有元素大于\(n\)则会使mex的最大值减小。所以可以根据有效最大公倍数的个数确定mex的上限值以去掉无效的最大公倍数。
枚举每个数为区间右端点，那么以这个数位右端点的所有区间的最小公倍数，可以通过前一个数为右端点的所有区间的最小公倍数推出来。这些数不会太多，设这些数为\(x_1<x_2<...<x_k\)，那么一定有\(x_{i+1}\)为\(x_i\)的倍数，所以\(k\)的数量级为\(O(log_{2}n)\)，总的时间复杂度不会超过\(O(nlog_{2}n)\)。
通过上面推导可以确定mex的最大值不会超过\(nlog_{2}n\)，把mex的上限值设为\(2n\)即可。
代码
void solve() {
int n;
cin >> n;
int lim = 2 * n;
vector<int> v(n);
for(int i = 0; i < n; i++) {
cin >> v[i];
}
set<int> st, pre;
for(int i = 0; i < n; i++) {
set<int> t;
for(int j : pre) {
int tmp = lcm(j, v[i]);
if(tmp < lim) {
st.insert(tmp);
t.insert(tmp);
}
}
st.insert(v[i]);
t.insert(v[i]);
pre.swap(t);
}
int mex = 1;
while(st.count(mex)) {
mex++;
}
cout << mex << "\n";
}