题解：P12400 [COI 2025] 人工智能 / Automatizacija（暂时无法评测）

· · 题解

终于弄懂了，太妙了！

千万不要想歪了，考虑直接让先手完整告诉后手自己的集合。对于一个数 x，先手在位置为 x 处做一个标记。

但是一个问题：由于每次双方都必须选择一个格子进行染色，当后手选择的位置恰好与先手的某个位置重复时就麻烦了。举个例子，n=7,k=3，先手的集合是 \{1,2,3\}。当先手传了一个 1 过去（给格子 1 打上标记）的时候，后手需要进行一次操作，一不小心选择了 2 这个位置，那么下一步先手就无法标记 2 这个格子了，后手也就永远无法知道先手的集合中到底有没有 2 了，也自然无法求交。

现在，我们希望后手进行的这些无意义的操作都不要干扰到先手的操作，也就是后手选择的格子都和先手选择的格子不同。这看上去几乎不可能做到。很显然，如果先手按照任意顺序染色的话，肯定是无法完成任务的，因为这样以来后手只能瞎猜凭运气。

为了让这一点可能做到，首先一个必要条件就是 k\le \frac{n}{2}，否则必然会出现重复。但是如果输入里面 k>\frac{n}{2} 怎么办呢？其实也很简单，只要让先手传补集就行了。具体来说：先手传输自己集合的补集给后手。由于后手也知道 k>\frac{n}{2} 时先手传的是补集，所以他也心领神会，可以轻松求出先手的原集。

很好，接下来我们只需处理 k\le \frac{n}{2} 的情况就行了。

我们先想想，最直观、简单的方法是什么？先手从小到大传自己的数，后手填充最左侧的空的位置，如此进行。但是这显然会出现问题。比如，先手的集合是 \{1,2\}，先手传了 1，后手涂了 2，然后就重复了。

先手从小到大传自己的数也太傻了！实际上，我们可以把先手集合中的数排成一个环形。比如说，n=8，先手手中的数是 \{1,2,3,5\}，我们不按照 1-2-3-5 的顺序传，我们按照 3-5-1-2 的顺序传。这个时候，如果后手能知道整个序列是以 3 开头的，就会发生如下神奇的事情：

完美完成了任务！

可惜的是，我们还需要解决以下两个问题：

  1. 在 k 种传输顺序中，一定存在一种使得可以满足我们的需求吗？
  2. 后手怎么知道下一个空位是啥？我们只能知道当前的状态啊，更不可能知道先手选的起点是啥。

第二个问题是很容易解决的。双方填数的编号一定是从 i\sim n，再从 1\sim i-1。如果编号最大的一个空位到编号为 n 的所有位置中还没有出现后手标记的记号，说明后手还在 i\sim n 这个阶段，直接找出编号最大的有后手标记的位置后面第一个空位即可；否则，后手已经在 1\sim i-1 这个阶段了，直接找出编号最小的空位即可。特别地，需要处理一下第一步时（没有后手标记）的 case。

关键是第一个问题，在 k 种选择起点的方式中，我到底应该选择哪一个？

如果一个起点是合法的，开头是 s，我们记红色的数是先手集合中有的，灰色的是先手集合中没有的。所以开头一定是红色的数。

我们举个例子吧！比如 a=[1,2,5],n=6,k=3，开头是 s=5。那么这个时候，数的颜色就分别是 \textcolor{red}{5}~\textcolor{gray}{6}~\textcolor{red}{1}~\textcolor{red}{2}~\textcolor{gray}{3}~\textcolor{gray}{4}。后手选的数可以是红色也可以是灰色（空位的定义是没被选过，如果一个红色没被选过，后手也会对红色进行操作）。我们不想让后手操作到红色。比如，我们需要判断后手是否会操作到红色的 2，如何判断呢？我们只要判断在 5,6,1,2 这个前缀除去开头 5 后，灰色的位置个数是否 \ge 红色的位置个数即可。

我们解释一下。如果灰色的位置个数 < 红色的位置个数，显然这个红色的位置会被后手率先抢到。因为先手还没拿完前面的红色，后手就已经拿完了所有灰色，所以后手只能拿红色了。比如在这个例子中，先手拿到了 5，后手拿到了 6，先手拿到了 1，此时由于灰色的位置个数过少，后手就可以拿到这个 2 了。如果换个情况就完全不一样了：如果变成 \textcolor{red}{5}~\textcolor{gray}{6}~\textcolor{red}{1}~\textcolor{gray}{2}~\textcolor{red}{3}~\textcolor{gray}{4}，此时灰色的位置个数 \ge 红色的位置个数，那么先手拿到 1 之后，后手还能拿一个 2，这样后手就不会拿到红色的 3 了。

