divisor 1864c chain cf
CF1681D Required Length 题解
题意: 思路: $ BFS $ : 对于每一个数 $ x $ ,枚举其数位 $ num \space (0 \le num \le 9) $ ,将 $ x $ 与 $ num $ 的乘积 $ y $ 放入队列。重复该过程,直至 $ y $ 的位数与 $ n $ 相同。 剪枝: $ 1 $ . 对于重 ......
CF1695C Zero Path 题解
题意: 思路: 设 $ minv $ 表示路径最小权值和, $ maxv $ 表示路径最大权值和。 当且仅当路径长度 $ n + m - 2 \equiv 0 \space (mod \space 2) $ 且 $ minv \le 0 \le maxv $ 时,一定有权值和为 $ 0 $ 的路径; ......
CF1163B2 Cat Party (Hard Edition) 题解
题意: 思路: 对于满足条件的区间 $ [1,x] $ ,有如下三种情况: $ 1 $ . 所有元素出现次数都为 $ 1 $ ; $ 2 $ . 除了一个元素出现次数为 $ 1 $ 之外,其余元素出现次数都相等; $ 3 $ . 除了一个出现次数比其他数的出现次数多 $ 1 $ 的元素之外,其余元素 ......
CF1198B Welfare State 题解
题意: 有一个长度为 $ n $ 的序列 $ a $ ,给定 $ q $ 次操作,每次操作为以下两种之一: $ 1 $ . $ 1 $ $ p $ $ x $: $ a_p = x $ $ 2 $ . $ 2 $ $ x $: $ a_i $ $ = $ $ max $$($$ a_i $ ,$ x ......
CF1442D Sum 题解
题目链接 点击打开链接 题目解法 \(n^3\) 的 \(dp\) 是显然的 但我们没用到 \(a\) 不降的性质 考虑一个很妙的结论:最优选法中,至多只有一个序列取了且未取满 为什么? 如果最优情况下,存在选且未选满的序列为 \(a,b\),第一个未选的元素为 \(x,y\) 如果 \(a_x>a ......
CF613D Kingdom and its Cities
题意 给定一棵树,每次询问给出 \(k\) 个点。 问最少删除多少个 节点 (不能删这 \(k\) 个点) 使得这 \(k\) 个点两两不连通。 Sol 无解的情况是 \(trivial\) 的。 判断是否有相邻的两个关键点就行了。 但是 \(dp\) 是不太 \(trivial\) 的。 设 \( ......
CF1692G 2^Sort 题解
题意: 思路: 必要性: 对于任意一个符合条件的区间[l,r],任意相邻两项,满足a_i < 2 * a_{i + 1}(l \le i \le r - 1)。 充分性: 对于任意一个长度为k + 1的区间[l,r],如果任意相邻两项满足a_i < 2 * a_{i + 1}(l \le i \le ......
CF1901 C Add, Divide and Floor 题解
Link CF1901 C Add, Divide and Floor Question 给定一个长度为 \(n\) 的序列,每次操作你需要选择一个整数 \(x\) ,并将所有 \(a_i\) 替换为 \(\lfloor \frac{a_i+x}{2} \rfloor\) 。求至少多少次操作后能将所 ......
CF1902 D Robot Queries 题解
Link CF1902 D Robot Queries Question Robot 初始在 \((0,0)\) ,有一个字符串 \(s\) ,表示运行列表 \(U\):y+1 \(D\):y -1 \(L\) :x -1 \(R\) :x+1 之后有 \(Q\) 次询问,有\(L,R,x,y\), ......
CF1902 C Insert and Equalize 题解
Link CF1902 C Insert and Equalize Question 有一个 \(n\) 个元素的数组 \(a\),每个元素都不一样 现在我们需要在 \(a\) 中添加一个数字 \(a_{n+1}\),和之前的元素都不一样 然后选择一个数 \(x\),可以在一个元素上加 \(x\), ......
CF1902 B Getting Points 题解
Link CF1902 B Getting Points Question Monocarp 的一个学期有 \(n\) 天,需要修 \(P\) 个学分,完成一节课程加 \(l\) 个学费,完成一个任务加 \(t\) 个学分 Monocarp 一天可以完成一节课+两个任务 任务每周分配一个,也就是 d ......
CF1902 A Binary Imbalance 题解
Link CF1902 A Binary Imbalance Question 给出一个 01串,可以在任意一个位置 \(i\) 插入一个字符,如果 \(a_i \ne a_{i+1}\) 插入的字符为 \(0\) 否则插入的字符为 \(1\) 问,是否可以通过任意次操作使得串中 \(0\) 的数量 ......
CF1692H Gambling 题解
题意: 思路: 考虑离散化: 枚举 $ x $ 中出现的每一个数 $ val $ , $ val $ 出现的次数为 $ cnt $ ,记录 $ val $ 每一次出现的索引 $ idx_i(1 \le i \le cnt) $ 。设 $ x $ 中与 $ val $ 相等的数贡献为 $ +1 $ , ......
[Codeforces] CF1807E Interview
题目翻译 有 \(n\) 堆石头,其中 \(n-1\) 堆都只有重量为一克的石头,剩下一堆有则有一块有两克的石头和若干重量为一克的石头。 你的任务是在 \(30\) 次询问内推理出那一堆有重量为两克的石头是第几堆。 首先输入 \(n\),接下来输入 \(n\) 个数 \(a_1,a_2\dots a ......
[Codeforces] CF1753A1 Make Nonzero Sum (easy version)
题目大意 给你一个数组 \([a_1,a_2,...a_n]\) ,其中每一项 \(a_i\) 都为 \(1\) 或 \(-1\) ,你需要构造一个划分 \([l_1,r_1],[l_2,r_2],[l_3,r_3],...[l_k,r_k]\) 使得: 将每一个区间内的数按照以下方法计算出\(s_ ......
[Codeforces] CF1733C Parity Shuffle Sorting
题面翻译 给定一个长度为 \(n\) 的数组,你可以对它进行不超过 \(n\) 次操作。 对于每次操作: 选择两个下标 \(l, r\),满足 \(1\leq l<r\leq n\); 若 \(a_l + a_r\) 为奇数,将 \(a_r\) 赋值为 \(a_l\),否则将 \(a_l\) 赋值为 ......
[Codeforces] CF1627B Not Sitting
题意 Rahul 和 Tina 在玩一个游戏。游戏在一个 \(n\times m\) 的网格图上进行,记第 \(r\) 行第 \(c\) 列上的格子为 \((r,c)\)。定义 \((a,b)\) 与 \((c,d)\) 之间的距离为 \(\left|a-c\right|+\left|b-d\rig ......
[Codeforces] CF1659B Bit Flipping
题面 给定一个长为 \(n\) 的 01 串,你可以进行 \(k\) 次操作。每次操作中,你可以选择任意一位,并将除了这一位以外的其它位翻转(\(1\) 变 \(0\),\(0\) 变 \(1\)),输出 \(k\) 次操作后能获得的字典序最大的字符串,并输出每一位在操作中被选择的次数。若有多解输出 ......
[Codeforces] CF1675D Vertical Paths
CF1675D Vertical Paths 题目描述 给定一棵由 \(n\) 个顶点组成的有根树。顶点由 \(1\) 到 \(n\) 编号。任何顶点都可以是树的根。 请在树上找出这样一组路径: 每个顶点恰好属于一条路径,每条路径可以包含一个或多个顶点; 在每条路径中,每个节点的下一个节点是当前节点 ......
CF1790F题解
思路 令 $dis_i$ 为离 $i$ 最近的黑点距离, $ans$ 是距离最近的一对黑点距离, 我们可以发现, 每次 $i \gets i + 1$ 后 $ans$ 的更新只会与 $dis_{c_i}$ 有关, 因为 $c_i$ 是新的黑点, 然后再从 $c_i$ 来一次 BFS 更新 $dis_ ......
CF234E解题报告
CF234E 解题报告 题意 给你 \(n\) 个球队,和四个作为随机数生成器的变量,再给出每个球队的名称和积分,让你通过某种随机数来进行分组。 分组方法:将 \(n\) 个球队分到 \(n/4\) 个盒子中,求出随机数 \(x=(x \times a + b)\bmod c\),再抽取盒子中剩余球 ......
CF200D解题报告
CF200D 解题报告 题意 给你 \(n\) 个函数,由函数类型、函数名和参数类型组成。 给你 \(m\) 个变量,由变量类型和变量名组成。 给你 \(k\) 个调用关系,由调用的函数名和参数名构成。 参数类型和变量类型保证为 int,double,string 和 T 中的一个,其中 T 表示可 ......
CF718A解题报告
CF718A 解题报告 题意 给你一个长度为 \(n\) 的浮点数,最多四舍五入 \(t\) 次,求可以得到的最大值。 注意: 四舍五入之针对小数部分,不针对整数部分。 输出时不能有前缀 \(0\),和后缀 \(0\)。 当最大的数变成整数了,就不输出小数点。 分析 根据题面,很容易想到要用贪心,只 ......
CF414C Mashmokh and Reverse Operation
\(\text{Links}\) cnblogs Luogu Codeforces 题意 给定一个长为 \(2^n\) \((n\le 20)\) 的序列 \(a\),有 \(m\) \((m\le 10^6)\) 次操作,每次操作给出 \(q\) \((q\le n)\),表示将序列从左至右按 \ ......
CF1842题解
洛谷传送门&CF传送门 题目大意 给定 $a$,$b$,$c$ 三个大小为 $n$ 栈,把 $u$ 初始化为 $0$,接下来可以挑选三个栈顶的的一个数 $v$,每次进行一次操作,使得 $u=u \operatorname{or} v$,最终问你 $u$ 能不能变为 $x$(不懂位运算的戳这里)。 题 ......
CF1368题解
CF1368 Codeforces Global Round 8 ABC略。 CF1368D link CF1368D题意 给定 \(n\) 个非负整数 \(a_1,\cdots,a_n\)。 你可以进行如下操作:选择两个不同的下标 \(i,j\) 满足 \(1\leq i,j\leq n\),并将 ......
CF1037H Security 做题记录
搬的学习笔记,之前没想过要新开一篇。 题目传送门(CF) 给出一个字符串 \(s\),有 \(q\) 次询问,第 \(i\) 次询问给出 \(l_i,r_i,t_i\),求一个字典序最小的字符串 \(str\),使得它是 \(s[l_i,r_i]\) 的子串,且 \(str>t_i\)。 \(|s| ......
CF1705E Mark and Professor Koro 题解
题意: 给定一个长度为 $ n $ $ (1 \le n \le 2e5) $ 的序列,每次可以把两个相等的 $ a_i $ 和 $ a_j $ 合并为一个 $ a_i + 1 $ 。给定 $ q $ $ (1 \le q \le 2e5) $ 次修改,每次将 $ a_k $ 修改为 $ l $ , ......
CF1896D Ones and Twos 题解
题意: 思路: 先考虑不带修: 如果长度为 $ n $ 的序列 $ a $ 中无 $ 1 $ ,当且仅当 $ 2 \le s \le sum(1,n) $ 时,一定有解;否则,一定无解。 通过 $ set $ 维护序列 $ a $ 中每个 $ 1 $ 的位置,找到最靠左的 $ 1 $ 的位置 $ l ......
CF1835D Doctor's Brown Hypothesis 题解
题目链接 点击打开链接 题目解法 首先只有在一个强联通分量里的点对才可能合法,因此我们这里说的图默认为强联通图 但是上面的条件成立只需要满足 \(k\ge n\),考虑用好 \(k\) 可以认为是极大的性质 所以说我们可以通过图中所有的环 \(+\) 路径来凑出 \(k\) 不难发现,所有的环能构成 ......