昆特牌 题解【模拟】【搜索】

作者: wjyyy 分类: 搜索,枚举,模拟,解题报告 发布时间: 2018-11-07 13:31

点击量:7

 

    毒瘤模拟+搜索决策。

 

题目背景

什么?你还有一场 NOIP 模拟赛? 什么都别说,先来盘昆特牌吧!

题目描述

昆特牌是一款双人对战卡牌游戏,游戏规则现简化如下:

游戏简化为仅有一局;

每位牌手有三行,分别是近战、远程和攻城;

每位牌手每次按顺序出一张牌;

每位牌手有同样数量张牌,而聪明的你能预知对手每次出的牌!

牌分为以下几种功能:

  • 单位牌:有一个点数和放置位置,\(0\)、\(1\)、\(2\)分别表示近战、远程和攻城,放置在你的场上;
  • 天气牌:有一个影响位置\(0\)、\(1\)、\(2\)分别表示近战、远程和攻城, 对你的和对手的相应行都会影响。天气下的单位无法被烧灼(烧灼下面有解释),天气下的单位计算点数和的时候视为每个为\(1\),对已经有天气牌的行使用视作无效;
  • 反天气牌:去除所有的天气牌并去除天气牌的视为每个为\(1\)效果(当然也包括其他效果);
  • 烧灼牌:消灭全场现有战力最高的单位(包括自己的单位)(除了天气下的), 若有多个则都消灭,若没有单位则视为无效,后续放入同行的单位仍然视作被天气影响;
  • 号角牌:选择\(6\)行(包括对手的)中一行使该行现有单位战力翻倍,但不能对天气牌影响下的行使用。如果每行都有天气视作无效,否则必须选择一行。由于丢了一些牌,这种卡最多只会出现\(2\)张,而且只有你有。这种牌视为立刻生效,然后消失;

所有牌都必须使用,且除了单位牌其他牌都没有点数。视作无效的牌不影响整个出牌过程,打出它什么用都没有,但你还是打出了它。

你想要让最后你的点数和减去对手的尽量大(不是绝对值!),该怎么办呢?

输入输出格式

输入格式:

第一行两个数\(W,N\)分别表示先后手和每人牌数,\(W=0\)表示你先手,\(W=1\)表示对手先。

接下来依次\(N\)行表示对手每次出的牌:

  • \(t=1\),这是一张单位牌,接下来\(x,y\)分别表示战力和位置;
  • \(t=2\),这是一张天气牌,接下来\(x\)表示位置;
  • \(t=3\),这是一张反天气牌;
  • \(t=4\),这是一张烧灼牌;
  • \(t=5\),这是一张号角牌。

接下来\(N\)行表示你的牌,描述同上。

输出格式:

点数和差的最大值和点数和差最大方案数,用空格分隔。号角放在不同行算不同方案(无效不算放在一行,但也是一种方案,同 \(012\)行不同),且每张牌是不同的。例如你有两种方案:第一张号角放在你的\(1\)行第二张号角放在你的\(0\)行与第一张号角放在你的\(0\)行第二张号角放在你的\(1\)行不同。

输入输出样例

输入样例#1:

1 3
1 5 1
1 4 2
1 500 1
5
1 5 1
4
输出样例#1:

1 1

说明

样例解释

唯一一种方案是:打出单位牌,打出号角选择自己的远程行,打出烧灼牌烧掉\(500\)点战力的牌,这样你有\(5\times 2=10\)点,对手有\(4+5=9\)点。

数据范围

对于\(10\%\)的数据,\(t\in\{1\}\)

对于\(20\%\)的数据,\(t\in\{1,2\}\)

对于\(40\%\)的数据,

t\in\{1,2,3\}

对于\(60\%\)的数据,

t\in\{1,2,3,4\}

对于\(100\%\)的数据,\(N\le 7,1\le \)所有单位战力\(\le 1000\)

TIPS

好好读题!
好好读题!
好好读题!

题解:

    这个题有\(60\)分是枚举+模拟,也就是不用决策。因为号角牌需要枚举放在哪里或无效,因此后面\(40\)分是需要搜索的。

    前\(60\)分其实可以用next_permutation,因为题目中说,每张牌是不同的。因此如果玩过《三国杀》,我们可以理解为我手上拿着红桃\(\heartsuit 3\sim 9\),对方手上拿着\(\spadesuit 3\sim 9\),应该这样理解才是对的,那么每张牌在结构体里用输入编号\(id\)来求排列即可。时间复杂度\(O(n!)\)。

    细节什么的最后再说。

    后面\(40\)分比较麻烦,因为需要枚举(最多)两张号角牌的使用对象。但是对于无效的情况也算一种这个要求,我们最好不要在外面枚举,因为只有当状态进行到号角牌之前才知道是否接下来的状态都无效,所以我们进行搜索。

    搜索的时候因为要还原现场,所以我们在开始枚举下一步之前,先存下图中的单位牌和天气状况。而向量方便排序和赋值,所以用\(6\)个vector来存\(2\times 3\)排的信息。

    如果在使用号角牌时发现所有位置都有天气,那么直接跳到下一步,否则只选择没有天气的位置进行搜索。这样一来,代码在结构上就会变得很简单,不过还原现场还是很麻烦的。在每次枚举操作之前,需要把单位牌存在一个临时开的vector中,天气存在\(2\times 3\)的数组中(但是由于天气是对称的,所以可以只开\(3\)个),做完了立即还原,因为天气可能改变。

    此外的细节:烧灼牌不能对天气影响的行使用;如果游戏结束时还有的排被天气覆盖,那么每个单位一定要按\(1\)来统计;注意先后手的区分。

