题解 CF1137D 【Cooperative Game】

2019-03-11 08:46:02


(前言

由于之前做过的交互题都是和倍增/二进制有关,本题给出了 $10$ 个点,而且 $\log_2 1000$ 也恰好是 $10$ ,于是就这样陷进去了…

题解

实际上我们只需要 $3$ 个点就能解决本题的问题,我们可以把这 $10$ 个点分为 $0,1,23456789$ 三个部分。

首先让 $0$ 每走 $2$ 步, $1$ 走一步。当 $0,1$ 相遇时环长即为 $0$ 走过的距离减去 $1$ 走过的距离。每次 $0$ 总比 $1$ 快一步。除了一种情况以外,环长也等于 $1$ 走过的步数。这叫做Floyd判环

一种情况:

如果下一步是 $0,1$ 一起走的话,那么 $0$ 走的步数就不恰好是 $1$ 走的步数的两倍了,因此需要判一下。

此时我们知道 $0,1$ 在环上的某个点相遇了。我们现在知道了环长 $c$ 和链长 $t$ ,但是我们不知道 finish vertex 在哪里。

我们为了让 $01$ 与 $23456789$ 在 finish vertex 相遇,我们可以构造出环上的一个点。设 $1$ 号棋子已经走了 $m$ 步,因此令 $01$ 在环上“倒退 $m$ 步”,也就是前进 $-m\pmod c$ 步,此时就和 $23456789$ 同步了。我们发现,环长一般情况下也恰好是 $m$ (特殊情况是 $m+1$ ,让 $01$ 先走一步就可以了),然后让 $0123456789$ 同时移动。

最终所有点相遇的地方就是 finish vertex 了。输出 done 即可。

一般情况下步数为 $2(t+c)-1$ ,上面提到的情况步数为 $2(t+c)$ 。

代码

#include<cstdio>
#include<cstring>
#include<vector>
//#define wjyyy
char s[100];
int main()
{
    int sum=0,n,p=0;
    while(++p)
    {
        printf("next 0 ");
        if(!(p&1))
        {
            printf("1");
            ++sum;
        }
        puts("");
        #ifndef wjyyy
            fflush(stdout);
        #endif
        scanf("%d",&n);
        int flag=0;
        for(int i=1;i<=n;++i)
        {
            scanf("%s",s);
            int tmp=0;
            for(int j=0;s[j]!='\0';++j)
                if(s[j]=='0'||s[j]=='1')
                    ++tmp;
            if(tmp==2)
                flag=1;

        }
        if(flag)
            break;
    }
    //环长是p-sum 1 走的是sum
    bool g=(p-sum==sum);

    while(n>1)
    {
        if(g)
            puts("next 0 1 2 3 4 5 6 7 8 9");
        else
            puts("next 0 1");
        g=1;
        #ifndef wjyyy
            fflush(stdout);
        #endif
        scanf("%d",&n);
        int flag=0;
        for(int i=1;i<=n;++i)
            scanf("%s",s);
    }
    puts("done");
    #ifndef wjyyy
        fflush(stdout);
    #endif
    return 0;
}