codeforces 1554D

96 阅读 0 评论 64 点赞

我是靠谱客的博主称心飞鸟，最近开发中收集的这篇文章主要介绍codeforces 1554D，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

D. Diane

  						D. Diane
You are given an integer n. Find any string s of length n consisting
only of English lowercase letters such that each non-empty substring
of s occurs in s an odd number of times. If there are multiple such
strings, output any. It can be shown that such string always exists
under the given constraints.

A string a is a substring of a string b if a can be obtained from b by
deletion of several (possibly, zero or all) characters from the
beginning and several (possibly, zero or all) characters from the end.

Input The first line contains a single integer t (1≤t≤500) — the
number of test cases.

The first line of each test case contains a single integer n
(1≤n≤105).

It is guaranteed that the sum of n over all test cases doesn’t exceed
3⋅105.

Output For each test case, print a single line containing the string
s. If there are multiple such strings, output any. It can be shown
that such string always exists under the given constraints.

题意: 给你一个字符串长度，让你求当前长度下的字符串的所有连续子序列的个数为奇数。例如: abc . a,b,c,ab,bc,abc所有连续子序列的个数都为1(奇数)

个人思路:本题绝对是一个贪心题目,且这种题目的都是有一种特别的式子能简单的得到题目的需求。

题解: 首先我们来假设一个例子 aaaaa . a(5) aa(4) aaa(3) aaaa(2) aaaaa(1)
当字符串长度为奇数时,相同的字母所组成的字符串的当长度为奇数时,数量为奇数,长度为偶数时，数量为偶数。字符串长度为偶数时则相反。那么利用他必须连续并且偶数+奇数=奇数的特性，将当前字符串分成份，其第一份和第三分为字符串长度/2，字符串长度/2-1 中间份找到任何一个不是相同字母的单词代替(截断连续)

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10,mod=998244353,INF=0x3f3f3f3f;
int dp[N][10];

int main()
{
    int T;cin>>T;
    while(T--)
    {
        int n;cin>>n;
        if(n==1)cout<<"a"<<endl;//特判一下1的时候
        else cout<<string(n / 2,'a')+(n & 1 ? "bc":"c")+string(n/2-1,'a')<<endl;
        //简单的来一个例子 当n=9时 aaaa+bc+aaa刚好所有的连续子序列都是奇数
    }

    return 0;
}