我t2的做法是这样的:先假定所有的变量都为True,然后模拟一遍。然后再以模拟出来的结果为基础,再模拟一遍。观察所有变量两遍模拟后的值,若二者相反,即以原来的输入为基础推出了完全相反的结果,则这个变量只能为Unknown。
但是这样会出问题,在于“直接把一个元素赋为Unknown”这个操作。例:
+ 1 2
+ 2 3
+ 3 4
+ 4 5
U 5
实际上五个都必须是Unknown。
所以我们不跑两遍模拟,而是直接跑n+1遍,然后比较最后两次模拟的结果。当n太大的时候适当地缩减跑的次数,比如1e5的数据只跑80遍。
这个东西随便整一条链或者深度稍微大一点应该就会挂。
想知道官方数据大概会给我多少分。
(洛谷80,云斗AC,民间数据是不是有点水了)