CF 1900 - 2100 分乱刷

Larry76 · 2023-09-19 00:14:11 · 题解

RT，有一说一的是，想干这件事情和 LgxTpre 中的刷题计划很有关系，说白了，也想跟着一块玩/se。

CF1851G Vlad and the Mountains

题目第一遍没读懂捏，感觉语文要重修了。

首先，题目有一个很重要的条件，就是 h_i \in [1, 10^9]，这使得我们可以将原问题转化为：

是否存在一条 S 到 T 的路线，使得路线上的所有点都小于等于 h_s + e。

然后就好办了，考虑离线，对边排序，然后对于某个询问，我们让两端点小于等于 h_s + e 的边全部加入并查集中，然后判断连通性，如果不能联通则为 NO，否则为 YES。

由于我们对边和询问都排序了，所以只会加边，不会删边，然后做完了，复杂度 O(n \log n)。

实现上还是有点小细节，不过无伤大雅。

CF1857G Counting Graphs

啧，咋最近老读不清楚题面/fn

有一个很强的限制，就是他要求最小生成树为给定树且唯一。

考虑 Kruskal 过程，发现如果有边权相同的情况则必定生成树不唯一，具体证明考虑「P4208 [JSOI2008] 最小生成树计数」这个题。

然后有要求没有重边，所以考虑在 K_n 上的非树边上计数，考虑线性加边，并查集维护连通块，然后你你会发现联通内部加边不影响外部，且加的值域范围不一样，所以你需要拆贡献，考虑让连通块看成是拥有连通块内部选边方案数状态的一个小球，则答案就变成了乘法原理，现在考虑怎么算连通块内部的方案数，如果你要是想到的是下式：

(S - w_{max})\sum_{i = 1} ^ {n} \dbinom{n}{i} + 1

那你和我一样就死了（调了 1 h 20 mins），正确应该是下式：

\sum_{i = 0}^{n} (S - w_{max})^i\dbinom{n}{i}

显然这是一个二项式定理，设 a = 1, b = (S - w_{max})，则原式等于：

\sum_{i = 0}^{n} (S - w_{max})^i\dbinom{n}{i} = (1 + S - w_{max})^n

时间复杂度 O(n (\log n + \alpha (n)))。

CF1854A2 Dual (Hard Version)

快难为死我了，真的就构造啥也不会呗/dk.

看完 A1 题解后会的，但是调了半天，不是这挂挂，就是那挂挂/zk

考虑我们可以通过对全是正数做前缀和，对全是负数做后缀和，此时消耗了 19 次，现在我们需要用 12 步将序列变为「全部非负」或「全部非正」。

我们尝试用绝对值最大值来进行填平，然后显然这是错的。

考虑一下如果不用这个方法，而是用另一个符号的最大值来进行填平，则构造尝试极限情况（例如 13 个 -1 和 7 个 20），然后考虑如果用 -1 填的话需要翻至多 5 次，所以当我们有 7 个 20 这样的数的时候通过这种方式填平。

然后很巧的是，两方个数一减一加正好又是另一种极限情况。

时间复杂度 O(Tn)。

CF1847D Professor Higashikata

MD 傻波傻波傻波傻波傻波，读错题了读错题了读错题了读错题了读错题了！！！

考虑重合部分不会影响拿取 1 的优先级，所以我们直接映射成一个区间，然后维护一个树状数组，来统计有效范围内 1 的个数，最后一减就行了。

现在复杂度瓶颈在统计有效范围上，考虑使用并查集维护右端点，这样统计过得连续段处于同一个颜色，我们跳转的时候就可以直接 find() + 1。

千万别按秩合并！！

时间复杂度 O(n (\log n + \alpha(n)))。

CF1846G Rudolf and CodeVid-23

一个经典的题型，但是我给忘了（芙兰达）

状压成十进制，然后现在我们就可以将每种状态当成节点，然后药物 i 就相当于是一条边权为 d_i 的边。

然后跑 S 到 0 的最短路就好了。

这里需要注意几个问题，就是为了减少重边，我们可以不用链式前向星，而转成用邻接矩阵，这样我们可以加边的过程中去掉重边，不过具体重边的影响多大没试过。

时间复杂度 O(n^2 \log n)。

CF1841D Pairs of Segments

差点被干碎。

我们不妨现将题目要求我们的条件拆一下，换句话说，我们可以选择先满足「两者有交」这条件，再满足「与他者无交」这一条件。这样就好办了，我们不难想到可以将两个有交的线段拍成一个线段，现在我们就可以将问题转化为「最大不相交区间数量」。

