題目
題目地址：https://gmoj.net/senior/#main/show/6652
題目大意：
給你 n n n 個 1.. m 1..m 1..m 的排列，對于每一個排列，你都可以從前往后將元素依次插入一個佇列中（要么放到佇列頭，要么放在佇列尾），問有多少種佇列是這 n n n 個排列都可以到達的，并要求給出這些佇列中字典序最小的那一個，
n ≤ 1000 , ∑ m ≤ 5000 n\le 1000,\sum m\le 5000 n≤1000,∑m≤5000
題解
這題不能用 D P DP DP 之類的演算法來處理，
發現每個排列的第 m m m 個元素必定在所得佇列的頭或者尾處，因此考慮倒著求這個佇列，這是一個從佇列的兩端向中間填數字的程序，
假設現在處理到第 k k k 個元素，第 i i i 個排列完成了佇列的 1.. x i ? 1 1..x_i-1 1..xi??1 及 y i + 1.. m y_i+1..m yi?+1..m 的部分（即現在要在 x i x_i xi? 和 y i y_i yi? 上填數字），
令 l = max ? x i , r = min ? y i l=\max x_i,r=\min y_i l=maxxi?,r=minyi? ，
如下圖：
由于要求佇列是可以由每一行得到的， 1.. l 1..l 1..l 和 r . . m r..m r..m 上的數字已經被固定了，令 s i s_i si? 表示佇列上第 i i i 位的數字，
對于第 i i i 個序列，分類討論：
- 若 x i < l , 且 y i > r x_i<l,\text{且} y_i>r xi?<l,且yi?>r ，就看 a i , k a_{i,k} ai,k? 與 s x i , s y i s_{x_i},s_{y_i} sxi??,syi?? 中的哪一個相等，把那一位給補上；
- 若 x i = l , 且 y i > r x_i=l,\text{且} y_i>r xi?=l,且yi?>r ，若 a i , k = s y i a_{i,k}=s_{y_i} ai,k?=syi?? ，就把 y i y_i yi? 補上，否則 a i , k a_{i,k} ai,k? 只能放在 l l l 處，即 s l = a i , k s_l=a_{i,k} sl?=ai,k? ；
- 若 x i < l , 且 y i = r x_i<l,\text{且} y_i=r xi?<l,且yi?=r ，若 a i , k = s x i a_{i,k}=s_{x_i} ai,k?=sxi?? ，就把 x i x_i xi? 補上，否則 a i , k a_{i,k} ai,k? 只能放在 r r r 處，即 s r = a i , k s_r=a_{i,k} sr?=ai,k? ；
- 若 x i = l , 且 y i = r x_i=l,\text{且} y_i=r xi?=l,且yi?=r ， a i , k a_{i,k} ai,k? 既可以放在 l l l 處，又可以放在 r r r 處；
把情況 2 , 3 , 4 2,3,4 2,3,4 中可以放到 l , r l,r l,r 上的 a i , j a_{i,j} ai,j? 都取出，若有 a i , j a_{i,j} ai,j? 有多于2種值，就說明無解（最多只能把一個數放在 l l l ，再把一個數放在 r r r ，不能放第三個數），因為不可能有所有數都不滿足情況 2 , 3 , 4 2,3,4 2,3,4 的情況，現在就只可能有一種或兩種 a i , j a_{i,j} ai,j? 的值，
對于有兩種值的情況，如果 s l , s r s_l,s_r sl?,sr? 中至少有一個已經被填了數字，繼續處理第 k ? 1 k-1 k?1 個元素即可；
否則，令這兩個值為 p , q p,q p,q ，可以發現既可以是 s l = p , s r = q s_l=p,s_r=q sl?=p,sr?=q ，也可以是 s l = p , s r = q s_l=p,s_r=q sl?=p,sr?=q ，因此有兩種方案，因為我們在求方案的同時還要求字典序最小的佇列，因此選擇其中字典序較小的那個即可，
對于有一種值的情況，如果 s l , s r s_l,s_r sl?,sr? 中有一個已經被填了數字了，繼續處理第 k ? 1 k-1 k?1 個元素即可；
否則，這個數既可以放到 l l l 上，又可以放到 r r r 上，有兩種方案，
那么怎么知道哪種方案字典序最小呢？直接往后暴力遞回看，假設它放在 l l l 上，后面會不會有比它小的數滿足放到 l + 1 l+1 l+1 上的條件就行了，
時間復雜度 O ( n ∑ m ) O(n\sum m) O(n∑m) ，
代碼
#include<cstdio>
using namespace std;
#define fo(i,l,r) for(i=l;i<=r;++i)
#define N 1005
const int P=1000000007;
char buf[100005],*l=buf,*r=buf;
inline char gc()
{return l==r&&(r=(l=buf)+fread(buf,1,100005,stdin),l==r)?EOF:*l++;}
inline void read(int &k)
{
char ch;while(ch=gc(),ch<'0'||ch>'9');k=ch-48;
while(ch=gc(),ch>='0'&&ch<='9') k=k*10+ch-48;
}
int a[N][N],num[N],x[N],y[N],n,m;
bool b[N],locked[N];
inline void swap(int &x,int &y){int z=x;x=y,y=z;}
inline int finish()
{
int i,j,l,r;
// puts("check");
// fo(i,1,m) printf("%d\t",num[i]);
// puts("");
fo(i,1,n)
{
l=1,r=m;
for(j=m;j;--j)
{
if(a[i][j]==num[l]) ++l;
else if(a[i][j]==num[r]) --r;
else return 0;
}
}
return 1;
}
bool judge(int k,int num)
{
if(!k) return 1;
int i,p=0,q=0;
fo(i,1,n) if(!locked[a[i][k]])
{
if(!p) p=a[i][k];
else if(p!=a[i][k])
{
if(!q) q=a[i][k];
else if(q!=a[i][k]) return 1;
}
}
if(!p) return judge(k-1,num);
if(!q)
{
if(p<num) return 0;
locked[p]=1;
bool res=judge(k-1,num);
locked[p]=0;
return res;
}
return num<p&&num<q;
}
int solve(int k,int l,int r)
{
if(l>r||!k) return finish();
int i,p=0,q=0;
// printf("[%d,%d]\t%d\n",l,r,k);
// fo(i,1,n) printf("(%d,%d)\t",x[i],y[i]);
// puts("");
// fo(i,1,m) printf("%d\t",num[i]);
// puts("");
fo(i,1,n)
{
b[i]=1;
if(x[i]<l&&a[i][k]==num[x[i]]) ++x[i],b[i]=0;
else if(y[i]>r&&a[i][k]==num[y[i]]) --y[i],b[i]=0;
if(b[i]&&x[i]<l&&y[i]>r) return 0;
// printf("%d\t",b[i]?a[i][k]:-1);
}
// puts("");
fo(i,1,n) if(b[i]) break;
if(i>n) return solve(k-1,l,r);
fo(i,1,n) if(b[i])
{
if(!p) p=a[i][k];
else if(a[i][k]!=p)
{
if(q&&q!=a[i][k]) return 0;
q=a[i][k];
}
}
if(p>q) swap(p,q);
int cnt=0;
bool b1,b2;
if(!p)
{
fo(i,1,n) if(b[i]&&x[i]<l&&y[i]>l) break;
if(i>n) ++cnt;b1=i>n;
fo(i,1,n) if(b[i]&&y[i]>r&&x[i]<r) break;
if(i>n) ++cnt;b2=i>n;
if(!cnt) return 0;
locked[q]=1;
if(b1&&(judge(k-1,q)||!b2))
{
num[l]=q;
fo(i,1,n) if(b[i]) x[i]==l?++x[i]:--y[i];
return l==r?finish():1LL*cnt*solve(k-1,l+1,r)%P;
}
else
{
num[r]=q;
fo(i,1,n) if(b[i]) y[i]==r?--y[i]:++x[i];
return l==r?finish():1LL*cnt*solve(k-1,l,r-1)%P;
}
}
fo(i,1,n) if(b[i])
{
if(a[i][k]==p&&x[i]<l) break;
if(a[i][k]==q&&y[i]>r) break;
}
if(i>n) ++cnt;b1=i>n;
swap(p,q);
fo(i,1,n) if(b[i])
{
if(a[i][k]==p&&x[i]<l) break;
if(a[i][k]==q&&y[i]>r) break;
}
if(i>n) ++cnt;b2=i>n;
if(!cnt) return 0;
if(!b1) swap(p,q);
locked[p]=locked[q]=1;
num[l]=q,num[r]=p;
fo(i,1,n) if(b[i])
{
if(a[i][k]==q) ++x[i];
else --y[i];
}
if(l==r) return finish();
return 1LL*cnt*solve(k-1,l+1,r-1)%P;
}
int main()
{
freopen("array.in","r",stdin);
freopen("array.out","w",stdout);
int T,i,j,ans;
read(T);
while(T--)
{
read(n),read(m);
fo(i,1,n) fo(j,1,m)
read(a[i][j]);
fo(i,1,n) x[i]=1,y[i]=m;
fo(i,1,m) num[i]=0,locked[i]=0;
ans=solve(m,1,m);
printf("%d\n",ans);
if(ans)
{
fo(i,1,m-1) printf("%d ",num[i]);
printf("%d\n",num[m]);
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/265486.html
標籤：其他