Code:

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using std::sort;
using std::vector;
int Max(int x,int y)
{
    return x>y?x:y;
}
struct card
{
    int ty,x,y;
    card(int ty,int x,int y)
    {
        this->ty=ty;
        this->x=x;
        this->y=y;
    }
    card(){}
}a[2][10];//我的卡和对方的卡
int w,n,ans=-1234567890,cnt=0;
int read()
{
    int x=0,o=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            o=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*o;
}
bool infl[2][3],used[10];//是否有天气/每张牌是否被用过
vector<int> v[2][3];
bool work(int x,int y)//只限于1~4,x表示人,y表示第几张
{
    int op=a[x][y].ty;
    if(op==1)
        v[x][a[x][y].y].push_back(a[x][y].x);
    else if(op==2)
    {
        infl[0][a[x][y].x]=1;
        infl[1][a[x][y].x]=1;
    }
    else if(op==3)
        memset(infl,0,sizeof(infl));
    else if(op==4)
    {
        int mx=0;
        for(int i=0;i<=1;++i)
            for(int j=0;j<=2;++j)
                if(!infl[i][j]&&!v[i][j].empty())//要保证不碰到天气
                {
                    sort(v[i][j].begin(),v[i][j].end());//需要排序
                    mx=Max(mx,v[i][j].back());
                }
        for(int i=0;i<=1;++i)
            for(int j=0;j<=2;++j)
                while(!infl[i][j]&&!v[i][j].empty()&&v[i][j].back()==mx)
                    v[i][j].pop_back();
    }
}
void dfs(int x)
{
    if(x==n+1)//统计答案
    {
        int sum=0;
        for(int j=0;j<=2;++j)
            if(infl[0][j])
                sum+=v[0][j].size();
            else
                for(vector<int>::iterator it=v[0][j].begin();it!=v[0][j].end();++it)
                    sum+=*it;
        for(int j=0;j<=2;++j)
            if(infl[1][j])
                sum-=v[1][j].size();
            else
                for(vector<int>::iterator it=v[1][j].begin();it!=v[1][j].end();++it)
                    sum-=*it;
        if(sum>ans)
        {
            ans=sum;
            cnt=1;
        }
        else if(sum==ans)
            ++cnt;
        return;
    }
    vector<int> ori[2][3];//存还原状态
    bool orii[2][3];
    for(int j=0;j<=1;++j)
        for(int k=0;k<=2;++k)
        {
            ori[j][k]=v[j][k];
            orii[j][k]=infl[j][k];
        }
    for(int i=1;i<=n;++i)
        if(!used[i])
        {
            for(int j=0;j<=1;++j)
                for(int k=0;k<=2;++k)
                {
                    v[j][k]=ori[j][k];
                    infl[j][k]=orii[j][k];
                }
            used[i]=1;
            if(a[0][i].ty<5)//号角牌要特判
            {
                if(w)
                    work(1,x);
                work(0,i);
                if(!w)
                    work(1,x);
                dfs(x+1);
            }
            else
            {
                int flag=0;
                for(int j=0;j<=1;++j)
                    for(int k=0;k<=2;++k)
                        if(!infl[j][k])
                        {
                            flag=1;
                            if(w)
                        	work(1,x);
                            for(int t=0;t<v[j][k].size();++t)
                        	v[j][k][t]*=2;
                            if(!w)
                        	work(1,x);
                            dfs(x+1);
                            for(int j_=0;j_<=1;++j_)//立即还原,保证天气的判断
                                for(int k_=0;k_<=2;++k_)
                        	{
                        	    v[j_][k_]=ori[j_][k_];
                            	    infl[j_][k_]=orii[j_][k_];
                                }
                        }
                if(!flag)//全部都有天气
                {
                    work(1,x);
                    dfs(x+1);
                }
            }
            used[i]=0;
        }
}
int main()
{
    w=read();
    n=read();
    for(int i=1;i<=n;++i)
    {
        a[1][i].ty=read();
        if(a[1][i].ty==1)
        {
            a[1][i].x=read();
            a[1][i].y=read();
        }
        else if(a[1][i].ty==2)
            a[1][i].x=read();
    }
    for(int i=1;i<=n;++i)
    {
        a[0][i].ty=read();
        if(a[0][i].ty==1)
        {
            a[0][i].x=read();
            a[0][i].y=read();
        }
        else if(a[0][i].ty==2)
            a[0][i].x=read();
    }
    dfs(1);
    printf("%d %d\n",ans,cnt);
    return 0;
}

说点什么

avatar
  Subscribe  
提醒
/* */