CF 1500 C
CF 1500 C
意思是：
？给你两个矩阵A，B(1 \(\leq\) n，m \(\leq\) 1500)的\(n \次m \)，它们的元素都是[1，n]内的整数。
？对于每一个操作，可以选择一列作为每行的关键字，按照关键字从小到大的顺序对所有行进行排序，得到一个新的矩阵。这里使用的排序是稳定的，即如果两行具有相同的关键字，则按照原始矩阵中的顺序进行排序。
可以做不超过5000个操作，问能不能把A变成b，不能输出吗？1，否则输出可行的操作序列。
？
解决方案：
？首先，考虑到排序稳定，我们可以确定B的哪一行对应A中的最后一行(当然，如果不对应，就会是-1)
？现在考虑处理一个指示B的第I行是A的第p[i]行的数组p[i]，那么我们可以发现我们最终想把p[i]放在第I个位置，并且把pos[i]设置为A的第I行的位置，也就是我们要求\ (\ for all \) POS [P [I]] POS [P [I]
？然后考虑每个列的操作。如果K列中有A(p[i]，k) A(p[i 1]，K)，那么什么都不会发生。如果有A(p[i]，k) A(p[i 1]，k)，那么如果操作该列，它后面必须跟一个才能做p[i]。
？于是一个图论模型自然出现了。如果一个运算X中的所有A(p[i]，X)=A(p[I ^ 1]，X)，那么我们必须用这个运算来求贪婪，因为它不会变质，也就是说X连接到每个A的I边(p[I ^ 1]，X)。X)A(p[I ^ 1]，X)，那么要求就是这些I在后续的操作中会被反转，也就是我会被连接到X，也就是说所有这样的I只有被解放后才能被释放。运行拓扑排序和反向输出方案。
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/126075.html