【学习笔记】CF1299

计算几何我是真不会

我们要求的点集其实是{(x,y)∣(x,y)=(xi,yi)−(xj,yj),i≠j}\\{(x_,y)|(x,y)=(x_i,y_i)-(x_j,y_j),i\\ne j\\}{(x,​y)∣(x,y)=(xi​,yi​)−(xj​,yj​),i=j}，然后把这个点集再求一个凸包过后和原来的$P$相似。显然点集是关于原点对称的，所以只需判断$P$是否为中心对称图形即可。

麻了，怎么突然就变成*3000了

打表发现252^525内本质不同的线性基数目只有$374$种（其实看到$w$的范围应该就能想到暴搜吧），于是这道题就变成了$dp$套$dp$的板题。唯一的难度在于代码实现。

难泵，感觉每道题都挺麻烦的，不过可能这才是$\text{oi}$的真实风格吧。

非常运气的尝试。因为$N$是偶数，所以询问所有大小为$N-1$的子集$S$，答案为Yes当且仅当 $S$是一段连续的数字，可以把$1,N$的位置确定出来。由于$N-2$仍为偶数，因此同样可以通过询问大小为$N-3$的子集把$2,N-1$确定出来，这带来了操作数O(N2)O(N^2)O(N2)的做法。值的一提的是，我们可以假装能够把$1,N$确定出来，把每个数和$1$放在一起询问就能知道其奇偶性，这样就可以把每个数具体区分出来了。

考虑求出一个数模$3,5,7,8$的答案，因为$3\times 5\times 7\times 8=840>800$，所以我们可以用中国剩余定理合并得到确切的数字。

具体怎么做呢，应该注意到的是，将$x$与$k-1$种模$k$不同余的$k-1$元组放在一起询问，就能确定$x\mathrm{mod}k$的值。那么我们可以先把$1,2,3,4,N-3,N-2,N-1,N$求出来，利用这些已知的值，我们可以拼凑得出每个数模$3,5,7$的值。对于模$8$的值，显然我们仍然可以这样做，但是如果我们仔细去计算总操作数的话，应该为$18.5n$次（具体比较繁琐就不展示了），不过对于模$8$我们可以通过倍增来处理。从模$2$倍增到模$4,8$只需要询问$2$次，这样总操作数约为$16n$。

每个细节都刚刚好，就很离谱。

说实话这道题代码的实现还是考察细节，其实思维难度也不是很大

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N=805;
int n,odd[N],res[N],one;
int point[10],cnt,mark[10];
vector<int>vec;
int ask(){cout<<"?"<<" "<<vec.size()<<" ";for(auto x:vec)cout<<x<<" ";cout<<endl;int ok;cin>>ok;return ok;
}
void output(){if(res[1]>n/2){for(int i=1;i<=n;i++){res[i]=n-res[i]+1;}}cout<<"!"<<" ";for(int i=1;i<=n;i++)cout<<res[i]<<" ";cout<<endl;exit(0);
}
int mod3(int x){memset(mark,0,sizeof mark);int tot=0;for(int i=1;i<=4;i++){for(int j=i+1;j<=4;j++){int num=(9-i-j)%3;if(!mark[num]){vec.clear();vec.pb(point[i]),vec.pb(point[j]),vec.pb(x);if(ask()){return num;}mark[num]=1;if(++tot==2){for(int i=0;i<3;i++){if(!mark[i])return i;}}}}}
}
int mod5(int x){memset(mark,0,sizeof mark);int tot=0;for(int i=5;i<=8;i++){int num=(4-(n-8+i)%5)%5;if(!mark[num]){vec.clear();vec.pb(point[1]),vec.pb(point[2]),vec.pb(point[3]),vec.pb(point[i]),vec.pb(x);if(ask()){return num;}mark[num]=1;if(++tot==4){for(int i=0;i<5;i++){if(!mark[i])return i;}}}}
}
int mod7(int x){memset(mark,0,sizeof mark);int tot=0;for(int i=1;i<=4;i++){for(int j=5;j<=8;j++){int num=(7-(4*n+4-i-(n-8+j))%7)%7;if(!mark[num]){vec.clear();for(int k=1;k<=8;k++){if(k!=i&&k!=j)vec.pb(point[k]);}vec.pb(x);if(ask()){return num;}mark[num]=1;if(++tot==6){for(int k=0;k<8;k++){if(!mark[k])return k;}}}}}
}
int mod8(int x){int val=odd[x];for(int i=1;i<=4;i++){if((10-i+val)%4==0){vec.clear();for(int j=1;j<=4;j++){if(i!=j)vec.pb(point[j]);}vec.pb(x);if(!ask()){val+=2;}break;}}for(int i=1;i<=4;i++){int num=(4*n+4-i)%8;if((val+num)%4==0){vec.clear();for(int j=1;j<=8;j++){if(i!=j){vec.pb(point[j]);}}vec.pb(x);if(((val+num)%8==0)^ask())val+=4;return val;}}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;if(n==2){res[1]=1,res[2]=2;output();}for(int i=1;i<=n;i++){vec.clear();for(int j=1;j<=n;j++){if(i!=j)vec.pb(j);}if(ask()){if(!point[1])point[1]=i,res[i]=1;else point[8]=i,res[i]=n;}}for(int i=1;i<=n;i++){if(i!=point[1]&&i!=point[8]){vec.clear();vec.pb(i),vec.pb(point[1]);odd[i]=ask();}}for(int i=2;i<=min(4,n/2);i++){for(int j=1;j<=n;j++){if(!res[j]){vec.clear();for(int k=1;k<=n;k++)if(k!=j&&!res[k])vec.pb(k);if(ask()){if(odd[j]==i%2){point[i]=j;}else{point[8-i+1]=j;}}}}res[point[i]]=i,res[point[8-i+1]]=n-i+1;}if(n<=8){output();}for(int i=1;i<=n;i++){if(!res[i]){int a=mod3(i),b=mod5(i),c=mod7(i),d=mod8(i);for(int j=1;j<=n;j++){if(j%3==a&&j%5==b&&j%7==c&&j%8==d){res[i]=j;break;}}}}output();
}