CF1774C 题解
吐槽一下,官方题解写的挺难看懂的,看了好久还是挺迷糊的(其实也是我太菜了)。搞懂之后感觉这题挺妙的,来写下题解。
思路
我们首先需要有一个观察,就是对于 串,最后一个连续字串不会增加可能的获胜人数。比如 时,后面结尾的 就不会增加可能的获胜人数。
为啥呢,设我们设经过任意次数对战后,玩家可能组合的集合为 那么对于任意的 ,连续在环境 中对战任意次数后,最终的赢家一定是 中温度最高的(因为每个剩下的玩家都会需要连续在环境 中对战,唯一能胜出所有对战的玩家一定是最大的)。同理, 中的玩家连续在环境 中对战任意次数后,最终的赢家一定是 中温度最低的。
例如, 时,最后胜出的一定是 号玩家。
这样一来,如果结尾段是 ( 结尾同理,后面为了方便先用 的例子了),我们只需要算出前面的部分最多能构造出多少种最大值(玩家温度)不同的玩家组合,就能知道当前长度的 的答案了。
现在考虑如何构造出最多的最大值不同的玩家组合。如果玩家数量为 ,那么没有经过任何对战时,最大值就是 。想要让最大值不同,只能删除当前的最大值。
特殊情况
刚刚的描述可能比较抽象,考虑 这个例子就能较好的理解了。
对于第一个 ,除了玩家组合中温度最低的不能删掉(这个不管怎样都能赢),其他的都能删掉(让温度最低的玩家和其他任意玩家对战),共有如下几种情况:
观察发现,只有第一种情况改变了最大值(为啥呢?因为他删掉了最大值)。其他的情况中,必须要连续的删除结尾的一段数字,才能改变最大值。
这时候第二个 就起到作用了。对于第二种情况,其可以把 删掉,使得玩家组合的最大值变为 。我们按照这个规律可以进一步推广出这个结论:设结尾段前面连续段的长度为 ,能产生的最大值不同的玩家组合就为 ,具体来说,可能的最大值范围是 。(这里 是因为可以选择不改变最初的最大值)。
现在为止,我们已经能求出 只有两个连续段时的答案了。即 ,其中 ,表示结尾段的长度。
推广
这个时候我们把例子换成 ,看看例子是否还成立( 不止一段)。同样,可以列出第一次对战后的可能玩家组合。因为第一个环境是 ,所以只能删除除了最大值以外的其他玩家:
虽然这些情况中,没有任何一种改变了玩家组合的最大值,但是我们只要在接下来的 环境中再对战一次,删除掉 ,就产生了 种新的最大值。对于第一种情况,最大值变为了 ,第二种变为了 。一共也是 种答案。
那如果段数再多一点呢?比如 。这个结论还是成立的。我们可以把 看作一组环境,其中 可以删除 范围内的任何玩家, 则为 中的任何玩家。把这两种环境组合起来就可以从 种任意挑选 个删除,构造出 种不同的最大值(取决于你删除前多少个温度最大的玩家)。
代码和实现
通过前面的例子我们已经分析出了,解决问题只需要知道 的 子串中,最后一个连续段的长度。不过对于每个 都扫一遍太慢了,需要采用类似动态规划的东西,具体我在代码注释里有解释:
#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';
}
}