1034
题解 CF1034C【Region Separation】/ SS221116D【Xiong AK 10 IOI】
很妙的性质题!全是意识流证明见过吗? problem 每次选一个非空边集删掉,谓之曰砍树。砍树后需要满足每个连通块的点权和相同。 在一个方案中可以砍很多次树,都要满足砍树后的要求。一共有多少种合法方案呢? \(n\leq 10^6,1\leq a_i\leq 10^9\)。 solution 假如我 ......
CF1034E Little C Loves 3 III
太神仙了。 直接子集卷积肯定是不行的,1s 的时限和 62MB 的空间摆在那里。 那就要考虑使用模 $4$ 的性质乱搞了。 我们考虑给每个 $i$,不管它符不符合条件,赋一个权值。如果 $i\ \text{and}\ j\neq 0$,它对答案是没有贡献的,否则它能贡献到 $i\ \text{or} ......
CF1034D 题解
## CF1034D 总评:非常牛逼的 $3500$。 求第 $k$ 大的价值可以二分一个 $m$,变成求价值 $\ge m$ 的区间**个数**,设其为 $C(m)$。求出第 $k$ 大价值 $M$ 后,本题求前 $k$ 大的价值和,这便要求我们求价值 $\ge m$ 的区间**价值和** ......
CF1034D Intervals of Intervals
简要题意 给定 $n$ 个区间组成的序列,定义它的一个连续段的价值为这个段内所有区间的并覆盖的长度。求价值前 $k$ 大的段的价值和。 数据范围:$1\le n\le 3\times 10^5, 1\le k\le \min{\frac{n(n-1)}{2}, 10^9}$。 题解 考虑一个经典问题 ......
CF1034D Intervals of Intervals 题解
传送门 CF1034D Intervals of Intervals 题目大意 有 $n$ 个线段,第 $i$ 个是 $[a_i,b_i]$。 定义区间 $[l,r]$ 的价值是第 $l$ 个线段到第 $r$ 个线段的并的长度。 找出 $k$ 个不同的区间,使得总价值最大。输出最大总价值。 $1 \ ......