抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

CF888G Xor-MST

题意 给定 n 个点的完全图,边 (i,j) 的边权定义为 a_i\oplus a_j ,求最小生成树。 即最小异或生成树模板 题解 考虑 Boruvka 算法,每次合并两个连通块,这样合并次数就是 O(\log n) 级别的。由于要...
OIsolcf

Codeforces Round 707 Div.2 based on moscow open olympiad in informatics

这场好毒瘤啊。。。A 和 B 题面长,C 开始不会做。。。 1501A - Alexey and Train 题意 这题很多人读题存在障碍... 某人从起点站(姑且可以认为其编号为 0 )坐火车在时刻 0 出发,沿线依次经过 n 个编号从 1 到 n 的火车站。列车的时刻表用 n 个数对...
OIsolcf

Codeforces Round 706 div.2

1496A - Split it! 题意 给定 S 和 k ,要求把 S 拆分为 a_1 + a_2 + \cdots + a_k + a_{k + 1} + R(a_k) + R(a_{k - 1}) + \cdots + R(a_i) ...
OIsolcf

CF1493D GCD of an Array

题意 给定 n 个数 a_{1\cdots n} ,进行 q 次单点乘法操作,满足 1\le n,q,a_i\le 2\times 10^5 ,求每次操作完后 \displaystyle\gcd_{i = 1}^na_i\...
OIsolcf

Codeforces Round 702 div.3

CF1490A Dense Array 题意 定义一个数组为“稠密的”当且仅当 \forall i < n,\frac{\max(a_i, a_{i+1})}{\min(a_i, a_{i+1})} \le 2 ...
OIsolcf

CF1000E We Need More Bosses

题意 给定一个 n 点 m 边的无向图,找到 s 和 t 使得从 s 到 t 的路径上必须经过的边数最多。求这个最多边数。 思路 必须经过的边即指割边。因此可以考虑把每个边双连通分量缩成一个点,不难发现其生成的必然是一棵树(不能有环,有环了就还有边双)。树上的各个边都是割边,而我们要寻...
OIsolcf

CF911F Tree Destruction

题意 给定一棵无根树,每次操作选两个叶子,把两者的距离加入贡献然后删掉其中一个,求最大贡献及对应方案 思路 不难发现离一个叶子节点最远的点必然是直径的一个端点,不妨删除这个叶子节点,这样既可以使破坏该节点产生的贡献最大又可以不用破坏直径。 先找出直径,然后删叶子,最后挨个删直径即可 1234567891011121314151617181920212223242526272829303132...
OIsolcf

CF734E Anton and Tree

题意 给定一棵 n 个节点的树,每个节点黑或白,每次可以使同种颜色的连通块变色,求使树变为同种颜色的最少操作次数。 思路 首先考虑将相邻连通块缩为一点(简单,一遍 dfs 解决),然后设新树直径为 d ,答案为 \displaystyle\left\lfloor\frac{d + 1}2\right\rfloor ...
OIsolcf

解题报告 CF607B Zuma

题目内容 CF607B 大意:给定一串序列,每次操作可以消除其中的一个回文串并将两侧拼一起,求消除所有元素所需的最小操作次数 解题思路 区间 dp 令 f_{i,j} 表示区间 [i,j] 需要的最小消除次数,接下来考虑转移: 显然,有 \begin{cases} f_{i,i}=1\quad\ f_{i,i...
OIsolcf



Blog content follows the [Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en)
本站总访问量为 访客数为
Use Volantis as theme