CF1342B Binary Period（数学分析)

题目描述

Let's say string ss has period kk if s_i = s_{i + k}si=si+k for all ii from 11 to |s| - k∣s∣−k ( |s|∣s∣ means length of string ss ) and kk is the minimum positive integer with this property.

Some examples of a period: for ss ="0101" the period is k=2k=2 , for ss ="0000" the period is k=1k=1 , for ss ="010" the period is k=2k=2 , for ss ="0011" the period is k=4k=4 .

You are given string tt consisting only of 0's and 1's and you need to find such string ss that:

1. String ss consists only of 0's and 1's;
2. The length of ss doesn't exceed 2 \cdot |t|2⋅∣t∣ ;
3. String tt is a subsequence of string ss ;
4. String ss has smallest possible period among all strings that meet conditions 1—3.

Let us recall that tt is a subsequence of ss if tt can be derived from ss by deleting zero or more elements (any) without changing the order of the remaining elements. For example, tt ="011" is a subsequence of ss ="10101".

输入格式

The first line contains single integer TT ( 1 \le T \le 1001≤T≤100 ) — the number of test cases.

Next TT lines contain test cases — one per line. Each line contains string tt ( 1 \le |t| \le 1001≤∣t∣≤100 ) consisting only of 0's and 1's.

输出格式

Print one string for each test case — string ss you needed to find. If there are multiple solutions print any one of them.

题目描述

假设有一个字符串ss，如果它的第i 个字符和第i +k 个字符相等 (1≤i≤∣s∣−k) ，那么这个字符串的周期为kk 。其中， ∣s∣ 表示字符串 s 的长度。

现在给你一个字符串t ，t  内只包括0和1，请你找出这个 s ，使其满足如下条件：

1. 字符串 s 也只包括0和1。
2. ∣s∣≤2×∣t∣（s 的长度不能超过t  的长度的两倍）。
3. t 是s 的子串。
4. 在满足上面3个条件的情况下， s 需要有最小的周期 k 。

t 是s  的子串就是说当s  删除0 个或更多个字符后（不能改变顺序）， s 就变成了 t 。例如011就是10101的子串。

输入格式

第一行是一个正整数T ，表示数据的组数。

接下来 T行，每行有一个只包含0和1的字符串t (1≤∣t∣≤100)。

输出格式

如果有多种解，输出一个符合条件的字符串 s 即可。

输入输出样例

输入

4

00

01

111

110

输出  

00

01

11111

1010

题意我们分析知道，

我们可以想一下如果我们要满足t是子串，那么我们就要把t里面的0，1都排好比如10（周期最小），如果全部是0，或者1；那么直接输出t；思路就是这样，具体实现看代码。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
int main() {
  char s[maxn];
    char ans[maxn];
    int T;scanf("%d",&T);
    while(T--) {
        scanf("%s",s+1);
        int n = strlen(s+1);
        int flag = 1;
        for(int i = 2;i <= n;i++) {
            if(s[i] != s[i - 1]) {
                flag = 0;break;
            }
        }
        if(flag) {
            for(int i = 1;i <= n;i++) {
                printf("%c",s[i]);
            }
        }
        else {
            int cnt = 1;
            ans[cnt] = s[1];
            for(int i = 2;i <= n;i++) {
                if(ans[cnt] != s[i]) {
                    ans[++cnt] = s[i];
                }
                else {
                    if(ans[cnt] == '1') {
                        ans[++cnt] = '0';
                    }
                    else if(ans[cnt] == '0') {
                        ans[++cnt] = '1';
                    }
                    ans[++cnt] = s[i];
                }
            }
            for(int i = 1;i <= cnt;i++) {
                printf("%c",ans[i]);
            }
        }
        printf("\n");
    }
}