首页 > 其他分享 >【XSY3905】字符串题(lyndon串,构造)

【XSY3905】字符串题(lyndon串,构造)

时间:2022-10-30 14:15:31浏览次数:45  
标签:AA ch len 1a while lyndon 字符串 XSY3905

题面

字符串题

题解

设所有长度不超过 \(n\) 的串的集合为 \(S\)。

考虑找到一种方法,能够对一个 lyndon 串 \(A\) ,直接求出 \(A\) 的下一个 lyndon 串。方法如下:

  1. 先将 \(A\) 不断复制, 取出前 \(n\) 位作为新的 \(A\) ,即 \(A\leftarrow AAA⋯\) 的前 \(n\) 位。
  2. 如果 \(A\) 的最后一位是 \('a'+m-1\),即字符集中最大的字符,则将其删去,一直删除直到最后一位不为 \('a'+m-1\)。
  3. 将 \(A\) 的最后一个字符变为这个字符在字符集中的后继。(其实 2、3 操作的实质是找到 1 操作后的 \(A\) 在字典序中的下一个字符串。

设构造出的串为 \(B\)。证明这种方法的正确性,只需要证明 \(B\) 是 lyndon 串,且 \(B\) 是 \(S\) 中字典序大于 \(A\) 的最小的 lyndon 串。

  • 先证 \(B\) 为 lyndon 串:

    根据构造方式,设 \(A=a_1a_2⋯a_{|A|}\)。显然可以发现 \(B\) 为 \(AA⋯Aa_1a_2⋯a_x(a_{x+1}+1)\) 的形式,其中 \(1\leq x<|A|\)。由于 \(A\) 为 lyndon 串,所以对 \(\forall 1<i≤|A|\),有 \(a_ia_{i+1}\cdots a_{|A|}a_1a_2⋯a_{i−1}>a_1a_2⋯a_{|A|}\) 。

    不难发现 \(B\) 的循环移位中 \(B\) 为其中的严格最小值,所以 \(B\) 为 lyndon 串。

  • 再证 \(A,B\) 之间没有 \(lyndon\) 串:

    如果有一个 \(S\) 中的串 \(T\) 字典序在 \(A,B\) 之间且为 lyndon 串,由构造方法可以知道 \(A<T<AAA⋯\) 。

    设 \(T=AA⋯AT′\),其中 \(T'\) 的前 \(|A|\) 位不等于 AA ,显然有 \(T'<A\),则以 \(T'\) 开头的循环移位小于 \(T\) ,与 \(T\) 是 lyndon 串矛盾。

由于大部分满足条件的 lyndon 串的长度均为 \(n\),这个算法均摊复杂度为 \(O(1)\),可以 \(O(x)\) 通过此题。

代码如下:

#include<bits/stdc++.h>
 
#define S 35
#define N 200010
 
using namespace std;
 
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
 
struct Query
{
    int x,id;
}q[N];
 
bool operator < (Query a,Query b)
{
    return a.x<b.x;
}
 
int n,m,Q;
int len;
char s[S],Ans[N][S];
 
int main()
{
    n=read(),m=read(),Q=read();
    for(int i=1;i<=Q;i++)
        q[i].x=read(),q[i].id=i;
    sort(q+1,q+Q+1);
    len=1;
    s[0]='a';
    int tmp=1;
    while(tmp<=Q&&q[tmp].x==1)
    {
        for(int i=0;i<len;i++)
            Ans[q[tmp].id][i]=s[i];
        tmp++;
    }
    for(int i=2;i<=q[Q].x;i++)
    {
        int nowl=len;
        while(1)
        {
            for(int i=0;i<nowl&&len<n;i++)
                s[len++]=s[i];
            if(len==n) break;
        }
        while(len>0&&s[len-1]=='a'+m-1) len--;
        s[len-1]++;
        while(tmp<=Q&&q[tmp].x==i)
        {
            for(int i=0;i<len;i++)
                Ans[q[tmp].id][i]=s[i];
            tmp++;
        }
    }
    for(int i=1;i<=Q;i++)
    {
        for(int j=0;Ans[i][j];j++)
            putchar(Ans[i][j]);
        puts("");
    }
    return 0;
}

标签:AA,ch,len,1a,while,lyndon,字符串,XSY3905
From: https://www.cnblogs.com/ez-lcw/p/16841168.html

相关文章

  • 字符串转int
    将string类型转换成int型:可以用integer类里面的valueof,但我们这里用parseintStringstr="123";Integer.parseInt(str);Integer.parseInt(str,2);其实对于valueof,其......
  • Vue学习笔记之Vue判断字符串(或数组)中是否包含某个元素
    Vue判断包含0x00概述Vue判断​​字符串​​中是否包含某个字符串,有如下方法。 0x01includes方法(数组,字符串都可以)varstr=“HelloWorld!”......
  • Vue学习笔记之vue.js 两个等号 == 和三个等号===的区别 数字0和空字符串
    vuejavascript等号=====数字0空字符串/**==用于比较两者是否相等,忽略数据类型===用于更严谨的比较,值和值的数据类型都需要同时比较*/<!DOCT......
  • Java 使用StringBuilder组装字符串
    下面这个例子来自SpringBoot源码,这里是要打印程序启动的时间这样的字符串,需要拼装的信息有程序名字,启动时长,JVM时长。privateStringBuildergetStartedMessage(StopWatc......
  • 【XSY2499】字符串(AC自动机+树状数组)
    题面DescriptionUPD:本题字符集为全体小写字母InputOutputSampleInput51abc3abcabc0abc3aba1abababcSampleOutput22HINT题解这个“强制在......
  • 0090-Go-字符串
    环境Time2022-08-23Go1.19前言说明参考:https://gobyexample.com/strings-and-runes目标使用Go语言的字符串。字节遍历packagemainimport"fmt"funcma......
  • 【LeeCode】字符串的全排列
    【题目描述】输入字符串str,返回str的字符的全排序【示例】输入:qwe输出:qweqewewqeqwwqeweq注意:如果输入的是n个相同的字符,那么也就只有1种排列组合【代码】list:保留......
  • js字符串转字节
    functionstringToByte(str){varlen,c;len=str.length;varbytes=[];for(vari=0;i<len;i++){c=str.charCodeAt(i);if(c>=0x010000&......
  • golang中的字符串
    0.1、索引​​https://waterflow.link/articles/1666449874974​​1、字符串编码在go中rune是一个unicode编码点。我们都知道UTF-8将字符编码为1-4个字节,比如我们常用的汉字......
  • 【LeeCode】字符串的排列
    【题目描述】给你两个字符串 ​​s1​​​ 和 ​​s2​​​ ,写一个函数来判断 ​​s2​​​ 是否包含 ​​s1​​ 的排列。如果是,返回 ​​true​​​ ;否则,返回 ......