Codeforces Global Round 11 個人題解（B題）

• 2020 年 10 月 11 日
• 筆記
• 刷題筆記: CF

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