[atACL001F]Center Rearranging

有一个（比较显然又有点假的）结论：最优方案中（若存在），每一个数（指$3n$个）最多被移动1次

先$o(n^{2})$枚举移动到队首和队尾的操作次数（即目标状态的一个前缀和后缀），判定能否合法

首先，根据这个前缀和后缀的数字以及个数，可以确定每类数（指$n$类）的操作（但不能确定顺序），即可以知道操作了多少次$L$和$R$

（同时由于不同类的顺序是独立的，这就保证了这个前缀和后缀符合条件，考虑中间未被操作的部分）

其次，对于每一类数，将其$L$和$R$的操作次数组成二元组，分为以下几类：

(1)$(3,0)$和$(0,3)$，一定无解

(2)$(1,1)$，与顺序有关，未被操作数的位置可能是原序列中最左/最右的

(3)$(1,2)$和$(2,1)$，强制顺序（例如$(1,2)$必须先$L$），可以确定未被操作数的位置

(4)除此之外（$(0,0)$、$(0,1)$和$(1,0)$），顺序无关（一共就1次）且可以确定未被操作数的位置

最后，考虑中间这些未被操作数的位置关系：

假设已经确定了未被操作数的位置（在目标状态中的），我们不需要算出具体的初始位置，比较相邻两数的对应位置是否满足单调性（因为未被操作的两数相对顺序不变）、操作的顺序是否有矛盾

（对应位置：根据目标状态以及二元组可以判断其在初始状态中是该类数中的第几个，初始状态中该类数的第“几”个即对应位置）

操作顺序的限制分为两类：1.对于第(2)(3)种情况，同一类数不同操作的限制；2.对于不同类数的同一种操作，距离1或$3n$越远的越优先，可以证明存在矛盾等价于存在4元环（点更多可以压缩）

还有$(1,1)$的情况，考虑2-sat连边，限制（边）同样有两类，每一类再分为确定点与非确定点、非确定点与非确定点两类讨论一下即可

