isolation 1129d cf
Sol.CF301A
签到题中夹带着贪心 考虑要尽可能把所有数变成正数。 若 \(n\) 为奇数,则一定可以变成全部正数,首先翻出 \(n\) 个负数,其他的下一次翻完。 若 \(n\) 为偶数,显然定有一个数还是负数,考虑最小的哪个。 Accept 代码如下: #include<iostream> #include<c ......
CF521E. Cycling City
套路的,先随便找这张图的一棵生成树,原条件等价于存在一条路径同时被两条非树边覆盖。 直接枚举非树边进行覆盖,发现如果只要有一条树边的覆盖次数达到了 2 就可以退出了。因此,我们选取这张图的 dfs 树作为我们的生成树。 这样做有一个很好的性质:非树边只会是返租边或是前向边。由于这是一张无向图,前向边 ......
CF1868C
问题链接 题意:\(n\)个点,每个点的点权在\([1,m]\)之间,求所有方案的所有路径的最大值的总和 首先,对于一条长度为\(x\)的路径,设它的贡献为\(pre_x\),他的最大值取值有\(m\)种,其中最大值为\(i\)的取值有\(i^x-i^{x-1}\)种,而除了该路径外的所有点的取值一 ......
CF1867D Cyclic Operations
前言 赛时没调出来,赛后调了一个上午,最后发现是有个地方没清零。 思路 首先对于位置 \(i\),我们必须要保证进行的操作中,最后一次出现 \(i\),\(i\) 的后面一定是 \(a_i\)。 那么我们考虑统计所有位置上的要求,用有向边链接,那么就会出现一个有环有向图(一定有环,因为点数等于边数) ......
CF1867A green_gold_dog, array and permutation
思路 很简单的一道题,洛谷大概都不会开放题解通道?(实际上貌似每场比赛的 A 都没开放?) 显然,对于原数组较小的数,我们尽量让大的数,取全排列的较小的数,这样可以保证差是逐渐变小的,也就让 \(c\) 数组差异变大。 所以直接拿个 struct 存,然后两边排序就好。 AC code #inclu ......
CF1867C Salyg1n and the MEX Game
思路 看着无从下手,实际上又是一道诈骗题。 假设原数列不存在 \(0\),那么我们可以直接加入 \(0\),然后游戏结束,假设答案是 \(k\)。那么,如果我们选择加入 \(k\),来试图让答案变大,那么 Bob 就会移除一个数,最优的话是 \(1\),这样的话,你无论加入 \(1\) 还是 \(0 ......
CF1867E1 Salyg1n and Array (simple version)
思路 首先考虑,\(n\) 是 \(k\) 的倍数的情况,直接枚举询问所有每一段就好,然后输出每一段的异或和的异或和。 如上图,每次询问都没有重叠部分,颠转互不干扰。 那么,\(n\) 不是 \(k\) 的倍数的情况呢? 可以看到,与第一种情况的区别就是末尾多了一小截,那么我们需要考虑如何计算这一小 ......
CF1867E2 Salyg1n and Array (hard version)
其实如果你在做 E1 的时候想到正解了,这道题都甚至不需要改 E1 的代码,直接交就好,这大概也是 E2 的分还没 E1 的高的原因。 因为一摸一样的思路,所以这里就不作介绍了,可以看看我的题解。 在这里呢,主要是稍微证明一下询问次数不会超,如下: 可以发现,有余数的情况,只会增加两次询问,而后面的 ......
202309 at&cf题目选讲
题目链接 题解 目录A AtCoder abc318_c Blue SpringB AtCoder abc318_d General Weighted Max MatchingC AtCoder abc318_e SandwichesD AtCoder abc318_f OctopusE AtCod ......
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\)) 我们可以发现一件事情,如果两个区间相互包含,那么就可以将大区间分为中间被包含的小区间的部分和外面没有被小区间覆盖的部分。 如果两个区间相交,那么就 ......