C.Build Permutation

思路： 定理：对于任意的非负数n，区间[n,2n]至少存在一个完全平方数。 证明

利用上述定理，对于数n，我们可以构造大于等于n的最小完全平方数x，n<=x<=2n，因此0<=x-n<=n，x位于0~n之间，这样的x一定存在，因此一定有解

构造序列方法如下：从后往前遍历n-1~0，对每个起始位置i=start，先找到最小完全平方数x，然后这个位置的res为x-i,然后从i位置往前，res的值依次加一，直到大于start时停止。然后再重复找完全平方数-依次向前赋值的流程，当所有位置都填上数后即是答案。

正确性：假设每一轮步骤将k到k+t的位置元素依次赋值为k+t~k，那么k到k+t这段区间上res的值一定时k+t到k，而到k-1位置时，因为完全平方数x-(k-1)一定小于等于k-1，因此不会用到已经用过的元素，所以正确

代码：

void slove(){
   int n;
   cin>>n;
   int q[n];
   _for(i,0,n)q[i]=i;
   int res[n];
   int maxn=n-1;
   int i=n-1;
   while(i>=0){
    int start;
    for(int j=0;;j++){
        if(j*j>=i){
            start=j*j-i;
            break;
        }
    }
    int mm=i;
    while(start<=mm){
        res[i--]=start++;
    }
   }
   _for(i,0,n)cout << res[i] << " ";
   cout << endl;
}

D. Tournament Countdown

思路：因为题目给的询问次数最多为1/3*2^(n+1)=2/3*2^n且一共有2^n个元素，最后要只剩下一个赢的次数最多的元素，因此可以猜测正确的解法应该是每2次询问能够排除掉3个元素，因为连续的4个人只有一个能胜出，因此考虑是否能通过2次查询找到4个人中的胜者，即排除掉3个人，这样刚好用2*(2^n/3)次因为12是一组，34是一组，因此可以先询问13，假设1>3，那么可以排除掉23，因为如果12中是2胜的话，那么会有1=3，然后再判断14即可。如果1=3，则胜者一定是在24之间，判断即可。另外2^n一定是4的倍数或者2，所以每次可以让剩余可能的人数/4，因为2^n是偶数，因此/2^2最后要么为2^0=1要么为2^1=2，为2的时候特殊处理下即可。

代码：

void slove(){
   int n;
   cin>>n;
   int res;
   vector<int> v;
   _fore(i,1,1<<n)v.pb(i);
   while(v.size()>1){
    vector<int> tv;
    if(v.size()==2){
        cout << "? " << v[0] << " " << v[1] << endl;
        int x;
        // if(f[v[0]]<f[v[1]])x=1;
        // else if(f[v[0]]==f[v[1]])x=0;
        // else x=2;
        cin>>x;
        if(x==1)res=v[0];
        else res=v[1];
        break;
    }
    int sz=v.size();
    for(int i=0;i<sz;i+=4){
        int mmax1=v[i];
        int mmax2=v[i+2];
        cout << "? " << mmax1 << " " << mmax2 << endl;
        int x;
        cin>>x;
        // if(f[mmax1]<f[mmax2])x=1;
        // else if(f[mmax1]==f[mmax2])x=0;
        // else x=2;
        if(x==1)mmax2=v[i+3];
        else if(x==0){
            mmax1=v[i+1],mmax2=v[i+3];
        }
        else mmax1=v[i+1];
        cout << "? " << mmax1 << " " << mmax2 << endl;
        cin>>x;
        // if(f[mmax1]<f[mmax2])x=1;
        // else if(f[mmax1]==f[mmax2])x=0;
        // else x=2;
        int tem;
        if(x==1)tem=mmax1;
        else tem=mmax2;
        tv.pb(tem);
    }
    v=tv;
   }
   if(v.size()==1)res=v[0];
   cout << "! " << res << endl;
}

E. Cross Swapping

思路：根据题意我们可以知道，不管怎么变换，每个元素都只能变到关于主对角线对称的位置或不动。因为要字典序最小，所以我们可以贪心的知道肯定优先让第一行的最小，然后第二行...因此我们考虑的顺序一定是先从(0,0)所在的行列到(1,1)所在的行列到......

定义：交换k表示第k行和第k列的元素一一交换

现在来考虑交换的情况，我们假设，t1=a[j][i],t2=a[i][j],(i<j)

1. t1<t2，此时我们一定要交换，要么交换i，要么j
2. t1=t2，交不交换无所谓
3. t1>t2，此时我们一定不要交换，或者交换i且交换j

如果只是简单贪心的交换两个位置就简单了，但是我们可以发现交换两个元素的同时还会影响到其它元素

同时我们发现，对其中交换的选择只有俩种，要么一个换一个不换，要么俩个都换或都不换，因此可以用带权并查集或带扩展域并查集来写

同时有个小技巧，即最后求出了所有相对关系后，怎么确定哪些行要换，这里可以按顺序将所有可以做的操作集合全部合并到0所带领的操作集合，这样最后看k可以取的值，就是看是不是在0的操作集合中，处理的步骤其实就是令和0没有关系的元素合并到0所在的集合中，并令某个元素的选择情况和p[0]相同，这样这个原本与0所在集合不相关的集合的选择情况就都确定了，最后将0~n-1中在0所在集合的都换或都不换即可，或者不用0，用n也一样的

代码：扩展域并查集

int p[2000];

int find(int u){
    if(p[u]!=u)p[u]=find(p[u]);
    return p[u];
}

void slove(){
   int n;
   cin>>n;
   int q[n][n];
   _for(i,0,n){
    _for(j,0,n)cin>>q[i][j];
   }
   _for(i,0,2*n)p[i]=i;
    _for(i,0,n){
        _for(j,i+1,n){
            int pi=find(i),pj=find(j);
            int pii=find(i+n),pjj=find(j+n);
            if(q[j][i]<q[i][j]){
                if(pi==pj||pii==pjj)continue;
                else{
                    p[pi]=pjj;
                    p[pj]=pii;
                }
            }
            else if(q[j][i]>q[i][j]){
                if(pi==pjj||pj==pii)continue;
                else{
                    p[pi]=pj;
                    p[pii]=pjj;
                }
            }
        }
    }
    _for(i,0,n){
        if(find(i)!=find(0)&&find(i+n)!=find(0)){
            p[find(i)]=find(0);
            p[find(i+n)]=find(n);
        }
    }
    _for(i,0,n){
        if(find(i)!=find(0)){
            _for(j,0,n){
                swap(q[i][j],q[j][i]);
            }
        }
    }
    _for(i,0,n){
        _for(j,0,n){
            cout << q[i][j] << " ";
        }
        cout << endl;
    }
}