【CodeForces 487E】Tourists / 题解

Posted on

题目描述 求简单无向图两点路径上最小权值,支持修改。 思路 先把图中的点双缩点,维护圆方树,把方点的值设为它儿子中点权最小的点的点权,树链剖分。利用 Multiset 维护每个点双的信息即可。 代码

【安利】我的音乐收藏

Posted on

OneDrive 分享链接 易音论坛 缓慢更新中,更新方法是全专上传,尽量同时提供压缩包。 很久以前,我还是一个使用酷狗音乐的小屁孩。2013年我入手了最新一代的 iPod Shuffle,开始使用 iTunes 管理我的音乐。我发现用酷狗音乐下载的歌 ID3 信息经常是错乱的,为了愉快地使用 VoiceOver 每次都要手动改曲名歌手专辑,极为浪费时间并且不便。 和我发小吐槽了酷狗的糟糕后,他拉着我下载了网易云,并且给我推广了他的个人歌单。就是从2014年的那个秋天,我的音乐审美有了“质的飞跃”。这个说法来自我发小本人,显然有夸大他功劳的成分。尽管我在那之前听了很多口水歌,甚至循环过《小苹果》,但我骨子里依然是一个热爱上个世纪民谣和摇滚的伪文艺青年。 除此之外,我的音乐审美还深受我爸的影响。我小时候学习的第一首流行歌曲就是我爸为数不多能不跑调唱完歌之一的《吻别》。众所周知的纵横线、刘德华、张学友、张国荣、谭校长等大佬的歌至今存在我爸的车载播放器内存里,也存在于我的童年记忆里。 然后是和我有着难解渊源的初中女同学带我听的《安和桥北》。一个人在出租屋里的时候,这张专我听一次哭一次。它对我没有什么确定的象征意义,但。。。其中的感情因素我也叙述不来,毕竟我只是一个文笔糟糕的理科生。宋胖子几百年没发新歌了,可能进了一次局子需要多思考一番人生吧。李志似乎暂时对我没有很大的影响,除了那个妹子亲自给我推的《寻找》。他早年的专我是最近才开始补的。民谣这种东西总是要听过几十遍以后才能听出其中真正的韵味来。 关于口水歌。。。Adele 和 Sam Smith 这两位还是听得很多的,《21》听了这么多年,我还是经常循环它,它也是我拥有的为数不多的实体专辑之一。《The Thrill of It All》似乎也循环了一整个暑假,也许 Sam Smith 拥有一些其他歌手看不到的视角,尽管性取向这件事在表达感情上没有太大的影。与此相似的还有 Troye Sivan(我承认颜值是我入坑的第一动力)。《Blue Neighborhood》陪我度过了一段相当困难的时期,我一直觉得它比《Bloom》优秀一点,但后者依然为我们带来了几首质量上乘的新曲,比如我最喜欢的《Postcard》。 几百年之后,我回来更新了。 主页现在是 Abbey Road 的专辑封面,点进去就是网盘里的资源。今年元旦晚会的想法就是完成 Golden Slumber, Carry That Weight, The End 这三首歌。在中山的日子里,这张专和 White Album, Sgt. Pepper’s Lonely Heart Club Band 一起成为了我循环的首选。时隔许久,再次认真听 Beatles 的专,感触还是很大。如果在联赛前,我选择听的都是 […]

【计蒜客 NOIP 提高组模拟竞赛第二试】手拉手 / 题解

Posted on

原题地址 题目描述 小 P 是个幼儿园老师。有一天,他组织 n 个小朋友玩游戏。游戏开始时,每个小朋友伸出两只手,没有手相互拉在一起。每次,小 P 等概率随机挑选两只空着的手,让这两只手拉在一起。小 P 一直重复这个操作,直到所有的手都拉在一起。小 P 在成为幼儿园老师之前是个数学专业的博士。因此,他想知道,当所有的手都拉在一起之后,小朋友们拉成的圈个数的期望是多少?其中,我们规定,一个小朋友左手拉右手的情况也形成一个圈。 由于小 P 忙着和小朋友们玩游戏,他找到了聪明的你,希望你能帮他解决这个问题。 输入格式 输入数据仅一行,包含一个正整数 $n$ ,表示小朋友的数量。 输出格式 输出文件仅一行,包含一个实数,表示当所有的手都拉在一起之后,小朋友们拉成的圈个数的期望是多少。输出和标准答案的绝对误差不能超过 $10^{-9}$。 数据规模与约定 对于 30% 的数据:$1 \le n \le 9$。 对于 50% 的数据:$1 \le n \le 10^3$。 对于 70% 的数据:$1 \le n \le 10^6$。 对于 100% 的数据:$1 \le n \le 10^{18}$。 输入输出样例说明 小 P […]

【NOI 2018】归程 / 题解

Posted on

题目背景 本题的故事发生在魔力之都,在这里我们将为你介绍一些必要的设定。 魔力之都可以抽象成一个 n 个节点、m 条边的无向连通图(节点的编号从 1 至 n)。 我们依次用 l, a 描述一条边的长度、海拔。 作为季风气候的代表城市,魔力之都时常有雨水相伴,因此道路积水总是不可避免的。由于整个城市的排水系统连通,因此有积水的边一定是海拔相对最低的一些边。 我们用水位线来描述降雨的程度,它的意义是:所有海拔不超过水位线的边都是有积水的。 题目描述 Yazid 是一名来自魔力之都的 OIer,刚参加完 ION2018 的他将踏上归程,回到他温暖的家。 Yazid 的家恰好在魔力之都的 1 号节点。对于接下来 Q 天,每一天 Yazid 都会告诉你他的出发点 v ,以及当天的水位线 p。 每一天,Yazid 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。Yazid 可以在任意节点下车,这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。 需要特殊说明的是,第二天车会被重置,这意味着: 车会在新的出发点被准备好。 Yazid 不能利用之前在某处停放的车。 Yazid 非常讨厌在雨天步行,因此他希望在完成回家这一目标的同时,最小化他步行经过的边的总长度。请你帮助 Yazid 进行计算。 输入和输出 从文件 return.in 中读入数据。 单个测试点中包含多组数据。输入的第一行为一个非负整数 T,表示数据的组数。 接下来依次描述每组数据,对于每组数据: 第一行 2 个非负整数 n, m,分别表示节点数、边数。 […]