洛谷 P5595 【XR-4】歌唱比赛

题目描述

小 X 参加了一场歌唱比赛。

经过一路鏖战，小 X 终于挺进了决赛，他的对手是小 Y。

这场歌唱比赛的冠军是由点赞数决定的，谁的点赞数高，谁就能夺冠。

小 X 和小 Y 依次演唱完自己的最后一首歌曲后，他们最终的点赞数确定了下来。

揭晓冠军的时刻终于到来了，主持人为了增加悬念，决定从小 X 与小 Y 的点赞数的最后一位开始，依次比较。

比如，小 X 的点赞数是 3737，小 Y 的点赞数是 2828。首先比较最后一位，小 X 是 77，小 Y 是 88，此时小 Y 暂时领先。再加上前一位，小 X 是 3737，小 Y 是 2828，此时小 X 暂时领先。比较结束，如果我们用 X 代表小 X 暂时领先，Y 代表小 Y 暂时领先，那么可以写下一个字符串 XY。

再比如，小 X 的点赞数是 137137，小 Y 的点赞数是 4747。如果我们再用 Z 表示小 X 与小 Y 的点赞数暂时一样，那么写下的字符串应该为 XYZ。

你作为一个精通 OI 的神仙，自然知道这种比较方式是非常不科学的，这样只是在无端拖延时间罢了，但是你却对最后写下的这个字符串很感兴趣。

现在，你得到了这个最后写下的字符串，你需要构造出一种可能的小 X 与小 Y 的点赞数。

当然，有可能不存在任何一种情况的点赞数满足这个字符串，那么你只需要输出 -1 即可。

为了方便你输出，请用前导零来补足位数。

输入格式

一行一个字符串 ss，表示最后写下的字符串。

输出格式

如果有解：

第一行一个整数，表示小 X 的点赞数。
第二行一个整数，表示小 Y 的点赞数。

如果无解：

一行一个整数 -1。

输入输出样例

输入 #1复制

输出 #1复制

输入 #2复制

输出 #2复制

输入 #3复制

输出 #3复制

输入 #4复制

输出 #4复制

说明/提示

本题采用捆绑测试。

Subtask 1（11 points）： ext{len}(s) = 1len(s)=1。
Subtask 2（42 points）：s_i in { exttt{X}, exttt{Y}}s**i∈{X,Y}。
Subtask 3（21 points）：数据保证有解。
Subtask 4（26 points）：无特殊限制。

对于 100%100% 的数据，s_i in { exttt{X}, exttt{Y}, exttt{Z}}s**i∈{X,Y,Z}，1 le ext{len}(s) le 10^61≤len(s)≤106。

题解：

~~一道橙题难了蒟蒻40多分钟~~

~~果然还是蒟蒻太菜了~~

一开始看觉得根本做不了，后来发现是SPJ。

那就好办了，我们随便构造出一个合法的序列就可以。

根据贪心的一个思想，为了维护序列的正确性，谁更大就往谁里捅9，谁更小往谁里捅0.

下面就是判断合法与否。

手推几组数据可以发现，如果Z不是连成串的，那么一定不合法：

比如：ZXYXYX这一段序列。到Z后面的那位的时候还是X比较大，突然就到了Z，两个人相等了？？！

这是无论如何也构造不出来的。

所以判断一下就可以了。

~~蒟蒻又判了一下len=1的情况~~

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
using namespace std;
const int maxl=1e6+1;
char s[maxl];
int ans1[maxl],ans2[maxl];
int main()
{
    scanf("%s",s+1);
    int len=strlen(s+1);
    if(len==1)
    {
        if(s[1]=='Z')
            printf("0
0");
        else if(s[1]=='X')
            printf("2
1");
        else
            printf("1
2");
        return 0;
    }
    for(int i=1;i<len;i++)
        if(s[i]=='Z'&&s[i+1]!='Z')
        {
            printf("-1");
            return 0;
        }
    for(int i=len;i>=1;i--)
    {
        if(s[i]=='X')
        {
            ans1[i]=9;
            ans2[i]=0;
        }
        else if(s[i]=='Y')
        {
            ans1[i]=0;
            ans2[i]=9;
        }
        else 
        {
            ans1[i]=0;
            ans2[i]=0;
        }
    }
    for(int i=1;i<=len;i++)
        printf("%d",ans1[i]);
    puts("");
    for(int i=1;i<=len;i++)
        printf("%d",ans2[i]);
    return 0;
}