题解 CF1137D 【Cooperative Game】

## （前言 由于之前做过的交互题都是和倍增/二进制有关，本题给出了 $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)$。 ## 代码 ```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; } ```