题解：CF2108D Needle in a Numstack

中考前最后一场 CF（指的是我回归文化课以前的最后一场）的好题。

拖得也有个半年了。

首先不难发现

a

和

b

肯定都是有循环的。设循环节为

k

则

a_1

一定等于

a_{k+1}

，因为

a_{[2,k]}

都相等且

a_{[1,k]}

和

a_{[2,k+1]}

在重排后意义相同。

首先询问

a

的前

k

个数和

b

的后

k

个数，找到

a

和

b

分别的循环节。如果两个循环节可以直接拼在一起，说明是可以任意分割出

a

和

b

的，只要

|a|,|b|\ge k

即可。该部分询问有

2k

次。

考虑二分得到

a,b

的大概分界点。直接选一个可以使序列有多种形态的位置（指的是

a,b

拼起来后模

k

同余且值不同的位置）。二分出这里的位置

x

，

a,b

的分界一定在

[x-k,x+k]

之间。对有多种形态的位置进行询问，得到可能的分界点。

总询问次数

4k+\log n

次。被题解区神仙吊打。

CPP

#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
	int a=0,b=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')	b=-1;
		c=getchar();
	}
	while(isdigit(c)){
		a=(a<<1)+(a<<3)+(c-'0');
		c=getchar(); 
	}
	return a*b;
} 
inline void write(int x){
	if(x<0)	putchar('-'),x=-x;
	if(x>=10)	write(x/10);
	putchar(x%10+48);
}
inline void write1(int x){
	write(x),putchar(' ');
}
inline void write2(int x){
	write(x),putchar('\n');
}

//似乎是一个 4k+log n  的做法，记录一下 

const int N=460;
const int M=1919810;
int query[N];
int query1[N];

int ans[M];

//int sol[N];	//代表哪些位置是我们可以去处理的  
int sol_first;
int sol_lst;	//代表与 sol_first 相对的值  
int n,k; 
int idx;

int sum_;	//	节数  
void solve(){
	idx=0;
	sol_first=1e18;
	n=read(),k=read();
	sum_=n/k +(n%k!=0);
	if(n==k*2){
		putchar('!'),putchar(' '),write1(k),write2(k);
		fflush(stdout); 
		return;
	}
	for(int i=n-k+1;i<=n;i++){
		//现在查询的 
		putchar('?'),putchar(' '),write2(i);
		fflush(stdout); 
		query[++idx]=i;
		query1[idx]=read();
		ans[i]=query1[idx];
		int j=i%k;
		if(j==0)	j=k;
		putchar('?'),putchar(' '),write2(j);
		fflush(stdout);
		query[++idx]=j;
		query1[idx]=read();
		ans[j]=query1[idx];
		if(ans[i]!=ans[j]){
			if(sol_first>j){
				sol_first=j;
				sol_lst=i;
			} 
		}
	}
	if(sol_first>1e16){
		putchar('!'),putchar(' '),write2(-1);
		fflush(stdout);
		return;//无法确定  
	}
	int l=1,r=(sol_lst-sol_first)/k+1;
	int mid=l+r>>1;
	while(l<r){
		int now=(mid-1)*k+sol_first;	//代表目前的位置 
		putchar('?'),putchar(' '),write2(now);
		fflush(stdout);
		query[++idx]=now;
		query1[idx]=read();
		ans[now]=query1[idx];
		if(ans[now]==ans[sol_first])	l=mid+1;
		else r=mid;
		mid=l+r>>1;
	}
//	cout<<'#'<<mid<<endl;
	//现在用了 2k+log 次询问  
	mid=(mid-1)*k+sol_first;	//代表目前所在的位置 
	
	int max_left=k,min_right=n-k+1; //如果 max_left 和 min_right 之间存在值 就为 -1  
	for(int i=min(mid+k,n-k);i>=max(k,mid-k);i--){
		//判断所有的位置和前后是否相关 
		int l=i%k;
		int r=l+sum_*k;
		if(l==0)	l=k;
		while(r>n)	r-=k;
		if(ans[l]==ans[r])	continue;	//说明这里进行询问没有意义  
		putchar('?'),putchar(' '),write2(i);
		fflush(stdout);
		query[++idx]=i;
		query1[idx]=read();
		ans[i]=query1[idx];
		if(ans[i]==ans[l]){
			//代表这里是左翼的 
			max_left=max(max_left,i); 
		}
		else{
			//右翼 
			min_right=min(min_right,i); 
		}
	} 
	if(max_left==min_right-1){
		putchar('!'),putchar(' '),write1(max_left),write2(n-max_left);
		fflush(stdout);
	}
	else{
		putchar('!'),putchar(' '),write2(-1);
		fflush(stdout);
	}
	for(int i=1;i<=idx;i++){
		ans[query[i]]=0;
		query[i]=0;
		query1[i]=0;
	}
	idx=0;
}
#undef int
int main(){
	#define int long long
	int T=read();
	while(T--)	solve();
	putchar('\n');
	return 0;
} //一定要挽回罗琪钧的遗憾啊，一定会挽回罗琪钧的遗憾的！

题解：CF2108D Needle in a Numstack

文章操作

相关推荐

评论

题解：CF2108D Needle in a Numstack