吐槽一下,官方题解写的挺难看懂的,看了好久还是挺迷糊的(其实也是我太菜了)。搞懂之后感觉这题挺妙的,来写下题解。

思路

我们首先需要有一个观察,就是对于 ss 串,最后一个连续字串不会增加可能的获胜人数。比如 s=0011s = \texttt{0011} 时,后面结尾的 11\texttt{11} 就不会增加可能的获胜人数。

为啥呢,设我们设经过任意次数对战后,玩家可能组合的集合为 tt 那么对于任意的 xtx \in t,连续在环境 11 中对战任意次数后,最终的赢家一定是 xx 中温度最高的(因为每个剩下的玩家都会需要连续在环境 11 中对战,唯一能胜出所有对战的玩家一定是最大的)。同理,tt 中的玩家连续在环境 00 中对战任意次数后,最终的赢家一定是 xx 中温度最低的。

例如,s=111s = \texttt{111} 时,最后胜出的一定是 44 号玩家。

这样一来,如果结尾段是 1100 结尾同理,后面为了方便先用 11 的例子了),我们只需要算出前面的部分最多能构造出多少种最大值(玩家温度)不同的玩家组合,就能知道当前长度的 ss 的答案了。

现在考虑如何构造出最多的最大值不同的玩家组合。如果玩家数量为 nn,那么没有经过任何对战时,最大值就是 nn。想要让最大值不同,只能删除当前的最大值。

特殊情况

刚刚的描述可能比较抽象,考虑 s=0011s = \texttt{0011} 这个例子就能较好的理解了。

对于第一个 00,除了玩家组合中温度最低的不能删掉(这个不管怎样都能赢),其他的都能删掉(让温度最低的玩家和其他任意玩家对战),共有如下几种情况:

1:123452:123453:123454:123451 : \texttt{1234} \cancel{\texttt{5}} \\ 2 : \texttt{123} \cancel{\texttt{4}} \texttt{5} \\ 3 : \texttt{12} \cancel{\texttt{3}} \texttt{45} \\ 4 : \texttt{1} \cancel{\texttt{2}} \texttt{345} \\

观察发现,只有第一种情况改变了最大值(为啥呢?因为他删掉了最大值)。其他的情况中,必须要连续的删除结尾的一段数字,才能改变最大值。

这时候第二个 00 就起到作用了。对于第二种情况,其可以把 55 删掉,使得玩家组合的最大值变为 33。我们按照这个规律可以进一步推广出这个结论:设结尾段前面连续段的长度为 ll,能产生的最大值不同的玩家组合就为 l+1l + 1,具体来说,可能的最大值范围是 [nl,n][n - l, n]。(这里 +1+1 是因为可以选择不改变最初的最大值)。

现在为止,我们已经能求出 ss 只有两个连续段时的答案了。即 nkn - k,其中 k=slk = |s| - l,表示结尾段的长度。

推广

这个时候我们把例子换成 s=1011s = \texttt{1011},看看例子是否还成立(ss 不止一段)。同样,可以列出第一次对战后的可能玩家组合。因为第一个环境是 11,所以只能删除除了最大值以外的其他玩家:

1:123452:123453:123451:123451 : \texttt{123} \cancel{\texttt{4}} \texttt{5} \\ 2 : \texttt{12} \cancel{\texttt{3}} \texttt{45} \\ 3 : \texttt{1} \cancel{\texttt{2}} \texttt{345} \\ 1 : \cancel{\texttt{1}} \texttt{2345} \\

虽然这些情况中,没有任何一种改变了玩家组合的最大值,但是我们只要在接下来的 00 环境中再对战一次,删除掉 55,就产生了 22 种新的最大值。对于第一种情况,最大值变为了 33,第二种变为了 22。一共也是 nkn - k 种答案。

那如果段数再多一点呢?比如 s=01011s = \texttt{01011}。这个结论还是成立的。我们可以把 010\texttt{010} 看作一组环境,其中 00 可以删除 [2,n][2, n] 范围内的任何玩家,11 则为 [1,n1][1, n - 1] 中的任何玩家。把这两种环境组合起来就可以从 [1,n][1, n] 种任意挑选 33 个删除,构造出 44 种不同的最大值(取决于你删除前多少个温度最大的玩家)。

代码和实现

通过前面的例子我们已经分析出了,解决问题只需要知道 ss[1,i][1, i] 子串中,最后一个连续段的长度。不过对于每个 ii 都扫一遍太慢了,需要采用类似动态规划的东西,具体我在代码注释里有解释:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    int t;
    cin >> t;
    while(t--){
        int n;
        string s;
        cin >> n >> s;
        int cur0len = 0; // 最后一个连续段如果是 0 的话 cur0len 表示其长度,
                         // 如果不是的话 cur0len 就是 0 
        int cur1len = 0; // 和 1 相同
        int curn = 2;    // 最开始是两个玩家
        for (char ch : s){
            int x = ch - '0';
            if (x == 0){
                cur0len++;   // 当前是 0 的话 0 结尾的连续段会比原来更长
                cur1len = 0; // s 的最后一个不是 1 了
            } else {
                cur1len++;
                cur0len = 0;
            }
            cout << curn - (x ? cur1len : cur0len) << " ";
            // 前文中的 n - k
            curn++;
        }
        cout << '\n';
    }
}