题解 CF1137D 【Cooperative Game】
wjyyy
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判环**。
> **一种情况:**
>
> ![](http://www.wjyyy.top/wp-content/uploads/2019/03/201903102139.png)
>
> 如果下一步是 $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)$。
## 代码
```cpp
#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;
}
```