尋找字元串

問題 : 尋找字元串

時間限制: 1 Sec  

記憶體限制: 128 MB

題目描述

對于一個字元串 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。

1. 當c>d時，我們可以發現以a開頭例如abab字典序是最小的，當有多餘的a，b的時候我們可以往裡面插，如aababb，這種情況一定是以a開頭，以b結束。
2. 當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。
3. 當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;
}