SP196 MUSKET - Musketeers

题目传送门

题意：

题目描述中讲的比较清楚，就不再赘述了

思路：

区间动归 + 看链为环的思想 ：

假设需要判断 x 是否能赢得整场战斗，把环看成链，x 点拆成两个，那么编号为x的人能从中胜出的充分必要条件是他能与自己“相遇”。

这样，在连续几个人的链中，只须考虑头尾两个人能否胜利会师，中间的则不予考虑。

设 meet[i][j] 记录 i 和 j 能相遇，能则为 $true$，否则为 $false$，则问题转化为了是否能找到一个 k，使得 i 和 k , k 和 j 均能相遇，而 i 或 j 能打败 k。

CODE：

（注释就不加了，理解了思路代码就没什么大问题）

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
bool e[105][105],meet[205][205],kkk[105];
int t,n,sum;
string s;
signed main(){
    t=read();
    while(t--){
        sum=0;
        n=read();
        for(int i=0;i<n;i++){
            cin>>s;
            for(int j=0;j<n;j++){
                if(s[j]=='1')e[i][j]=1;
                else e[i][j]=0;
            }
        }
    	memset(kkk,0,sizeof(kkk));
		memset(meet,0,sizeof(meet));
        for(int i=0;i<2*n-1;i++)meet[i][i+1]=1;
        for(int k=2;k<=n;k++){
            for(int i=0;i+k<2*n;i++){
                int j=i+k,flag=0;
                for(int q=1;q<j;q++){
                    if(meet[i][q]==1&&meet[q][j]==1&&(e[i%n][q%n]==1||e[j%n][q%n]==1)){
                        flag=1;
                        break;
                    }
                }
                if(flag){
                    meet[i][j]=1;
                    if(k==n)sum++,kkk[i]=1;
                }
            }
        }
        cout<<sum<<endl;
        for(int i=0;i<n;i++){
            if(kkk[i])cout<<i+1<<endl;
        }
    }
    return 0;
}