寻找字符串_牛客博客

问题 : 寻找字符串

时间限制: 1 Sec 内存限制: 128 MB
</center>

题目描述

对于一个字符串 s,定义一个函数 S(x),表示 s 中有多少个子串 x。现在给定 S(a),S(b),S(ab),S(ba)的值,求满足这 4 个值的字符串 s,如果有多个满足条件的字符串,输出字典序最小的。

输入

输入一个 T(T ≤ 50)表示 T 组数据。
对于每组数据按顺序输入用空格分开的四个整数,分别表示 S(a),S(b),S(ab),S(ba) (0 ≤ S(a), S(b), S(ab), S(ba) ≤ 10^6 ,S(a) + S(b) >0)的值。

输出

对于每组数据输出一行,包含一个字符串表示结果,如果无解则输出-1。

样例输入

2
2 2 1 1
4 3 7 1

样例输出

abba
-1

解题思路

这道题其实只要找到规律基本上都可以做出来。假设输入的四个数分别为a，b，c，d，我们可以分别讨论a>d,c==d,c<b三种情况。

首先我们可以知道a<c，a<d，b<c，b<d，a+b<=c+d，c-d>1，d-c>1，a ！=0&&b！=0&& c ==0&& d==0这几种情况是无解的，输出-1。

当c>d时，我们可以发现以a开头例如abab字典序是最小的，当有多余的a，b的时候我们可以往里面插，如aababb，这种情况一定是以a开头，以b结束。
当c==d时，我们可以分a>c和a==c两种情况讨论。当a>c时，我们可以看出以a开头以a结尾可以构成c==d这种情况，例如abababa，当有a，b有剩余的时候可以往里面插，例如aaabababba；当a==c时，我们可以看出上种情况其实a的个数是多余b的，所以以b开头以a结尾可以构成c==d这种情况，例如bababab，当有b有剩余的时候可以往里面插，例如babababbb。
当c<d时，我们可以分c>0和c==0两种情况，当c>0时，我们可以知道当以b开头以a结尾可以满足c<d，例如bababa，当有a，b有剩余的时候往里面插，例如baababbba；至于c==0的时候，因为c<d，那么d==1，则可以直接输出b个b，a个a，例如bbbaaa。具体见代码：

#include <stdio.h>
int main() {
    int t, m, n, a, b, c, d, i;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d%d", &a, &b, &c, &d);
        if (a < c || a < d || b < c || b < d) {
            puts("-1");
            continue;
        }
        if (a + b <= c + d || c - d > 1 || d - c > 1) {
            puts("-1");
            continue;
        }
        if (a && b && !c && !d) {
            puts("-1");
            continue;
        }
        if (c > d) {
            for (i = 0; i < a - c; i++)
                printf("a");
            for (i = 0; i < c; i++)
                printf("ab");
            for (i = 0; i < b - c; i++)
                printf("b");
            printf("\n");
        }
        else if (c == d) {
            if (a > c) {
                for (i = 0; i < a - c - 1; i++)
                    printf("a");
                for (i = 0; i < c; i++)
                    printf("ab");
                for (i = 0; i < b - c; i++)
                    printf("b");
                printf("a\n");
                continue;
            }
            for (i = 0; i < c; i++)
                printf("ba");
            for (i = 0;i < b - c; i++)
                printf("b");
            printf("\n");
        }
        else if(c < d) {
            if (!c) {
                for (i = 0; i < b; i++)
                    printf("b");
                for (i = 0; i < a; i++)
                    printf("a");
                printf("\n");
                continue;
            }
            printf("ba");
            for (i = 0; i < a - d; i++)
                printf("a");
            for (i = 0; i < d - 2; i++)
                printf("ba");
            for (i = 0; i < b - c; i++)
                printf("b");
            printf("a\n");
        }
    }
    return 0;
}