Codeforces Global Round 11
1427A. Avoiding Zero
题目链接：click here
待补
1427B. Chess Cheater
题目链接：click here
Example
input
8
5 2
WLWLL
6 5
LLLWWL
7 1
LWLWLWL
15 5
WWWLLLWWWLLLWWW
40 7
LLWLWLWWWLWLLWLWWWLWLLWLLWLLLLWLLWWWLWWL
1 0
L
1 1
L
6 1
WLLWLW
output
7
11
6
26
46
0
1
6
Note
第一个测试用例的说明。 在改变任何结果之前，得分为 \(2\) 分。 的确，您赢得了第一场比赛，因此获得了\(1\)分，您也赢得了第三场，因此又获得了\(1\)分（而不是\(2\)分，因为输了第二场比赛）。
作弊的最佳方法是更改第二局和第四局的结果。 这样做，您最终赢得了前四场比赛（结果的字符串变为WWWWL）。 因此，新分数是\(7 = 1 + 2 + 2 + 2\) ：第一场比赛\(1\)分，第二场，第三场和第四场比赛\(2\)分。
第二个测试用例的说明。 在更改任何结果之前，得分为\(3\) 。确实，您赢得了第四场比赛，所以您获得了\(1\)分，并且您还赢得了第五场比赛，因此又获得了\(2\)分（因为您也赢得了上一场比赛）。
作弊的最佳方法是更改第一局，第二局，第三局和第六局的结果。 这样做，您最终赢得了所有比赛（结果的字符串变成WWWWWW）。 因此，新分数是\(11 = 1 + 2 + 2 + 2 + 2 + 2\)：第一场比赛\(1\)分，其他所有比赛\(2\)分。
思路：
请注意，分数等于
\]
连胜是连续获胜的最大顺序。
在下面的说明中，变量\(＃\{wins\}，＃\{winning\_streaks\}\) 始终与初始情况相关。
如果 \(k +＃\{wins\}≥n\)，则有可能赢得所有比赛，因此答案为 \(2n-1\) 。
否则，很明显，我们要转换k获胜中的k损失。因此，作弊后，获胜次数将为\(k +＃\{wins\}\)。考虑到以上公式，仍然仅是要减少获胜间隔的数量。
我们如何才能减少连胜的次数？非常直观的是，我们将从长度最短的差距开始，以“填补”连续的获胜间隔之间的差距。可以证明，如果没有填补 g 个缺口（即在作弊之后，g个缺口仍然至少包含一个损失），则至少有g + 1个获胜间隔。
实现过程如下。通过线性扫描，我们可以找到间隙的长度，然后对它们进行排序。最后，我们计算可以选择的总和 \(≤k\) 的数量。答案是
\]
解决方案的复杂度为 \(O(log(n))\)。
AC代码
#include<bits/stdc++.h>
#define ms(a,b) memset(a,b);
using namespace std;
typedef long long ll;
int main() {
//freopen("in.txt", "r", stdin);
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T;
cin >> T;
for (int t = 1; t <= T; t++) {
int N, K;
cin >> N >> K;
string S;
cin >> S;
int winning_streaks_cnt = 0;
int wins = 0;
int losses = 0;
vector<int> losing_streaks;
for (int i = 0; i < N; i++) {
if (S[i] == 'W') {
wins++;
if (i == 0 or S[i - 1] == 'L') winning_streaks_cnt++;
}
if (S[i] == 'L') {
losses++;
if (i == 0 or S[i - 1] == 'W') losing_streaks.push_back(0);
losing_streaks.back()++;
}
}
if (K >= losses) {
cout << 2 * N - 1 << "\n";
continue;
}
if (wins == 0) {
if (K == 0) cout << 0 << "\n";
else cout << 2 * K - 1 << "\n";
continue;
}
if (S[0] == 'L') losing_streaks[0] = 1e8;
if (S[N - 1] == 'L') losing_streaks.back() = 1e8;
sort(losing_streaks.begin(), losing_streaks.end());
wins += K;
for (int ls : losing_streaks) {
if (ls > K) break;
K -= ls;
winning_streaks_cnt--;
}
cout << 2 * wins - winning_streaks_cnt << "\n";
}
}