
Codeforces Global Round 11 个人题解(B题)
发布日期:2021-05-09 00:12:03
浏览次数:18
分类:精选文章
本文共 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"; }}
发表评论
最新留言
表示我来过!
[***.240.166.169]2025年05月06日 09时17分11秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Mac环境安装Kibana
2023-02-06
Mac环境安装logstash
2023-02-06
MAC生成公钥私钥、PKCS1 转 PKCS8
2023-02-06
Mac电脑 如何合并相同名称的文件夹(不用替换)
2023-02-06
Mac电脑怎么读写不了移动硬盘?解决苹果电脑不能读写移动硬盘问题
2023-02-06
Mac电脑生成git的公私钥(拉取代码更便捷)
2023-02-06
mac电脑遇到choose startup disk
2023-02-06
mac的safari浏览器调试h5
2023-02-06
mac破解软件安装后无法打开解决方案(MacOS10.15之后亲测有效)
2023-02-06
Mac终端使用mysql
2023-02-06
MAC解决端口号被占用
2023-02-06
Mac设置crontab
2023-02-06
Mac进入home目录、根目录的方法
2023-02-06
mac配置自定义域名
2023-02-06
magento mysql主从_Magento数据库配置选项,以及mysql 读写分离
2023-02-06
magento1给customer添加自定义属性
2023-02-06
magento如何改变首页的布局
2023-02-06
magento目录结构完整版
2023-02-06