Codeforces 1129E - Legendary Tree（思维题）

考虑以 \(1\) 为根，记 \(siz_i\) 为 \(i\) 子树的大小，那么可以通过询问 \(S=\{2,3,\cdots,n\},T=\{1\}\) 以及每个 \(u\) 得出 \(siz_u\) 的值。

考虑将所有点按 \(siz\) 从小到大排序并维护一个集合 \(st\) 表示目前还没有找到父亲的点的集合，那么我们枚举到一个点 \(x\) 时就在 \(st\) 中二分找到所有父亲为 \(x\) 的点并将它们从 \(st\) 中删除，具体步骤是，我们先二分找出 \(st\) 中编号最小的点，即二分出一个 \(mid\) 后就询问 \(S=st\) 中编号最小的 \(mid\) 个点组成的集合，\(T=\{1\}\)，\(u=x\)，如果交互库返回的值 \(>0\) 就向左二分，否则向右二分，二分出第一个后再找第二个、第三个……以此类推。删完这些点之后加入将 \(x\) 加入集合，如此进行下去即可。最后扫描到 \(1\) 时就将 \(st\) 中的点的父亲全部设为 \(1\) 并清空 \(st\)

时间复杂度 \(n\log^2n\)，询问次数 \(n\log n\)，实测在 \(7000\) 左右，可以通过此题的限制。

看到没？什么超纲的算法都没有。所以啊，菜是原罪/kk——Codeforces Round #691 (Div.2) 题解

const int MAXN=500;

int n,siz[MAXN+5],ord[MAXN+5];set<int> st;

bool cmp(int x,int y){return siz[x]<siz[y];}

bool check(int x,int l,int r){

	set<int>::iterator it=st.begin();

	for(int i=1;i<l;i++) ++it;printf("%d\n",r-l+1);

	for(int i=1;i<=r-l+1;i++) printf("%d%c",*it++," \n"[i==r-l+1]);

	printf("1\n1\n%d\n",x);fflush(stdout);

	int t;scanf("%d",&t);return t>0;

}

int main(){

	scanf("%d",&n);siz[1]=n;

	for(int i=2;i<=n;i++){

		printf("%d\n",n-1);

		for(int j=2;j<=n;j++) printf("%d%c",j," \n"[j==n]);

		printf("1\n1\n%d\n",i);fflush(stdout);

		scanf("%d",&siz[i]);

	} for(int i=1;i<=n;i++) ord[i]=i;sort(ord+1,ord+n+1,cmp);

	vector<pii> ans;

	for(int i=1;i<n;i++){

		if(!st.empty()){

			int cur=0;vector<int> son;

			while(cur<st.size()){

				int l=cur+1,r=st.size(),p=st.size()+1;

				while(l<=r){

					int mid=l+r>>1;

					if(check(ord[i],cur+1,mid)) p=mid,r=mid-1;

					else l=mid+1;

				} if(p!=st.size()+1){

					set<int>::iterator it=st.begin();

					for(int j=1;j<p;j++) ++it;

					son.pb(*it);

				} cur=p;

			} for(int x:son) st.erase(st.find(x)),ans.pb(mp(x,ord[i]));

		} st.insert(ord[i]);

	} printf("ANSWER\n");

	for(int x:st) ans.pb(mp(x,1));

	for(pii p:ans) printf("%d %d\n",p.fi,p.se);

	fflush(stdout);

	return 0;

}

巴特西

Codeforces 1129E - Legendary Tree（思维题）

最新文章

热门文章