判定时间复杂度为$o(n^{2})$，因此总复杂度为$o(n^{4})$，可以通过

  1 #include<bits/stdc++.h>

  2 using namespace std;

  3 #define N 105

  4 struct ji{

  5     int nex,to;

  6 }edge[N*N];

  7 vector<int>vv,v[N];

  8 int E,n,x,ans,a[N],mx[N],mn[N],sl[N],sr[N],s[N],p[N],head[N],vis[N];

  9 void add(int x,int y){

 10     edge[E].nex=head[x];

 11     edge[E].to=y;

 12     head[x]=E++;

 13 }

 14 void dfs(int k){

 15     if (vis[k])return;

 16     vis[k]=1;

 17     for(int i=head[k];i!=-1;i=edge[i].nex)dfs(edge[i].to);

 18 }

 19 bool pd(int k){

 20     memset(vis,0,sizeof(vis));

 21     dfs(k);

 22     return vis[k^1];

 23 }

 24 bool pd(int x,int y){

 25     memset(sl,0,sizeof(sl));

 26     memset(sr,0,sizeof(sr));

 27     for(int i=1;i<=x;i++)sl[a[i]]++;

 28     for(int i=y;i<=3*n;i++)sr[a[i]]++;

 29     for(int i=1;i<=n;i++)

 30         if ((sl[i]==3)||(sr[i]==3))return 0;

 31     vv.clear();

 32     memset(s,0,sizeof(s));

 33     memset(p,0,sizeof(p));

 34     p[x]=-1,p[y]=0x3f3f3f3f;

 35     for(int i=x+1;i<y;i++){

 36         if ((sl[a[i]]==1)&&(sr[a[i]]==1)){

 37             vv.push_back(i);

 38             continue;

 39         }

 40         if (!s[a[i]]){

 41             p[i]=0;

 42             if ((sl[a[i]]==2)&&(sr[a[i]]==0))p[i]=2;

 43         }

 44         if (s[a[i]]==1){

 45             p[i]=2;

 46             if ((!sl[a[i]])&&(!sr[a[i]]))p[i]=1;

 47         }

 48         if (s[a[i]]==2)p[i]=2;

 49         p[i]=v[a[i]][p[i]];

 50         if (p[i]<p[i-1])return 0;

 51         s[a[i]]++;

 52     }

 53     for(int i=1;i<=n;i++)

 54         if ((sl[i]==2)&&(sr[i]==1))

 55             for(int j=1;j<=n;j++)

 56                 if ((sl[j]==1)&&(sr[j]==2)&&(mx[j]<mx[i])&&(mn[j]<mn[i]))return 0;

 57     E=0;

 58     memset(head,-1,sizeof(head));

 59     for(int i=0;i<vv.size();i++){

 60         if (p[vv[i]-1]){

 61             if (v[a[vv[i]]][2]<p[vv[i]-1])return 0;

 62             if (v[a[vv[i]]][0]<p[vv[i]-1])add(2*i,2*i+1);

 63         }

 64         else{

 65             if (v[a[vv[i]]][2]<v[a[vv[i]-1]][0])return 0;

 66             if (v[a[vv[i]]][2]<v[a[vv[i]-1]][2])add(2*i+1,2*i-2);

 67             if (v[a[vv[i]]][0]<v[a[vv[i]-1]][0])add(2*i,2*i+1);

 68             else

 69                 if (v[a[vv[i]]][0]<v[a[vv[i]-1]][2])add(2*i,2*i-2);

 70         }

 71         if (p[vv[i]+1]){

 72             if (v[a[vv[i]]][0]>p[vv[i]+1])return 0;

 73             if (v[a[vv[i]]][2]>p[vv[i]+1])add(2*i+1,2*i);

 74         }

 75         else{

 76             if (v[a[vv[i]]][0]>v[a[vv[i]+1]][2])return 0;

 77             if (v[a[vv[i]]][0]>v[a[vv[i]+1]][0])add(2*i,2*i+3);

 78             if (v[a[vv[i]]][2]>v[a[vv[i]+1]][2])add(2*i+1,2*i);

 79             else

 80                 if (v[a[vv[i]]][2]>v[a[vv[i]+1]][0])add(2*i+1,2*i+3);

 81         }

 82     }

 83     for(int i=1;i<=n;i++)

 84         if ((sl[i]==2)&&(sr[i]==1))

 85             for(int j=0;j<vv.size();j++)

 86                 if ((mx[a[vv[j]]]<mx[i])&&(mn[a[vv[j]]]<mn[i]))add(2*j+1,2*j);

 87     for(int i=1;i<=n;i++)

 88         if ((sl[i]==1)&&(sr[i]==2))

 89             for(int j=0;j<vv.size();j++)

 90                 if ((mx[a[vv[j]]]>mx[i])&&(mn[a[vv[j]]]>mn[i]))add(2*j,2*j+1);

 91     for(int i=0;i<vv.size();i++)

 92         for(int j=0;j<vv.size();j++)

 93             if ((i!=j)&&(mx[a[vv[j]]]<mx[a[vv[i]]])&&(mn[a[vv[j]]]<mn[a[vv[i]]])){

 94                 add(2*i,2*j);

 95                 add(2*j+1,2*i+1);

 96             }

 97     for(int i=0;i<vv.size();i++)

 98         if ((pd(2*i))&&(pd(2*i+1)))return 0;

 99     return 1;

100 }

101 int main(){

102     scanf("%d",&n);

103     for(int i=1;i<=3*n;i++){

104         scanf("%d",&x);

105         v[x].push_back(i);

106     }

107     for(int i=1;i<=3*n;i++){

108         scanf("%d",&a[i]);

109         if (!mn[a[i]])mn[a[i]]=i;

110         mx[a[i]]=i;

111     }

112     ans=0x3f3f3f3f;

113     for(int i=0;i<=3*n;i++)//[1,i]

114         for(int j=3*n+1;j>i;j--)//[j,3*n]

115             if ((i+3*n-j+1<ans)&&(pd(i,j)))ans=i+3*n-j+1;

116     if (ans==0x3f3f3f3f)ans=-1;

117     printf("%d",ans);

118 }

巴特西

[atACL001F]Center Rearranging

最新文章

热门文章