2025 SC省队集训相关题目

首先我们考虑什么情况下需要输出Impossible。
坏人可以说谎，也就意味着它可以伪装成好人，那么当 \(a\le b\) 的时候，我们让 \(a\) 个坏人伪装成好人就无法分辨了。

现在我们只需要考虑 \(a>b\) 的情况。我们现在列一张表，表示向 A 询问 B 时的可能情况。

可以发现，当回答为N时，两个人中至少有一个坏人。而当回答为Y的时候，B 的身份一定不劣于 A。
于是我们考虑维护一个栈，栈的最顶层时我们当前已知的最好的人（这个人可能是坏人）。用栈顶的人去问当前的人 C，如果回答为N，直接将这两个人都当成“坏人”就好了，因为 \(a>b\)，所以哪怕每次回答均为N，也是坏人先去除完。
而回答为Y时，直接将其设为新的栈顶就好了。

这样，最后我们的栈顶一定是好人（这个的证明是并不困难的），我们再用这个好人挨个挨个询问，就可以知道每个人的身份了。

前面问至多 \(n-1\) 次，后面问 \(n\) 或者 \(n-1\) 次，总共不多于 \(2n\) 次，可以通过。

// Problem: AT_arc070_d [ARC070F] HonestOrUnkind
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_arc070_d
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,a,b;
bool ans[MAXN];
char res;
stack<int> s;

void query(int x,int y){
    cout<<"? "<<x<<" "<<y<<endl;
    cin>>res;
}

signed main(){
    cin>>a>>b;
    if(a<=b){
        cout<<"Impossible";
        return 0;
    }
    n=a+b;
    for(int i=0;i<n;i++){
        if(s.empty()) s.push(i);
        else{
            query(s.top(),i);
            if(res=='N') s.pop();
            else s.push(i);
        }
    }
    ans[s.top()]=true;
    for(int i=0;i<n;i++){
        if(i==s.top()) continue;
        query(s.top(),i);
        ans[i]=res=='Y';
    }
    cout<<"! ";
    for(int i=0;i<n;i++) cout<<ans[i];
    cout<<endl;
    return 0;
}

一些性质

因为交互库有些是自适应的，所以很难利用被控制的位置来传递信息。那么对于一个数据包，我们就只能传输 \(16\) 位有效信息。
注意到如果我们发送的 \(A\) 全为同一个数，篡改后的消息 \(B\)，我们统计一下众数，发现和 \(A\) 的众数是一样的。

\(10\) 分做法

根据上文性质，我们可以挨个挨个发送 \(M\) 的内容，总共发送 \(S\) 个数据包，可以通过第一个子任务。

\(29\) 分做法

消息长度是不固定的，我们不妨将所有消息的长度补充至 \(1025\)。具体怎么补充？我们在消息最后加入一个 \(1\) 以及一串 \(0\)，并且令最后一个 \(1\) 及以后的消息均无效。

先前 \(10\) 分的做法太不优秀了，我们没有充分利用有效位置。如果我们已经知道了有效位置有哪些，便可以用 \(\left\lceil\dfrac{1025}{16}\right\rceil=65\) 次来发送所有消息。
不难想到我们沿用 \(10\) 分的做法，使用 \(31\) 次将 \(C\) 发送出去。然后再使用 \(65\) 次将 \(M\) 发送过去。
总共需要发送 \(96\) 次，能获得 \(29.317\) 分。

\(58\) 分做法

我能想到的最优做法。（我还是太菜了/kk）

我们 \(30\) 分的做法在发送完 \(C\) 后，才开始使用有效位置发送信息，但实际上，我们在发送出第一个有效位置后，便可以使用这个位置来发送信息了。后面解锁更多有效位置后，就可以一次发送更多有效信息。
并且我们假如当前已经发送了 \(15\) 个 \(1\) 或是 \(16\) 个 \(0\)，也就不需要继续发送 \(C\) 了。
根据 \(C\) 的情况也可以调整顺序发送 \(C\) 或者是逆序发送 \(C\)，最劣的情况应该是 0111111100000000000000111111110，总共需要发送 \(\left\lceil\dfrac{1025-9}{16}\right\rceil+13+1=78\) 次。能获得 \(58.632\) 分。
多一次是因为还需要发送 \(C\) 的方向。

\(66\) 分做法

