牛客多校4.C.LCS 构造

牛客多校4.C.LCS 构造

Analysis

题目要求构造三个长度为 n n n​​的字符串 s 1 , s 2 , s 3 s_1,s_2,s_3 s1​,s2​,s3​​​​，同时满足 L C S ( s 1 , s 2 ) = a ,   L C S ( s 2 , s 3 ) = b ,   L C S ( s 3 , s 1 ) = c LCS(s_1, s_2) = a, \ LCS(s_2, s_3) = b, \ LCS(s_3,s_1) = c LCS(s1​,s2​)=a, LCS(s2​,s3​)=b, LCS(s3​,s1​)=c​

很容易想到，对于待构造的三个串，我们应该先选择最小的 L C S 1 LCS_1 LCS1​​​​​，将三个空串填充 L C S 1 LCS_1 LCS1​​个相同字母；然后将次小和最大的两个 L C S LCS LCS​值减去已经填充的 L C S 1 LCS_1 LCS1​长度。此时三个 L C S LCS LCS​​最小值一定为0，然后再选择非零最小值(就是前面的次小值)，对两个串进行填充，再对剩下的另外一个 L C S LCS LCS值对应的两个串进行填充。

那么对于样例：1 2 3 4

首先对于三个空串填充最小值 1 1 1：

a
a
a

三个 L C S LCS LCS值减去 1 1 1后，为0 1 2，那么接下来对第二、三个串填充 1 1 1个 b b b，第三、一个串填充 2 2 2个 c c c：

acc
ab
abcc

剩余的均填充不同的字符即可。

accd
abee
abcc

这样便得到了一组合法的解。接下来考虑不合法的情况：填充超出给定长度 n n n：

若首次填充的长度 L C S 1 LCS_1 LCS1​加上后面填充的长度 L C S 2 − L C S 1 、 L C S 3 − L C S 1 LCS_2 - LCS_1、LCS_3 - LCS_1 LCS2​−LCS1​、LCS3​−LCS1​即 L C S 2 + L C S 3 − L C S 1 > n LCS_2 + LCS_3-LCS_1 > n LCS2​+LCS3​−LCS1​>n那么即为不合法的解。注意此处 L C S LCS LCS是对输入三个值的升序排序。

AC Code

#include 
#define a aa[1]
#define b aa[2]
#define c aa[3]
using namespace std;

struct node{
    int x;
    string ans;
    bool operator a.x >> b.x >> c.x >> n;
    sort(aa + 1, aa + 4);
    if(b.x + c.x - a.x > n) return cout