A.思维：https://codeforces.com/contest/1983/problem/A
AC代码：
#include<bits/stdc++.h>
using namespace std;
int t;
int n;
int main(){cin>>t;while(t--){cin>>n;for(int i=1;i<=n;i++) cout<<i<<" ";cout<<endl;}
}B.思维：https://codeforces.com/contest/1983/problem/B
比较考验观察能力：
1.每一次操作都不改变每一行每一列在模3意义下的总和。
因此，要保证可以转化过去，就得保证每一行列在模3意义下的总和相等。
2.满足了条件1就一定可以转化过去，我们不妨从上到下，从左到右考虑每一个点，假如他和B一样就跳过，否则一定可以用2/1补上。这样我们一定可以使的矩阵和B一样，加上条件1，最后一行列也相等，证毕！
AC代码：
#include<bits/stdc++.h>
using namespace std;
int a[550][550],b[550][550];
int t,n,m;
int main(){cin>>t;while(t--){cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){char c;cin>>c;a[i][j]=(int)(c-'0');}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){char c;cin>>c;b[i][j]=(int)(c-'0');}}int f=1;for(int i=1;i<=n;i++){int sum1=0,sum2=0;for(int j=1;j<=m;j++){sum1+=a[i][j];sum2+=b[i][j];}if(sum1%3!=sum2%3) f=0;}for(int j=1;j<=m;j++){int sum1=0,sum2=0;for(int i=1;i<=n;i++){sum1+=a[i][j];sum2+=b[i][j];}if(sum1%3!=sum2%3) f=0;}if(f) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
}C.双指针：https://codeforces.com/contest/1983/problem/C
枚举中间一个分段即可。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n;
ll a[200010],b[200010],c[200010],tot;
ll suma[200010],sumb[200010],sumc[200010];
struct node{int l,r;
}res[4];
int bian(ll* sum1,ll* sum2,ll* sum3){int j=1;for(int i=1;i<=n-1;i++){while(sum2[j]-sum2[i-1]<tot&&j<n-1) j++;//看看两边是否合法if(sum3[n]-sum3[j]>=tot&&sum2[j]-sum2[i-1]>=tot&&sum1[i-1]-sum1[0]>=tot){res[1]={1,i-1},res[2]={i,j},res[3]={j+1,n};return 1;} }return -1;
}
int main(){cin>>t;while(t--){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i];for(int i=1;i<=n;i++) cin>>c[i];for(int i=1;i<=n;i++){suma[i]=suma[i-1]+a[i];sumb[i]=sumb[i-1]+b[i];sumc[i]=sumc[i-1]+c[i];}tot=suma[n]%3==0?suma[n]/3:suma[n]/3+1;if(bian(sumb,suma,sumc)==1){cout<<res[2].l<<" "<<res[2].r<<" "<<res[1].l<<" "<<res[1].r<<" "<<res[3].l<<" "<<res[3].r<<endl;}else if(bian(sumc,suma,sumb)==1) cout<<res[2].l<<" "<<res[2].r<<" "<<res[3].l<<" "<<res[3].r<<" "<<res[1].l<<" "<<res[1].r<<endl;else if(bian(suma,sumb,sumc)==1) cout<<res[1].l<<" "<<res[1].r<<" "<<res[2].l<<" "<<res[2].r<<" "<<res[3].l<<" "<<res[3].r<<endl;else if(bian(sumc,sumb,suma)==1) cout<<res[3].l<<" "<<res[3].r<<" "<<res[2].l<<" "<<res[2].r<<" "<<res[1].l<<" "<<res[1].r<<endl;else if(bian(suma,sumc,sumb)==1) cout<<res[1].l<<" "<<res[1].r<<" "<<res[3].l<<" "<<res[3].r<<" "<<res[2].l<<" "<<res[2].r<<endl;else if(bian(sumb,sumc,suma)==1) cout<<res[3].l<<" "<<res[3].r<<" "<<res[1].l<<" "<<res[1].r<<" "<<res[2].l<<" "<<res[2].r<<endl;else{cout<<-1<<endl;}}
}D.思维+逆序对：https://codeforces.com/contest/1983/problem/D
首先，我们可以观察到：
1.的交换等价于若干个
的交换，于是条件等于两者相邻交换，交换次数相等，问是否可以变一样。
2.对于两个序列，相邻交换相同次数不改变逆序对的相对奇偶，也就是说一开始逆序对奇偶不同的一定不可以变成相等序列。
3.反之奇偶相同一定可以，因为他们一定差2的倍数，而我们可以通过1与2交换，再2与1交换抵消若干个2.
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n;
ll a[100010],b[100010];
ll a1[100010],b1[100010];
ll cnt;
ll a2[100010];
ll e=2,ee=1;
void merge(ll i,ll mid,ll j,ll* a){ll x1=i,x2=mid+1,f=i;while(x1<=mid&&x2<=j){if(a[x1]<=a[x2]){a2[f++]=a[x1++];}else{a2[f++]=a[x2++];cnt+=mid-x1+1;}}while(x1<=mid){a2[f++]=a[x1++];}while(x2<=j){a2[f++]=a[x2++];}for(int h=i;h<=j;h++){a[h]=a2[h];}
}
void mergesort(int l,int r,ll* a){if(l<r){int mid=(l+r)/e;mergesort(l,mid,a);mergesort(mid+ee,r,a);merge(l,mid,r,a);}
}
ll qiu(ll* a){ll k=ee;mergesort(k,n,a);return cnt;
}
int main(){cin>>t;while(t--){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) a1[i]=a[i];for(int i=1;i<=n;i++) cin>>b[i];for(int i=1;i<=n;i++) b1[i]=b[i];sort(a1+1,a1+n+1);sort(b1+1,b1+n+1);int f=0;for(int i=1;i<=n;i++){if(a1[i]!=b1[i]){f=1;break;}}if(f){cout<<"NO"<<endl;continue;}cnt=0;ll k1=qiu(a);cnt=0;ll k2=qiu(b);//cout<<k1<<" "<<k2<<" ";if(k1%2==k2%2) cout<<"YES"<<endl;else cout<<"NO"<<endl; }
}E.数学期望：https://codeforces.com/contest/1983/problem/E
我们假设0为特殊球，1为普通球,假设存在一个排列：00101100.
那么Alice取的就是001和1.
接下来我们考虑每一个1对答案Alice的贡献：
因为有个1，那么Alice取的都是奇数位：即
个末尾1段。
所以贡献：
考虑特殊球：
我们有个1，也就是有
个空隙可以放0，因此每一个空隙相当于放了
个0，而Alice取得的是奇数段，因此贡献为：
也就是：
加起来既可以，对手就是总的减去Alice即可。
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9+7;
int n,k;
const int maxn = 5e5;
int v[maxn],sumA,sumB;
int chA,chB;
int qpow(int a,int b){int res=1;while(b){if(b&1) res=(res*a)%mod;b>>=1;a=a*a%mod;}return res;
}
signed main(){int t;cin>>t;while(t--){sumA=sumB=chA=chB=0;cin>>n>>k;for(int i=1;i<=n;i++){cin>>v[i];if(i<=k) sumA=(sumA+v[i])%mod;else sumB=(sumB+v[i])%mod;}chA=ceil((n-k+1)*1.0/2);chB=ceil((n-k+1)/2);int ans=(int)ceil((n-k)*1.0/2)*qpow(n-k,mod-2)%mod*sumB%mod+chA*qpow(chA+chB,mod-2)%mod*sumA%mod;ans%=mod;cout<<ans<<' '<<(sumA+sumB+mod-ans)%mod<<'\n';}
}F.二分+01Trie:https://codeforces.com/contest/1983/problem/F
联系上次ABC上的kth不难想到先二分出一个mid，现在的问题就是有多少子对的值是小于等于它的。
我们不妨先固定,它的贡献就是离他最近的又满足
异或上
小于等于mid的
的下标。
联系到二进制异或的运算可以想到01Trie，对于每一个r，我们把它和mid放目前建立好的01Trie比较，假如在一个分支上mid是1，那么我们往异或r为0的路径走就一定可以，我们对pos进行更新。然后继续往1的方向走保证考虑所有情况。反之mid那位为0，那么我们就只可以往0的方向走。最后走到头因为等于也算再更新。
实在找不到我们就用上一次可以的pos。
此时还有最后一个问题，在对pos更新时如何快速知道与r异或的l的最大下标？
我们再开一个数组在add操作中把最新的值的走的路径上的最大下标进行更新维护即可。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t,n;
ll k;
int a[500010];
int tr[5000100][2];
int tot=1;
int ck[5000100];
int find(int x,int mid){int now=1;int pos=0;for(int i=29;i>=0;i--){int k1=((x>>i)&1),k2=((mid>>i)&1);if(k2==0){now=tr[now][k1];}else{pos=max(pos,ck[tr[now][k1]]);now=tr[now][1-k1];}}pos=max(pos,ck[now]);return pos;
}
void add(int id,int x){int now=1;for(int i=29;i>=0;i--){if((x>>i)&1){if(tr[now][1]==0) tr[now][1]=++tot;now=tr[now][1];}else{if(tr[now][0]==0) tr[now][0]=++tot;now=tr[now][0];}ck[now]=max(id,ck[now]);}
}
ll check(int mid){ll ans=0;//小于等于mid的数量 int pos=0;//右边界 for(int i=1;i<=n;i++){pos=max(pos,find(a[i],mid));ans=ans+pos;add(i,a[i]);}//清空for(int i=0;i<=tot;i++) ck[i]=0;for(int i=0;i<=tot;i++){tr[i][0]=tr[i][1]=0;} tot=1;return ans;
}
int main(){cin>>t;while(t--){cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i];int l=0,r=(1<<30)-1;while(l<r){int mid=(l+r)/2;if(check(mid)>=k)//check(mid):小于等于mid的数量{r=mid;} else l=mid+1;}cout<<l<<endl;}
}
