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

ustze.cn

ustze.cn

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

Recent Posts

noi2019游记

noi2019游记

咕咕咕 day -inf 在实验舱集训,遇到好多神题,自闭。 noi.ac rating […]

CF1215E – Marbles

CF1215E – Marbles

题意:给定一个长度为n的序列,每次操作可以交换相邻连个数,求最少需要几次操作使得所有颜色都 […]

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;
}

 

[noi2019]弹跳

[noi2019]弹跳

不知道有没有原题,给人一种非常原题的感觉 因为这个题学了kd-tree,然后就是板题了 # […]

luogu P5072 [Ynoi2015]盼君勿忘

luogu P5072 [Ynoi2015]盼君勿忘

这题有毒….反正我的写法常数巨大 记中出现次数为k的数的和为 则答案显然为 因为值不为0的 […]