これこそシュタインズ・ゲートの选択だ

20191002训练 T1 小Y增员操直播群

20191002训练 T1 小Y增员操直播群

对于一个大小为n的图,考虑如何组成它。 考虑编号为n-1的点,它连到的编号最小的节点一定是在最后一次合并时连的,假设为x

那么n-x-2这个点连的一定是左边一半最大的点。(n-1)%y=x\ (n-x-2)%y=y-1

于是可以得到左边一半的size。 然后按规则拆分即可。

在这个过程中,出现任何矛盾即无解。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
	int s=0;char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) s=s*10+ch-'0',ch=getchar();
	return s;
}
const int N=100005;
int T,n,m;
vector<int> G[N];
inline int cmp(int a,int b){return a>b;}
inline int solve(int l,int r){
	if(l==r&&!G[r].size()) return 0;
	if(l>r||!G[r].size()) return -1;
	int mid=G[r].back();
	if(mid-l+1>r-mid||mid<l) return -1;
	if(mid-l+1<r-mid){
		int p=r-(mid-l+1);
		if(!G[p].size()) return -1;
		if(G[p].back()<mid) return -1;
		mid=G[p].back();
	}
	for(int i=r;i>mid;i--){
		if(!G[i].size()) return -1;
		if((i-l)%(mid-l+1)!=G[i].back()-l) return -1;
		G[i].pop_back();
	}
	int a1=solve(l,mid),a2=solve(mid+1,r);
	if(a1==-1||a2==-1) return -1;
	return max(a1,a2)+1;
} 
int main(){
	T=read();
	while(T--){
		n=read(),m=read();
		for(int i=0;i<n;i++) G[i].clear();
		for(int i=1;i<=m;i++) {
			int u=read(),v=read();
			if(u<v) swap(u,v);
			G[u].push_back(v);
		}
		for(int i=0;i<n;i++) sort(G[i].begin(),G[i].end(),cmp);
		printf("%d\n",solve(0,n-1));
	}
	return 0;
}

 



发表评论

电子邮件地址不会被公开。 必填项已用*标注