暑假集訓Day11 H（優雅一些的暴力）

原題連結在這裡:​​UESTC 2022 Summer Training #01 (Div.1&Div.2) - Virtual Judge (vjudge.net)​​

一開始想成二分了，打完以後發現并不滿足單調性，令人感慨。

如果是一般的暴力的話，枚舉第一個轉的，枚舉第二個轉的，再判斷是否符合條件，這是個O(n^3)的暴力，肯定寄了。

1 #include "bits/stdc++.h"
 2 using namespace std;
 3 const int MAX=1e4+5;
 4 const int N=5e3+5;
 5 int n;
 6 char sa[MAX],sb[MAX],sc[MAX];
 7 bool ckab[MAX],ckac[MAX],ckbc[MAX];
 8 bool checkab(int x){
 9     int i,j;
10     for (i=1;i<=n;i++)
11         if (sa[i]==sb[i+x])
12             return false;
13     return true;
14 }
15 bool checkac(int x){
16     int i,j;
17     for (i=1;i<=n;i++)
18         if (sa[i]==sc[i+x])
19             return false;
20     return true;
21 }
22 bool checkbc(int x){
23     int i,j;
24     for (i=1;i<=n;i++)
25         if (sb[i]==sc[i+x])
26             return false;
27     return true;
28 }
29 int main(){
30     int i,j,low,high,mid,ans=1e9;
31     scanf("%s%s%s",sa+1,sb+1,sc+1);
32     n=strlen(sa+1);
33     for (i=n+1;i<=2*n;i++){
34         sa[i]=sa[i-n];
35         sb[i]=sb[i-n];
36         sc[i]=sc[i-n];
37     }
38     for (i=0;i<n;i++) ckab[i]=checkab(i);
39     for (i=0;i<n;i++) ckac[i]=checkac(i);
40     for (i=0;i<n;i++) ckbc[i]=checkbc(i);
41     ckab[n]=ckab[0];ckac[n]=ckac[0];ckbc[n]=ckbc[0];
42     for (i=0;i<n;i++)
43         for (j=0;j<n;j++){
44             if (ckab[i] && ckac[j] && ckbc[(j-i+n)%n]){//b_i c_j
45                 ans=min(ans,min(n-i,i)+min(n-j,j));
46                 continue;
47             }
48             if (ckab[n-i] && ckac[(j-i+n)%n] && ckbc[j]){//a_i c_j 
49                 ans=min(ans,min(n-i,i)+min(n-j,j));
50                 continue;
51             }
52             if (ckab[(j-i+n)%n] && ckac[n-i] && ckbc[n-j]){//a_i b_j 
53                 ans=min(ans,min(n-i,i)+min(n-j,j));
54                 continue;
55             }
56         }
57     printf("%d",(ans==1e9?-1:ans));
58     return 0;
59