CodeForces CF1846G 题解

• CodeForces题目链接

• 洛谷题目链接

• 标准答案是状压之后，转化成Dijkstra算法跑最短路。我这里提供一个不一样的思路。

题意简述

主人公得了病，有部分类型的症状。所有类型症状共有 $n$ 种，用长为 $n$ 的01串表示是否有那种症状。共有 $m$ 种药，吃第 $i$ 种药需要花费时间 $t_i$， 能够治好症状 $a_i$， 留下后遗症 $b_i$， 其中 $a_i$、$b_i$均为长度为 $n$ 的01串，表示每种症状是否治好或者后遗。

主人公每次只能吃一种药。求康复需要的最少时间。

保证输入不会自相矛盾，药物能治好某种症状就不会后遗。

多组测试。

题目分析

1. 最后吃什么？

实际上这个过程和“化学除杂”有些类似。我们考虑最后吃的药的特征，发现最后吃的药一定没有后遗症。简单的证明就是：我们考虑症状个数 $cnt$，最终目标是 $cnt=0$，如果每种药物都有后遗症，那么即使能够治好全部症状，也至少会遗留下一种后遗症，于是 $cnt\ge 1$，矛盾。我们暂且把这种药物成为“纯药”（无后遗症）。

2. 交换吃药顺序？

我们发现交换药物服用顺序是不行的（显然后吃“纯药”和先吃“纯药”，一个康复，一个可能不康复）。

3. 一种药物吃几次？

接下来我们尝试考虑一种药物吃几次。

假设一个药物吃两次及以上，为了方便表示，我们不妨交换每种症状的相对位置，使得对于这个药物而言，是“治疗症状、保持原状、后遗症”的格式。例如原来是：

交换症状相对位置之后（此处3、4列和4、5列对调）变成：

我们将药物的效果压缩成一个串来表示，治疗用 $\mathtt{\text{–}}$ 表示，保持不变用 $\mathtt{\text{0}}$ 表示， 后遗症用 $\mathtt{\text{+}}$ 表示，于是：

我们将不确定的位置用 $\mathtt{\text{Q}}$ 来占位表示。（下面表中的各部分串的长度仅为示意，实际上是某一特定的数值。）假如一个药物吃了两次及以上，肯定存在两次吃某一个药，于是有：

我们发现在两次服药中间的步骤，所起到的效果（或者说吃它们的目的），是为了改变 $Q$ 的值。因此我们发现，如果把第一次吃药这一步撤掉，我们的结果是：

效果没有改变。

因此一种药物吃一遍就足够了。也就是说，每种药只吃一次。

4. 从最后的药物出发

所以我们找到一个“纯药”之后，根据上面的结论，这个纯药应当在最后吃，而且只在最后吃（因为每种药只吃一次）。

我们观察一下：

我们发现，吃纯药后把“可治疗”症状全部归 $\mathtt{\text{0}}$，也就意味着，如果最后吃这个“纯药”，那么再考虑之前的药物时，不用考虑“可治疗”的那几个症状，因为最后都会被纯药一次性全治好。

因此，我们把纯药从所有药物中删除，所有的药物和主人公症状中，涉及到所删除纯药“可治疗”的症状全部抹去，就转化成了规模更小的问题。我们暂时称这些位置“被覆盖了”。 如表格所示：

于是我们重复上述过程，在剩下的位置中，找剩下药物中的“纯药”（只考虑剩下的位置来判断）。

最终我们可以求得答案。

5. 具体实现的一些细节

具体实现中，我采用的是类似SPFA的算法（用优先队列，或者说是BFS也行），以及状态更新。我们令状态压缩的01串 $S$ 表示每一个位置（症状）是否被覆盖。令 $f_S$ 表示 $S$ 状态下的最短时间。我们在更新的时候，除了更新 $S$ 本身外，还要更新其“包含”状态的值（例如 $\mathtt{\text{11001110}}$ 中间包含 $\mathtt{\text{10001010}}$）：

由于使用优先队列，所以每个状态只访问一次，对应的vis数组记录，判断重复。

其他的位运算等细节请见代码。

记得没病要特判。

代码

#include <bits/stdc++.h> #define N (int)(12)#define M (int)(1e3 + 5) using namespace std; typedef long long LL; struct drag{	LL t,e,se,idx;}d[M]; LL f[1<<N];bool vis[1<<N]; LL T; LL n,m; string to_str(int x); struct state{	LL e,t;}; bool operator<(const state xx, const state yy){	return xx.t > yy.t; priority_queue<state> q; void dfs(LL e,LL p, LL t){	if(vis[e]) return;	if(e < (1<<p))	{		vis[e] = true;		f[e] = t;		return;	}	if(((e>>p)&1) == 1)	{		dfs(e^(1<<p),p+1,t);	}	dfs(e,p+1,t);} LL ansdfs(LL e,LL p){	if(e < (1<<p))	{		return f[e];	}	LL ans = 1e18;	if(((e>>p)&1) == 0)	{		ans = min(ans,ansdfs(e|(1<<p),p+1));	}	ans = min(ans,ansdfs(e,p+1));	return ans;} inline void setf(LL e,LL t){	dfs(e,0,t);} inline LL anti(LL x){	return (1<<n) - 1 - x;} bool check(LL e,LL se){	for(LL i = 0;i < n;i++)	{		if((((e>>i)&1) == 0) && (((se>>i)&1) == 1))		{			return false;		}	}	return true;} string to_str(int x){	string str = "";	for(int i = 0;i < n;i++)		str += ((x>>i)&1) + '0';	return str;} int main(){	ios::sync_with_stdio(false);	cin.tie(0);cout.tie(0);	cin >> T;	while(T--)	{		memset(vis,0,sizeof(vis));		memset(f,0x7f,sizeof(f));		cin >> n >> m;		string str;		cin >> str;		LL e0 = 0;		for(LL j = n - 1;j >= 0;j--)				e0 = (e0 << 1) | (str[j] - '0');		for(LL i = 1;i <= m;i++)		{			cin >> d[i].t;			d[i].idx = i;			cin >> str;			d[i].e = 0;			for(LL j = n - 1;j >= 0;j--)				d[i].e = (d[i].e << 1) | (str[j] - '0');			cin >> str;			d[i].se = 0;			for(LL j = n - 1;j >= 0;j--)			{				d[i].se = (d[i].se << 1) | (str[j] - '0');			}		}		if(e0 == 0)		{			cout << "0\n";			continue;		}		q.push({0,0});		while(!q.empty())		{			state top = q.top();			q.pop();			if(!vis[top.e])			{				setf(top.e,top.t);				for(int i = 1;i <= m;i++)				{					if(check(top.e,d[i].se))					{						LL ne = top.e | d[i].e;						if(!vis[ne])						{							q.push({ne,top.t + d[i].t});						}					}				}			}		}		LL ans = ansdfs(e0,0);		if(ans >= 1e9) cout << "-1\n";		else cout << ans << "\n";	}	return 0;}

本人能力有限，欢迎大家来Hack！

__EOF__

本文作者： l-cacherr

本文链接： https://www.cnblogs.com/l-cacherr/p/17615176.html

关于博主： 评论和私信会在第一时间回复。或者直接私信我。

版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

声援博主： 如果您觉得文章对您有帮助，可以点击文章右下角【推荐】一下。