哪里有html企业网站模板下载,域名备案查询网站备案信息,广州旅游攻略,wordpress 安装文件前言
期望#xff1a;100700170 实际#xff1a;400040 rnk14
分全部挂没了#xff0c;太行了。 T1不开longlong见祖宗#xff0c;而且KH说的那个也有道理#xff0c;带权之后树的重心可以不只有两个#xff0c;所以最后还应该倍增的跳。#xff08;然而这个地方题解似…前言
期望100700170 实际400040 rnk14
分全部挂没了太行了。 T1不开longlong见祖宗而且KH说的那个也有道理带权之后树的重心可以不只有两个所以最后还应该倍增的跳。然而这个地方题解似乎都忽略了 T2线性筛写挂身败名裂。 T3根本没摸本来还打算至少敲个暴力来着但被T2心态搞炸了。
题目解析
树的核心core
我、kH、pdf一边一个做法的一道题。 但是必须承认pdf的做法实现是最简单的。
我这个题的做法倒是出的很快差不多8:30就出思路了。 我的做法是找到当前加一的部分的重心新重心一定在旧重心和原来这个重心的路径上。 代码实现的很不好写拍调整到十点。
pdf思路答案的子树权值大小必然严格大于总权值一半那么在dfs序的线段树上按照点权二分找到权值中点对应的结点其必然在答案的子树内也就是说答案必然在该结点的返祖链上。 往上倍增的找即可。
随机填数random
写完T1看这题。 是我之前做过的一道CF的多测板。 按照CF的做法有70。 一方面给了我方便也某种程度上限制了我的思维罢。 但这题我也确实做不出来需要的那个技巧根本就不在我脑子的“寄存器”里估计很难访问到了。
一个重要结论 E(x)∑i1P(x≥i)E(x)\sum_{i1}P(x\ge i)E(x)i1∑P(x≥i) 较为显然之前也见到过但没有特别上心。 然而本题后面这个概率却能很方便的求出。 首先分母很好办就是 mi−1m^{i-1}mi−1。x≥ix\ge ix≥i 也就等价于 [1,i−1][1,i-1][1,i−1] 的序列的 gcd\gcdgcd 大于1只考虑 i1i1i1。那么我们考虑补集也就是 gcd1\gcd1gcd1 的序列有多少个 ∑a1...i−1[(a1,a2,...,ai−1)1]\sum_{a_{1...i-1}}[(a_1,a_2,...,a_{i-1})1]a1...i−1∑[(a1,a2,...,ai−1)1] ∑a1...i−1∑d∣(a1,a2,...,ai−1)μ(d)\sum_{a_{1...i-1}}\sum_{d|(a_1,a_2,...,a_{i-1})}\mu(d)a1...i−1∑d∣(a1,a2,...,ai−1)∑μ(d) ∑d1mμ(d)⌊md⌋i−1\sum_{d1}^m\mu(d)\lfloor\frac m d \rfloor^{i-1}d1∑mμ(d)⌊dm⌋i−1 那么我们其实就是求 ∑i2∞P(x≥i)1\sum_{i2}^{\infty}P(x\ge i)1i2∑∞P(x≥i)1 ∑i2∞mi−1−∑d1mμ(d)⌊md⌋i−1mi−11\sum_{i2}^{\infty}\frac{m^{i-1}-\sum_{d1}^m\mu(d)\lfloor\frac m d \rfloor^{i-1}}{m^{i-1}}1i2∑∞mi−1mi−1−∑d1mμ(d)⌊dm⌋i−11 ∑i1∞mi−∑d1mμ(d)⌊md⌋imi1\sum_{i1}^{\infty}\frac{m^i-\sum_{d1}^m\mu(d)\lfloor\frac m d \rfloor^{i}}{m^i}1i1∑∞mimi−∑d1mμ(d)⌊dm⌋i1 1−∑i1∞∑d2mμ(d)⌊md⌋imi1-\sum_{i1}^{\infty}\frac{\sum_{d2}^m\mu(d)\lfloor\frac m d \rfloor^{i}}{m^i}1−i1∑∞mi∑d2mμ(d)⌊dm⌋i 1−∑d1mμ(d)∑i1∞⌊md⌋imi1-\sum_{d1}^m\mu(d)\sum_{i1}^{\infty}\frac{\lfloor\frac m d \rfloor^{i}}{m^i}1−d1∑mμ(d)i1∑∞mi⌊dm⌋i 1−∑d1mμ(d)⌊md⌋m−⌊md⌋1-\sum_{d1}^m\mu(d)\frac{\lfloor\frac m d \rfloor}{m-\lfloor\frac m d \rfloor}1−d1∑mμ(d)m−⌊dm⌋⌊dm⌋ 预处理 μ\muμ 的前缀和整除分块即可做到单次 O(n)O(\sqrt n)O(n)。
等权划分value
由于本次考试上来就对T1有了思路调完T1又一直在T2挣扎所以这个题几乎没有摸。 因而谈不太上考场感受但是看题解感觉我应该是做不出来的。 三个关键点我的评价分别是很难想到很难想到很难想到。 毕竟做题可是且运算卡一个地方这题就没了。 由于字典序优秀的贪心性质我们可以每次都尽可能的尝试填A然后判断接下来的局面是否有解。 那么问题就转化为了对于一个局面如何快速判断有无解。 关键性质如果一个局面有解那么必然可以构造一种合法方案使得一个序列中的合法点都是完整原序列的前缀最大值其必然也所在序列的合法点以下简称必大点。 证明如果一个序列存在非必大点的合法点那么其前方第一个必大点必然在另一个序列里。那么若两个序列都存在非必大点的合法点令两个对应的必大点互换位置即可保证合法点数都减一的同时使非必大点个消失一个。不断如此操作至少有一个序列的合法点全是必大点。 个人感觉证明倒不是特别难但真的很难独立猜出这种鬼马结论并认为它有用…
我们强制令一个序列全是必大点注意这个序列即可以是A也可以是B下面假设其为B。若后边还有 ccc 个必大点A选的合法点中必大点和非必大点分别有 p,qp,qp,q 个A、B当前选的合法点有 fa,fbfa,fbfa,fb 个那么就有 fapqfbc−pfapqfbc-pfapqfbc−p 整理得 2pqfb−fac2pqfb-fac2pqfb−fac 其中右边的东西对于某个确定局面为定值设其为 www。令A序列选取必大点为合法点的价值为2非必大点的价值是1那么就要求存在一种选点方案使得总权值为 www。 结论对于一个残局一个子序列S可以成为A的合法点序列的充要条件是其递增。并且可以使B序列只选取该子序列外的必大点作为合法点。 这个pdf没有细讲但我觉得还是需要讲一下的 证明前缀最大值必然递增必要性显然。充分性尝试构造性证明对于一个递增子序列S从前往后考虑每个元素划分到哪里。对于一个属于S的元素直接给A否则若是必大点直接给B否则其前面必然存在比它大的元素x把当前元素划分到x所在的序列即可。
又注意到由于元素只有1或2那么如果权值x是合法的那么x-2必然也是合法的。所以我们只需要对奇权值和偶权值分别从后往前做一遍带权LIS并互相转移每次在 www 奇偶性对应的线段树上查询是否不小于 www 即可。
