Codeforces Global Round 11 个人题解（B题）-白红宇

Codeforces Global Round 11 个人题解（B题）

阅读量：398 次

发布时间：2019-03-06

本文共 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\)分，因为输了第二场比赛）。

作弊的最佳方法是更改第二局和第四局的结果。这样做，您最终赢得了前四场比赛（结果的字符串变为WWWWL）。因此，新分数是\(7 = 1 + 2 + 2 + 2\) ：第一场比赛\(1\)分，第二场，第三场和第四场比赛\(2\)分。

第二个测试用例的说明。在更改任何结果之前，得分为\(3\) 。确实，您赢得了第四场比赛，所以您获得了\(1\)分，并且您还赢得了第五场比赛，因此又获得了\(2\)分（因为您也赢得了上一场比赛）。

作弊的最佳方法是更改第一局，第二局，第三局和第六局的结果。这样做，您最终赢得了所有比赛（结果的字符串变成WWWWWW）。因此，新分数是\(11 = 1 + 2 + 2 + 2 + 2 + 2\)：第一场比赛\(1\)分，其他所有比赛\(2\)分。

思路：

请注意，分数等于

\[score =2⋅＃\{wins\} −＃\{winning\_streaks\}\]

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

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

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

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

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

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

\[2⋅（k +＃\{wins\}）−＃\{winning\_streaks\} +＃\{gaps\_we\_can\_fill\}\]

解决方案的复杂度为 \(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";	}}

转载地址：http://njykz.baihongyu.com/

你可能感兴趣的文章