我们就可以把他视为一条路径，x,y 坐标分别为除去开头后，红色的位置个数和灰色的位置个数。

开头相当于是 (0,0)。随后每一步，如果遇到一个红色的位置，位置 (x,y) 会变成 (x+1,y)，否则会变成 (x,y+1)。整个路径始终不能使得 x>y，即越过直线 x=y。

一个经典操作是，我们将坐标系转化为：(x,y)\to (x+y,y-x)。开头你在 (0,0)，随后每一步，如果遇到一个红色的位置，位置 (x,y) 会变成 (x+1,y-1)，否则会变成 (x+1,y+1)。整个过程不能使得 y<0。

我们考虑以 1 为起点顺次遍历整个环，记点 i 处的前缀和为 pre_i。可以证明，选择 pre_i 最小的那个点一定满足条件。证明：考虑 i\to j 的路径，如果 j>i，那么由于 pre_j-pre_i\ge 0，必然成立；如果 j<i，那么 pre_j+pre_n-pre_i\ge 0，由于 k\le \frac{n}{2}，有 pre_n\ge 0，故必然成立。

所以，起点就被定下来了，整个问题也得到了完美的解决。

给出我的代码，是目前 QOJ 最短解（再过几天就肯定要被超越了）。注意：这份代码是 QOJ 上的输入/输出格式，和洛谷上的输入/输出格式有所不同，思路完全遵循上述题解。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F(i, a, b) for (int i = (a); i <= (b); i ++ )
#define DF(i, a, b) for (int i = (a); i >= (b); i -- )
const int N=100;
int op,n,k,a[N],st[N],v[N],pre[N],sz,f=0;
char ch[N];
void pt(int x){
    if(ch[x]=='.')cout<<"+ "<<x<<endl;
    else F(i,1,n)if(ch[i]=='.')return cout<<"+ "<<i<<endl,void();
}
void solve(){
    F(i,1,n)cin>>ch[i];
    int cc=0;F(i,1,n)cc+=ch[i]!='.';if(cc==n)return cout<<"! "<<n<<endl,void();
    int cnt=0;F(i,1,n)cnt+=ch[i]=='P';
    if(op==2&&k==n||op==1&&cnt>=sz)return cout<<"! "<<n<<endl,void();
    if(op==2&&(cnt==k||cnt==n-k)){
        int res=0;
        if(f){F(i,1,n)if(ch[i]!='P')res+=st[i];}
        else{F(i,1,n)if(ch[i]=='P'){res+=st[i];}}
        cout<<"! "<<res<<endl;return;
    }
    if(op==1)return pt(v[cnt+1]);
    int blk=0;F(i,1,n)if(ch[i]=='.')blk=i;
    int fl=0;F(i,blk+1,n)if(ch[i]=='C')fl=1;
    if(cnt==1)F(i,1,n)if(ch[i]=='P')return pt(i+1);
    if(!fl){
        int pos=0;F(i,1,n)if(ch[i]=='C')pos=i;
        int pos2=0;F(i,pos,n)if(ch[i]=='.')return pt(i);
        cout<<"+ "<<pos2<<endl;
    }else pt(0);
}
signed main()
{
    cin>>op>>n>>k;F(i,1,k)cin>>a[i];
    f=k>n/2;
    if(op==1&&k>n/2){
        F(i,1,k)st[a[i]]=1;int cc=0;
        F(i,1,n)if(!st[i])a[++cc]=i;k=cc;
        memset(st,0,sizeof st);
    }
    F(i,1,k)st[a[i]]=1;sort(a+1,a+k+1);
    F(i,1,n)pre[i]=pre[i-1]+(st[i]?-1:1);
    int res=1e18,p=0;F(i,1,n)if(st[i]&&pre[i]<res)res=pre[i],p=i;
    F(i,1,k)if(a[i]>=p)v[++sz]=a[i];
    F(i,1,k)if(a[i]<p)v[++sz]=a[i];
    int T;cin>>T;while(T--)solve();
    return 0;
}

有问题可以评论或私信哦！