昆特牌 题解【模拟】【搜索】
点击量：126
毒瘤模拟+搜索决策。
题目背景
什么？你还有一场 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\%\)的数据，
对于\(60\%\)的数据，
对于\(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;
}
说点什么