problem
给出 n 个数组 A1 到 An ,数组中的元素为 1 到 M 之间的数字。
数组之间也存在字典序,即从第一个数开始逐位比较,一旦某个数字大于另一个,则数组的字典序大于另一个,如果某一个是另一个的前缀,则前缀的字典序更小。
你可以选择一些大于 0 的数字执行减法操作,一旦选中某个数字 k ,则从 A1 到 An 中,所有的数字 k 都要被减掉 M,即变成 k−M,并且只能对于正数执行减法操作。
问能否通过这样的操作,使得这 n 个数组的字典序是不下降的(可以相等)。
solution
以下是显然无解的情况,请特判:
[1 2 3]
[1 2]
观察一些性质:
- 如果 \(A_{11}>A_{21}\),那么必然是 \(A_{11}\) 被减而 \(A_{21}\) 不被减。
- 如果 \(A_{11}<A_{21}\),除了 \(+A_{11}\land -A_{21}\) 外其他都行。
以下就有很多种做法:
solution 1:2-sat
每个点拆成两个点表示被减(\(-x\)) 和不被减(\(+x\)),除此之外还有超级源 \(S\)。
对于两个相邻的数组,找到第一个不相同的,记为 \(u,v\)。
- 如果 \(u<v\) 那么 \(+u\to +v,-v\to -u\)。
- 如果 \(u>v\) 那么 \(S\to-u,S\to+v\)。
建出来一个图。我们强制选 \(S\),看一下 \(S\) 能选到的有没有矛盾(即同时选到 \(-x\) 和 \(+x\))。如果有就无解。
否则,\(S\) 所指示的数字该减就减,该加就加,和 \(S\) 不联通的直接不管。
solution 2:建 DAG
对于两个相邻的数组,找到第一个不相同的,记为 \(u,v\)。然后 \(u\to v\)。
如果建出来的图有环,无解。
注意到对于一条 DAG 上的链,我们把这些数字的符号拿出来,那么就是说 \(u>v\) 时符号必须由负变为正,\(u<v\) 时符号不能减少。
也就是 \(u>v\) 的边,要满足 \(v\) 以后全是正数,\(u\) 往上全是负数。其他没提到的点默认为负。
solution 3:随机化
我们放弃图论。按列考虑这些数组,有个结论是:删除的必然是一段前缀(否则必然不满足条件)。所以有两个大于号的就无解。
考虑第二列,按照 \(A_{i1}\) 相同的分开,继续处理。
问题是如果 \(A{i1}\) 合法,那么不知道删什么。
随机化:继续往下,每次到要删除的时机,退回到 \(A_{i1}\) 从头来过。
听说 100 次能过。
code
solution 2
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cassert>
#include <numeric>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
template<int N> struct dsu{
int fa[N+10],siz[N+10],cnt;
dsu(int n=N):cnt(n){iota(fa+1,fa+n+1,1),fill(siz+1,siz+n+1,1);}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y){if(x=find(x),y=find(y),x!=y) cnt--,siz[x]<siz[y]&&(swap(x,y),0),siz[fa[y]=x]+=siz[y];}
};
int n,m,deg[1<<16],S,col[1<<16],key[1<<16],f[1<<16];
vector<int> a[1<<16],g[1<<16];
queue<int> q;
dsu<1<<17> s;
bool toposort(){
for(int i=1;i<=m;i++) for(int v:g[i]) deg[v]++;
for(int i=1;i<=m;i++) if(!deg[i]) q.push(i);
while(!q.empty()){
int u=q.front(); q.pop();
for(int v:g[u]){
//u 是正数,u+n 是负数
if(u>v) col[v]=1,key[u]=1;
else col[v]|=col[u];
if(--deg[v]==0) q.push(v);
}
}
return *min_element(deg+1,deg+m+1)||*max_element(deg+1,deg+m+1);
}
bool kly=0;
bool dfs(int u){
if(~f[u]) return f[u];
f[u]=key[u];
for(int v:g[u]) f[u]|=dfs(v);
if(f[u]) kly|=col[u];
return f[u];
}
int main(){
#ifdef LOCAL
// freopen("22.in","r",stdin);
// freopen("log.out","w",stderr);
#endif
scanf("%d%d",&n,&m),S=m<<1|1;
for(int i=1,k;i<=n;i++){
scanf("%d",&k);
a[i]=vector<int>(k);
for(int&x:a[i]) scanf("%d",&x);
}
for(int i=2;i<=n;i++){
int j=0,lim=min(a[i-1].size(),a[i].size());
while(j<lim&&a[i-1][j]==a[i][j]) j++;
//最多两倍时间
if(j<lim) g[a[i-1][j]].push_back(a[i][j]);
else if(a[i-1].size()>a[i].size()) return puts("No"),0;
}
for(int i=1;i<=m;i++){
for(int v:g[i]) debug("%d %d\n",i,v);
}
if(toposort()) return debug("fuck"),puts("No"),0;
memset(f,-1,sizeof f);
for(int i=1;i<=m;i++) dfs(i);
if(kly) return debug("sewoifhqoigiwueg"),puts("No"),0;
puts("Yes");
vector<int> dest;
for(int i=1;i<=m;i++) if(!col[i]) dest.push_back(i);
#ifdef LOCAL
for(int i=1;i<=m;i++){
for(int v:g[i]) assert(i-!col[i]*m<v-!col[v]*m);
}
#endif
printf("%zu\n",dest.size());
for(int x:dest) printf("%d ",x); puts("");
return 0;
}