题意：给出两个数组，通过调换两个数组相同位置的数字，使得两个数组的最大值的成绩最小。
思路：两个数的乘积最小，所以尽量使两个数相差较大。同时遍历两个数组，比较两个数组同一个位置上的两个数，每次使大的数在a数组，小的数在b数组，并同时将两个数组的最大值找出来，这个最大值的乘积就是最小的乘积。
代码：
#includeB-Fun with Even Subarraysusing namespace std; int main() { int t; cin >> t; while(t--){ int n, a[105], b[105]; cin >> n; for(int i = 0; i < n; ++i){ cin >> a[i]; } for(int i = 0; i < n; ++i){ cin >> b[i]; } int max1 = 0, max2 = 0; for(int i = 0; i < n; ++i){ max1 = max(max1, max(a[i], b[i]));//寻找a数组的最大值 max2 = max(max2, min(a[i], b[i]));//寻找b数组的最大值 } cout << max1 * max2 << endl; } return 0; }
题意：选择一个大小为2k的子区间，用子区间内后面k个数替代前面k个数，多次使用该操作，使得所给的数组中所有数字都相同。
思路：由题目中所给的操作不难发现，不论在什么情况下，数组的最后一个数字都没有办法改变，所以我们只能将所有的数都转化成与最后一个数相等。故令k = 1开始遍历，若 a n − 1 − k = a n − 1 a_{n - 1 - k}= a_{n - 1} an−1−k=an−1，则i继续左移直到第一个值不等于ai的数，然后执行一次操作，并令k = 2 * k，直到k >= n。
代码：
#includeC-Add Matchingusing namespace std; int a[200005]; int main() { int t; cin >> t; while(t--){ int n; cin >> n; for(int i = 0; i < n; ++i){ cin >> a[i]; } int k = 1, cnt = 0; while(k < n){ while(a[n - 1 - k] == a[n - 1]){ k++; } if(k < n){ k *= 2; ++cnt; } } cout << cnt << endl; } return 0; }
题意：将0~n-1中的数字分成n/2对，使得所有对的按位与之和等于k。
思路：找到题目中每一个数字对应的按位与为0的那个数c(x)，即c(x)=x⊕(n−1) ，其中n−1=11…11（二进制），然后根据k的大小分情况讨论：
当k = 0时：
就按照顺序从i = 0开始输出i和c(i)。
当0 < k < n - 1时：
不难发现k & (n - 1) = k，0 & c(k) = 0，然后使其他数x与对应的c(x)组成一队，这样就使得最终所有数对的按位与之和等于k了。
当k = n - 1时：
有(n - 2) & (n - 1) = (n - 2)；
(n - 3) & 1 = 1；
0 & 2 = 0;
所以使得以上三组各位一队时，按位与之和为n - 1，然后使其他数x与c(x)成一对。
但是这种情况下至少要有3对，又因为n总是2 的幂，所以n >= 8时才有解，当n = 4时无解。
代码：
#includeD-Range And Partitionusing namespace std; int main() { int t; cin >> t; while(t--){ int n, k; cin >> n >> k; if(n <= 4 && k == n - 1){ cout << -1 << endl; } else if(k == 0){ for(int i = 0 ; i < (i ^ (n - 1)); ++i){ cout << i << " " << (i ^ (n - 1)) << endl; } } else if(k == n - 1 && n > 4){ for(int i = 0; i < (i ^ (n - 1)); ++i){ //cout << (i ^ (n - 1)) << endl; if(i == 0) cout << 0 << " " << 2 << endl; else if(i == 2) continue; else if(i == 1) cout << 1 << " " << n - 3 << endl; else cout << i << " " << (i ^ (n - 1)) << endl; } cout << n - 2 << " " << n - 1 << endl; } else{ for(int i = 0; i < (i ^ (n - 1)); ++i){ if(i == 0) cout << i << " " << (k ^ (n - 1)) << endl; else if(i == k || i == (k ^ (n - 1))) cout << k << " " << n - 1 << endl; else{ cout << i << " " << (i ^ (n - 1)) << endl; } } } } return 0; }
题意：将所给数组分为k个子数组，寻找一个最小区间[x, y]，使得所得到的k个数组中，处于该区间的数的数量多余不处于该区间的数的数量。
思路：利用前缀和的思想，如果索引为i的数在该区间内，则
b
i
b_i
bi的值为1，反之则为-1，那么数组b的前缀和
s
u
m
i
sum_i
sumi是否大于0，则说明前i位数中处于区间内的数是多还是少，那么进一步
s
u
m
r
−
s
u
m
l
−
1
sum_r - sum_{l - 1}
sumr−suml−1的值表示的就是在区间[l, r]中，在区间内的数比不在区间内的数多的个数。
①先找到这个最小的区间[x, y]
由前缀和的思想可得：
∑
i
=
1
n
b
i
≥
k
displaystylesum_{i=1}^{n}b_i geq k
i=1∑nbi≥k
∑
i
=
1
n
(
−
1
+
2
∗
[
x
≤
a
i
≤
y
]
)
≥
k
displaystylesum_{i=1}^{n}({-1 + 2 * [xleq a_i leq y]} )geq k
i=1∑n(−1+2∗[x≤ai≤y])≥k
∑
i
=
1
n
[
x
≤
a
i
≤
y
]
≥
k
+
n
2
displaystylesum_{i=1}^{n}[xleq a_i leq y] geq {frac{k + n }{2}}
i=1∑n[x≤ai≤y]≥2k+n(取上限)
所以将数组排序之后遍历即可找到这个最小的区间。
②将区间分成k个子区间
然后计算
s
u
m
r
−
s
u
m
l
−
1
sum_r - sum_{l - 1}
sumr−suml−1的值，从第一个数开始遍历，当遇到第一个索引r满足条件时输出，然后l置为r + 1，依次列举出分割的数组。
代码：
#includeusing namespace std; int main() { int t; cin >> t; while(t--){ int n, k, a[200005], sorted_a[200005]; cin >> n >> k; for(int i = 0; i < n; ++i){ cin >> a[i]; sorted_a[i] = a[i]; } sort(sorted_a, sorted_a + n); int min = INT_MAX, len = (k + n + 1) / 2, x = 1, y = n; for(int i = 0; i + len - 1 < n; ++i){ if(min > sorted_a[i + len - 1] - sorted_a[i]){ min = sorted_a[i + len - 1] - sorted_a[i]; x = sorted_a[i]; y = sorted_a[i + len - 1]; //cout << x << " " << y << endl; } } cout << x << " " << y << endl; int sum = 0, count = 1, pos = 0; for(int i = 0; i < n; ++i){ if(x <= a[i] && a[i] <= y) ++sum; else --sum; if(sum > 0 && count < k){ cout << pos + 1 << " " << i + 1 << endl; pos = i + 1; ++count; } } cout << pos + 1 << " " << n << endl; } return 0; }
这次的比赛其实还是只做出来了前面的两道题，卡在了第三题上面，想到了寻找按位与为0的组队，但是没有想到对应的数就是与 n − 1 n - 1 n−1的异或，所以思路就卡住了，但是就算这一步想到了，也很难想到后面的；第四道题的话，最开始想的时候大致思路与题解一样，但是在实现的时候还是没有想到前缀和推导求[x, y]的范围，把处于区间内的数组之和误当成了大于等于 n 2 frac{n}{2} 2n，还是要多学会用数学推导求范围。
