清北学堂模拟day6 圆桌游戏

【问题描述】

有一种圆桌游戏是这样进行的：n个人围着圆桌坐成一圈，按顺时针顺序依次标号为1号至n号。对1<i<n的i来说，i号的左边是i+1号，右边是i-1号。1号的右边是n号，n号的左边是1号。每一轮游戏时，主持人指定一个还坐在桌边的人（假设是i号），让他向坐在他左边的人（假设是j号）发起挑战，如果挑战成功，那么j离开圆桌，如果挑战失败，那么i离开圆桌。当圆桌边只剩下一个人时，这个人就是最终的胜利者。

事实上，胜利者的归属是与主持人的选择息息相关的。现在，你来担任圆桌游戏的主持人，并且你已经事先知道了对于任意两个人i号和j号，如果i向j发起挑战，结果是成功还是失败。现在你想知道，如果你可以随意指定每轮发起挑战的人，哪些人可以成为最终的胜利者？

【输入】

第一行包含一个整数n，表示参加游戏的人数；

接下来n行，每行包含n个数，每个数都是0或1中的一个，若第i行第j个数是1，表示i向j发起挑战的结果是成功，否则表示挑战结果是失败。第i行第i列的值一定为0。

【输出】

一行，包含若干个数，表示可能成为最终胜利者的玩家的标号。标号按从小到大的顺序输出，相邻两个数间用1个空格隔开。

【输入输出样例1】

game.in

game.out

0 1 0

0 0 1

0 1 0

1 3

见选手目录下的game / game1.in与game / game1.out

【输入输出样例1说明】

先指定2号向3号发起挑战，3号离开；再指定1号向2号发起挑战，2号离开。此时1号是最终胜利者。

先指定1号向2号发起挑战，2号离开；再指定1号向3号发起挑战，1号离开。此时3号是最终胜利者。

无论如何安排挑战顺序，2号都无法成为最终胜利者。

【输入输出样例2】

见选手目录下的game / game2.in与game / game2.out

【数据规模与约定】

对于30%的数据，n≤7

对于100%的数据，n≤100

/*
先说说我的90分算法，o（玄学），而且时间复杂度与最终人数有关，设f[i][j][k]表示区间i……j中第k个可能获胜的人是谁，然后记录一下，每次把两个区间合并就可以了
*/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
const int maxn = 105;
int dp[maxn*2][maxn*2][maxn],cnt[maxn*2][maxn*2];
int n,a[maxn][maxn],cir;
bool vis[maxn*2][maxn*2][maxn],ans[maxn];
inline void psh(int l,int r,int v){
    if(vis[l][r][v]) return;
    vis[l][r][v] = true;
    dp[l][r][++cnt[l][r]] = v;
    if(r - l + 1 == cir) ans[v] = true;
}
int main(){
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    cin>>n;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            scanf("%d",&a[i][j]);
        }
    }
    for(int i = 1;i <= n ;i++){
        dp[i][i][1] = dp[i+n][i+n][1] = i;
        cnt[i][i] = cnt[i+n][i+n] = 1;
    }
    cir = n;
    n = 2*n + 1;
    int ft,fe;
    for(int l = 2;l <= cir;l++){
        for(int i = 1;i <= n - l + 1;i++){
            int j = i + l - 1;
            for(int k = i;k < j;k++){
                for(int t1 = 1;t1 <= cnt[i][k];t1++){
                    for(int t2 = 1;t2 <= cnt[k+1][j];t2++){
                        ft = dp[i][k][t1];
                        fe = dp[k+1][j][t2];
                        if(a[ft][fe]) psh(i,j,ft);
                        else psh(i,j,fe);
                        if(l == cir){
                            if(a[fe][ft]) psh(i,j,fe);
                            else psh(i,j,ft);
                        }
                    }
                }
            }
        }
    }
    for(int i = 1;i <= cir;i++){
        if(ans[i]) printf("%d ",i);
    }
    return 0;
}
/*
标算：f[i][j]==true表示i与j可能相邻，每次枚举区间内最后一个被淘汰的人，若f[i][i+n]为true则i可能获胜！
*/
#include <cstdio>
int n,i,j,k,a[205][205],q[205];
bool f[205][205],o;

int main()
{
    freopen("game.in", "r", stdin);
    freopen("game.out", "w", stdout);
    
    scanf("%d", &n);
    for (i=1; i<=n; ++i)
    for (j=1; j<=n; ++j) scanf("%d", &a[i][j]);
    
    for (i=1; i<=n; ++i) q[i] = q[i+n] = i;
    for (i=1; i<n+n; ++i) f[i][i+1] = true;
    
    for (i=n+n-2; i>=1; --i)
    for (j=i+2; j<=n+n; ++j)

    for (k=i+1; k<j; ++k)
    if (f[i][k] && f[k][j] && (a[q[i]][q[k]] || !a[q[k]][q[j]]))
    {
        f[i][j] = true;
        break;
    }
    
    for (i=1; i<=n; ++i)
    if (f[i][i+n])
    {
        if (o) printf(" ");
        printf("%d", i);
        o = true;
    }
    printf("\n");
    return 0;
}

清北学堂模拟day6 圆桌游戏

推荐阅读