「MCOI-03」村国题解
第二篇题解!
可能是退役之前的最后一篇题解了
(好像总共都只写了两篇)
不说了,讲题:
题面
题意:
有T个数据
有一颗树(保证所有的的节点都是相连的),有n个节点,每个节点都有相应的权值与序号,现在你要进行M次操作,操作是:
找到权值最大的节点(如果有权值相同且又是最大的节点,则选择序号较小的节点),与节点直接相连的节点权值+1(本身不增加权值)
最后输出权值最大的节点(有相同的则输出序号较小的节点)。
数据范围:
对于 100% 的数据,1≤N≤2×10^6,
1≤M≤10^18,
1≤A i≤2^31-1,
1≤T≤10
部分分就不写了。
反正很大就是了,看到这个M小于等于10的18次方,你怕了吗
题解(主要是思路):
首先看题目,有人看完题面可能会不知道为什么是一棵树只有你会,题目给出的是N个点,由N-1条双向路径相连,
C 国一共有 N 个村庄,N-1 条道路。这些道路都可以双向通行。
保证小 S 可以从一座村庄到其他任何一座村庄。
这 N 个村庄编号为 1 到 N。
保证小 S 可以从一座村庄到其他任何一座村庄
众所周知,想要组成环,至少需要与节点数相同的路径,而题意又保证各个节点一定相连,就必须要N条路径,但题目给出的只有n-1条路径
,则是一棵树。
好啰嗦
看完题意看数据范围,发现M的范围巨大,连O(M)的算法都过不了,不可做。
于是我陷入了思考,先写一下数据推推规律:
三个点
2 6 3
都相连
2->6->3
M次操作
//1:
num[2]:6最大
3 6 4
//2:
num[2]:6最大
4 6 5
//3:
num[2]:6最大
5 6 6
出现了!相等的点!但是num[2]序号小,答案依旧是选num[2];
//4:
num[2]:6最大
6 6 7
num[3]大于num[2]了;
//5:
num[3]:7最大
6 7 7
又相等了,num[2]序号小,选num[2]。
//6:
num[2]:7最大
7 7 8
num[3]最大了
推到这就差不多了,可以得出以下规律:
(此处的权值指的是初始权值)
x1为权值最大的节点,y1为与它相连的权值相对最大的节点
只需要记录下x1与y1,而其他的节点,拜托,他们超逊的!可以从数据中看出,与6相连的num[1]由于小于num[2],在答案的选择中没有任何竞争力,不与权值最大的节点直接相连的节点就更不要说了。(觉得不对的同学可以自己写几组数据试试)
在M小于num[2]与num[3]的差时,答案恒为num[2],(num[2]:哼,没点时间还想超过我?)可以转化为-----当M小于x1-y1,选x1;
然后就是M>=他们的差时:看数据,第3次操作到第6次操作答案是有循环的,很容易得到是跟M的奇偶性有关的(等于的话就是直接取序号最小就行了),先将M减去x1-y1,奇数取y1,偶数取x1.
这一切都是建立在这个图是一颗树的前提下。
代码实现就行
然后就没了
吗?
还有特判!
在代码实现中,当n=1时的情况要特殊考虑
我就是被这个点坑杀了4个点
85分没了
结束
不点个赞再走?
有什么意见可以发在评论区哦
最新文章
- position定位
- 爱上MVC~为CheckBoxFor和RadioButtonFor加个扩展方法吧(希望MVC5把这方法收纳——呵呵)
- 项目总结笔记系列 wsTax KT Session1
- [javaSE] 练习队列线程和对象序列化
- Linux第二次学习笔记
- Android 框架简介--Java环境(转)
- HTTPS的工作原理
- 李洪强iOS开发之最全App上架流程
- MAVEN:::::: maven-dependency-plugin (goals ";copy-dependencies";, ";unpack";) is not supported
- LINUX系统GIT使用教程
- ChromiumFX中js调用C#方法
- SmartCoder每日站立会议 01
- Temperature hdu 3477
- 2017";百度之星";程序设计大赛 - 资格赛【1001 Floyd求最小环 1002 歪解(并查集),1003 完全背包 1004 01背包 1005 打表找规律+卡特兰数】
- 衡量android开发者水平的面试问题-android学习之旅(91)
- C语言二维数组实现扫雷游戏
- flutter 返回键监听
- PPT vba从Execl 拷贝图表
- Chapter 2 Basic Elements of JAVA
- dedecms在后台替换文章标题、内容、摘要、关键字