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. 一种药物吃几次？
接下来我们尝试考虑一种药物吃几次。
假设一个药物吃两次及以上，为了方便表示，我们不妨交换每种症状的相对位置，使得对于这个药物而言，是“治疗症状、保持原状、后遗症”的格式。例如原来是：
\[\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 #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< yy.t;priority_queue q;void dfs(LL e,LL p, LL t){if(vis[e]) return;if(e < (1<>p)&1) == 1){dfs(e^(1<>p)&1) == 0){ans = min(ans,ansdfs(e|(1<>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！
标签：
