序幕
\(\text{6:50}\):到校,早上稍微墨迹了一小会。
一直不会的某个结论差不多会证明了,先写一下题再写写题解。
\(\color{blueviolet}{CF1495D}\)
此题是好题。
考虑对于 \(x\) 和 \(y\) 共同的生成树一定包含两者的最短路径。
先假设 \(x, y\) 最短路径有且只有一条,考虑其上一点 \(z\),\(x, y\) 两者中一者到其最短路径依然有且只有一条,为了满足 \(dis(x, z), dis(y, z)\) 不变,必须保留此最短路。
当 \(x, y\) 最短路径不止一条时,对于这两条路径上的点依然需要满足上述 \(z\) 的条件,因此多条最短路都需要保留,此时一定会成环,无法保持树的形态,也就一定无解。
现在对于 \(x, y\) 两点已有一条唯一的链链接,考虑其他点如何挂在树上。对于一个点 \(u\) 有边 \((u, v)\),若保留此边(使得 \(v\) 为 \(u\) 的父节点)必须满足 \(dis(x, v) + 1 = dis(x, u) \land dis(y, v) + 1 = dis(y, u)\)。所以我们对于一个点找出其合法父节点个数,对所有的点乘法原理计数即可。
间幕 \(1\)
找了到 2700 的瞅了瞅,感觉做不出来就直接看题解了,莫队倒是想到了点,就是没想到能卡过去。
这个神秘的单 \(\log\) 算法是真想不出来。
刷了会手机,\(\text{8:20}\) 接着做题。
\(\color{blueviolet}{CF1511G}\)
此题是神仙题。
首先转化问题,对于一个询问只要判断 \(\bigoplus \limits _{l \le c_i \le r} c_i - l\) 是否等于 \(0\) 即可。
设 \(f_{i, j}\) 表示 \(\bigoplus \limits _{i \le c_i \le i + 2 ^ j - 1} c_i - i\),考虑如何倍增转移。
\(f_{i, j}\) 由 \(f_{i, j - 1}\) 与 \(f_{i + 2 ^ {j - 1} - 1, j - 1}\) 两部分组成,前者的异或和可以直接转移过来,后者包括的元素每个会与需要的值相差 \(2 ^ {j - 1}\),所以需要额外异或上后者元素个数个 \(2 ^ {j - 1}\),只需要通前缀和维护一下区间元素个数即可。
\[f_{i, j} = f_{i, j - 1} \oplus f_{i + 2 ^ {j - 1} - 1, j - 1} \oplus \left([(g_{i + 2 ^ j - 1} - g_{i + 2 ^ {j - 1} - 1}) \mod 2 = 1] \times 2 ^ {j - 1} \right) \]求答案也是类似的,倍增逼近即可。
\(\color{blueviolet}{CF1510B}\)
此题是坏题,它让你输出方案。
首先考虑转化问题,进行简单图论建模,每个状态向可以达到的状态连边,于是得到一张 DAG。
首先考虑最劣情况,对于每一个点单独成为一条路径进行覆盖,贡献是其二进制下 \(1\) 的个数。每一个点可以选择一个出边把自己贡献抵消掉,这个就类似二分图最大匹配,费用流即可。
间幕 \(1\)
午休,中午还吃鱼丸饭,西红柿炒蛋真的太好吃啦!
下两把棋,打会块,然后小睡一会。
两点多苏醒接着做题。
\(\color{blueviolet}{CF1539F}\)
此题是坏题,第一遍打假了。
我们只考虑 \(a_i\) 大于中位数的情况,另一情况可以通过取负反转数组取到相同情况,式子只有一个加减 \(1\) 不同。
区间固定时贡献是 \(\frac{t_l + t_m + t_r}{2} - t_r = \left \lfloor \frac{t_l + t_m - t_r}{2} \right \rfloor\)。
其中 \(t_l, t_m, t_r\) 分别表示小于、等于、大于 \(a_i\) 的 数字个数。
然后运用到一个套路,对于这种中位数的东西离线并从小到大遍历数字,比自己小的设为 \(-1\),比自己大的设为 \(1\),求一下以 \(i\) 结尾的后缀最大、以其开头的前缀最大,求和即可。
间幕 \(2\)
和 iazm 出去逛逛,在操场上瞎聊天,溜达了半小时,回来吃饭,一直墨迹到 \(19:00\),写题写题。
发现任务里的 2600 快写完了,只剩 2700,悲伤的。(虽然我没觉得两者差距很多,反正大部分我都不会做。)
\(\color{blueviolet}{CF1469F}\)
首先注意到先挂长链更优,并且将中点挂在树上是更优的,可以使得整体深度更小。
设 \(fa\) 为链挂在上面的点,则会使得深度为 \(dep_{fa}\) 的点减少一个,并增加连续深度的两段点数,用线段树维护即可,注意分讨奇偶即可,以及注意空间。
尾声
看了一道 2700,就下班了。
回家打会游戏后直接昏迷。
标签:27,Log,color,2023.10,le,即可,此题,blueviolet,dis From: https://www.cnblogs.com/Eon-Sky/p/17790957.html