发布于

lp1288 取数游戏

事实上这是一道结论题。
首先，如果双方足够聪明，那么他们都不会回头。
这是因为，如果先手方往一个方向走，在背后留下了一个必败局面，那么后手方一定不会回头。
而如果先手方往一个方向走，在背后留下了一个必胜局面，那么他一定会选择破坏了这条边。
所以游戏必然成是链。
我们首先考虑边数为2的情况。此时先手必胜，这是因为如果先手足够聪明，那么他一定会选择把这整条边拿掉。此时后手输了。
而，对于边数是3的情况，先手必败。这是因为，先手无论取任何数，都会使得情况转化为边数为2的情况，那么后手可以走一步然后断绝通向必胜局面的路。
故而我们得知，如果起始点的两端有一条链的边数为偶，则先手必胜；否则后手必胜。

#include<iostream>
#include<cstdio>
using namespace std;
int n,a[20];
void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;++i){
        if(!a[i]){
            if(!(i&1)){
                puts("YES");
                return;
            }
            break;
        }
    }
    for(int i=1;i<=n;++i){
        if(!a[n-i+1]){
            if(!(i&1)){
                
                puts("YES");
                return;
            }
            break;
        }
    }
    puts("NO");
    return;

}
int main(){
    init();
    return 0;
}

 

发布于

lp1199 NOIP2009 三国游戏

首先我们定义最优配对：最优配对指的是，对于一个武将而言，与他默契值最高的武将。
其次我们定义次优配对，次优配对指的是，对于一个武将而言，与他默契值次高的武将。
那么我们知道，无论如何，人类能够选取的一定只能是一组次优配对，而不可能是一组最优配对。
当然人类一定可以取到次优配对中的最大值。这是因为电脑的操作一定会用于破坏人类取到最优配对，因此取到次优配对一定是可能的。
如果人类想要胜利，就必须防止电脑取到最优配对中比次优配对最大值更大的那些值。我们定义这样的值为「危险值」
如果危险值存在，那么组成它的两个部分一定都互为最优配对：证明如下。
如果组成危险值的两个部分不互为最优配对，那么危险值一定是两者中一者关于另一者的最优配对。
我们不妨设定甲武将是乙的最优配对，该配对是危险值，那么乙武将必须存在一个最优配对，使得该配对的值大于危险值。
这时候乙武将的次优配对一定大于等于危险值，但是这与危险值的定义矛盾。所以组成危险值的两个部分一定互为最优配对。
故而，我们发现，危险值一定是一种最优配对。
那么，当我们优先取得足以构成次优配对中的最大值的两个武将以后，电脑已经控制的一个武将总是不能构成危险值。
这是因为组成危险值的两个武将一定互为最优配对，而电脑已经控制的仅为其中的一个武将，并且与该武将构成最优配对的武将控制在玩家手中。
当游戏进行三步时，玩家已经控制了次优配对中的最大值，并且电脑不控制任何危险值，此时可以将游戏转化为
「电脑先手且必须控制危险值」的情况。
由于危险值总是需要由一组互为最优配对的武将构成，容易证明无论电脑如何选择，玩家都可以破坏危险值的构成。
因此，总是有解，且解总为次优配对中的最大值。

当然这一题还有一个实现难点在于读入，这里就不再细说。

#include<iostream>
#include<cstdio>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
/*
lp1199 三国游戏
*/
int n,f[505][505];
void init(){
    scanf("%d",&n);
    int mx,lmx,ans=0,x;
    for(int i=1;i<n;++i){
        for(int j=i+1;j<=n;++j){
            scanf("%d",&f[i][j]);
            f[j][i]=f[i][j];
        }
    }
    /*
    for(int i=1;i<n;++i){
        for(int j=1;j<n;++j){
            printf("%d ",f[i][j]);
        }
        puts("");
    }
    */
    for(int i=1;i<=n;++i){
        mx=0,lmx=0;
        for(int j=1;j<=n;++j){
            x=f[i][j];
            if(mx<x){
                lmx=mx;
                mx=x;
            }else{
                lmx=Max(lmx,x);
            }
        }
        ans=Max(ans,lmx);
    }
    puts("1");
    printf("%d",ans);
}
int main(){
    init();
    return 0;
}