我们可以对上述做法进行一个优化。
我们在找到第一个有效位置前，利用的是众数的性质，此时所有有效位置均被利用了。而我们在找到第一个有效位置后，发送信息的一直是当前已知的有效位置，其他未知的有效信息并没有被利用。
实际上，我们最后在还原信息的时候，是可以重复看曾经的消息的，所以我们可以在找到第一个有效位置后，其他的有效位置也开始发送 \(M\)，等到 \(C\) 被彻底还原后，再去读取先前的消息即可。
我们同样可以根据 \(C\) 的情况调整发送方向，这样的最劣情况应该是 1111111000000000000000011111111。需要发送 \(\left\lceil\dfrac{1025-58}{16}\right\rceil+13+1=75\) 次，可以获得 \(66.722\) 分。

不难发现，在找到第一个有效位置后，每个有效位置都发送了有效信息，如果依然按照 \(61\) 分的做法，会很难写。我们不妨就只用一个位置来发送 \(C\)，其余位置发送 \(M\)，所有的有效位置依然都被使用了。次数是 \(\left\lceil\dfrac{1025-23*15}{16}\right\rceil+31+1=75\) 次，得分不变。

\(83\) 分做法

不难发现我们的瓶颈主要在找第一个有效位置。不难发现，我们决定好 \(C\) 的发送方向后，第一个有效位置一定出现在第 \(8\) 位即以前。于是我们便可以通过发送一个值为 \(0\) 到 \(7\) 的数字的二进制来快速找到第一个有效位置，因为不知道方向，所以还需要多发送一个包。
其实也就和每次就从前往后发送 \(C\)，第一个有效位置一定位于第 \(16\) 位以前，发送一个值为 \(0\) 到 \(15\) 的数字的二进制是一样的。
可以再小小优化一下，如果第一个有效位置在第 \(4\) 个以前，直接暴力发送前面几个位置。

最劣的情况出现在第一个有效位置位于第 \(4\) 个位置，总共发送 \(\left\lceil\dfrac{1025-(31-4)*15}{16}\right\rceil+4+(31-4)=70\) 次，可以获得 \(83.305\) 分。

\(83\) 分做法

继续优化，考虑到一次只能发送 \(16\) 个有效位置，而我们在找到第一个有效位置后，已经将所有的有效位置使用了，那么留给我们传输 \(C\) 的有效次数只有 \(66\times16-1025=31\) 次。

而我们当前的做法，只能继续优化获取第一个有效位置所需的数据包的数量。
尝试继续挖掘众数的性质，我们将 \(C\) 拆成 \(16\) 和 \(15\) 两部分，根据鸽巢原理简单分析，一定有一个部分，其中有效位置的数量是大于无效位置数量的。

我们先暴力发送是哪个区间，然后其中有效位置的位置至多为第 \(8\) 位，再用这个区间发送三次找到这个位置，发送这三次的同时用剩下最少 \(3\) 个有效位置发送 \(M\)。
最后用最多 \(28\) 次发送 \(X\)，同时用另外 \(15\) 有效位置发送 \(M\)。
总共需要发送 \(\left\lceil\dfrac{1025-3\times3-28\times15}{16}\right\rceil+1+3+28=70\) 次，看似没有优化。

\(87\) 分做法

我们不妨继续拆分，拆成 \(8,8,8,7\)，也一定有一段的有效位置的数量是大于无效位置数量的。我们先暴力发送两次找到这个区间，然后这段区间，有效位置至多为第 \(4\) 位，和上文类似，我们直接算所需次数。
\(\left\lceil\dfrac{1025-8\times2-29\times15}{16}\right\rceil+2+2+29=69\) 次，可以获得 \(87.163\) 分。

\(95\) 分做法

继续拆，拆成 \(2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1\) 后，依然有一段的有效位置数量是大于无效位置数量的。
如果同样按照上文的思路，计算发现次数大约是 \(70\) 次。
但是我们在传递哪个区间的时候，可以利用类似于二分的思路，众数表示往左边走还是往右边走，每次都可以释放一些有用位置，这样的话，我们至多会浪费 \(16+8+4+2=30\) 个位置，需要 \(67\) 次，可以获得 \(95.5\) 分。

上面的方法利用同样的优化，应该可以做到 \(68\) 次，也就是 \(91.225\) 分。

\(100\) 分做法

