1881 cf
CF1867B XOR Palindromes
思路 题目问的是改 \(i\) 位,能不能让原串变成回文串,其中 \(0\le i \le n\)。 首先,我们可以统计前后对称位置不一样的对数,记为 \(k\),那么至少也得改 \(k\) 次,假设剩下前后对称位置一样的有 \(m\) 对(如果 \(n\) 为奇数,则最中间的一位不计入 \(m\) ......
CF1718F Burenka, an Array and Queries
显然先考虑把每个 \(a_i\) 只因数分解,令 \(S(x)\) 表示 \(x\) 只因子的集合。 令 \(S_{l,r}=S\left(\prod\limits_{i=l}^ra_i\right)=S(a_l)\cup S(a_{l+1})\cup\cdots \cup S(a_r)\)。假如我 ......
CF1559D1&D2 Mocha and Diana
原题(Eazy Version) 原题(Hard Version) 翻译 首先我们先考虑Eazy Version。容易发现,在\(A,B\)两个森林中一定有一个是一棵树。这个结论说明: 选边顺序没影响 能选就选 因此我们枚举\(n^2\)条边,用并查集判断连通性即可 最终复杂度\(O(n^2 \al ......
【题解】CF1819A Constructive Problem
你考虑这道题中判 No 显然有两种情况: 如果说 mex 是 n 的话,即我们的所有数都是必不可少不能更改的,那么就是 No 如果说原序列中有 mex+1 那么我们就可以发现添加 mex 显然会有很大的问题,我们显然要将所有的 mex+1 的区间替换为 mex,并且保证其他的数的 mex 和原序列的 ......
CF1864E Guess Game
原题 翻译 非常好的一道题,不过前半部分的逻辑推理比较难理解,这很博弈 由于或运算是有\(1\)就为\(1\),因此我们对于一对数\((a,b)\),我们不需要看\(a|b\)中为\(0\)的那些位,因此我们只需要考虑\(a|b\)全\(1\)的情况即可 我们考虑一下如果\(Alice\)说"我不知 ......
CF1869B 2D Traveling
思路 首先思考,除了 \(a\) 和 \(b\) 我们不应该到达任何非主要城市。 理由很简单,两点之间线段最短,如果我们目前要从 \(u\) 前往 \(v\) 且 \(u\) 和 \(v\) 不都是主要城市,即 \(u\) 到 \(v\) 需要花钱,那么如果再选择一个不是主要城市的 \(k\),那么 ......
CF1868B1 Candy Party (Easy Version)
思路 首先想要均分糖果,那么必须满足糖果总数 \(sum\) 是人数 \(n\) 的倍数。 然后我们再取平均值,令 \(s=\frac{sum} n\)。 因为每个人必须收到一次糖果且只能送出一次糖果,所以对于每一个 \(a_i\),我们首先需要满足 \(a_i-s\) 可以被表示为 \(2^x-2 ......
CF1868B2 Candy Party (Hard Version)
建议先看简单版本以及我的题解。 思路 可以发现困难版本比简单版本唯一不一样的地方就是可以给糖也可以不给,可以收糖也可以不收。 首先还是需要求和,如果无法平分,肯定无解,再算出平均数 \(s\)。 还是考虑每一个 \(a_i\),如果 \(|a_i-s|\) 不是二次幂,那么肯定必须同时给糖和收糖,判 ......
CF1864C Divisor Chain
原题 翻译 好题难想 首先考虑\(x = 2^k\)怎么做,显然每次\(- 2^{k-1}\)即可 然后我们考虑对于\(x \neq 2^k\)怎么把他变成\(2^k\),答案就是\(x -= lowbit(x)\) 操作次数\(O(logn)\)的,\(< 1000\),正确性显然 ......
【CF1513C】Add One(动态规划)
题目大意: 给\(n()\)的每个数码加一,重复\(m(1\le m\le 2\times 10^5)\)次,求最终结果的长度,询问\(t(1\le \times)\)次。 #include<bits/stdc++.h> using namespace std; typedef long long ......
【题解】Educational Codeforces Round 142(CF1792)
没有手速,再加上被 E 卡了,废掉了。 A.GamingForces 题目描述: Monocarp 正在玩电脑游戏。他打算杀死 \(n\) 个怪兽,第 \(i\) 个的血量为 \(h_i\)。 Monocarp 的角色有两个魔法咒语如下,都可以以任意顺序用任意次(可以不用),每次使用相当于一次操作。 ......
CF *2600 DP选练
CF258D 题目描述: 有一个长度为 \(n\) 的排列,有 \(m\) 次操作,操作为交换两个数 \(a,b\) ,每次操作都有 \(50\%\) 的概率进行,求进行 \(m\) 次操作后期望逆序对个数 \(n,m\le1000\) 题目分析: 看到 \(n\) 和 \(m\) 都只有 \(10 ......
sol. CF1680F Lenient Vertex Cover
CF1680F Lenient Vertex Cover 下面用 \(G\) 表示一个环的边集,记作环 \(G\)。 我们令一个环 \(G\) 的价值为它经过的返祖边数量,记作 \(Z(G)\),下面给出核心结论: 若存在一条边 \(e_0\) 经过所有 \(Z(G) = 1\) 的奇环,且不经过任 ......
【题解】CF1830D Mex Tree
我们考虑这道题一看题就特别难受,所有路径?\(mex\) 之和?这是什么东西? 我们考虑 \(mex\) 之和其实是有一点诈骗的感觉,毕竟是 \(0\) 或 \(1\),还比较简单。就是路径上全都是 \(1\) 的时候是 \(0\),全都是 \(0\) 的时候是 \(1\),有 \(0\) 和 \( ......
【题解】CF1830E Bully Sort
考虑一次交换,我们发现,被选出来的 \([i,j]\) 的区间里 \(p_i\) 一定是最大的,\(p_j\) 一定是最小的。 然后我们会发现,我们原序列的逆序对数量会减少 \(2(j-i) - 1\),而 \(\sum|p_i-i|\) 会减少 \(2(j-i)\) 那么答案就是原序列的两部分相减 ......
CF题解合集
CF 比赛题解合集 \(\downarrow 2023.09.04\) CF1952, CF1954 1952 A. Ntarsis' Set 有一个集合,初始状态里面有数字 \(1\)、\(2\)、\(3\)、\(4\)、\(5\)、......、\(10^{1000}\)。 现在给你一个长度为 ......
CF1446F Line Distance
Dqy 7。 计几结论拍脸,感觉不如原神。 Binary search is your friend. 考虑二分答案,二分一个距离 \(r\),考虑求出 \(d(O,AB)>r\) 的无序点对 \((A,B)\) 数量。 以 \(r\) 为半径作圆 \(C:x^2+y^2=r^2\)。考虑如果一个点 ......
CF1801G A task for substrings
Day 6。 好神奇的题啊,我完全不会做。 建出 \(s_1,s_2,\cdots, s_n\) 的 ACAM。 考虑在 \(r\) 处统计满足条件的数对 \((l,r)\) 的贡献。那么需要求出 \(f_r\) 表示文本串以 \(r\) 为结尾的前缀 \([1,r]\) 中,其所有后缀中模式串的出 ......
cf edu 1700
1430D. String Deletion 因为要最大话操作次数,所以我们每次删除的时候删除没有被删除最左侧连续相同长度大于等于 2 的部分。 想清楚贪心策略后,用快慢指针就可以\(O(N)\)实现本体。 #include <bits/stdc++.h> using namespace std; ......
【题解】CF1830C Hyperregular Bracket Strings
我们知道,一个长度为 \(n\) 的合法括号序列的种数就是第 \(\frac n 2\) 个卡特兰数(当然 \(n\) 是奇数答案肯定就是 \(0\)) 我们可以发现一件事情,如果两个区间相互包含,那么就可以将大区间分为中间被包含的小区间的部分和外面没有被小区间覆盖的部分。 如果两个区间相交,那么就 ......
【题解】CF1830B The BOSS Can Count Pairs
你考虑,我们观察数据范围,发现可以是 \(O(n\sqrt n) / O(n\log n)\) 的,我们又看到乘法,便有几个大概的想法: 数论分块 \(O(\sqrt n)\) 枚举其中一个乘数 还有什么……(笔者学识浅陋,读者可以帮忙补充) 我们可以找到两种 \(O(n^2)\) 做法: \(O( ......
[题解} CF1217D Coloring Edges
CF1217D Coloring Edges 知识点: dfs 树。 题意 给定一张有向图,现在要求为图上所有的边进行染色,使得颜色种类最少的同时,同种颜色的边无法构成环,输出最少需要的颜色种类和任意一种染色可行方案。 思路 假设该有向图中不存在环,那么我们可以直接对所有的边染为同一种颜色。因此可以 ......
CF1570C 题解
一道纯粹的贪心题。 思路分析 通过观察,我们可以发现,每个瓶子所需要的射击次数的增长是与 \(x\) 密切相关的。 这样我们很容易想到,如果我们将耐久度大的瓶子放在后面射击,那么 \(x\) 就会较大,因而导致最终的射击次数变大。 说到这儿,思路已经显而易见了。我们可以对 \(a\) 数组根据耐久度 ......
CF285B 题解
不可多得的小清新模拟题! 思路分析 题目中已经暗示地很明显了,只能对 \(x\) 进行操作使得 \(x\) 变成 \(p_x\)。 而我们现在可以操作的值唯独 \(s\),所以我们的思路就呼之欲出了。 我们重复将 \(s\) 迭代为 \(p_s\)。如果 \(s=t\),那么我们就找到了答案。如果 ......
CF1252A 题解
思路分析 前置知识:排列是没有重复元素的! 猜想 我们可以进行一种猜想,对于 \(x\),输出: \[\begin{cases} x+1&x<N\\ 1&x=N \end{cases}\]将代码提交上去,我们可以发现这种猜想值正确的! 证明 但是作为一名合格的 OIer我们必须证明这种做法是正确的。 ......
CF387B 题解
思路分析 因为最终要使得 \(a,b\) 相同,所以我们应该希望让相同的数字尽量相同。所以,我们需要先对 \(a\) 和 \(b\) 进行排序,这样子就可以使用双指针的方法来维护最终值了。 我们定义 \(l\) 指针指向 \(a_l\),\(r\) 指针指向 \(b_r\)。因为题目要求添加数字的次 ......
CF431B 题解
思路分析 答题思路 一道纯暴力题! 因为我们发现数据最大是 \(5\),而枚举全排列的时间复杂度为 \(\mathcal O(n!)\),对于这种极小的数据范围是丝毫不用顾虑的,因为我们只需要执行 \(120\) 次。 如何快速求出一个数组的全排列? 我们可以使用 dfs,一层一层获取这个数组的全排 ......
CF 1863 B
B. Split Sort 一开始想麻烦了,搞的没思路。 这道题只需要遍历一遍数组并查询当前查询的数小\(1\)的数是否查询过,如果没有查询过就代表该数在这个数的后面,\(Ans\)就需要加一,最后输出就行。 代码 #include <bits/stdc++.h> #define endl '\n' ......
CF 1863 C
C. MEX Repetition 通过观察样例,直接猜结论可知,例如第二个样例\([0, 1, 3]\)后面其实有一个隐藏数字(2),所以完整的排列为\([0, 1, 3, 2]\)。然后每一次操作都是把最后的一位数字移到整个排列的最前面,并把最后一位隐藏,所以直接取模就能求出最后的排列。 代码 ......