P11647 题解

· · 题解

不妨假设所有 a_i 和 a_i+a_j 互不相等，数据随机，显然冲突的概率极低。

正解数据范围：n\ge 5，两次询问，每次询问不超过 n-1 个点对，所有点对互不相等。

一个想法是第一次问一个菊花，第二次问一个环，但这样只能确定第一个位置的值，以及后面的位置组成的集合。

考虑把环上 (1,2) 的询问和菊花上 (0,n-1) 的询问交换，这样只要我们能够正确地把它们换回来，就能用这个信息唯一确定环上节点的顺序。

正确地把它们换回来的方法也很简单，就是枚举所有可能的方案，首先 a_0 需要是整数，其次后面的部分需要能够正确地连成一个环，最后这个环上需要有相邻的 (1,2) 和 n-1。

直接做似乎是 O(n^4) 的，不可接受。然而，第一步的正确概率在 \frac{1}{n} 级别，这样复杂度就优化到了 O(n^3)；同时，如果发现连不成环可以在循环中途跳出，因此这个复杂度跑不满。

正确率我不太会算，但数据范围 n=500,V=10^{18},T=20，这样的话 \frac{n^5}{V} 级别的错误概率也是可以接受的；同时，在本地用 0x66CCFF 的种子随机了 2\times 10^5 组极限数据全部正确，所以没啥过不去的道理。

#include"kiwi.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=507;
ll to[N][N],deg[N],U,V;
unordered_map<ll,ll> mp;
__int128 sA,sB;
vector<ll> game(int n){
    vector<ll> ans(n,0),A,B;
    vector<int> qx(n-1),qy(n-1);
    for (int i=1;i<n-1;++i) qy[i-1]=i;
    qx[n-2]=1;qy[n-2]=2;
    A=ask(qx,qy);
    qy[n-2]=n-1;
    for (int i=1;i<n-2;++i){
        qx[i]=i+1;qy[i]=i+2;
    }
    qy[0]=n-1;
    B=ask(qx,qy);
    sA=sB=0;
//  for (int i=0;i<n-1;++i) cout<<A[i]<<' ';cout<<endl;
//  for (int i=0;i<n-1;++i) cout<<B[i]<<' ';cout<<endl;
    for (int i=0;i<n-1;++i){
        sA+=A[i];sB+=B[i];
    }
    for (int i=0;i<n-1;++i) for (int j=0;j<n-1;++j){
        __int128 sumA=sA-A[i]+B[j],sumB=sB-B[j]+A[i];
        if ((sumB%2==0)&&(sumA-sumB/2)%(n-1)==0){
            ans[0]=(sumA-sumB/2)/(n-1);
//          cout<<i<<' '<<j<<' '<<ans[0]<<endl;
            swap(A[i],B[j]);
//          for (int i=0;i<n-1;++i) cout<<A[i]<<' ';cout<<endl;
//          for (int i=0;i<n-1;++i) cout<<B[i]<<' ';cout<<endl;
            for (int k=1;k<n;++k) deg[k]=0;
            int cnt=0;mp.clear();
            for (int k=0;k<n-1;++k) mp[B[k]]=k;
            bool fl=1;
            for (int o=1;o<n;++o){
                for (int p=o+1;p<n;++p) if (mp.find(A[o-1]+A[p-1]-2*ans[0])!=mp.end()){
                    ++cnt;
                    to[o][deg[o]++]=p;to[p][deg[p]++]=o;
                    if (mp[A[o-1]+A[p-1]-2*ans[0]]==j) U=o,V=p;
                }
                if (deg[o]!=2){
                    fl=0;break;
                }
            }
            if (!fl){
                swap(A[i],B[j]);continue;
            }
            if ((to[V][0]^to[V][1]^U)==i+1) swap(U,V);
            if ((to[U][0]^to[U][1]^V)!=i+1){
                swap(A[i],B[j]);
                continue;
            }
            ans[n-1]=A[i]-ans[0];
            ans[1]=A[U-1]-ans[0];
            ans[2]=A[V-1]-ans[0];
            for (int i=3;i<n-1;++i){
                U=to[V][0]^to[V][1]^U;swap(U,V);
                ans[i]=A[V-1]-ans[0];
            }
            return ans;
        }
    }
    return vector<ll>(n,-1);
}