时间复杂度 O(n^2 \log n)。

CF1834D Survey in Class

被干碎了。

首先明确题意，题目想让我们求的是所有线段中最大的不交长度。

先假设所有线段都互相包含，这样的话我们将长度最长的那个减去长度最小的那个就是答案。

但是实际上不是相互包含的关系，但是这么算出的答案一定小于正确答案，所以没关系，后面遇到正确答案就好。

现在我们考虑不包含的情况，考虑我们想让答案变大，那肯定是与其相交的区间的左端点越右越大，右端点越左越大。

这样就好办了，我们直接虚拟出来一个线段，左端点 l_{max} 为所有线段最大值（靠左），右端点 r_{min} 为所有线段最小值（靠右），不难发现这个东西有可能是个倒着的线段，不过不要紧，我们统计的时候同时考虑两边即可，此时一个线段的贡献就是：

\min \{ len_i, \max\{ l_{max} - l, r - r_{min}\} \}

然后统计答案即可，最后别忘了 \times 2。

时间复杂度 O(n)。

CF1830B The BOSS Can Count Pairs

破防了破防了破防了破防了破防了破防了破防了。

首先，仔细阅读题面，我们发现我们的 a_i \cdot a_j 最大只能是 2n。

然后，我们显然存在不等式 \min(a_i, a_j) \le \sqrt {a_i \cdot a_j}，这样就好办了，我们可以选择枚举较小的那个数 k，然后再在序列中寻找那个数。

此时进行分类讨论，因为有可能存在 k^2 = a_i^2 的情况，考虑分两类：

k = a_i
k \not = a_i

第一种情况我们实时维护针对 b 数组的桶，并统计答案。

第二种情况我们直接统计即可。

注意：算贡献的时候别忘了判断一下计算出来的边界，否则小心越界。

时间复杂度 O(n \sqrt n)。

CF1823D Unique Palindromes

打球前看出来了一半，打完球又看出来了另一半。

说明运动还是有益于思维的。

性质一：第一次出现的字符算回文串。

性质二：周期为 n(n \ge 3) 的周期串只有 n 个回文串。

性质三：k \lt |\Sigma|。

性质四：无解只存在两种情况，一个是长度变化量无法赶上需求变化量，一个是需求量大于长度。

然后做完了，贪心的搞就行了。

（PS：性质四是玩出来的，证明了在构造题中手玩的重要性。）

CF1808D Petya, Petya, Petr, and Palindromes

感觉不如 1900 的贪心和构造，根本不会贪心和构造。

开个值域桶，然后同个值再分位置上的奇偶。

然后你稍微想一想就能发现对于一个位置，只会对前面的 \lfloor \dfrac{k}{2} \rfloor 个元素可能有贡献，但是具体是怎样的呢，需要你手玩一下。

然后首先你会发现 \lfloor \dfrac{k}{2} \rfloor 这一部分的贡献可能需要单独算，因为他们的贡献不完整。

然后你又会发现，当 k 为奇数的时候，因为回文中心上有值，所以还是一个间隔的贡献，然后贡献位置要么全为奇数，要么全为偶数（这也是为什么同个值上还要奇偶）。

然后偶数最好了，偶数是一段连续的。

这样我们就牛逼了，因为我们知道我们贡献区间的上下界，那我们直接在桶里面二分上下界，看看有多少个元素就行了。

然后对每个位置做一遍，这样时间复杂度 O(n \log n)，轻松秒杀。

什么？你问为啥没有我的提交记录？拜托这么难写的代码根本不想写！

~~（要是所有 2100 都这么无脑就好了）~~

CF1696D Permutation Graph

拥抱分治，远离贪心。

考虑无论如何都会经过最大最小值。

所以我们找到当前的最大最小值的位置，然后向下分治。

可以用 ST 表维护区间最大最小值。

时空复杂度 O(n \log n)。

CF1696E Placing Jinas

6。

考虑我们画一下加一的转移方向，然后顺时针旋转 45^{\circ}，不难发现这是个杨辉三角。

然后推一推每一行的式子，不难发现：

\sum_{i = 0}^{n} \sum_{j = 0}^{a_i - 1} \dbinom{i + j}{j}

然后这个东西运用一下平行求和法，得：

\sum_{i = 0}^{n} \dbinom{i + a_i}{a_i - 1}

然后这个东西不出意外的话已经优化到头了，时间复杂度 O(n)。

（推傻波式子就是爽啊）