C
https://codeforces.com/contest/1631/problem/C
n是一个2的幂次，给0~n-1这些数两两配对，使得配对之后所有数对 进行与运算 的和 等于给定的k值。
最初的想法是先按顺序配对上，和k的差值再通过交换配对的数来实现。但是没有找到交换的规律，代码很难写出来
正解：
在发现了n的特殊性质后，我们发现i&(n-1-i)=0.
当n-1==k时，n-1&n-2 n-3&1 0&2 i&(n-1-i)(3<=i<n/2) 这么配对
否则，n-1&k 0&n-1-k i&(n-1-i)(2<=i<n/2) 这么配对
code
#include<bits/stdc++.h>
using namespace std;
int t,n,k;
int main(){
cin>>t;
while(t--){
cin>>n>>k;
if(n==4&&k==3){
puts("-1");
continue;
}
if(k==0){
for(int i=0;i<n/2;i++){
cout<<i<<" "<<n-1-i<<endl;
}
continue;
}
if(n!=k+1){
cout<<n-1<<" "<<k<<endl;
cout<<0<<" "<<n-1-k<<endl;
for(int i=1;i<n/2;i++){
if(i==k||n-1-i==k) continue;
cout<<i<<" "<<n-1-i<<endl;
}
}
else{
cout<<n-1<<" "<<n-2<<endl;
cout<<n-3<<" "<<1<<endl;
cout<<2<<" "<<0<<endl;
for(int i=3;i<n/2;i++){
cout<<i<<" "<<n-1-i<<endl;
}
}
}
return 0;
} D
https://codeforces.com/contest/1631/problem/D
由数据范围知，求x,y的时间复杂度应该为On或者Onlogn。
很容易想到尺取法（时间复杂度On）：预处理出取每个值的区间个数，当固定区间一端时，另一端的增加或减少使得答案单调性改变（本题对应子序列中位于[x,y]区间内的数随着区间增大而单调不减），因此采用尺取法。
求得x,y之后，遍历原数组，如果当前子序列内的位于xy区间内的数多1，就保存答案，段数++，最后一段单独成段。
还要特判k==1的情况
code
#include<bits/stdc++.h>
using namespace std;
int t,n,k;
int a[200005];
int cnt[200005],pre[200005];
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&k);
int num=(n+k+1)/2;
for(int i=1;i<=n;i++) cnt[i]=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
cnt[a[i]]++;
}
pre[0]=0;
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]+cnt[i];
}
int l=1,len=1e9,x,y;
for(int r=1;r<=n;r++){
while(pre[r]-pre[l-1]>=num){
if(r-l+1<len){
len=r-l+1;
x=l;y=r;
}
l++;
}
}
cout<<x<<" "<<y<<endl;
if(k==1){
printf("%d %d\n",1,n);
continue;
}
int last=1,cnt=0,cnt1=0;
int kk=0;
for(int i=1;i<=n;i++){
cnt++;
if(a[i]>=x&&a[i]<=y) cnt1++;
if(2*cnt1>cnt){
cout<<last<<" "<<i<<endl;
cnt1=0;cnt=0;
last=i+1;
kk++;
if(kk==k-1){
cout<<i+1<<" "<<n<<endl;
break;
}
}
}
}
return 0;
}
赛后总结
这次的cf只做出了A和B两题，C题想了很久...竟然不知道这是构造题
发现了自身的很多问题：以前学过的知识点很多都忘掉了，算法掌握不牢；看到题目如果不是马上有思路会陷入死循环（分析问题不够有条理、不够细致）；代码能力下降，有思路也不能马上实现。
发誓要变强大。
cf+专题训练 行动起来！！！！！