被教育专场教育了,呜呜呜
沙拉查词和谷歌翻译误我啊！找到一个好用的翻译Deepl，这个翻译不会吧(Latex)翻译错。
A - Dungeon
有(3)个怪，生命值分别是(a,b,c)，普通攻击对其中一只怪(hp-1)，每(7)次可以对所有怪(hp-1)（此时必须3只怪都还有生命值），问杀死所有怪的最后一击能否是特殊攻击。
第一次被翻译坑是特殊攻击翻译成(hp-11)，第二次是没翻译好特殊攻击必须全部都打
把(3)只怪生命值求和，因为普通攻击可以随便打，所以只需要看和(\%9)（一轮攻击）是不是等于(0)，注意特判生命值最小的怪是不是提前被打死
B - Find The Array
构造题+思维
给定([a_1, a_2, dots, a_n]1 le a_i le 10^9)，求数组(b)满足
- (1 le b_i le 10^9)
- (b_i)能整除(b_{i+1})或(b_{i+1})能整除(b_i)或两者都可
- (2 sum limits_{i = 1}^{n} |a_i - b_i| le S)，(S= sum_{i=1}^na_i)
观察条件(2)，可以通过中间插入一些(1)，来轻松实现，例如([1,b_2,1,b_3,1,b_4,......])
接下来问题在于如何满足条件(3)
这个条件用人话来说就是要求两个数组差距尽量小，显然如果对于任意(i)都有(a_i=b_i)，那差距就是(0)
结合一些上面就能轻松得出构造方法([1,a_2,1,a_4,.....])
当然上面都是思考的过程，并没有严谨的论证，下面是来自parfe211的证明：
假设(n)是偶数。设(X=[1,a[2],1,a[4],...])，(Y=[a[1],1,a[3],1,...])。那么对于(X)有(W_{X}=2sumlimits_{i=1}^{n}|a_{i}-X_{i}|=a_{1}+a_{3}+ dots - frac{n}{2})，对于(Y)有(W_{Y}=2sumlimits_{i=1}^{n}|a_{i}-Y_{i}|=a_{2}+a_{4}+ dots - frac{n}{2})
那么这个表达式的和是(a_{1}+a_{2}+ dots +a_{n}-n=S-n)。但(S-n=W_X+W_Y)。因此，(W_X)和(W_Y)中至少有一个数小于或等于(frac{S-n}{2})。
仍要注意的是需要开(longlong)
C - Busy Robot
大模拟
非常恶心，还没写/kk
D - Pairs
思维+二分
给定 $2n $个整数 (1,2,...,2n)。将这(2n)个元素重新分配成(n)对。选择(x)对，并从其中取最小元素，并从其他(n-x)对中取最大元素。选出的元素构成集合(b)。给定(n)，和集合(b)，问有多少个(x)能构成(b)
关键的结论：
方法(1)
找到最大的(x)和最小的(x)，中间的(x)也都可以构成(b)集合
考虑两个数组(v_1,v_2)。(v_1)包含(b)中的数字，(v_2)包含不在(b)中的数字，两个数组都按递增顺序排序。
定义(cmp(l_1,r_1,l_2,r_2))如下。
如果可以将(v_1[l_1...r_1])和(v_2[l_2...r_2])重新分配成((r_1-l_1+1))对，使得每一对数组中，(v_1)的数字都小于(v_2)的数字，那么(cmp(l_1,r_1,l_2,r_2)=-1)，(v_1)都大则返回(1)，否则返回(0)。
当且仅当(cmp(0,x-1,n-x,n-1)=-1)且(cmp(x,n-1,0,n-x-1)=1)时，则某个(x)可以得到(b)。
序列(cmp(0,0,n-1,n-1),cmp(0,1,n-2,n-1),...,cmp(0,n-1,0,n-1))是不递减的。因此，满足(cmp(0,x-1,n-x,n-1)=-1)的最大(x)可以通过二元搜索找到。
同理，最小的(x)也可以找到，答案就是(x_{max}-x_{min}+1)
/*
@ author:pyyyyyy
-----思路------
本代码存在bug，谨慎参考，明天再改改
-----debug-------
*/
#include <bits/stdc++.h>
#include <vector>
using namespace std;
inline int read() {
char c = getchar();
int x = 0, f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
const int N = 1e5 + 2077;
int T, n;
vector<int> v1, v2;
int v[N];
int cmp(int l1, int r1, int l2, int r2){
int flag1 = 1, flag2 = 1;
for(int i = 0; i <= r1 - l1; ++i){
if(v1[l1 + i] > v2[l2 + i]) flag1 = 0;
else if(v1[l1 + i] < v2[l2 + i]) flag2 = 0;
}
if(flag1 == 0 && flag2 == 0) return 0;
else if(flag1 == 1) return -1;
else return 1;
}
int main()
{
// freopen(".in","r",stdin);
// freopen("test.out","w",stdout);
T = read();
while(T--){
int minn = 0, maxn = 0;
v1.clear(), v2.clear();
n = read();
for(int i = 0; i <= 2 * n; ++i) v[i] = 0;
for(int i = 1; i <= n; ++i) {
int x = read();
v[x] = 1;
v1.push_back(x);
}
for(int i = 1; i <= 2 * n; ++i)
if(v[i] == 0) v2.push_back(i);
if(cmp(1, n, 1, n) == -1) maxn = n;
else if(cmp(1, 1, n, n) != -1) maxn = 0;
else {
int l = 1, r = n;
while(l <= r){
int mid = (l + r) >> 1;
if(cmp(1, mid, n - mid + 1, n) == -1) l = mid + 1, maxn = mid;
else r = mid - 1;
}
}
if(cmp(n, n, 1, 1) != 1) minn = n;
else if(cmp(1, n, 1, n) == 1) minn = 0;
else {
int l = 1, r = n;
while(l <= r){
int mid = (l + r) >> 1;
if(cmp(n - mid + 1, n, 1, mid) == 1) l = mid + 1, minn = mid;
else r = mid - 1;
}
}
cout << maxn - minn + 1 << '
';
}
return 0;
}
/*
input：
output:
*/
方法(2)
和群友交流后，有大佬提出可以用田忌赛马的方法思考本题，我太菜了，不懂