Codeforces Round #575 (Div. 3) D2. RGB Substring (hard version)

曾经终败给现在 2023-10-11 09:40 34阅读 0赞

[传送门][Link 1]

题意：

给你一个长为n的仅由'R','G','B'构成的字符串s，你需要在其中找出来一个子串。使得这个子串在“RGBRGBRGBRGB........（以RGB为循环节，我们称这个串为str）”里面也是一个子串，这个子串的长度是k

可是有可能s字符串中找不到，那么这个时候就可以改变s字符串中某些位置的字母来完成任务。问最少需要改变多少个字母

题解：

主要看暴力的姿势对不对。在上一道的D1上面，我是对s字符串的每一个位置进行‘R’，‘G’，‘B’的枚举，因为如果这个子串也是str的子串的话，那么肯定是以‘GB’，‘B’，“RGB”这三个为开头后面都是RGB

1 if(s[i]!='G') sum++;//,printf("1\n");
     2     if(s[i+1]!='B') sum++;//,printf("2\n");
     3 for(int k=0,j=i+2; j<i+m; ++j,k++,k%=3)
     4 //因为str字符串是以RGB循环，所以k就是来表示现在是R、G、B中的谁
     5 
     6 if(s[i]!='B') sum++;//,printf("6\n");
     7                 //if(s[i+1]!='B') sum++;
     8                 for(int k=0,j=i+1; j<i+m; ++j,k++,k%=3)
     9 
    10 
    11 
    12 //if(s[i]!='B') sum++,printf("6\n");
    13                 //if(s[i+1]!='B') sum++;
    14                 for(int k=0,j=i; j<i+m; ++j,k++,k%=3)

就是这样先枚举字符串s的每一个位置，再枚举开头的第一个字母（‘R’、‘G’、‘B’）

但是T了 T\_T

T代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 #include<string.h>
     3 #include<iostream>
     4 #include<algorithm>
     5 #include<map>
     6 #include<math.h>
     7 using namespace std;
     8 typedef long long ll;
     9 const int maxn=2e5+5;
    10 const int mod=26;
    11 const int INF=0x3f3f3f3f;
    12 const int block=300;
    13 char s[maxn];
    14 int main()
    15 {
    16     int t;
    17     scanf("%d",&t);
    18     while(t--)
    19     {
    20         int n,m,ans=INF,sum;
    21         scanf("%d%d",&n,&m);
    22         scanf("%s",s);
    23         if(m==1)
    24         {
    25             printf("0\n");
    26             continue;
    27         }
    28         for(int i=0; i<n; ++i)
    29         {
    30             if(i+m<=n)
    31             {
    32                 sum=0;
    33                 if(s[i]!='G') sum++;//,printf("1\n");
    34                 if(s[i+1]!='B') sum++;//,printf("2\n");
    35                 for(int k=0,j=i+2; j<i+m; ++j,k++,k%=3)
    36                 {
    37                     if(k==0)
    38                     {
    39                         if(s[j]!='R') ++sum;//,printf("3\n");
    40                     }
    41                     else if(k==1)
    42                     {
    43                         if(s[j]!='G') ++sum;//,printf("4\n");
    44                     }
    45                     else if(k==2)
    46                     {
    47                         if(s[j]!='B') ++sum;//,printf("5\n");
    48                     }
    49                 }
    50                 ans=min(sum,ans);
    51                 sum=0;
    52                 if(s[i]!='B') sum++;//,printf("6\n");
    53                 //if(s[i+1]!='B') sum++;
    54                 for(int k=0,j=i+1; j<i+m; ++j,k++,k%=3)
    55                 {
    56                     if(k==0)
    57                     {
    58                         if(s[j]!='R') ++sum;//,printf("7\n");
    59                     }
    60                     else if(k==1)
    61                     {
    62                         if(s[j]!='G') ++sum;//,printf("8\n");
    63                     }
    64                     else if(k==2)
    65                     {
    66                         if(s[j]!='B') ++sum;//,printf("9\n");
    67                     }
    68                 }
    69                 ans=min(sum,ans);
    70                 //printf("%d %d\n",sum,i);
    71                 sum=0;
    72                 //if(s[i]!='B') sum++,printf("6\n");
    73                 //if(s[i+1]!='B') sum++;
    74                 for(int k=0,j=i; j<i+m; ++j,k++,k%=3)
    75                 {
    76                     if(k==0)
    77                     {
    78                         if(s[j]!='R') ++sum;//,printf("77\n");
    79                     }
    80                     else if(k==1)
    81                     {
    82                         if(s[j]!='G') ++sum;//,printf("88\n");
    83                     }
    84                     else if(k==2)
    85                     {
    86                         if(s[j]!='B') ++sum;//,printf("99\n");
    87                     }
    88                 }
    89                 ans=min(sum,ans);
    90             }
    91             else
    92             {
    93                 break;
    94             }
    95         }
    96         printf("%d\n",ans);
    97     }
    98     return 0;
    99 }

除了这样外，还可以先枚举k（开头第一个字母），然后再枚举每一个字符串s的位置

这样也把所有情况包含了，具体看代码

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11529817.html

[Link 1]: https://codeforc.es/contest/1196/problem/D2
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif