当前位置: 首页 > 工具软件 > Some Chess > 使用案例 >

B. Chess Cheater

仲孙夕
2023-12-01

题目:
You like playing chess tournaments online.

In your last tournament you played n games. For the sake of this problem, each chess game is either won or lost (no draws). When you lose a game you get 0 points. When you win you get 1 or 2 points: if you have won also the previous game you get 2 points, otherwise you get 1 point. If you win the very first game of the tournament you get 1 point (since there is not a “previous game”).

The outcomes of the n games are represented by a string s of length n: the i-th character of s is W if you have won the i-th game, while it is L if you have lost the i-th game.

After the tournament, you notice a bug on the website that allows you to change the outcome of at most k of your games (meaning that at most k times you can change some symbol L to W, or W to L). Since your only goal is to improve your chess rating, you decide to cheat and use the bug.

Compute the maximum score you can get by cheating in the optimal way.

Input
Each test contains multiple test cases. The first line contains an integer t (1≤t≤20,000) — the number of test cases. The description of the test cases follows.

The first line of each testcase contains two integers n,k (1≤n≤100,000, 0≤k≤n) – the number of games played and the number of outcomes that you can change.

The second line contains a string s of length n containing only the characters W and L. If you have won the i-th game then si=W, if you have lost the i-th game then si=L.

It is guaranteed that the sum of n over all testcases does not exceed 200,000.

https://codeforces.com/contest/1427/problem/B

题意:
给出一串字符串,字符串中含有W和L,W表示游戏胜利,L表示游戏失败,对于每个W,如果左边相邻也是W的话,分数加两分,如果左边相邻不是W,加一分,L加0分。现给出字符串的长度n和你可以修改的次数K,你可以将任意的小于等于K个L变成W,问改变之后你的分数最大是多少。

思路:
及其之巧妙。
用cur记录连续的L的每段长度。score记录初始时的分数。这里需要注意,cur我们只记录每段W之间的L,以及其实的L长度加5+k,串末尾的L的长度我们是没算进去的。
先令cur=k+5,如果cur==k+5+n,说明串中只有L,那结果就是0和变成连续的k个W的最大值。
否则,将V从小到大排序,从小到大,如果k大于等于v[i]的话,说明可以将这段L全部变为W,那分数就应该增加v[i]*2+1,因为他是两段连续的W之间的L,其中每个L变为W之后的价值都是2,并且后面一段的起始W价值也增加1.最后如果K还有剩余的话,那就直接乘2加到结果里,因为尽可能多的变为W,多了的话在下面程序中我们会保证不超过最大值。

代码:

#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
const double N = 1e6+10;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const inline int read(){
    int k = 0, f = 1; char c = getchar();
    for(;!isdigit(c); c = getchar())
        if(c == '-') f = -1;
    for(;isdigit(c); c = getchar())
        k = k * 10 + c - '0';
    return k * f;
}
#define CL(a,b) memset(a,b,sizeof(a))
#define MAXN 200010
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		int n , k;
		vector<int> v;
		string s;
		cin >> n;
		cin >> k;
		cin >> s;
		int cur = k+5;
		int score = 0;
		for(int i = 0 ; i < n ; i++)
		{
			if(s[i] == 'L')
			{
				cur++;
			}
			else
			{
				score+=cur>0?1:2;
				if(cur > 0)
					v.push_back(cur);
				cur = 0;
			}
		}
		if(cur == k+5+n)
		{
			cout << max(0,2*min(k,n)-1) << endl;
			continue;
		}
		sort(v.begin() , v.end());
		for(int i = 0 ; i < v.size() ; i++)
		{
			if(k >= v[i])
			{
				score = score + 2*v[i];
				score++;
				k = k - v[i];
			}
		}
		score+=2*k;
        score=min(score,2*n-1);//保证不超过最大值
        cout<<score<<endl;
	}
	return 0;
}
 类似资料:

相关阅读

相关文章

相关问答