本文共 2313 字，大约阅读时间需要 7 分钟。

Codeforces Global Round 11

1427A. Avoiding Zero

题目链接：

待补

1427B. Chess Cheater

题目链接：

Example

input

85 2WLWLL6 5LLLWWL7 1LWLWLWL15 5WWWLLLWWWLLLWWW40 7LLWLWLWWWLWLLWLWWWLWLLWLLWLLLLWLLWWWLWWL1 0L1 1L6 1WLLWLW

output

71162646016

Note

第一个测试用例的说明。 在改变任何结果之前，得分为 \(2\) 分。 的确，您赢得了第一场比赛，因此获得了\(1\)分，您也赢得了第三场，因此又获得了\(1\)分（而不是\(2\)分，因为输了第二场比赛）。

思路：

请注意，分数等于

连胜是连续获胜的最大顺序。

在下面的说明中，变量\(＃\{wins\}，＃\{winning\_streaks\}\) 始终与初始情况相关。

如果 \(k +＃\{wins\}≥n\)，则有可能赢得所有比赛，因此答案为 \(2n-1\) 。

否则，很明显，我们要转换k获胜中的k损失。因此，作弊后，获胜次数将为\(k +＃\{wins\}\)。考虑到以上公式，仍然仅是要减少获胜间隔的数量。

我们如何才能减少连胜的次数？非常直观的是，我们将从长度最短的差距开始，以“填补”连续的获胜间隔之间的差距。可以证明，如果没有填补 g 个缺口（即在作弊之后，g个缺口仍然至少包含一个损失），则至少有g + 1个获胜间隔。

实现过程如下。通过线性扫描，我们可以找到间隙的长度，然后对它们进行排序。最后，我们计算可以选择的总和 \(≤k\) 的数量。答案是

解决方案的复杂度为 \(O(log(n))\)。

AC代码

#include
   
    #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
    
      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";	}}