[Codeforces 1131E]String Multiplication

Link

s\cdot t=t+s_1+t+s_2+…+s_n+t
\prod s_i中最长的连续的相同字符组成的字符串的长度。

Solution

L(s,c)sc字符的最长连续长度,则要求的结果就是\max L(\prod s_i,c),c\in[‘a’,’z’]
实时维护L(\prod s_i,c)。当读入一个t字符串时,分如下情况讨论:
1. t中的字符全部相同,设为x

L(\prod s_i\cdot t,c)=
\begin{cases}
(L(\prod s_i,c)+1)({\rm len}(t)+1)-1,&c=x\\
1,&c\not=x,c\in \prod s_i\\
0,&\text{otherwise}
\end{cases}
  1. t的字符不全部相同
    t的最长相同前缀的长度为p,最长相同后缀为s
    再分情况

    1. {\rm first}(t)={\rm last}(t)=x
      对于c\not=x
    L(\prod s_i\cdot t,c)=
    \begin{cases}
    1,&c\in\prod s_i\\
    0,&\text{otherwise}
    \end{cases}

    对于x

    L(\prod s_i\cdot t,x)=
    \begin{cases}
    p+s+1,&x\in\prod s_i\\
    \max(p,s),&\text{otherwise}
    \end{cases}
    1. {\rm first}(t)\not={\rm last}(t)
      与上相似。

Code

const int XN=1e5+11;
typedef std::array<long long,26> Record;

int main() {
    freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n;std::cin>>n;
    std::string s;std::cin>>s;
    auto Do=[&](std::string s)->std::tuple<long long,long long,Record> {
        s+=' ';
        long long pref=-1,suf=-1;
        Record mxl;
        for(int i=0;i<26;++i)
            mxl[i]=0;
        for(size_t i=1,len=1;i<s.length();++i)
            if(s[i]==s[i-1])
                len++;
            else {
                if(pref==-1)
                    pref=len;
                if(i==s.length()-1)
                    suf=len;
                Enlarge(mxl[s[i-1]-'a'],(long long)len);
                len=1;
            }
        if(pref==s.length()-1)
            suf=0;
        return {pref,suf,mxl};
    };
    Record smxl;long long pre,suf;
    static bool has[26];
    for(size_t i=0;i<s.length();++i)
        has[s[i]-'a']=1;
    std::tie(pre,suf,smxl)=Do(s);
    for(int i=2;i<=n;++i) {
        std::string t;std::cin>>t;
        Record tmxl;
        std::tie(pre,suf,tmxl)=Do(t);
        if(!suf) {
            long long temp=(smxl[t[0]-'a']+1)*(t.length()+1)-1;
            for(int c=0;c<26;++c)
                smxl[c]=(bool)smxl[c];
            Enlarge(smxl[t[0]-'a'],temp);
        } else {
            for(int c=0;c<26;++c)
                smxl[c]=(bool)smxl[c];
            if(t[0]==t[t.length()-1]) {
                long long temp=std::max(pre,suf);
                if(has[t[0]-'a']) {
                    temp=pre+suf+1;
                }
                smxl[t[0]-'a']=temp;
            } else {
                if(has[t[0]-'a']) {
                    smxl[t[0]-'a']=pre+1;
                }
                if(has[t[t.length()-1]-'a']) {
                    smxl[t[t.length()-1]-'a']=suf+1;
                }
            }
        }
        for(size_t i=0;i<t.length();++i)
            has[t[i]-'a']=1;
        for(int c=0;c<26;++c)
            Reduce(smxl[c],(long long)1e9);
        for(int c=0;c<26;++c)
            Enlarge(smxl[c],tmxl[c]);
    }
    std::cout<<*std::max_element(smxl.begin(),smxl.end())<<'\n';
    return 0;
}

Tips

题意理解反了浪费了半个小时。。
题目给了答案\le 10^9,就直接暴力取min就好了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注