Codeforces1698F Equal Reversal【构造】

标签：int Equal 相邻 num maxn Reversal Codeforces1698F

分析：

注意到你无论如何都无法改变a[1]的值，而你要改变a[2]的值时，你就必须要选择一个和a[1]相同的值，然后翻转这一段区间。

又可以发现，任意两个数的相邻情况是不会改变的。比如1和2相邻，那你无论如何也无法使得1 2不相邻。同理，不相邻也无法变成相邻。

所以依据上面的理论构造即可。

时间复杂度$O(n^3)$

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn = 540;
 5 
 6 int n,num;
 7 int a[maxn],b[maxn],pre[maxn];
 8 int l[maxn*maxn],r[maxn*maxn];
 9 
10 int main(){
11     int t; cin >> t;
12     while(t--){
13     int flag = 0;
14     num = 0;
15     cin >> n;
16     for(int i=1;i<=n;i++) cin >> a[i];
17     for(int i=1;i<=n;i++) cin >> b[i];
18     for(int i=1;i<n;i++){
19         if(a[i] != b[i]){
20         flag = 1;
21         break;
22         }else{
23         if(a[i+1] == b[i+1]){continue;}
24         else{
25             for(int j=i+2;j<=n;j++){
26             if(a[j] == a[i] && a[j-1] == b[i+1]){
27                 l[++num] = i; r[num] = j;
28                 for(int k=i+1,len=1;k<=(i+j)/2;k++,len++){
29                 swap(a[k],a[j-len]);
30                 }
31                 break;
32             }
33             }
34             if(a[i+1] == b[i+1]) continue;
35             for(int j=i+1;j<=n;j++){
36             pre[j] = 0;
37             for(int k=j-1;k>=i;k--){
38                 if(a[k] == a[j]){
39                 pre[j] = k;
40                 break;
41                 }
42             }
43             }
44             for(int j=i+1;j<n;j++){
45             if(a[j] == a[i] && a[j+1] == b[i+1]){
46                 bool ok = 0;
47                 for(int k=j+1;k<=n;k++){
48                 if(pre[k] <= j && pre[k] != 0 ){
49                     ok = 1;
50                     l[++num] = pre[k];
51                     r[num] = k;
52                     for(int x=pre[k]+1,len=1;x<=(pre[k]+k)/2;x++,len++){
53                     swap(a[x],a[k-len]);
54                     }
55                     break;
56                 }
57                 }
58                 if(ok) break;
59             }
60             }
61             for(int j=i+2;j<=n;j++){
62             if(a[j] == a[i] && a[j-1] == b[i+1]){
63                 l[++num] = i; r[num] = j;
64                 for(int k=i+1,len=1;k<=(i+j)/2;k++,len++){
65                 swap(a[k],a[j-len]);
66                 }
67                 break;
68             }
69             }
70             if(a[i+1] == b[i+1]) continue;
71             else {flag = 1;break;}
72         }
73         }
74     }
75     if(a[n] != b[n]) flag = 1;
76     if(flag){
77         puts("NO");
78     }else{
79         puts("YES");
80         cout<<num<<endl;
81         for(int i=1;i<=num;i++){
82         cout<<l[i]<<" "<<r[i]<<endl;
83         }
84     }
85     }
86 }
87 
88 //10
89 //1 3 4 5 3 3 4 2 1 4 
90 //1 4 3 5 4 2 1 3 3 4 

 

标签：int,Equal,相邻,num,maxn,Reversal,Codeforces1698F
From： https://www.cnblogs.com/Menhera/p/16594473.html