P7796 [COCI2014-2015#7] POLICE

· · 题解

图书馆里有 n 个书架，每个书架可以放 m 本书。小C是一位优秀的图书管理员，所以他决定整理图书馆中的所有图书，如果可以的话，把所有图书放回它们原来的位置。他打算用下面的方法来整理图书：

1.如果书架上的某本书的左边或右边是空的，就可以把这本书书向左或向右移动。

2.把一本书从书架上拿起来，再放回到另一个空的位置（可以是任意一个书架）。

可是没过多久小 C 就累了。如果他手上已经有了一本书，他就不能再移动其他的书。而且因为把书拿出来又放回去实在太麻烦了，所以小 C 希望尽可能少地将书从书架上拿起来（即步骤2）。请帮小 C 算出，他最少需要将书拿出来多少次。

1\leq n,m\leq 1000

感觉做法挺奇妙的 .

一行一行地考虑 .

先考虑当前行和最终行出现书本相同的情况 . 此时，又分出来两种 ，有空位和无空位 .

  1. 有空位，相当于，找到一本书，再放到它原本的位置上 . 那么，要选出 k 本书，这 k 本书相对顺序是正确的，其他的书要根据这 k 本书的位置放入 . 会发现，这是一个 lis 的问题 . 那么，可以 O(n\log n) 地解决.
  2. 没有空位，此时分为两种情况 .
    • 当前行与目标行相同 . 无需操作 .
    • 当前行与目标行不同，如果其他书架上没有空位，则输出 -1 . 否则，将当前行中一本不位于 k 本书中的书放到其他书架上，再将当前行排序，排完序后直接插入正确的位置，时间复杂度为 O(n\log n) .

考虑玩当前行和最终行出现书本相同的情况，下面就是不同的 .

如果最终应该出现在第 j 行的书出现在了第 i 行，那么，由 i 向 j 连一条有向边 ，得到一个有向图 G_1 ；将 G_1 中的有向边变成无向，可以得到一个无向图 G_2 . 对于 G_2 中的每一个连通块，在 G_1 中可以加上一些虚构的有向边，是的其变成一个具有欧拉回路的图 .

那么，对于这个欧拉回路，就是一个移动的方案，但是，这个方案的开始，必定是存在一个连通块中的行有一个空位 . 如果其他的行没有空位的话，那么，必定是不可行的，要输出 -1 .否则，如果连通块不存在空位，需要拿出一本书放在另一行中，然后再移动 ，代价加 1 .

因为从当前书架拿起，放到其他书架的书必定花费代价 1 ，而且必定会放到正确的相对位置上 . 代价就是原来就同时存在与当前和最终行中的书的和 - 当前和最终行中的书的和的 lis + 在最终行但不在当前行的书的数量 . 再加上启动时可能需要的 1 代价.

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

空间复杂度 : O(nm)

code

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    int res=0;
    while(ch>='0'&&ch<='9'){
        res=res*10+ch-'0';
        ch=getchar();
    }
    return res;
}
inline void print(int res){
    if(res==0){
        putchar('0');
        return;
    }
    int a[8],len=0;
    while(res>0){
        a[len++]=res%10;
        res/=10;
    }
    for(int i=len-1;i>=0;i--)putchar(a[i]+'0');
}
const int inf=1e9+10;
int n,m;
int a[1010][1010],b[1010][1010],nu[1010*1010];
int pos[1010*1010];
bool ok[1010],spare=false;
int exist[1010*1010];
int ans=0;
int bit[1010];
inline void upd(int i,int val){
    while(i<=m){
        bit[i]=max(bit[i],val);
        i+=i&-i;
    }
}
inline int qry(int i){
    int res=0;
    while(i){
        res=max(res,bit[i]);
        i-=i&-i;
    }
    return res;
}
vector<int>v,g[1010];
bool vis[1010];
void dfs(int x){
    vis[x]=true;v.push_back(x);
    for(int i=0;i<(int)g[x].size();i++){
        int to=g[x][i];
        if(!vis[to])dfs(to);
    }
}
int solve(int id){
//  cout<<endl;
//  for(int i=0;i<m;i++)cout<<a[id][i]<<" ";cout<<endl;
//  for(int i=0;i<m;i++)cout<<b[id][i]<<" ";cout<<endl;
    int cnt=0;
    for(int i=0;i<m;i++)if(a[id][i]>0)nu[a[id][i]]=cnt++;
    for(int i=0;i<=m;i++)bit[i]=0;
    for(int i=0;i<m;i++)if(b[id][i]>0)
        upd(nu[b[id][i]]+1,qry(nu[b[id][i]])+1);
    int mx=0;
    for(int i=1;i<=cnt;i++)mx=max(mx,qry(i));
    return mx;
}
int na[1010],nb[1010];
void solve(vector<int>v){
    bool sp=false;
    for(int i=0;i<(int)v.size();i++){
        int id=v[i];
        for(int j=0;j<m;j++)if(a[id][j]==0)sp=true;
    }
    int cnt=0;
    for(int i=0;i<(int)v.size();i++){
        int id=v[i];
        for(int j=0;j<m;j++)if(a[id][j]>0)exist[a[id][j]]++,cnt++;
        for(int j=0;j<m;j++)if(b[id][j]>0)exist[b[id][j]]++;        
        for(int j=0;j<m;j++)na[j]=a[id][j];
        for(int j=0;j<m;j++)nb[j]=b[id][j];
        for(int j=0;j<m;j++)if(a[id][j]>0&&exist[a[id][j]]<2)a[id][j]=0;
        for(int j=0;j<m;j++)if(b[id][j]>0&&exist[b[id][j]]<2)b[id][j]=0;
        ans-=solve(id);
        for(int j=0;j<m;j++)a[id][j]=na[j];
        for(int j=0;j<m;j++)b[id][j]=nb[j];
        for(int j=0;j<m;j++)if(a[id][j]>0)exist[a[id][j]]--;
        for(int j=0;j<m;j++)if(b[id][j]>0)exist[b[id][j]]--;
    }
//  putchar('\n');
    ans+=cnt;
    if(!sp){
        if(!spare){
            putchar('-');
            putchar('1');
            exit(0);
        }
        else ans++;
    }
}
int main(){
//  freopen("test.txt","r",stdin);
    n=read();m=read();
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)a[i][j]=read();
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)b[i][j]=read();
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(a[i][j]==0)spare=true;
    for(int i=0;i<n;i++){
        bool flag=true;
        int cnt=0;
        for(int j=0;j<m;j++){
            if(a[i][j]>0){
                exist[a[i][j]]=true;
                cnt++;
            }
        }
        for(int j=0;j<m;j++){
            if(b[i][j]>0){
                if(!exist[b[i][j]])
                    flag=false;
                else exist[b[i][j]]=false;
            }
        }
        for(int j=0;j<m;j++){
            if(exist[a[i][j]]){
                flag=false;
                exist[a[i][j]]=false;
            }
        }
        if(flag){
            ok[i]=true;
            int tmp=cnt-solve(i);
            ans+=tmp;
            if(cnt==m&&tmp!=0){
                if(!spare){                 
                    putchar('-');
                    putchar('1');
                    return 0;
                }
                else ans++;
            }
        }
    }
//  for(int i=0;i<n;i++)print(ok[i]),putchar(' ');
//  putchar('\n');
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(a[i][j]>0&&(!ok[i]))pos[a[i][j]]=i;
    for(int i=0;i<n;i++)for(int j=0;j<m;j++){
        if(b[i][j]>0&&(!ok[i])&&pos[b[i][j]]!=i){
        //  print(pos[b[i][j]]);putchar(' ');print(i);putchar('\n');
            g[pos[b[i][j]]].push_back(i);
            g[i].push_back(pos[b[i][j]]);
        }
    }
    for(int i=0;i<n;i++)if((!ok[i])&&(!vis[i])){
        v.clear();
        dfs(i);
    //  for(int j=0;j<(int)v.size();j++)print(v[j]),putchar(' ');
        solve(v);
    }   
    print(ans);
    return 0;
}
/*inline? ll or int? size? min max?*/