CodeForces CF1846G 题解

CodeForces CF1846G 题解

题意简述

主人公得了病,有部分类型的症状。所有类型症状共有 \(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. 一种药物吃几次?

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

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

\[\begin{array}{} \text{主人公症状} & \texttt{01011}\\ \text{药物的疗效} & \texttt{11010}\\ \text{药物后遗症} & \texttt{00100}\\ \end{array} \]

交换症状相对位置之后(此处3、4列和4、5列对调)变成:

\[\begin{array}{} \text{主人公症状} & \texttt{01110} \\ \text{药物的疗效} & \texttt{11100}\\ \text{药物后遗症} & \texttt{00001}\\ \end{array} \]

我们将药物的效果压缩成一个串来表示,治疗用 \(\texttt{-}\) 表示,保持不变用 \(\texttt{0}\) 表示, 后遗症用 \(\texttt{+}\) 表示,于是:

\[\begin{array}{} \text{药物的疗效} & \texttt{11100}\\ \text{药物后遗症} & \texttt{00001}\\ \text{药物效果} & \texttt{---0+}\\ \end{array} \]

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

\[\begin{array}{} \text{项目} & \text{可治疗} & \text{不变} & \text{后遗症} \\ \text{用药前一状态} & \texttt{QQQ} & \texttt{QQQQ} & \texttt{QQ} \\ \text{药物效果} & \texttt{---} & \texttt{0000} & \texttt{++} \\ \text{一次用药后状态} & \texttt{000} & \texttt{QQQQ} & \texttt{11} \\ \text{中间若干用药} & \cdots & \cdots & \cdots \\ \text{二次用药后状态} & \texttt{000} & \texttt{QQQQ} & \texttt{11} \\ \end{array} \]

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

\[\begin{array}{} \text{项目} & \text{可治疗} & \text{不变} & \text{后遗症} \\ \text{用药前一状态} & \texttt{QQQ} & \texttt{QQQQ} & \texttt{QQ} \\ \text{药物效果} & \texttt{---} & \texttt{0000} & \texttt{++} \\ \text{中间若干用药} & \cdots & \cdots & \cdots \\ \text{原二次用药后状态} & \texttt{000} & \texttt{QQQQ} & \texttt{11} \\ \end{array} \]

效果没有改变。

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

4. 从最后的药物出发

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

我们观察一下:

\[\begin{array}{} \text{项目} & \text{可治疗} & \text{不变} & \text{后遗症} \\ \text{某状态} & \texttt{QQQ} & \texttt{QQQQ} & \texttt{QQ} \\ \text{中间若干用药} & \cdots & \cdots & \cdots \\ \text{纯药效果} & \texttt{---} & \texttt{0000} & \texttt{00} \\ \text{吃纯药后状态} & \texttt{000} & \texttt{QQQQ} & \texttt{QQ} \\ \end{array} \]

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

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

\[\begin{array}{} \text{项目} & \text{不变} & \text{后遗症} \\ \text{某状态} & \texttt{QQQQ} & \texttt{QQ} \\ \text{中间其他若干用药} & \cdots & \cdots \\ \end{array} \]

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

最终我们可以求得答案。

5. 具体实现的一些细节

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

\[f_{S'} \gets f_{S} , S' \subseteq S \]

由于使用优先队列,所以每个状态只访问一次,对应的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!

热门相关:我的治愈系游戏   未来兽世:买来的媳妇,不生崽   大妆   未来兽世:买来的媳妇,不生崽   腹中人的有嚼劲的肉