题目
分析
这道题目还是典型的并查集题目,“等式”一类的约束相当于“朋友”,可以直接归并;“不等式”一类的约束相当于“敌人”。举个例子:
\( \left\{\begin{matrix} x_1 = x_2 \\x_2 = x_3 \\x_3 = x_4 \\x_4\neq x_1 \end{matrix}\right. \)
前三个等式都可以简单归并成为一个集合。此时\(x_4\)的祖先也归并到了\(x_1\)。在处理不等式的时候,\(x_4\)和\(x_1\)有一个共同祖先——这表明它俩存在等式约束,所以出现了矛盾。因此就可以马上中断运行,约束条件已经无法全部满足了。
答案
思考
在用Trae编写时,它用了一些高级的语法(比如tuple
,以及直接用{...}
构建tuple
,但是洛谷的编译器还比较老,不能编译。所以改用了更通用的语法。
另外,这里要用map<int, int>
来保存祖先关系,因为给出的变量序号可能很大但很稀疏。
做到这题的时候(2025年4月24日上午),我发现我可以下载测试数据了。虽然只能下载2次,但还是内牛满面。
我下载了测试点2的输入数据(因为一开始在这里出现RE——数组下标的问题),竟然有14K,72万行!