题解：P12741 [POI 2016 R3] 等价程序 Equivalent programs

fish_love_cat · 2025-07-10 09:51:51 · 题解

秒了，但是目前最劣解，但是目前最短解。

每个限制关系只限制了两种数字的相对位置关系，于是考虑对于每个限制进行 check，这个是好做的。

具体的，我们可以统计每一个位置前某个数字的数量，然后对于限制 (x,y)，我们将两个数列中对应 x 前面的 y 数量进行比对即可。

一个很好想的维护思路是前缀和，但是 MLE 了。

于是可以存位置，查找的时候二分即可。

时间复杂度 O(nm\log n)。

我们对于 (x,y) 做一个类似于启发式合并的优化，这样就有了 O(m\frac{n}{k}\log n)。

另外的数据范围其实应该是 m\le \frac{k(k-1)}{2}，代进去复杂度应为 O(nk\log n)，喜提最劣解。

#include<bits/stdc++.h>
using namespace std;
int a[100005],b[100005];
vector<int>v1[1005];
vector<int>v2[1005];
pair<int,int>p[50005];
int main(){
    int n,k,m;
    cin>>n>>k>>m;
    for(int i=1;i<=m;i++)
    cin>>p[i].first>>p[i].second;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        v1[a[i]].push_back(i);
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        v2[b[i]].push_back(i);
    }
    for(int i=1;i<=k;i++)
    if(v1[i].size()!=v2[i].size()){
        puts("NIE");
        return 0;
    }
    for(int i=1;i<=m;i++){
        int x=p[i].first,y=p[i].second;
        if(v1[x].size()>v1[y].size())swap(x,y);
        for(int j=0;j<v1[x].size();j++)
        if((lower_bound(v1[y].begin(),v1[y].end(),v1[x][j])-v1[y].begin())!=
          (lower_bound(v2[y].begin(),v2[y].end(),v2[x][j])-v2[y].begin())){
            puts("NIE");
            return 0;
        }
    }
    puts("TAK");
    return 0;
}