题解：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 次。被题解区神仙吊打。

#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;
} //一定要挽回罗琪钧的遗憾啊，一定会挽回罗琪钧的遗憾的！