Codeforces 1213E Two Small Strings

cf题面

中文题意

给个n，再给两个长度为2的字符串，要求构造一个长度为\(3n\)的字符串，a、b、c三个字母各n个，且构造出的字符串子串中不能出现给定的两个字符串。如果不存在这样的字符串，就输出NO

解题思路

首先生成a、b、c的6个全排列，然后，每种全排列以两种方式扩大n倍——举个例子，n为3时，对于acb，可以扩展成这两种：acbacbacb、aaacccbbb。然后依次检查这12种字符串是否有满足要求的，有就输出，没有就代表没有了（可以考虑字符串排列的内部以及扩展后字符串之间的边界）

（虚拟赛时想到第一种扩展方式，把自己卡了以后，想到第二种，又把自己卡了，愣是想不到两种都试试……）

源代码

#include<cstdio>
#include<stdlib.h>
#include<algorithm>
const int MAXN=3e5+5;
int n;
char mo[6][4]={"abc","acb","bac","bca","cab","cba"};
char input[2][3];
char s[MAXN];
void check()
{
   for(int i=2;i<=n*3;i++)
   {
       if(s[i]==input[0][1]&&s[i-1]==input[0][0]||s[i]==input[1][1]&&s[i-1]==input[1][0]) return;
   }
   printf("YES\n%s",s+1);
   exit(0);
}
int main()
{
    scanf("%d%s%s",&n,input[0],input[1]);
    for(int m=0;m<6;m++)
    {
        for(int i=1;i<=n;i++)//然后一个奇怪的地方，我之前提交的时候input数组开到[2][2]，输入时显然溢出了，但是输入那里不报错，反而这个循环不会进入，就是i这个循环。m那个循环进来了，然后直接进入check函数。为什么嘞……留坑
        {
            s[(i-1)*3+1]=mo[m][0];
            s[(i-1)*3+2]=mo[m][1];
            s[(i-1)*3+3]=mo[m][2];
        }
        check();
        for(int i=1;i<=n;i++)
        {
            s[i]=mo[m][0];
            s[i+n]=mo[m][1];
            s[i+n+n]=mo[m][2];
        }
        check();
    }
    puts("NO");
    return 0;
}

本博客第一篇被打上构造标签的博文（真该打个标签叫智商）

Codeforces 1213E Two Small Strings

原文：https://www.cnblogs.com/wawcac-blog/p/11464774.html