1857d cf
CF237D T-decomposition
原题链接 链式前向星,他来了 通过观察发现,每个集合的大小最小为 \(2\),显然我们需要构造一种方案使得每一个集合的大小都为 \(2\),这样是最优的。 每个集合大小为 \(2\),等价于把每条边转换成新树上的一个点,一共 \(n-1\) 边,对应 \(n-1\) 个集合,每个集合的点对在 dfs ......
CF1872G Replace With Product 题解
原题 翻译 初看此题,显然感觉有点不对劲,因为感觉如果 \(a_i\) 很大的话肯定是选越多越优秀,但之后并没有什么思路,反而想到线段树上去了(值域这么大做 nm 线段树) 发现如果 \(\prod a_i > 2 \times 10^{14}\) ,那就把做右端点收敛到都不是 \(0\) 的最远位 ......
CF1204D2 Kirk and a Binary String (hard version) 题解
CF1204D2 Kirk and a Binary String (hard version) 题解 分析 先来分析 \(01\) 串的最长不下降子序列。全是 \(0\) 显然是不下降的,如果中间出现一个 \(1\),为了维护不下降的性质,后面就只能全是 \(1\)。一句话概括一下,\(0\) 后 ......
CF785D Anton and School - 2 题解
CF785D Anton and School - 2 题解 分析 很明显有一种 \(\mathcal O(n^2)\) 的做法,遍历每一个 (,再枚举 \(k\),左边不包含这一位选 \(k-1\) 个 (,右边选 \(k\) 个 ),求组和即可。 但是数据范围是 \(n \le 2\times ......
CF & AT 做题记录
选一些 \(\text{div 1}\) 中的好题总结一下 \(\textrm{qwq}\) 从现在开始像 \(\color{red}\text{r} \color{black}\text{ainboy}\) 一样打比赛 \(\textrm{qaq}\) $$\textrm{Codeforces R ......
CF1303D Fill The Bag
贪心,二进制 很容易想到:把 \(n\) 转化为二进制,考虑如何得到每一位。 很显然,用小的数去“凑出”大的数不花费代价,用大的数“分解”出小的数要花费代价。所以。一个简单的贪心是:设当前要得到 \(n\) 的第 \(i\) 位的数 \(2^i\),尽量用小的数凑,若小的数凑不出,再用大的数分出 \ ......
CF1816B
Grid Reconstruction 题面翻译 题目描述 在一个 \(2×n\) 的网格中 (\(n\) 为偶数),标记 \(1,2,\ldots,2n\),但每个数只能被使用 \(1\) 次。 某条路径是从 \((1,1)\) 开始的单元序列,随后不断地向下走或向右走,直到到达 \((2,n)\ ......
CF1816A
Ian Visits Mary 题面翻译 题目描述 \(\textrm{lan}\) 和 \(\textrm{Mary}\) 是生活在笛卡尔坐标系格点上的青蛙,\(\textrm{lan}\) 在 \((0,0)\),而 \(\textrm{Mary}\) 在 \((a,b)\)。 \(\textr ......
CF1815A
Ian and Array Sorting 题面翻译 题目描述 为了感谢 \(\textrm{lan}\),\(\textrm{Mary}\) 赠送了 \(\textrm{lan}\) 一个长度为 \(n\) 的序列。为了让他自己看起来聪明,他想要让序列按非递减排序。他可以执行以下操作若干次: 选择 ......
CF1817A Almost Increasing Subsequence
CF1817A 题面翻译 给定长度为 \(n\) 一个序列 \(a\) 以及 \(q\) 次询问,每次询问给出 \(l\) 和 \(r\),找出序列 \(a\) 在 \([l,r]\) 内最长的几乎递增子序列。 对于几乎递增的定义:如果一个序列中不存在连续的三个数 \(x\),\(y\),\(z\) ......
CF1874F Jellyfish and OEIS【容斥,DP】
给定序列 \(m_i\),求有多少排列 \(p\) 满足:对于满足 \(l \le r \le m_l\) 的所有 \((l,r)\),\(p_{l \sim r}\) 都不是 \(l \sim r\) 的排列。答案对 \(10^9 + 7\) 取模。 \(n \le 200\),时限 \(\tex ......
题解:CF118E
Tarjan 思路 先来看一下题目给出的无解的这个样例。 不难发现,导致无解的两条边就是 \(6 - 7\) 和 \(2 - 4\) 这两个桥。所以这个题就转换成了求桥,如果存在桥就是无解。 代码 #include<bits/stdc++.h> using namespace std; const ......
CF1416E Split
暴力 dp 是很拉跨的,我们会设 \(dp_{i,j}\) 表示前 \(i\) 个 \(a_i\) 分裂后,最后一个 \(b\) 为 \(j\) 时的最小答案,爆炸。 但这里面有很多性质啊,直观地我们可以感受到,若已经确定了决策 \(dp_{i-1,k}\),那么无论如何选择 \(a_i\) 的分裂 ......
CF1523F Favorite Game
当前的状态有:传送门的激活状态,已经完成的任务数量,当前的位置(传送门/任务),经过的时间。显然我们会先将所有任务按照 \(t_i\) 升序排序。把前三维列为状态,后一维列为答案,此时我们可以得到一个状态数为 \(O(2^nm^2)\),转移为 \(O(m)\) 的 dp。 状态数很没救,显然要被优 ......
CF1149D Abandoning Roads
首先 \(a\) 边可以随便选。 显然,若某条 \(b\) 边的两端位于同一 \(a\) 连通块,一定不会被我们考虑。剩下的 \(b\) 边一定会将两个 \(a\) 连通块相连。 那么此时我们对于 \(b\) 边的约束是,位于一个环上的 \(b\) 边不能同时存在图中,即,我们的路径不能从当前连通块 ......
CF713E Sonya Partymaker
其实做题可以先算法导向一下的。 比如看到显著特征:【最大值最小】,我们第一反应还是应该为二分答案转判定的。 考虑二分答案 \(d\),此时转化为了,对于每个人 \(i\),选择一个朝向左/右,向该朝向覆盖 \(d\) 的距离,能否将整个环全部覆盖。 如果不是环的话,很 lantern 啊!考虑序列情 ......
CF1877E Autosynthesis
总结题目约束其实就是,所选数下标组成的集合和未选数值组成的集合相同。 我们发现该约束把值和下标联系在了一起,所以我们不妨考虑建出图来显式地表示二者,即,我们由 \(i\) 向 \(a_i\) 连边,然后考虑整张图。 首先这肯定是个内向基环树森林,然后我们要对其黑白染色,设黑色表示选择,白色表示未选择 ......
CF1877F Lexichromatography
题中的约束可以描述为: 红的字典序比蓝大。 对于每个数值,必然是红蓝交替涂色。 设总共出现了 \(c\) 个颜色,总涂色方案数就是 \(2^c\) 种,其中字典序情况包含 大于,小于,相等,且前两者方案数相同。所以不妨选取更简单的部分 相等 进行处理,设相等的方案数为 \(x\),则答案就为 \(\ ......
CF1439D INOI Final Contests
先总结一些充要条件。 一个人 \(i\) 选不到自己的 \(a_i\) 的充要条件为:若为左侧,则存在左侧的一个 \(j\) 满足 \(a_k\in[j,i]\) 且 \(b_k=R\) 的 \(k\) 的个数 \(> i-j\),右侧同理,满足其一即可。 一个方案不合法的充要条件为,若对于一个 \ ......
CF786C Till I Collapse
题外话 根分纸张第一次自己做出根分虽然很水,纪念一下。 \(\text{Links}\) Codeforces Luogu 题意 给定一个长度为 \(n\) \((1\le n\le 10^5)\) 的序列 \(a\) \((1\le a_i\le n)\),对于 \(k=1,2,3,\dots,n ......
CF1886C Decreasing String 题解
题面 \(S_n\) 由 \(S_{n-1}\) 去掉一个字母得到,\(S=S_1+S_2+...+S_n\) 给定 \(S_1\) 求 \(S\) 的第 \(N\) 位 solution 我们先考虑怎样去字母能保持字典序最小 显然,我们发现如果一个字母比前面那个字母小,那么我们就要删除前面那个字母 ......
CF1886A Sum of Three 题解
Question 给定一个正整数 N ,我们需要找三个不同的整数x,y,z,使得 N = x+y+z,其中下x,y,z不能被三整除 solution 我们把N%3会有一些余数,我们针对余数来讨论,其中我们只关注xyz的余数 如果余数为0 那么也就可能是1+1+1,或者2+2+2,但是考虑到xyz不同 ......
CF1886D Monocarp and the Set
Questions Monocarp 有 \(n\) 个整数和一个集合,他需要把这 \(n\) 个数添加到集合中,每次添加一次 除了第一次,每次添加元素都会输出一个字符 如果当前添加的元素比原有的元素都要小,那么输出 \(>\) 如果当前添加的元素比原有的元素都要大,那么输出 \(<\) 否则输出 ......
CF1886B Fear of the Dark 题解
Question Monocarp 在一个二维平面上,他的初始点在 \(O=(0,0)\) ,他需要到 \(P(P_x,P_y)\) 不幸的是,他能走的范围在两个圆内,我们给出了两个圆的坐标 \(A=(A_x,A_y)\) ,\(B=(B_x,B_y)\) 两个圆的半径相同,我们需要找到最小的半径让 ......
CF1886E I Wanna be the Team Leader
贪心 #动态规划 Question Monocarp 是一家大型 IT 公司的负责人 他有 \(m\) 个项目个项目需要完成,第 \(i\) 个项目的难度为 \(b_i\) 他的团队离有 \(n\) 个程序员,第 \(j\) 个程序员的耐受能力为 \(a_j\) Monocarp 需要分配这些项目, ......
Almost Sorted (CF F ) (压状dp)
思路: 性质1, 相当于重新对这个序列排序 性质2, 等式关于 值域, 对于任意一个都满足, 那么就是 当前点 比前面放入的点 的最大值 - k 都要大, 比后面最小值+k都要小, --> 每一个点都要满足, 那么对于当前点的放置是有限制的,以 值域 来看 1-i 里面都已经放置了, 那么放置 后面 ......
CF1881F Minimum Maximum Distance
给定一棵树,树上的一些点被打上了标记,定义一个节点的贡献为其到所有标记节点距离的最大值,求最小贡献。 \(n \le 2 \times 10^5\)。 这道题的原题是 CF337D(甚至要更困难一些)。 很套路的换根 DP 啊。我们考虑设 \(f_i\) 为 \(i\) 子树内的标记节点到 \(i\ ......
CF1881D Divide and Equalize
solution \(a_i\) 和 \(a_j\) 在操作前后的乘积是不变的,也就是总乘积是固定的。最后要求所有的元素相同,那也就是说所有元素的乘积 \(total\) 一定满足 \(\sqrt[n]{total}\) 是整数。看了看数据范围没有办法直接乘起来,于是考虑分解质因数,最后看一下每个质 ......
CF963B Destruction of a Tree 题解
CF963B Destruction of a Tree 题解 洛谷题目链接 这里提供一个较为朴素的 DP 想法。 题意简述 给定一棵树,节点个数不超过 \(2 \times 10^5\),每次可以删掉度数为偶数的点。问最后能不能删完;能删完给出删除方案。 思路分析 首先可以随便选一个点作为根。 其 ......