【CF1774C】Ice and Fire（构造，DP）

【题目描述】
有$n$个人，第$i$个人的温度为$i$。
环境类型为$0$或$1$，若环境为$0$，则温度低的人胜利，若环境为$1$，则温度高的人胜利，$n-1$个环境类型组成一个长为$n-1$的二进制串$s$。
若$x$个人参与游戏，则共有$x-1$场战斗，环境类型即为$s$的前$x-1$个元素。在有不少于$2$个人时，任选$2$个人进行战斗，其中第$i$场战斗的环境类型为sis_isi​。
对于任意一个从$2$到$n$的$x$，如果所有温度不超过$x$的人都参与比赛，有多少人有机会获胜（活到最后）？

【输入格式】
第一行一个整数t(1≤t≤103)t(1\\le t\\le 10^3)t(1≤t≤103)，表示测试样例的数量。
对于每组测试样例第一行输入一个整数n(2≤n≤2×105)n(2\\le n\\le 2\\times 10^5)n(2≤n≤2×105)，表示玩家个数。
第二行输入一个长度为$n-1$的字符串$s$。
数据保证每组测试用例中的$n$的和不超过3×1053\\times 10^53×105。

【输出格式】
对于每组测试用例，输出一行共$n-1$个整数，即对于从$2$到$n$的每一个$x$，有多少人有机会获胜。

【输入样例】

2
4
001
4
101

【输出样例】

1 1 3
1 2 3

【说明/提示】
In the first test case, for $x=2$ and $x=3$, only the player whose temperature value is $1$ can be the winner. For $x=4$ , the player whose temperature value is $2,3,4$ can be the winner.

【分析】

假设最后一场的环境为$1$，即温度大的人赢，那么温度为$1$的人即使活到了最后一场也必输。

同理，如果最后$k$场的环境都为$1$，那么有$k(1\sim k)$个人一定没机会赢，另外的$x-k$名选手都有机会赢，因为只有温度大于等于$k+1$的人才可能连续战胜温度为$1\sim k$的人活到最后。

那么如何保证$k+1\sim x$名选手都有机会活到最后$k$场呢？假设要使选手$i(k+1\le i\le x)$活到最后$k$场，只需要先让剩下的在$k+1\sim x$中的选手互相对战，由于第$k-1$场环境一定为$0$，那么让剩下的另一名选手$j$和$1\sim k$中的选手打，被淘汰，那么$i$就活到了最后$k$场。

反之如果最后$k$场的环境都为$0$也同样可以证明有机会赢的人数为$x-k$。

【代码】

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;int main()
{int T, n;string s;cin >> T;while (T--){cin >> n >> s;cout << 1 << ' ';for (int i = 1, k = 1; i < s.size(); i++)  // k表示最长相同后缀的长度{if (s[i] == s[i - 1]) k++;else k = 1;cout << i + 2 - k << ' ';  // 第1 ~ i + 2名选手参赛}cout << endl;}return 0;
}