专栏文章

《三国杀》张昌蒲严教算法

传传奇英雄
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq7vh1v
此快照首次捕获于
2025/12/04 00:23
3 个月前
此快照最后确认于
2025/12/04 00:23
3 个月前
查看原文
玩《三国杀》的时候想出了这个问题。 张昌蒲严教：出牌阶段限一次，你可以选择一名其他角色。从牌堆顶亮出四张牌，该角色将这些牌分成点数之和相等的两组，你与其各获得其中一组，然后将剩余未分组的牌置入弃牌堆。若未分组的牌超过一张，你本回合手牌上限-1。
张昌蒲可以亮出牌堆顶的n张牌（初始n=4），经典天平问题。每张牌有三种策略：放左边，放右边，弃置。那么我们编写一个程序，将所有牌的点数作为输入，输出所有的可行方案。
算法一：直接暴力深搜，最后使用13进制哈希（因为卡牌的点数A到K，分别对应0到12，注意不是1到13）去除重复方案。复杂度O(3^n)
优化：将点数一样的牌一起处理，可以减少一部分重复。
可行性剪枝：计算卡牌点数的后缀和。如果将所有剩余卡牌都放在天平轻的一侧仍然轻，那么此状态无解，直接return;
CPP
#include<bits/stdc++.h>
using namespace std;
int a[12],numa[12],n,s,h[12],l[12],r[12],num,num2,numans,w;
bool b[1000005];
char c;
struct answer
{
	int num,num2,l[12],r[12];
};
answer ans[10005];
bool mycmp(answer x1,answer x2)
{return x1.num+x1.num2>x2.num+x2.num2;}

void f(int t)
{
	if(t>n)
	{
		if(!w&&num)
		{
			int hash=l[1]-1,hash2=r[1]-1;
			for(int i=2;i<=num;i++)
				hash=(hash*13+l[i]-1)%999983;
			for(int i=2;i<=num2;i++)
				hash2=(hash2*13+r[i]-1)%999983;
			if(!b[hash]||!b[hash2])//13进制哈希查重 
			{
				b[hash]=b[hash2]=1;
				numans++;
				ans[numans].num=num,ans[numans].num2=num2;
				for(int i=1;i<=num;i++)
					ans[numans].l[i]=l[i];
				for(int i=1;i<=num2;i++)
					ans[numans].r[i]=r[i];
			}
		}
		return;
	}
	if(abs(w)<=h[t])//可行性剪枝
	{ 
		for(int i=1;i<=numa[t];i++)//全放左侧 
			l[++num]=a[t];
		w+=a[t]*numa[t];
		f(t+numa[t]);
		for(int i=1;i<=numa[t];i++)//逐个拿下，再放入右侧
		{
			num--;
			w-=a[t];
			f(t+numa[t]);
			r[++num2]=a[t];
			w-=a[t];
			f(t+numa[t]);
		}
		num2-=numa[t];
		w+=a[t]*numa[t];//回溯 
	}
}

int main()
{
	while(scanf("%c",&c))
	{
		if(c==' ')
		{
			a[++n]=s;
			s=0;
		}
		else if(c=='\n')
		{
			a[++n]=s;
			break;
		}
		else s=s*10+c-48;
	}
	sort(a+1,a+n+1);
	for(int i=n;i;i--)//后缀和 
		h[i]=h[i+1]+a[i];
	for(int i=1;i<=n;i+=numa[i])
	{
		numa[i]=1;
		for(int j=i+1;a[i]==a[j];j++)
			numa[i]++;
	}
	f(1);
	sort(ans+1,ans+numans+1,mycmp);
	for(int i=1;i<=numans;i++)
	{
		printf("方案%d：",i);
		for(int j=1;j<ans[i].num;j++)
			printf("%d+",ans[i].l[j]);
		printf("%d=",ans[i].l[ans[i].num]);
		for(int j=1;j<ans[i].num2;j++)
			printf("%d+",ans[i].r[j]);
		printf("%d\n",ans[i].r[ans[i].num2]);
	}
	return 0;
}
算法二：使用对称性剪枝，保证在搜索时就能去除重复，故删除哈希。镜像重复的方案（手性）仅保留将第一张不对称卡牌放在左侧多的情况。
CPP
#include<bits/stdc++.h>
using namespace std;
int a[12],numa[12],n,s,h[12],l[12],r[12],num,num2,numans,w;
char c;
struct answer
{
	int num,num2,l[12],r[12];
};
answer ans[10005];
bool mycmp(answer x1,answer x2)
{return x1.num+x1.num2>x2.num+x2.num2;}

