【树上倍增】【内向基环树】【 图论 】2836. 在传球游戏中最大化函数值

本文涉及知识点

树上倍增 内向基环树 图论

LeetCode2836. 在传球游戏中最大化函数值

给你一个长度为 n 下标从 0 开始的整数数组 receiver 和一个整数 k 。
总共有 n 名玩家,玩家 编号 互不相同,且为 [0, n - 1] 中的整数。这些玩家玩一个传球游戏,receiver[i] 表示编号为 i 的玩家会传球给编号为 receiver[i] 的玩家。玩家可以传球给自己,也就是说 receiver[i] 可能等于 i 。
你需要从 n 名玩家中选择一名玩家作为游戏开始时唯一手中有球的玩家,球会被传 恰好 k 次。
如果选择编号为 x 的玩家作为开始玩家,定义函数 f(x) 表示从编号为 x 的玩家开始,k 次传球内所有接触过球玩家的编号之 和 ,如果有玩家多次触球,则 累加多次 。换句话说, f(x) = x + receiver[x] + receiver[receiver[x]] + … + receiver(k)[x] 。
你的任务时选择开始玩家 x ,目的是 最大化 f(x) 。
请你返回函数的 最大值 。
注意:receiver 可能含有重复元素。
示例 1:

传递次数 传球者编号 接球者编号 x + 所有接球者编号
2
1 2 1 3
2 1 0 3
3 0 2 5
4 2 1 6

输入:receiver = [2,0,1], k = 4
输出:6
解释:上表展示了从编号为 x = 2 开始的游戏过程。
从表中可知,f(2) 等于 6 。
6 是能得到最大的函数值。
所以输出为 6 。
示例 2:

传递次数 传球者编号 接球者编号 x + 所有接球者编号
4
1 4 3 7
2 3 2 9
3 2 1 10

输入:receiver = [1,1,1,2,3], k = 3
输出:10
解释:上表展示了从编号为 x = 4 开始的游戏过程。
从表中可知,f(4) 等于 10 。
10 是能得到最大的函数值。
所以输出为 10 。

提示:

1 <= receiver.length == n <= 105
0 <= receiver[i] <= n - 1
1 <= k <= 1010

树上倍增

记录各节点传球一次的接受者和积分。
然后计算传球两次的接受者和积分。
⋯ \cdots 4 次 ⋯ \cdots
⋯ \cdots 8 次 ⋯ \cdots
⋮ \vdots

代码

核心代码

class CPow2
{
public:
	CPow2(vector<int>& receiver, long long k): m_c(receiver.size())
	{
		long long tmp = k;
		int iPow2 = 0;
		for( ; iPow2 <= 63;iPow2++ )
		{
			if ((1LL << iPow2) == tmp)
			{
				break;
			}
			tmp &= ~(1LL << iPow2);
		}
		m_vParent.assign(iPow2 + 1, vector<int>(m_c));
		m_vSum.assign(iPow2 + 1, vector<long long>(m_c));
		for (int i = 0; i < m_c; i++)
		{
			m_vParent[0][i] = receiver[i];
			m_vSum[0][i] =  receiver[i];
		}
		for (int j = 1; j <= iPow2; j++)
		{
			for (int i = 0; i < m_c; i++)
			{
				const int next = m_vParent[j - 1][i];
				m_vParent[j][i] = m_vParent[j - 1][next];
				m_vSum[j][i] = m_vSum[j-1][i] + m_vSum[j-1][next];
			}
		}
	}
	long long Query(int cur, long long k)
	{
		long long ans = 0;
		for (int i = 0; i < m_vParent.size(); i++)
		{
			if ((1LL << i) & k)
			{
				ans += m_vSum[i][cur];
				cur = m_vParent[i][cur];
			}
		}
		return ans;
	}
	const int m_c;
protected:	
	vector<vector<int>> m_vParent;
	vector<vector<long long>> m_vSum;
};
class Solution {
public:
	long long getMaxFunctionValue(vector<int>& receiver, long long k) {
		CPow2 pow(receiver, k);
		long long llMax = 0;
		for (int i = 0; i < pow.m_c; i++)
		{
			llMax = max(llMax, i+pow.Query(i, k));
		}
		return llMax;
	}
};

