本文最后更新于:2020年4月11日 下午

题目分析

思想很简单,但是很难实现。

首先,让我们定义f(x)

f(x):=连续攻击x次时造成的伤害

这是“f(x)= 1 + 2 + 3 + ... + x = x *(x +1)/ 2”。

定义M = S.length()

$N$次合并和进攻时的问题是$S$的开头和结尾都有进攻。

如果在开始和结束时都有攻击,则连续攻击的次数会增加,因此损害额也会增加。

在开始实际计算之前,让我们计算出连续攻击的数量。
这称为数组$v$。

首先,让我们处理各种极端情况。

在所有攻击的情况下,f(MN)是答案,因为攻击是连续的MN次。

如果$N = 1$,则只需模拟攻击即可。换句话说,如果f(v [0])+ f(v [1])+ ...
都不是答案S的第一个或最后一个,则损害金额即使相加也不会改变,因此:

N * (f(v [0])+ f(v [1])+ ...)是答案。

最后,考虑联接的情况。

令数组$v$的大小为$n$。

int n = v.size();

第一个添加答案,除了最后一个攻击优先。
rep(i,0,n-1)ans + = f(v [i]);

增加自此之后的第一次攻击以来的攻击次数,将其视为先前$S$
v [0]的最后一次攻击的一部分+ = v [n-1];

计算$S$次并重复此$N-2$次(第一次和最后一次除外)

ll sm = 0;
rep(i0,n-1)sm + = f (v [i]);
ans + = sm *(N-2);
计算并添加最后一个并回答
rep(i0,n)ans + = f(v [i]);

核心部分伪代码

ll N; string S; int M;
//---------------------------------------------------------------------------------------------------
ll f(ll x) { return x * (x + 1) / 2; }
//---------------------------------------------------------------------------------------------------
int main() {
    cin >> N >> S;
    M = S.length();
 
    if (S.find('B') == string::npos) {
        // 全是A
        ll ans = f((ll)M * N);
        cout << ans << endl;
        return;
    }
 
    vector<ll> v;
    S += "B";
    int pre = -1;
    rep(i, 0, M + 1) if (S[i] == 'B') {
        if (0 < i - pre - 1) v.push_back(i - pre - 1);
        pre = i;
    }
 
    //fore(i, v) printf("%d\n", i);
 
    ll ans = 0;
    if (S[0] == 'A' and S[M - 1] == 'A') {
        if (N == 1) {
            fore(i, v) ans += f(i);
        } else {
            int n = v.size();
            rep(i, 0, n - 1) ans += f(v[i]);
            v[0] += v[n - 1];
            ll sm = 0;
            rep(i, 0, n - 1) sm += f(v[i]);
            ans += sm * (N - 2);
            rep(i, 0, n) ans += f(v[i]);
        }
    }
    else {
        ll sm = 0;
        fore(i, v) sm += f(i);
        ans = sm * N;
    }
 
    cout << ans << endl;
}

本文在 CC BY-NC-ND 4.0( https://creativecommons.org/licenses/by-nc-nd/4.0/deed.zh )协议 的前提下,禁止超过文章30%字数的摘录(对于不超过文章30%字数的摘录,要求在醒目位置注明原文作者与原文链接),同时,在未经作者本人手写签名许可的情况下,禁止任何形式的全文转载,禁止发布任何基于本文的再创作。

hexo博客【NexT从主题下载到随心DIY】 上一篇
题解 AT908 【辞書式順序ふたたび】 下一篇
本博客采用 xCss 的 Valine 评论系统,搭配了 Valine-Admin,垃圾评论将会被过滤。所以在评论的时候,请注意您的语言。如果您的评论被过滤但并非垃圾评论,请发邮件到 luosiweimail@gmail.com 进行申诉。