void f(int t,bool fl)
{
	if(t>n)
	{
		if(!w&&num)
		{
			numans++;
			ans[numans].num=num,ans[numans].num2=num2;
			for(int i=1;i<=num;i++)
				ans[numans].l[i]=l[i];
			for(int i=1;i<=num2;i++)
				ans[numans].r[i]=r[i];
		}
		return;
	}
	if(abs(w)<=h[t])//可行性剪枝
	{
		for(int i=1;i<=numa[t];i++)//全放左侧 
			l[++num]=a[t];
		w+=a[t]*numa[t];
		f(t+numa[t],1);
		//对称性剪枝，规定"打破对称的"第一张牌必须放左侧 
		if(fl)//无对称性要求
		{
			for(int i=1;i<=numa[t];i++)//逐个拿下，再放入右侧
			{
				num--;
				w-=a[t];
				f(t+numa[t],1);
				r[++num2]=a[t];
				w-=a[t];
				f(t+numa[t],1);
			}
			num2-=numa[t];
			w+=a[t]*numa[t];//回溯
		}
		else//有对称性要求 
		{
			if(num&1)//奇数 
			{
				for(int i=1;i<=numa[t]>>1;i++)//逐个拿下，再放入右侧
				{
					num--;
					w-=a[t];
					f(t+numa[t],1);
					r[++num2]=a[t];
					w-=a[t];
					f(t+numa[t],1);
				}
				num--;
				w-=a[t];
				f(t+numa[t],0);
			}
			else
			{
				for(int i=1;i<=(numa[t]-1)>>1;i++)//逐个拿下，再放入右侧
				{
					num--;
					w-=a[t];
					f(t+numa[t],1);
					r[++num2]=a[t];
					w-=a[t];
					f(t+numa[t],1);
				}
				num--;
				w-=a[t];
				f(t+numa[t],1);
				r[++num2]=a[t];
				w-=a[t];
				f(t+numa[t],0);
			}
		}
	}
}

int main()
{
	while(scanf("%c",&c))
	{
		if(c==' ')
		{
			a[++n]=s;
			s=0;
		}
		else if(c=='\n')
		{
			a[++n]=s;
			break;
		}
		else s=s*10+c-48;
	}
	sort(a+1,a+n+1);
	for(int i=n;i;i--)//后缀和 
		h[i]=h[i+1]+a[i];
	for(int i=1;i<=n;i+=numa[i])
	{
		numa[i]=1;
		for(int j=i+1;a[i]==a[j];j++)
			numa[i]++;
	}
	f(1,0);
	sort(ans+1,ans+numans+1,mycmp);
	for(int i=1;i<=numans;i++)
	{
		printf("方案%d：",i);
		for(int j=1;j<ans[i].num;j++)
			printf("%d+",ans[i].l[j]);
		printf("%d=",ans[i].l[ans[i].num]);
		for(int j=1;j<ans[i].num2;j++)
			printf("%d+",ans[i].r[j]);
		printf("%d\n",ans[i].r[ans[i].num2]);
	}
	return 0;
}
算法三：使用记忆化搜索，复杂度降低到O(min(3^n,n*S))。S为卡牌点数和范围，S<=13n，显然复杂度达不到上界。
为w设置初始偏移量65（为了避免数组下标负数）。设状态dp[n][w]表示在当前状态下继续搜索下去是否有解（状态里没有fl，因为fl对是否有解无影响）。将f函数从void改为bool，传递当前状态的dp值。状态转移方程：dp[n][w]=max(dp[n+numa[n]][所有可能到达的状态w])
有了dp[n][w]的记录之后，所有重叠子问题最多计算一次，第二次遇到“此路不通”的情况会直接“掉头”，而遇到“有路”的情况只会在“正确的路上”行走，免去搜索直奔答案，不会走“岔路”。就像有了雅努斯（门径之泰坦）的指引一样顺利。
对于这类问题，我一般用记忆化搜索完成DP，理由：1.一般的DP需要用循环，这样会循环到很多不可能到达的状态，白白浪费时间。而记搜搜过的所有状态都是能到达的状态。2.这个问题需要输出答案，而且是多个答案，一般的DP写法很难存储多个答案，要么需要用邻接表建图保存答案，要么就要做完DP之后再次根据DP值深搜出答案，非常繁琐。虽然深搜的常数比较大。
CPP
#include<bits/stdc++.h>
using namespace std;
int a[12],numa[12],n,s,h[12],l[12],r[12],num,num2,numans,w=65;
char c;
bool dp[12][135],vis[12][135];

