列表

详情

NC21531. Hello, Hello and Hello

描述

A ternary string is a sequence of digits, where each digit is either 0, 1, or 2.
Chiaki has a nonempty ternary string s. Initially, the characters are sorted in non-decreasing order (i.e. all 0s appear before all 1s and all 1s appear before all 2s). Chiaki would like to shuffle the characters such that no two consecutive characters have the same value using the following operation: choose two integers l and r (l ≤ r), take characters from position l to position r inclusively, and move them to the end of the string.
Chiaki would like to know the minimum number of operations needed.

输入描述

There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case:
The first line contains a ternary string s (1 ≤ |s| ≤ 106).
It is guaranteed that the sum of all |s| does not exceed 106.

输出描述

For each test case, output ``-1'' (without the quotes) if Chiaki can not shuffle the string using the operations described above. Otherwise, output an integer k in the first line -- the minimum number of operations needed. Each of the next k lines output two integers l and r -- denoting an operation.

示例1

输入: 

2
001122
000022

输出: 

2
4 5
1 1
-1

原站题解

import java.util.Scanner;
public class Main {
public static void main(String[] arg) {
Scanner scanner = new Scanner(System.in);
// todo
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

C++11(clang++ 3.9) 解法, 执行用时: 88ms, 内存消耗: 8036K, 提交时间: 2020-03-14 14:21:34 

#include<bits/stdc++.h>

using namespace std;

const int maxn=(int)1e6+1;

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        static char buf[maxn];

        scanf("%s",buf);

        int c[3]={};

        for(int i=0;buf[i];++i)

        ++c[buf[i]-'0'];

        int mx=max(c[0],max(c[1],c[2])),sum=c[0]+c[1]+c[2];

        if(mx>sum-mx+1)

        {

            puts("-1");

        }

        else

        {

            int pos=-1,op[3]={},rem[3]={c[0]-1,c[1]-1,c[2]-1};

            if(mx==sum-mx+1&&mx>=2)

            if(mx==c[0])

            {

                pos=0;

                --rem[0];

            }

            else if(mx==c[1]&&c[2])

            {

                pos=1;

                --rem[1];

            }

            while(rem[0]>0||rem[1]>0||rem[2]>0)

            {

                int low=min(rem[0],min(rem[1],rem[2]));

                int i=low==rem[2]?2:(low==rem[0]?0:1);

                int j=!i,k=3-i-j;

                ++op[i];

                --rem[j];

                --rem[k];

            }

            printf("%d\n",op[0]+op[1]+op[2]+(pos>=0));

            for(int i=0;i<op[0];++i)

            {

                int x=c[0]+c[1];

                printf("%d %d\n",x,x+1);

                --c[1];

                --c[2];

            }

            if(pos==1)

            {

                int x=c[0]+c[1];

                printf("%d %d\n",x,x);

                --c[1];

            }

            for(int i=0;i<op[2];++i)

            {

                int x=c[0];

                printf("%d %d\n",x,x+1);

                --c[0];

                --c[1];

            }

            assert(c[1]<=1);

            for(int i=0;i<op[1];++i)

            {

                int x=c[0],y=c[0]+c[1];

                printf("%d %d\n",x,y+1);

                --c[0];

                c[1]=0;

                --c[2];

            }

            if(!pos)

            {

                int x=c[0];

                printf("%d %d\n",x,x);

                --c[0];

            }

        }

    }

    return 0;

}

上一题

© 2025 nowcoder.com