2016 计蒜之道 初赛 第三场 百度帐号的选取方案 - dblank

2016 计蒜之道 初赛 第三场 百度帐号的选取方案

<div id="description" class="jsk-margin-top">

在注册百度帐号的时候,由于帐号数量巨大,常会遇到账户名冲突的情况。如果希望设置的用户名(比如 jsk)已经被占用,那么就会将初始的用户名重复一遍(此时用户名为 jskjsk),再检查 jskjsk 是否被占用,如果被占用则会再重复一遍初始的用户名(即为 jskjskjsk),直到没有冲突为止。

每个用户名都有一个幸运值 <span class="katex"><span class="katex-mathml">P</span><span class="katex-html"><span class="base textstyle uncramped"><span class="mord mathit">P</span></span></span></span>,对应用户名的最大冲突次数。现在想从一长串字符中选出两个不相交的子串分别用作用户名,并且希望两个用户名的幸运值相等。请计算一共有多少种符合要求的选取方案。注意,在原串中位置不同但值相等的字符串被认为是不同的字符串,并且每个方案中两个用户名没有先后顺序。

输入格式

输入为一行,输入一个长度为 <span class="katex"><span class="katex-mathml">len(len geq 1)</span><span class="katex-html"><span class="base textstyle uncramped"><span class="mord mathit">l</span><span class="mord mathit">e</span><span class="mord mathit">n</span><span class="mopen">(</span><span class="mord mathit">l</span><span class="mord mathit">e</span><span class="mord mathit">n</span><span class="mrel">≥</span><span class="mord mathrm">1</span><span class="mclose">)</span></span></span></span>的只包含小写字母a-z的字符串 <span class="katex"><span class="katex-mathml">S</span><span class="katex-html"><span class="base textstyle uncramped"><span class="mord mathit">S</span></span></span></span>。

对于简单版本:<span class="katex"><span class="katex-mathml">len leq 50</span><span class="katex-html"><span class="base textstyle uncramped"><span class="mord mathit">l</span><span class="mord mathit">e</span><span class="mord mathit">n</span><span class="mrel">≤</span><span class="mord mathrm">5</span><span class="mord mathrm">0</span></span></span></span>;

对于中等版本:<span class="katex"><span class="katex-mathml">len leq 1000</span><span class="katex-html"><span class="base textstyle uncramped"><span class="mord mathit">l</span><span class="mord mathit">e</span><span class="mord mathit">n</span><span class="mrel">≤</span><span class="mord mathrm">1</span><span class="mord mathrm">0</span><span class="mord mathrm">0</span><span class="mord mathrm">0</span></span></span></span>;

对于困难版本:<span class="katex"><span class="katex-mathml">len leq 100000</span><span class="katex-html"><span class="base textstyle uncramped"><span class="mord mathit">l</span><span class="mord mathit">e</span><span class="mord mathit">n</span><span class="mrel">≤</span><span class="mord mathrm">1</span><span class="mord mathrm">0</span><span class="mord mathrm">0</span><span class="mord mathrm">0</span><span class="mord mathrm">0</span><span class="mord mathrm">0</span></span></span></span>。

输出格式

输出一行,输出一个整数,表示可从串 <span class="katex"><span class="katex-mathml">S</span><span class="katex-html"><span class="base textstyle uncramped"><span class="mord mathit">S</span></span></span></span> 中选出多少对幸运值相同的不相交子串。

</div>
<div id="samples">
<div class="jsk-margin-vertical-sm">
<h4 class="title">样例输入1</h4>