struct answer
{
	int num,num2,l[12],r[12];
};
answer ans[10005];
bool mycmp(answer x1,answer x2)
{return x1.num+x1.num2>x2.num+x2.num2;}

bool f(int t,bool fl)
{
	if(t>n)
	{
		if(w!=65||!num) return 0;
		ans[++numans].num=num;
		ans[numans].num2=num2;
		for(int i=1;i<=num;i++)
			ans[numans].l[i]=l[i];
		for(int i=1;i<=num2;i++)
			ans[numans].r[i]=r[i];
		return 1;
	}
	if(abs(w-65)>h[t]||(vis[t][w]&&!dp[t][w]))
		return 0;//可行性剪枝
	vis[t][w]=1;
	for(int i=1;i<=numa[t];i++)//全放左侧 
		l[++num]=a[t];
	w+=a[t]*numa[t];
	bool flag=0;
	flag|=f(t+numa[t],1);
	//对称性剪枝，规定"打破对称的"第一张牌必须放左侧 
	if(fl)//无对称性要求
	{
		for(int i=1;i<=numa[t];i++)//逐个拿下，再放入右侧
		{
			num--;
			w-=a[t];
			flag|=f(t+numa[t],1);
			r[++num2]=a[t];
			w-=a[t];
			flag|=f(t+numa[t],1);
		}
		num2-=numa[t];
		w+=a[t]*numa[t];//回溯
	}
	else//有对称性要求 
	{
		if(num&1)//奇数 
		{
			for(int i=1;i<=numa[t]>>1;i++)//逐个拿下，再放入右侧
			{
				num--;
				w-=a[t];
				flag|=f(t+numa[t],1);
				r[++num2]=a[t];
				w-=a[t];
				flag|=f(t+numa[t],1);
			}
			num--;
			w-=a[t];
			flag|=f(t+numa[t],0);
		}
		else
		{
			for(int i=1;i<=(numa[t]-1)>>1;i++)//逐个拿下，再放入右侧
			{
				num--;
				w-=a[t];
				flag|=f(t+numa[t],1);
				r[++num2]=a[t];
				w-=a[t];
				flag|=f(t+numa[t],1);
			}
			num--;
			w-=a[t];
			flag|=f(t+numa[t],1);
			r[++num2]=a[t];
			w-=a[t];
			flag|=f(t+numa[t],0);
		}
	}
	return dp[n][w]=flag;
}

int main()
{
	while(scanf("%c",&c))
	{
		if(c==' ')
		{
			a[++n]=s;
			s=0;
		}
		else if(c=='\n')
		{
			a[++n]=s;
			break;
		}
		else s=s*10+c-48;
	}
	sort(a+1,a+n+1);
	for(int i=n;i;i--)//后缀和 
		h[i]=h[i+1]+a[i];
	for(int i=1;i<=n;i+=numa[i])
	{
		numa[i]=1;
		for(int j=i+1;a[i]==a[j];j++)
			numa[i]++;
	}
	f(1,0);
	sort(ans+1,ans+numans+1,mycmp);
	for(int i=1;i<=numans;i++)
	{
		printf("方案%d：",i);
		for(int j=1;j<ans[i].num;j++)
			printf("%d+",ans[i].l[j]);
		printf("%d=",ans[i].l[ans[i].num]);
		for(int j=1;j<ans[i].num2;j++)
			printf("%d+",ans[i].r[j]);
		printf("%d\n",ans[i].r[ans[i].num2]);
	}
	return 0;
}
算法四：考虑到这个问题只有一个起点（w=0）和一个终点（也是w=0），故从两端开始搜索，在中间汇合。大大降低时间复杂度。但我认为对这道题来说使用这个策略是有些多此一举的，甚至不一定比得过算法三。两端搜索的策略适合指数爆炸式复杂度的问题，适合越往深处搜索，结点数量便指数爆炸式增长的问题。而这个问题当n过半之后，范围S由于可行性剪枝反而缩小了。呈现“两头尖，中间大”的形态。两端搜索的目的就是为了达成“两头尖，中间大”的形态并在中间汇合，这个目的已经达成了，再用两端搜索就多此一举了。而且两端搜索还会增加代码量，需要两半对接答案，也更繁琐。
策略游戏嘛，算法打击！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...