IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> C++知识库 -> C. Ice and Fire(贪心/思维) -> 正文阅读

[C++知识库]C. Ice and Fire(贪心/思维)

题目

题意

  • 有n位玩家,每个玩家有有一个热力值,分别为1到n。
  • 准备n-1场比赛,每场比赛由0或1构成。
  • 对于每场比赛,可以任意选择两个玩家进行比赛。如果比赛为0,则热力值低的玩家获胜;如果比赛为1,则热力值高的玩家获胜。输的玩家退出,且不得参与后边的比赛。

执行n-1场比赛后,则最终会产生最后的胜者。

给定n-1场比赛的值,对于i从1到n-1,
求 安排前i个玩家,参与前i-1场比赛,可能取胜的玩家有多少种情况。

思路

先关注子问题,安排k个玩家,参与前k-1场比赛,可能取胜的玩家有多少种情况。
首先,至少有1个玩家可以取胜。

假设这k-1场比赛有a个0,b个1。我们可以选择热力值为a+1的选手,让他在参与每场比赛,比赛为0时则与热力值小于他的比赛;比赛为1时则与热力值大于他的比赛。这样,该选手最终可以获胜。

其次,对于这k-1场比赛,从后往前最多有x场比赛的值相同,那么取胜的玩家总共有k-1-x种情况。
不失一般性,我们设最后这x场比赛取值为0,那么热力值为k-x的选手可以取胜,我们只需要让他参与后边x+1场比赛。同时在后边x场比赛,安排与热力值更高的选手比赛。
最后x场比赛,由于参数的玩家热力值都高于k-x的选手,他可以取得获胜。
倒数第x+1场比赛(如果存在)的值为0,且剩余玩家的热力值都低于k-x的选手,他可以取得获胜。

同理,热力值k-x-1的选手也可以获胜,我们只需要让 热力值 k-x的选手去代替热力值k-x-1 选手的位置即可。把热力值k-x-1 选手放到后边x场比赛中。
依次类推,热力值k-x-1可以获胜,热力值k-x-2也可以获胜。

依次类推,热力值1的选手也可以获胜

即热力值1到热力值k-x的选手,都可以获胜。

因此,我们只需要维护当前最长连续序列长度x即可。

代码

#include<bits/stdc++.h> 
using namespace std;
const int maxn = 200010;

int n;
char s[maxn];
void solve() {
	scanf("%d", &n);
	scanf("%s", &s);
	int tot = 1;
	vector<int> res = {1};
	for (int i = 1; i < n - 1; ++i) {
		if (s[i] == s[i-1]) {
			++tot;
		} else {
			tot = 1;
		}
		res.push_back(i + 2 - tot);
	}
	for (int i = 0; i < n - 2; ++i) {
		printf("%d ", res[i]);
	}
	printf("%d\n", res[n-2]);
}
int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		solve();
	}
}
  C++知识库 最新文章
【C++】友元、嵌套类、异常、RTTI、类型转换
通讯录的思路与实现(C语言)
C++PrimerPlus 第七章 函数-C++的编程模块(
Problem C: 算法9-9~9-12:平衡二叉树的基本
MSVC C++ UTF-8编程
C++进阶 多态原理
简单string类c++实现
我的年度总结
【C语言】以深厚地基筑伟岸高楼-基础篇(六
c语言常见错误合集
上一篇文章      下一篇文章      查看所有文章
加:2022-12-25 10:47:31  更:2022-12-25 10:51:43 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年6日历 -2024/6/17 6:38:27-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码