aaaa
</div> <div class="jsk-margin-vertical-sm"> <h4 class="title">样例输出1</h4>
7
</div> <div class="jsk-margin-vertical-sm"> <h4 class="title">样例输入2</h4>
abcd
</div> <div class="jsk-margin-vertical-sm"> <h4 class="title">样例输出2</h4>
15
</div> </div> <h4 class="title">提示信息</h4> <div id="hint" class="jsk-margin-vertical-sm" style="box-sizing: border-box; margin-top: 1rem; margin-bottom: 1rem; color: #333333; font-family: Full-Width-Quoration-Marks, '.SFNSText', '.SFUIText', 'Helvetica Neue', Helvetica, 'Segoe UI', Roboto, 'Open Sans', 'Lucida Grande', Arial, Verdana, 'Hiragino Sans GB', 'PingFang SC', 'Source Han Sans CN', 'Source Han Sans SC', 'Microsoft YaHei', 'Wenquanyi Micro Hei', 'WenQuanYi Zen Hei', 'ST Heiti', SimHei, 'WenQuanYi Zen Hei Sharp', FontAwesome, sans-serif; font-size: 16px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 25.6px; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 1; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: #ffffff;" data-hint="<p>对于一个用户名来说,最大冲突次数为一个用户名产生过程中经历的最多的冲突次数。</p> <p>比如 <code>aaaa</code>,有可能为 <code>aa</code> 冲突一次,也有可能 <code>a</code> 冲突三次。所以最大的冲突次数为 $3$,因此 <code>aaaa</code> 的幸运值为 $3$。</p> <p>接下来我们解释第一组样例。令字符串为 $S=s_0 s_1 s_2 s_3 ...$。对于第一组样例,一共有如下 $7$ 种选取方案:</p> <p>$(s_0,s_1) = (a,a)$</p> <p>$(s_0,s_2) = (a,a)$</p> <p>$(s_0,s_3) = (a,a)$</p> <p>$(s_1,s_2) = (a,a)$</p> <p>$(s_1,s_3) = (a,a)$</p> <p>$(s_2,s_3) = (a,a)$</p> <p>$(s_0s_1,s_2s_3) = (aa, aa)$</p> "> 对于一个用户名来说,最大冲突次数为一个用户名产生过程中经历的最多的冲突次数。 比如 aaaa,有可能为 aa 冲突一次,也有可能a 冲突三次。所以最大的冲突次数为 <span class="katex"><span class="katex-mathml">3</span><span class="katex-html"><span class="base textstyle uncramped"><span class="mord mathrm">3</span></span></span></span>,因此aaaa 的幸运值为 <span class="katex"><span class="katex-mathml">3</span><span class="katex-html"><span class="base textstyle uncramped"><span class="mord mathrm">3</span></span></span></span>。 接下来我们解释第一组样例。令字符串为 <span class="katex"><span class="katex-mathml">S=s_0 s_1 s_2 s_3 ...</span><span class="katex-html"><span class="base textstyle uncramped"><span class="mord mathit">S</span><span class="mrel">=</span><span class="mord"><span class="mord mathit">s</span><span class="vlist"><span class="fontsize-ensurer reset-size5 size5"></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">0</span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"></span></span></span></span><span class="mord"><span class="mord mathit">s</span><span class="vlist"><span class="fontsize-ensurer reset-size5 size5"></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"></span></span></span></span><span class="mord"><span class="mord mathit">s</span><span class="vlist"><span class="fontsize-ensurer reset-size5 size5"></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"></span></span></span></span><span class="mord"><span class="mord mathit">s</span><span class="vlist"><span class="fontsize-ensurer reset-size5 size5"></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">3</span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"></span></span></span></span><span class="mord mathrm">.</span><span class="mord mathrm">.</span><span class="mord mathrm">.</span></span></span></span>。对于第一组样例,一共有如下 <span class="katex"><span class="katex-mathml">7</span><span class="katex-html"><span class="base textstyle uncramped"><span class="mord mathrm">7</span></span></span></span> 种选取方案: <span class="katex"><span class="katex-mathml">(s_0,s_1) = (a,a)</span><span class="katex-html"><span class="base textstyle uncramped"><span class="mopen">(</span><span class="mord"><span class="mord mathit">s</span><span class="vlist"><span class="fontsize-ensurer reset-size5 size5"></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">0</span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"></span></span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit">s</span><span class="vlist"><span class="fontsize-ensurer reset-size5 size5"></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"></span></span></span></span><span class="mclose">)</span><span class="mrel">=</span><span class="mopen">(</span><span class="mord mathit">a</span><span class="mpunct">,</span><span class="mord mathit">a</span><span class="mclose">)</span></span></span></span> <span class="katex"><span class="katex-mathml">(s_0,s_2) = (a,a)</span><span class="katex-html"><span class="base textstyle uncramped"><span class="mopen">(</span><span class="mord"><span class="mord mathit">s</span><span class="vlist"><span class="fontsize-ensurer reset-size5 size5"></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">0</span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"></span></span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit">s</span><span class="vlist"><span class="fontsize-ensurer reset-size5 size5"></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"></span></span></span></span><span class="mclose">)</span><span class="mrel">=</span><span class="mopen">(</span><span class="mord mathit">a</span><span class="mpunct">,</span><span class="mord mathit">a</span><span class="mclose">)</span></span></span></span> <span class="katex"><span class="katex-mathml">(s_0,s_3) = (a,a)</span><span class="katex-html"><span class="base textstyle uncramped"><span class="mopen">(</span><span class="mord"><span class="mord mathit">s</span><span class="vlist"><span class="fontsize-ensurer reset-size5 size5"></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">0</span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"></span></span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit">s</span><span class="vlist"><span class="fontsize-ensurer reset-size5 size5"></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">3</span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"></span></span></span></span><span class="mclose">)</span><span class="mrel">=</span><span class="mopen">(</span><span class="mord mathit">a</span><span class="mpunct">,</span><span class="mord mathit">a</span><span class="mclose">)</span></span></span></span> <span class="katex"><span class="katex-mathml">(s_1,s_2) = (a,a)</span><span class="katex-html"><span class="base textstyle uncramped"><span class="mopen">(</span><span class="mord"><span class="mord mathit">s</span><span class="vlist"><span class="fontsize-ensurer reset-size5 size5"></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"></span></span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit">s</span><span class="vlist"><span class="fontsize-ensurer reset-size5 size5"></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"></span></span></span></span><span class="mclose">)</span><span class="mrel">=</span><span class="mopen">(</span><span class="mord mathit">a</span><span class="mpunct">,</span><span class="mord mathit">a</span><span class="mclose">)</span></span></span></span> <span class="katex"><span class="katex-mathml">(s_1,s_3) = (a,a)</span><span class="katex-html"><span class="base textstyle uncramped"><span class="mopen">(</span><span class="mord"><span class="mord mathit">s</span><span class="vlist"><span class="fontsize-ensurer reset-size5 size5"></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"></span></span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit">s</span><span class="vlist"><span class="fontsize-ensurer reset-size5 size5"></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">3</span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"></span></span></span></span><span class="mclose">)</span><span class="mrel">=</span><span class="mopen">(</span><span class="mord mathit">a</span><span class="mpunct">,</span><span class="mord mathit">a</span><span class="mclose">)</span></span></span></span> <span class="katex"><span class="katex-mathml">(s_2,s_3) = (a,a)</span><span class="katex-html"><span class="base textstyle uncramped"><span class="mopen">(</span><span class="mord"><span class="mord mathit">s</span><span class="vlist"><span class="fontsize-ensurer reset-size5 size5"></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"></span></span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit">s</span><span class="vlist"><span class="fontsize-ensurer reset-size5 size5"></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">3</span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"></span></span></span></span><span class="mclose">)</span><span class="mrel">=</span><span class="mopen">(</span><span class="mord mathit">a</span><span class="mpunct">,</span><span class="mord mathit">a</span><span class="mclose">)</span></span></span></span> <span class="katex"><span class="katex-mathml">(s_0s_1,s_2s_3) = (aa, aa)</span><span class="katex-html"><span class="base textstyle uncramped"><span class="mopen">(</span><span class="mord"><span class="mord mathit">s</span><span class="vlist"><span class="fontsize-ensurer reset-size5 size5"></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">0</span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"></span></span></span></span><span class="mord"><span class="mord mathit">s</span><span class="vlist"><span class="fontsize-ensurer reset-size5 size5"></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"></span></span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit">s</span><span class="vlist"><span class="fontsize-ensurer reset-size5 size5"></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"></span></span></span></span><span class="mord"><span class="mord mathit">s</span><span class="vlist"><span class="fontsize-ensurer reset-size5 size5"></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">3</span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"></span></span></span></span><span class="mclose">)</span><span class="mrel">=</span><span class="mopen">(</span><span class="mord mathit">a</span><span class="mord mathit">a</span><span class="mpunct">,</span><span class="mord mathit">a</span><span class="mord mathit">a</span><span class="mclose">)</span></span></span></span> 只会n^2的算法,于是只能过中等和简单的数据范围。。。。 思路:我们可以用kmp的next数组来求出每一个子串的循环节,这个每个子串的指数都是他的循环节数。这个处理的复杂度是n^2,然后我们用一个数组保存起来,ai表示i到j的子串的指数,同时用dpi表示以i为起点指数为j的子串个数。然后我们就可以统计ans了,因为一个子串可以和后面所有的没有交集的子串匹配,我们可以用后缀和来优化这个地方,做到n^2统计。ans会爆int用long  long.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1e3 + 10, Mod = 1000000007;
typedef long long ll;
int Next[N], aN, dpN;
void getnext(string s)
{
    Next[0] = -1;
    int i = 0, j = -1;
    while(i<s.size())
    {
        if(j == -1 || s[i] == s[j])
        {
            Next[++i] = ++j;
        }
        else
            j = Next[j];
    }
}
int main()
{
    string x;
    cin>>x;
    memset(a, 0, sizeof(a));
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i<x.size(); i++)
    {
        string s = x.substr(i, x.size()-i+1);
        getnext(s);
        for(int j = 1; j<=s.size(); j++)
        {
            if(j % (j - Next[j]) == 0)
                ai = j / (j - Next[j]);
            else ai = 1;
            dpi[j+i-1]]++;
        }
    }
    for(int i = x.size()-1; i>=0; i--)
    {
        for(int j = x.size()-1; j>=0; j--)
        {
            dpj += dpj+1;
        }
    }
    ll ans = 0;
    for(int i = 0; i<x.size(); i++)
    {
        for(int j = i; j<x.size(); j++)
        {
            ans += dpj+1[j]];
        }
    }
    cout<<ans<<endl;
    return 0;
}

 

</div>

相关文章

发表新评论