找回密码
 立即注册
首页 业界区 业界 P9869 [NOIP2023] 三值逻辑题解

P9869 [NOIP2023] 三值逻辑题解

绂染 2026-1-27 22:35:01
题目链接
这里使用扩展域并查集实现。
既然来看题解了,相信你已经读懂题了,这里不再赘述题意,直接进入主题。
没读懂可以去看其他题解
思路:

为何用并查集

考虑什么情况下一个变量的最终值为 \(U\)?当且仅当一个变量 \(x=-x\) 或 \(x\) 与 \(-x\) 中有一个等于 \(U\) 那么这个变量就是 \(U\)。
关于维护 \(x\)、\(-x\) 以及与 \(U\) 之间的关系,可以想到用扩展域并查集。正负对应 \([1,n]\) 与 \([n+1,2n]\),\(T\)、\(F\)、\(U\) 分别对应 \(2n+1\)、\(2n+2\) 与 \(2n+3\)。
维护赋值操作

此题的特殊点在于初始值都不知道,无法直接进行赋值操作。所以考虑如何维护。
我们记每个变量的最终值为 \(ed_i\)。
一个错误的思路就是用 \(ed_x\) 表示当前 \(x\) 赋到的值的下标 \(y\)。这样子做的问题在于 \(ed_y\) 在不停改变,如果 \(ed_y\) 又发生了改变,那么 \(ed_x\) 相应的也会被改变。
但是,如果每个变量的初始值已知,那么就可以直接进行赋值,且不会受到后续变量改变的干扰。
所以,我们假设初始值已知(令初始时 \(ed_i=i\)),然后直接进行赋值操作。最终可以得到 \(ed_i\) 等于某个值 \(x\)。由于变量的初始值等于它的最终值,所以 \(i\) 和 \(x\) 属于同一集合,\(-i\) 与 \(-x\) 属于同一集合,这样就能用并查集维护了。
(记得更新完后还要更新相应负值
统计答案

将 \(x=-x\) 或 \(x\) 与 \(-x\) 中有一个等于 \(U\) 的与 \(U\) 合并,最后判断哪些 \(i\) 与 \(U\) 在同一集合即可。
实现:

赋值操作

[code]    for(int i=1;i

相关推荐

2026-2-3 23:35:55

举报

感谢发布原创作品,程序园因你更精彩
2026-2-7 22:54:41

举报

2026-2-8 09:21:13

举报

很好很强大  我过来先占个楼 待编辑
2026-2-8 17:14:51

举报

2026-2-8 23:08:52

举报

2026-2-26 09:57:32

举报

2026-2-27 23:16:40

举报

2026-3-8 05:11:27

举报

12下一页
您需要登录后才可以回帖 登录 | 立即注册