Problem B. Wpremig的AH之战

题目描述 

AH是auction house,拍卖行的缩写。众所周知,为了道具流通,基本上每个网络游戏都会有拍卖行或者类似拍卖行的系统存在。

Wpremig最近喜欢上玩《XX传奇》,游戏为了吸引玩家,推出了一种”抢拍模式”,在原有的拍卖行竞价基础上,增加了一条规则:只有最早竞价的两个人有资格竞价。

原本规则如下:

所有物品初始价格为0, 每次加价必须在[1,N]内,并且不存在一口价功能,只有一个价格上限M,当某次某个玩家加价后的价格大于等于M时,这个玩家就可以拍下物品,或者在48小时后还没有超出上限,那么当前出价人拍下物品。

Wpremig通过内部消息知道明天会拍卖一件神器,并且找到了一个脚本软件,能保证自己一定是第一个竞价的人,但是现在他的几个不同的消息来源,给出的物品价格是不一样的,所以他并不知道到时候神器的准确价格是多少,但是可以知道一点,另一个玩家一定不会在中途放弃。

所以Wpremig想要知道对于每种N,M的情况,自己一开始出价多少才能够保证自己拍到这件物品?

输入描述:

多组数据,不超过100组。
每组数据包含两个整数N,M表示加价区间[1,N]和价格上限M,(1<=N,M<=1024)

输出描述:

对于每组数据输出Wpremig所有可行的第一次加价方案,从小到大用空格隔开。若不存在可行的方案,则输出"You are loser"

示例1

输入

4 3

输出

3 4

题解:简单的博弈论,套用SG函数就可以解决问题(显然是杀鸡用牛刀了)

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0×7ffffff
#define EPS 1e-8
#define maxn 1000+110
#define PI acos(-1.0)
using namespace std;
int m,n;
 
//f[]:可以取走的石子个数
//sg[]:0~n的SG函数值
//vis[]:mex{}
int f[maxn],sg[maxn],vis[maxn];
void getSG(int n)
{
    int i,j;
    memset(sg,0,sizeof(sg));
    for(i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        for(j=1;f[j]<=i&&f[j]<=m;j++) //注意加f[i]的限定条件
            vis[sg[i-f[j]]]=1;
        for(j=0;j<=n;j++)    //求mes{}中未出现的最小的非负整数
        {
            if(vis[j]==0)
            {
                sg[i]=j;
                break;
            }
        }
        //cout<<i<<" "<<sg[i]<<endl;
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    for(int i=1;i<=1200;i++)
        f[i]=i;
    while(cin>>m>>n)
    {
        if(m>=n)
        {
            for(int i=n;i<=m;i++)
            {
                if(i==n) cout<<i;
                else cout<<" "<<i;
            }
            cout<<endl;
            continue;
        }
        getSG(n);
        if(sg[n]==0)
            cout<<"You are loser\n";
        else
        {
            int first=1;
            for(int i=1;i<=m;i++)
            {
                if(sg[n-i]==0)
                {
                    if(first)
                    {
                        cout<<i;
                        first=0;
                    }
                    else cout<<" "<<i;
                }
            }
            cout<<endl;
        }
    }
}

 

当然也可以用巴什博弈论解决

如果我们上来就遇见(n+1)*m的局势,必败,因为如果你挣扎拿 p 个,你的对手只要拿 n-p+1 个,然后你将面对(n+1)*(k-1)的局面,直至最后你面对 n+1 ,你最多拿 n 个,你的对手拿一个终结你,你最少拿 1 个,你的对手拿 n 个终结你。相反的,如果你不是处于奇异局,比如是(n+1)*m+r(r<(n+1)这是一定的,如果r>(n+1),倍数就是k+1,所以余出来的一定小于(n+1)

#include <cstdio>
int main(void)
{
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        if(m<=n)
        {
            for(int i=m;i<=n;i++)
                printf("%d ",i);
            printf("\n");
            continue;
        }
        if(m%(n+1)==0)
            printf("You are loser\n");
        else
            printf("%d\n",m%(n+1));
    }
    return 0;
}

 

发表评论,支持MarkDown语法