上述的做法似乎已经没有办法继续优化了。由前文可知，我们只能只用最多 \(31\) 位有效位置来传输 \(C\)，这个是很困难的。
令人震惊的是，正解和前文的做法几乎没有关系。

我们可以发现，将 \(C\) 首尾相连，形成一个环后，对于每一个有效位置，我们定义 \(f_{i}\)，表示其距离下一个有效位置的距离。如果是无效位置，则 \(f_{i}=0\)，容易得到 \(\sum_{i=1}^{31} f_{i}=31\)。
并且如果我们对于未被篡改的 \(C\) 的所有 \(f_{i}\not=0\)，都将 \(i\) 和 \(i+f_{i}\) 相连，可以得到一个长度为 \(16\) 的环。

那么我们不妨对于每一个位置 \(i\)，其前 \(f_{i}-1\) 次的消息包，这个位置均发送 \(0\)，而第 \(f_{i}\) 次则发送 \(1\)，并且我们定义每个位置第一个获取到 \(1\) 的第几个消息包就是这个点 \(f_{i}\) 的值。

首先，对于有效位置，其 \(f_{i}\) 的值不会被篡改。对于无效位置，其 \(f_{i}\) 可能被篡改，那么我们依然按照先前的方法连边后，会得到一颗基环树森林。并且其中只会存在一个长度为 \(16\) 的环，并且这个环上的点正好就是有效位置！
为什么？因为剩下 \(15\) 个无效位置无论如何都不能连成一个长度为 \(16\) 的环，而有效位置的 \(f_{i}\) 又不会发生改变，原来就能连成环，现在依然可以。

那么，我们一共就浪费了 \(31\) 个有效位置，刚好符合题目要求的 \(66\) 次。

#include "message.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;

//send_packet()

int f[MAXN],F[MAXN],k,head[MAXN],pre[MAXN];
bool vis[MAXN],c[MAXN];
struct node{
    int to,next;
}edge[MAXN];

void build(int u,int v){
    edge[++k].to=v;
    edge[k].next=head[u];
    head[u]=k;
}

void send_message(vector<bool> M,vector<bool> C){
    vector<bool> A[66];
    for(int j=0;j<66;j++) for(int i=0;i<31;i++) A[j].push_back(0);
    M.push_back(1);
    while(M.size()<1025) M.push_back(0);
    int last=-1;
    for(int i=0;i<31;i++){
        if(!C[i]){
            if(~last) f[last]=i-last;
            last=i;
        }
    }
    for(int i=0;i<31;i++){
        if(!C[i]){
            f[last]=i+31-last;
            break;
        }
    }
    int cnt=0;
    for(int i=0;i<31;i++){
        if(!C[i]){
            A[f[i]-1][i]=1;
            for(int j=f[i];j<66;j++) A[j][i]=M[cnt++];
        }
    }
    for(int i=0;i<66;i++) send_packet(A[i]);
}

void dfs(int u){
    vis[u]=true;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(vis[v]){
            int pos=u,cnt=1;
            while(pos!=-1&&pos!=v) cnt++,pos=pre[pos];
            if(pos!=v) cnt=0;
            if(cnt==16){
                pos=u,c[v]=0;
                while(pos!=v){
                    c[pos]=0;
                    pos=pre[pos];
                }
            }
            continue;
        }
        pre[v]=u;
        dfs(v);
    }
}

vector<bool> receive_message(vector<vector<bool> > R){
    vector<bool> ans,ANS;
    for(int i=0;i<31;i++){
        for(int j=0;j<66;j++){
            if(R[j][i]){
                F[i]=j+1;
                break;
            }
        }
    }
    k=0;
    for(int i=0;i<31;i++) head[i]=vis[i]=0;
    for(int i=0;i<31;i++) if(F[i]) build(i,(i+F[i])%31);
    for(int i=0;i<31;i++) c[i]=1,pre[i]=-1;
    for(int i=0;i<31;i++) if(!vis[i]) dfs(i);
    for(int i=0;i<31;i++){
        if(!c[i]){
            for(int j=0;j<66;j++){
                if(R[j][i]){
                    for(int p=j+1;p<66;p++) ans.push_back(R[p][i]);
                    break;
                }
            }
        }
    }
    for(int i=ans.size()-1;i>=0;i--){
        if(ans[i]){
            for(int j=0;j<i;j++) ANS.push_back(ans[j]);
            break;
        }
    }
    return ANS;
}