测试用例

template<class T, class T2>
void Assert(const T& t1, const T2& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{
	vector<int> receiver; long long k;
	{
		Solution sln;
		receiver = { 1,0 }, k = 10000000000;
		auto res = sln.getMaxFunctionValue(receiver, k);
		Assert(5000000001, res);
	}
	{
		Solution sln;
		receiver = { 2, 0, 1 }, k = 4;
		auto res = sln.getMaxFunctionValue(receiver, k);
		Assert(6, res);
	}
	{
		Solution sln;
		receiver = { 1,1,1,2,3 }, k =3;
		auto res = sln.getMaxFunctionValue(receiver, k);
		Assert(10, res);
	}
}

2023年8月

class CCycle
{
public:
CCycle(vector& receiver):m_receiver(receiver),m_c(receiver.size())
{
}
void Init(const unordered_set& setNotCycle)
{
CalCycleDis(setNotCycle);
CalCycleNode();
}
long long CalScore(int begin, long long needNode)
{
const int iCycleHead = m_mNodeToCycleHead[begin];
const long long llCycleNum = needNode / m_mCycleNodes[iCycleHead].size();//需要走多少整圈
needNode %= m_mCycleNodes[iCycleHead].size();//不足一圈部分
const long long llCycleScore = m_vDisScoreToCycelHead[m_receiver[iCycleHead]].second;//完整一圈的分数
if (0 == needNode)
{
return llCycleScore * llCycleNum;
}
const int iNodeNumToHead = m_vDisScoreToCycelHead[begin].first+1;//当前点到环首,共经过多少个点
long long llRet = m_vDisScoreToCycelHead[begin].second;
if (needNode > iNodeNumToHead )
{//过了环首后,还需要继续
const int iSubBegin = m_mCycleNodes[iCycleHead][needNode - iNodeNumToHead+1];
llRet += llCycleScore - m_vDisScoreToCycelHead[iSubBegin].second ;
}
else if( needNode < iNodeNumToHead)
{//没到环首
const int index = (m_mCycleNodes[iCycleHead].size() - (iNodeNumToHead - needNode - 1)) % m_mCycleNodes[iCycleHead].size();
const int iSubBegin = m_mCycleNodes[iCycleHead][index];
llRet -= m_vDisScoreToCycelHead[iSubBegin].second;
}
return llRet + llCycleScore* llCycleNum;
}
protected:
void CalCycleNode()
{
for (const auto& head : m_setCycelHead)
{
m_mCycleNodes[head].emplace_back(head);
m_mNodeToCycleHead[head] = head;
for (auto next = m_receiver[head]; next != head; next = m_receiver[next])
{
m_mCycleNodes[head].emplace_back(next);
m_mNodeToCycleHead[next] = head;
}
}
}
void CalCycleDis(const unordered_set& setNotCycle)
{
//环上各点到环首(编号最小的点)的距离
m_vDisScoreToCycelHead.assign(m_c, std::make_pair(-1, -1));
for (int i = 0; i < m_c; i++)
{
if (setNotCycle.count(i))
{
continue;//非环
}
DFSHead(i, i);
}
}
std::pair<int, long long> DFSHead(int cur, int head)
{
if (-1 != m_vDisScoreToCycelHead[cur].first)
{
return m_vDisScoreToCycelHead[cur];
}
if (cur == head)
{
m_setCycelHead.emplace(head);
m_vDisScoreToCycelHead[cur] = std::make_pair(0, cur);
DFSHead(m_receiver[cur], head);
return m_vDisScoreToCycelHead[cur];
}
const auto [nextDis, nextScore] = DFSHead(m_receiver[cur], head);
return m_vDisScoreToCycelHead[cur] = std::make_pair(nextDis + 1, nextScore + cur);
}
vector<std::pair<int, long long>> m_vDisScoreToCycelHead;//环上个点到环首(编号最小): 距离 和 分数(包括当前点、环首)
unordered_set m_setCycelHead;//环首
unordered_map<int, vector> m_mCycleNodes;//环上各点(按顺序存储)
unordered_map<int, int> m_mNodeToCycleHead;//各点对应环首
const int m_c;
const vector& m_receiver;
};

class Solution {
public:
long long getMaxFunctionValue(vector& receiver, long long k) {
m_c = receiver.size();
m_receiver = receiver;
k++;//点数比边数多1
//由于出度为1,所以没个联通区域只有一个环
//由于点数等于边数,故每个联通区域必定有一个环
//由于出度为1,所以进入环后,就只能在环上循环
//计算入度
vector vInDeg(m_c);
for (const auto& n : receiver)
{
vInDeg[n]++;
}
queue que;
for (int i = 0; i < m_c; i++)
{
if (0 == vInDeg[i])
{
m_setInDeg0.emplace(i);
que.emplace(i);
}
}
//通过拓扑排序判断那些点时环上
while (que.size()) {
const int cur = que.front();
que.pop();
m_setNotCycle.emplace(cur);
const int next = receiver[cur];
vInDeg[next]–;
if (0 == vInDeg[next])
{
que.emplace(next);
}
}

	//求各点到环上的次数,及距离
	m_vDisScoreToCycle.assign(m_c, std::make_tuple(- 1,-1,-1));
	for (int i = 0; i < m_c; i++)
	{
		dfs(i);
	}

	m_vRet.assign(m_c,-1);
	CCycle cycle(receiver);
	cycle.Init(m_setNotCycle);
	//处理整个路径都在环上
	for (int i = 0; i < m_c; i++)
	{
		if (m_setNotCycle.count(i))
		{
			continue;
		}		
		m_vRet[i] = cycle.CalScore(i, k);
	}
	//处理整个路径不在环上的点
	for (const auto cur : m_setInDeg0)
	{
		dfsLen(cur, k);
	}
	//非环开始,环结束
	for (int i = 0; i < m_c; i++)
	{
		if (-1 != m_vRet[i])
		{
			continue;
		}
		m_vRet[i] = get<1>(m_vDisScoreToCycle[i]) + cycle.CalScore(get<2>(m_vDisScoreToCycle[i]), k - get<0>(m_vDisScoreToCycle[i]));
	}
	return *std::max_element(m_vRet.begin(),m_vRet.end());
}
void dfsLen(int cur, const long long llNeedNode)
{	
	if (get<0>(m_vDisScoreToCycle[cur]) < llNeedNode)
	{
		return ;
	}
	long llScoer = 0;
	int r = cur;
	for(int i = 0 ; i < llNeedNode;i++ )
	{
		llScoer += r;
		r = m_receiver[r];
	}
	m_vRet[cur] = llScoer;
	while (get<0>(m_vDisScoreToCycle[m_receiver[cur]]) >= llNeedNode)
	{
		llScoer += r - cur;
		cur= m_receiver[cur];
		r = m_receiver[r];
		m_vRet[cur] = llScoer;
	}		
}
std::tuple<int,long long,int> dfs(int cur)
{
	auto& curRes = m_vDisScoreToCycle[cur];
	if (-1 != get<0>(curRes))
	{
		return curRes;
	}
	if (!m_setNotCycle.count(cur))
	{
		return curRes = std::make_tuple(0,0,cur);
	}	
	auto [iDis,iScore,iCycle] = dfs(m_receiver[cur]);
	return curRes = std::make_tuple(iDis+1,iScore+cur, iCycle);
}		
std::unordered_set<int> m_setNotCycle,m_setInDeg0;//非环上点; 入度为0的点
vector<tuple<int,long long,int>> m_vDisScoreToCycle;
std::unordered_map<int, int> m_mNodeToCycle;
vector<long long> m_vRet;
int  m_c;
vector<int> m_receiver;

};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/515424.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

ideaSSM图书借阅管理系统VS开发mysql数据库web结构java编程计算机网页源码maven项目

一、源码特点 SSM 图书借阅管理系统是一套完善的信息管理系统&#xff0c;结合SSM框架和bootstrap完成本系统&#xff0c;对理解JSP java编程开发语言有帮助系统采用SSM框架&#xff08;MVC模式开发&#xff09;&#xff0c;系统具有完整的源代码 和数据库&#xff0c;系统主…

【爬虫+数据清洗+数据分析+可视化】“淄博烧烤”现象热评舆情python数据分析大屏

一、开发背景 您好&#xff0c;我是马哥小迷弟132 &#xff0c;一枚10年程序猿。 自从2023.3月以来&#xff0c;"淄博烧烤"现象持续占领热搜流量&#xff0c;体现了后疫情时代众多网友对人间烟火气的美好向往&#xff0c;本现象级事件存在一定的数据分析实践意义。…

Java零基础入门-java8新特性(上篇)

一、本期教学目标 java8有哪些新特性什么是函数式接口什么是Lambda表达式掌握Stream ApiStream和Collect集合区别Stream创建方式Stream操作三步骤 二、概述 上几期&#xff0c;我们是完整的学完了java异常类的学习及实战演示、以及学习了线程进程等基础概念&#xff0c;而这一…

Cache多核之间的一致性MESI

快速链接: 【精选】ARMv8/ARMv9架构入门到精通-[目录] &#x1f448;&#x1f448;&#x1f448; 思考: 1、为什么要学习MESI协议&#xff1f; 哪里用到了&#xff1f;你确定真的用到了&#xff1f; 2、MESI只是一个协议&#xff0c;总得依赖一个硬件去执行该协议吧&#xff0c…

电商技术揭秘一:电商架构设计与核心技术

文章目录 引言一、电商平台架构概述1.1 架构设计原则与架构类型选择1.2 传统电商平台架构与现代化架构趋势分析 二、高并发处理与负载均衡2.1 高并发访问特点分析与挑战2.2 负载均衡原理与算法选择 三、分布式数据库与缓存技术3.1 分布式数据库设计与一致性考量3.2 缓存策略与缓…

C++实现二叉搜索树的增删查改(非递归玩法)

文章目录 一、二叉搜索树的概念结构和时间复杂度二、二叉搜索树的插入三、二叉搜索树的查找四、二叉搜索树的删除&#xff08;最麻烦&#xff0c;情况最多&#xff0c;一一分析&#xff09;3.1首先我们按照一般情况下写&#xff0c;不考虑特殊情况下4.1.1左为空的情况&#xff…

分享:搭建企微知识库简单易学步骤

说起企微知识库&#xff0c;可能有些人还不太清楚&#xff0c;为什么现在很懂企业选择搭建企微知识库&#xff1f;其实&#xff0c;企微知识库就是一个装满了企业的各种知识、经验和资料的载体。目的是为了方便员工随时查找和学习、有助于知识的传承和共享、加强团队协作和沟通…

自然语言处理: 第二十一章大模型基底之llama2

文章地址: LLaMA:OpenandEfficient Foundation Language Models 项目地址: meta-llama/llama: Inference code for Llama models (github.com) 前言 在LLaMa1的基础之上有兴趣的可以看看我上一篇博客自然语言处理: 第二十一章大模型基底之llama1。Meta 又继续推出了LLaMa2&a…

windows安装OpenUSD

一、下载OpenUSD git clone https://github.com/PixarAnimationStudios/OpenUSDOpenUSD&#xff0c;原名USD&#xff08;Universal Scene Description&#xff0c;通用场景描述&#xff09;&#xff0c;是由皮克斯动画工作室开发的一种开放数据格式。OpenUSD主要用于在虚拟世界…

AI论文速读 |【综述】 时序分析基础模型:教程与综述

论文标题&#xff1a;Foundation Models for Time Series Analysis: A Tutorial and Survey 作者&#xff1a; Yuxuan Liang&#xff08;梁宇轩&#xff09;, Haomin Wen&#xff08;温浩珉&#xff09;, Yuqi Nie&#xff08;PatchTST一作&#xff09;, Yushan Jiang, Ming J…

机器学习全攻略:概念、流程、分类与行业应用案例集锦

目录 1.引言 2.从零开始认识机器学习&#xff1a;基本概念与重要术语 3.五步走&#xff1a;掌握机器学习项目执行的完整流程 3.1.问题定义与数据收集 3.2.数据预处理与特征工程 3.3.模型选择与训练 3.4.模型评估与优化 3.5.模型部署与监控 4.深入了解各类机器学习方法…

计算机网络—TCP协议详解:特性、应用(2)

&#x1f3ac;慕斯主页&#xff1a;修仙—别有洞天 ♈️今日夜电波&#xff1a;マリンブルーの庭園—ずっと真夜中でいいのに。 0:34━━━━━━️&#x1f49f;──────── 3:34 &#x1f504; ◀️…

基于卷积神经网络的苹果等级分类系统(pytorch框架)【python源码+UI界面+前端界面+功能源码详解】

功能演示&#xff1a; 苹果等级分类系统&#xff0c;基于vgg16&#xff0c;resnet50卷积神经网络&#xff08;pytorch框架&#xff09;_哔哩哔哩_bilibili &#xff08;一&#xff09;简介 基于卷积神经网络的苹果等级分类系统是在pytorch框架下实现的&#xff0c;系统中有两…

LangChain-05 RAG Conversational 增强检索会话

安装依赖 pip install --upgrade --quiet langchain-core langchain-community langchain-openai编写代码 from langchain_core.messages import AIMessage, HumanMessage, get_buffer_string from langchain_core.prompts import format_document from langchain_core.runn…

腾讯云轻量服务器8核16G服务器价格1668元一年送3个月,18M大带宽

腾讯云轻量应用服务器8核16G配置租用优惠价格1668元15个月&#xff0c;买一年送3个月&#xff0c;配置为&#xff1a;轻量8核16G18M、270GB SSD盘、3500GB月流量、18M带宽&#xff0c;腾讯云优惠活动 yunfuwuqiba.com/go/txy 活动链接打开如下图&#xff1a; 腾讯云8核16G服务器…

基于java+SpringBoot+Vue的网上订餐系统设计与实现

基于javaSpringBootVue的网上订餐系统设计与实现 开发语言: Java 数据库: MySQL技术: Spring Boot JSP工具: IDEA/Eclipse、Navicat、Maven 系统展示 前台展示 菜品浏览与选择&#xff1a;用户可以浏览不同的菜品分类&#xff0c;并选择心仪的菜品。 订单创建与管理&…

多线程--深入探究多线程的重点,难点以及常考点线程安全问题

˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好&#xff0c;我是xiaoxie.希望你看完之后,有不足之处请多多谅解&#xff0c;让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如…

SpringBoot登录校验(四)过滤器Filter

JWT令牌生成后&#xff0c;客户端发的请求头中会带有JWT令牌&#xff0c;服务端需要校验每个请求的令牌&#xff0c;如果在每个controller方法中添加校验模块&#xff0c;则十分复杂且冗余&#xff0c;所以引入统一拦截模块&#xff0c;将请求拦截下来并做校验&#xff0c;这块…

100道面试必会算法-18-岛屿问题(数量、周长、面积)

100道面试必会算法-18-岛屿问题&#xff08;数量、周长、面积&#xff09; 题目描述 给你一个由 1&#xff08;陆地&#xff09;和 0&#xff08;水&#xff09;组成的的二维网格&#xff0c;请你计算网格中岛屿的数量。 岛屿总是被水包围&#xff0c;并且每座岛屿只能由水平…

银行数字化转型导师坚鹏:银行数字化转型给支行带来的8大价值

银行数字化转型给支行带来的8大价值 银行数字化转型对不仅对总行、分行产生了深远影响&#xff0c;给总行、分行带来了新质生产力&#xff0c;对银行支行&#xff08;包括网点&#xff09;也会产生重要价值&#xff0c;银行数字化转型导师坚鹏从以下8个方面进行详细分析&#…