|
题目
题意
- 有n位玩家，每个玩家有有一个热力值，分别为1到n。
- 准备n-1场比赛，每场比赛由0或1构成。
- 对于每场比赛，可以任意选择两个玩家进行比赛。如果比赛为0，则热力值低的玩家获胜；如果比赛为1，则热力值高的玩家获胜。输的玩家退出，且不得参与后边的比赛。
执行n-1场比赛后，则最终会产生最后的胜者。
给定n-1场比赛的值，对于i从1到n-1，
求 安排前i个玩家，参与前i-1场比赛，可能取胜的玩家有多少种情况。
思路
先关注子问题，安排k个玩家，参与前k-1场比赛，可能取胜的玩家有多少种情况。
首先，至少有1个玩家可以取胜。
假设这k-1场比赛有a个0，b个1。我们可以选择热力值为a+1的选手，让他在参与每场比赛，比赛为0时则与热力值小于他的比赛；比赛为1时则与热力值大于他的比赛。这样，该选手最终可以获胜。
其次，对于这k-1场比赛，从后往前最多有x场比赛的值相同，那么取胜的玩家总共有k-1-x种情况。
不失一般性，我们设最后这x场比赛取值为0，那么热力值为k-x的选手可以取胜，我们只需要让他参与后边x+1场比赛。同时在后边x场比赛，安排与热力值更高的选手比赛。
最后x场比赛，由于参数的玩家热力值都高于k-x的选手，他可以取得获胜。
倒数第x+1场比赛（如果存在）的值为0，且剩余玩家的热力值都低于k-x的选手，他可以取得获胜。
同理，热力值k-x-1的选手也可以获胜，我们只需要让 热力值 k-x的选手去代替热力值k-x-1 选手的位置即可。把热力值k-x-1 选手放到后边x场比赛中。
依次类推，热力值k-x-1可以获胜，热力值k-x-2也可以获胜。
…
依次类推，热力值1的选手也可以获胜
即热力值1到热力值k-x的选手，都可以获胜。
因此，我们只需要维护当前最长连续序列长度x即可。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 200010;
int n;
char s[maxn];
void solve() {
scanf("%d", &n);
scanf("%s", &s);
int tot = 1;
vector<int> res = {1};
for (int i = 1; i < n - 1; ++i) {
if (s[i] == s[i-1]) {
++tot;
} else {
tot = 1;
}
res.push_back(i + 2 - tot);
}
for (int i = 0; i < n - 2; ++i) {
printf("%d ", res[i]);
}
printf("%d\n", res[n-2]);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
solve();
}
}
|