洛谷:P1955:程序自动分析


洛谷:P1955:程序自动分析

Table of Contents

题目

P1955:程序自动分析

分析

这道题目还是典型的并查集题目,“等式”一类的约束相当于“朋友”,可以直接归并;“不等式”一类的约束相当于“敌人”。举个例子:

\( \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\)有一个共同祖先——这表明它俩存在等式约束,所以出现了矛盾。因此就可以马上中断运行,约束条件已经无法全部满足了。

答案

Solution

思考

在用Trae编写时,它用了一些高级的语法(比如tuple,以及直接用{...}构建tuple,但是洛谷的编译器还比较老,不能编译。所以改用了更通用的语法。

另外,这里要用map<int, int>来保存祖先关系,因为给出的变量序号可能很大但很稀疏。

做到这题的时候(2025年4月24日上午),我发现我可以下载测试数据了。虽然只能下载2次,但还是内牛满面。

我下载了测试点2的输入数据(因为一开始在这里出现RE——数组下标的问题),竟然有14K,72万行!

上一篇 下一篇