题解：P14055 [POI 2015 R3] 路标 Direction signs

· · 题解

设路标的位置为 x_1,x_2,\cdots,x_n，城市的位置为 y_{1},y_2,\cdots,y_m。

那么 正确的 d_{i,j} 相当于限制了：

\exist \varepsilon_{i,j}\in [0,1):y_j-x_i-\varepsilon_{i,j}=d_{i,j} 现在钦定路标 $u$ 在最大集合中，要找到 **此时最大合法路标集合**。 考虑判断这东西肯定是行找个参照减一下，列找个参照减一下。这样就把 $x,y$ 消掉了。 行显然是找 $u$ 减：$a_{i,j}=d_{i,j}-d_{u,j}=x_u-x_1-\varepsilon_{i,j}+\varepsilon_{u,j}

列我们可以找最小值减，设第 i 行的最小值为 a_{i,w_i}，则有：

b_{i,j}=a_{i,j}-a_{i,w_i}=-\varepsilon_{i,j}+\varepsilon_{u,j}+\varepsilon_{i,w_i}-\varepsilon_{u,w_i}\ge 0

接下来要找到最大集合 S，使得 \{i\in S,\varepsilon_{i,*}\} 的取值互不矛盾，即存在 \varepsilon_{i,*} 的填法满足 b 数组。

首先根据 \varepsilon_{i,j}\in [0,1) 得出 b_{i,j}<2，而 b_{i,j}\in \N\Rightarrow b_{i,j}\in \{0,1\}。

我们就可以丢弃所有存在 b_{i,j}>1 的行。接下来变形一下：

\varepsilon_{i,j}=\varepsilon_{u,j}-\varepsilon_{u,w_i}+\varepsilon_{i,w_i}-b_{i,j}

单独考虑第 i 行，存在一个 \varepsilon_{i,w_i}\in[0,1) 使得对所有 j 上式都落在 [0,1) 的 充要条件 是：

\text{D}(\{\varepsilon_{u,j}-b_{i,j}\})<1 \\ \text{D}(S)=\max S-\min(S)

因为 b_{i,j}\in\{0,1\}，把行中的两类列分成 S_{0/1}=\{j:b_{i,j}=0/1\}，可以证明上面的条件等价于：

\max_{k\in S_0}\varepsilon_{u,k}\;<\;\min_{j\in S_1}\varepsilon_{u,j}

也就是说，在某个给定的 \varepsilon_u 大小顺序下，行 i 可行当且仅当所有 0 列都小于所有 1 列。

换句话说，记 T_i=\{j:b_{i,j}=1\}，相当于选出最多的 T_i 使得两两之间存在包含关系，否则顺序就矛盾了。

直接 bitset 然后拓扑序遍历一遍，复杂度 \mathcal{O}(\frac{n^2m}{w})。

上述结论充分性显然，必要性就是具体构造合法的 \varepsilon。这里不赘述，感兴趣可以自己想想。

:::info[\mathbf{code}]

#include<bits/stdc++.h>
#define LL long long
#define all(x) x.begin(),x.end()
#define bs basic_string<int>
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
mt19937 rnd(time(0));
const int N=1005,M=205;
int n,m,d[N][M],a[N][M],L[N],pre[N];
bitset<M>f[N];bs ans;
inline bs sol(int u)
{
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=d[i][j]-d[u][j];
    bs g;int w;
    for(int i=1;i<=n;i++)
    {
        w=*min_element(a[i]+1,a[i]+1+m);
        bool o=1;f[i].reset();
        for(int j=1;j<=m;j++)
        {
            a[i][j]-=w;
            if(a[i][j]>1){o=0;break;}
            f[i][j]=a[i][j];
        }
        if(o) g+=i,L[i]=pre[i]=0;
    }
    sort(all(g),[](int x,int y){return f[x].count()<f[y].count();});
    for(int i=0;i<g.size();i++)
    {
        int x=g[i];
        for(int j=0;j<i;j++)
        {
            int y=g[j];
            if((f[y]&f[x])==f[y]&&L[y]+1>L[x])
                L[x]=L[y]+1,pre[x]=y;
        }
    }w=0;
    for(int i:g) if(L[i]>=L[w]) w=i;
    for(g.clear();w;w=pre[w]) g+=w;return g;
}
int main()
{
    cin.tie(0)->sync_with_stdio(0);cout.tie(0);cin>>n>>m;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>d[i][j];
    for(int i=1;i<=40;i++)
    {
        int x=rnd()%n+1;bs t=sol(x);
        if(t.size()>ans.size()) ans=t;
    }
    sort(all(ans),[](int x,int y){
        for(int i=1;i<=m;i++) if(d[x][i]^d[y][i]) return d[x][i]>d[y][i];
        return x<y;
    });cout<<ans.size()<<"\n";
    for(int i:ans) cout<<i<<" ";
    return 0;
}

:::