【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 的专,感触还是很大。如果在联赛前,我选择听的都是 […]

【正睿 OI】国庆集训趣题分享

Posted on

这几天在蔡老板的带领下学习到了很多有趣(shui)的题,挑几道印象深刻的分享一下。 自闭的游戏 题目描述 小 A 和小 B 在玩一个游戏,游戏一开始有 n 张卡牌,第 i 张卡牌上面的值为 a[i],且有一个关键数字 M。 两个玩家轮流操作,小 A 先手。每轮每个玩家可以移除任意一张卡牌,假设卡牌上的数字为 x ,则关键数字 M 会变成 $⌊\dfrac M x⌋$ 如果某位玩家操作后,关键数字变成 0 了,那么游戏结束,最后操作的玩家输。 小 B 玩了几天后输得有点自闭,所以他想问你,对于给定的 n 张牌 a[1..n],有多少 $x∈[L,R]$,满足关键数字为 x 时后手必胜。 保证 $∏_{i=1}^{n}a[i]>R$,这样永远都不会出现没有牌了但是游戏还未结束的情况。 数据范围 对于 100% 的数据,有 $1≤n≤10$,$1≤a[i]≤1000$,$1≤L≤R≤10^{18}$,$\prod\limits_{i=1}^{n}a[i]>R$ 思路 首先我们不要管 $L,R$ 的范围,思考一下对于一个确定的 M 如何快速求得答案。。。然后会发现无法快速求得答案。。。 这个时候观察发现 $n$ 不管什么时候都很小,考虑一下是不是可以暴搜判断胜负。 枚举两个人在某个时刻选择了哪张牌,发现最后的胜负是取决于选出来的牌的数字之积(废话)。由于 M 是被整除,所以对于一个数字之积,对应的一段连续 […]

【正睿 OI】嘤嘤嘤嘤 / 题解

Posted on

不要问我为什么标题这么毒瘤 题目描述 你有一棵 $n$ 个点的树( $n \leq 5000$),树上第 $i$ 个点有权值 $a_i$。选取 k 条互不相交的链,其上所有点权值和为 $s$,最大化 $\dfrac{s}{k+1}$。 现在出题人觉得这样太简单了,于是给了你一个区间$[0,T]$ 和一个模数 $m$。你现在可以在区间内选择一个整数 $x$,令 $a_i=(a_i+x) \ mod \ m$。 求最大的可能答案。 思路 我们先不考虑修改点的权值,那这道题就是分数规划。二分最后的答案 $ans$,那么选择一条新链的代价是 $ans$,树形dp 即可,时间复杂度 $O(nlogn)$。 现在我们考虑修改权值的操作。最暴力的修改是对于每一个合法的 $x$ 都计算一遍答案。由于 $T$ 很大,所以爆炸。 发现对于每一个 $a_i$,都有一个可能的最优 $x_i$ 使得修改权值后 $a_i$ 达到最大的可能值 $m-1$。预处理出最优 $x$ 序列,长度为 $n$。这样就是 $O(n^2logn)$ 了。 最后我们发现,对于 $x_i$,先验证当前最大的答案 $ans_i$ 在此时是否可行,如果不行就跳过。这样我们相当于从 $x_i$ 序列中提出了一个子序列进行二分。我们可以 $random […]

【计蒜客 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 […]