题解1359a cf
CF练习题18
这次的题都是什么怪物!!! Short Colorful Strip 因为 \(n=m\),所以最终的形态一定是 \(n\) 的一个排列。 根据题意,发掘几个性质: 一个区间染色,一定最先对其中颜色最小的染色。 染色要求覆盖的点颜色完全相同。 对于第一次来说,先找到颜色为 \(1\) 的点,位置是 ......
CF827D Best Edge Weight 题解
Problem - 1867D - Codeforces Cyclic Operations - 洛谷 差一点就想出来了 首先 \(b_i\) 构建出来的肯定是一个章鱼森林,而且手玩一下样例就会发现我们每次要找到一个大小为 \(K\) 的环后让里面的点重新指向,一直重复这些操作直到所有点都被找到。 ......
CF1821F
传送门 solution 对于一个确定的树木种植位置方案 \(\{x\}\),我们规定树木优先向左侧倒下。 枚举有 \(p\) 个树木向右倒,然后我们要求每个向右倒的树木左侧不能有连续 \(k\) 个空格。设 \(f_{i}\) 表示有 \(p\) 个树木向左倒,恰好有 \(i\) 个能向左倒的树木 ......
CF1837E
这是一道非常有意思的题。 设 \(n\) 为当前队伍数量。 下面对于每个队伍的“数值”不是编号,而是能力。(比如说这时编号为 \(1\) 的队伍能力为 \(n\))。 思路清晰的,我们发现在初始状态下,每两格一组,每组之间是互相独立的。然后我们当前已经确定了一些队伍的位置,只知道这些发现很难去计算答 ......
CF1861D
废话: VP 时 T3 思路不清晰,写了很久,然后这题没时间做了,赛后五分钟 AC 了(还好不是正赛,不然我会气死的)。 所以做题前思路一定要清晰且严谨! 思路: 观察这个问题,发现如果 \(l\) 到 \(r\) 不是单调的,那么完全没必要一起乘。 那么本题中的操作将会一整段一整段的进行,我们肯定 ......
[ARC104B] DNA Sequence 题解
题意 对于一个只含有 A,C,T,G 的字符串 \(s\), 定义其为匹配的当且仅当其中 A 的数量和 T 的数量相等,C 的数量和 G 的数量相等。 给定一个长度为 \(N\) 的字符串 \(S\),求其有多少个非空子串是匹配的。 \(1 \le N \le 5000\)。 题解 \(\mathc ......
[ARC104C] Fair Elevator 题解
题意 有 \(N\) 个区间 \([a_i,b_i](a_i<b_i)\),都是 \([1,2n]\) 内的整数且互不相同(\(a_i\ne b_j,a_i\ne a_j,b_i\ne b_j\))。 现在给定一些 \(a\) 和 \(b\) 的值,剩下不知道的用 \(-1\) 表示。问是否存在一种 ......
[ARC104D] Multiset Mean 题解
题意 给定 \(N,K\) 和 \(M\)。对于每个大小在 \([1,N]\) 中的 \(x\),求每个元素大小在 \([1,N]\) 中,平均数为 \(x\) 且相同元素不超过 \(K\) 个的可重集的数量,对 \(M\) 取模。 \(1 \le N,K \le 100\),\(M\) 为质数。 ......
CF580E Kefa and Watch 题解
花了一个半个下午+半个晚上终于调出来了...... 0. 题面 长度为 \(n\) 的字符串,每个字符是 \(\mathtt{0} \sim \mathtt{9}\) 的数位,\(m + k\) 种操作: 格式为 1 l r c,表示将 \(l \sim r\) 赋值为 \(c\),保证 \(0 \ ......
题解:USACO23OPEN-Silver
题解:USACO23OPEN-Silver T1 Milk Sum 给定一个长度为 \(N\) 的序列 \(a_1,a_2,...,a_n\),现在给出 \(Q\) 次操作每次将 \(a_x\) 修改为 \(y\) , 每次修改后,求将序列重排后的 \(T\) 的最大值,定义 \(T=\sum_{i ......
CF773A Success Rate 题解
Success Rate (提供二分做法) 前言 听说是史上最简单蓝题,做了一下。 题意 已知 \(x,y,p,q\),通过只让 \(y\) 加 \(1\) 或 \(x,y\) 同时加 \(1\),使得满足: \[\frac{x'}{y'}=\frac{p}{q} \]思考 目标状态为 \(\fra ......
CF 随机做题
CF1884 2C 假设咱们钦定在 \(x\) 处取到最大值,则对于任意线段 \(i\),若 \(i\) 覆盖点 \(x\),则选中她会使得 \(\max a \leftarrow \max a + 1\),\(\min a \leftarrow \min a + y\),\(y \in \{0, ......
CF1868B2 Candy Party (Hard Version) 题解
Problem - 1868B2 - Codeforces Candy Party (Hard Version) - 洛谷 相信大家已经看过 Simple Version ,这题和上题不同之处就在于如果 \(b_i = 2^x\) ,他可以被分解成 \(2^x\) 或 \(2^{x+1}-2^x\) ......
CF227A Where do I Turn? 题解
题目大意: \(A\),\(B\) 在一条直线上。\(B\),\(C\) 在一条直线上你从 \(A\) 走到了 \(B\) 去 \(C\),问现在应该是直走、左转、还是右转。 思路: 分类讨论:分别求 \(A\) 到 \(B\),\(B\) 到 \(C\) 是什么方向,然后可得 \(A\) 到 \( ......
CF333B题解
分析 发现只能跳 \(n - 1\) 次,所以每个点一定是畅通无阻地抵达终点,所以有障碍的行和列放不了,并且每一个行或列最多放一个。 因为同时跳,思考会不会跳到一起,发现如果不在正中间可以将起点放到另一头就不会跳到一起,如果在正中间就一定会跳到一起,所以正中间的行和列加一起最多只能放一个。 代码 # ......
P9740 「KDOI-06-J」ION 比赛 题解
题目 思路: 先计算总分数 \(sum\),\(c_i=\frac{100}{a_i}\) 为每道题的每个测试点分数。 如果总分数达到 \(Au\) 线,直接输出 Already Au. 。 否则计算到达 \(Au\) 线还需多少分 \(p\),遍历所有题,求出每道题的失分,如果失分大于等于 \(p ......
CF333A题解
分析 被除数一定,除数越小,商越大,所以选择合法的最小 \(3_{x}\)。 枚举指数即可,复杂度 \(\mathcal{O(\log_{3}w)}\),\(w\) 为值域 \(1e18\),可以通过本题。 代码 #include <iostream> #define int long long u ......
Educational Codeforces Round 134 (Div.2) D 题解
题目链接 D. Maximum AND 题目大意 给定两组序列 \(a\) \(b\),长度为 \(n\) ,现有一新序列 \(c\),长度也为 \(n\) 。 其中,\(c_i = a_i \oplus b_i\) 。 定义 \(f(a,b) = c_1\&c_2\&……\&c_n\)。 现在你可 ......
CF1868B1 Candy Party (Easy Version) 题解
Problem - 1868B1 - Codeforces Candy Party (Easy Version) - 洛谷 喵喵题。首先每个数最终肯定变成 \(\overline a\) ,如果 \(\overline a\) 不是整数显然无解。 然后记 \(b_i=a_i-\overline a\ ......
abc194f O(nk)题解
前言 洛谷唯一的题解似乎是 \(O(nk^2)\) 的,怎么卡过去的orz 这里提供一种与 AT 官方题解时间复杂度相同的 \(O(nk)\) 做法。 Solution 题意很显然,就不解释了。 一眼丁真,考虑数位 dp。 设 \(dp_{i,j}\) 表示做到第 \(i\) 位,不同的个数有 \( ......
CF743C Vladik and fractions
大胆拆开,变成两个 \(\frac{1}{n}\),令 \(z=n\),那么 \(\frac{1}{x}+\frac{1}{y}=\frac{x+y}{xy}=\frac{1}{n}\)。 注意到分母是乘积,分子是和,可以令 \(x,y\) 的单位为 \(n\)。设 \(x=kn\),那么 \(x+ ......
[ARC159F] Good Division 题解
[ARC159F] Good Division 题解 首先对于题目要求的划分方式转化一下,转化为划分的每一段都没有 绝对众数,可以证明这与题目中的要求是完全等价的,证明如下: 充分性:考虑构造一种操作方法,就是每次操作都消去一个出现次数最多的数,按照这样操作可以保证每次操作之后该区间仍然不会出现绝对 ......
10.30 CF1685 题解
10.30 CF1685 A.Circular Local MiniMax 题意 给你 \(n\) 个整数 $ a_1, a_2, \ldots, a_n $ 。 问有没有可能将它们排列在一个圆上,使每个数字严格地大于其相邻的两个数字或严格地小于其相邻的两个数字? 题解 直接排序然后按照 \(1,4 ......
题解:[SCOI2008] 城堡
应该是联赛前最后一次任性了,浪费的时间有点多,不过也揭露了我的基础知识和代码能力都很弱的问题,得加油啊。 先 sto dwt。 给定一棵基环树森林,起初有 \(m\) 个点已被选进 \(S\) 里,你需要再选 \(k\) 个点加入到 \(S\) 中,最小化其余点到 \(S\) 距离的最大值。 这个问 ......
Luogu P3862 数圈 题解
看数据范围 ——题记 传送门 考虑记 \(f_i\) 表示有 \(i\) 个点的完全图的圈数 \(g_i\) 表示有 \(i\) 个点的完全图中一个点到另一个点不同路径的方案数 \(ans\) 表示答案 容易知道递推式 \[f_i=g_{i-1} \times C_{i-1}^2+f_{i-1} \ ......
「Note」CF 杂题集 6
前言 难度:CF 2600-2700(有一道是 2500) 别问我为啥没有 1 到 5。 \(\color{blueviolet}{CF1473F}\) 此题是坏题,他卡你空间。 每一个元素有选或不选两种状态,并且有依赖项,元素的贡献有正负,数据范围不大,可以自然联系到最大权闭合子图,采用最小割模型 ......
《CF1889C2 Doremy's Drying Plan (Hard Version)》 解题报告
考场上不会做。 如果考虑删掉哪些区间实际上不太可做。正难则反,转化贡献,考虑哪些点可以有贡献。 显然一个点如果可能有贡献,那么当且仅当覆盖它的区间 \(\le K\) 个。 于是我们记一个状态 \(f_{i,j}\) 表示前 \(i\) 个点中, \(i\) 是最后一个贡献的点,已经删除了 \(j\ ......
CF911G Mass Change Queries
CF911G Mass Change Queries 题解 首先这题有一个很一眼的分块做法,并且由于只需要维护颜色,所以会极其好写。 对每个块维护并查集,表示整块中颜色变成了哪个颜色,每个位置单独也指向一个颜色表示最初指向哪个颜色,这样就很好维护了。 但是发现值最大只有 \(100\),所以考虑和值 ......
题解 P2217 [HAOI2007] 分割矩阵
题目描述 将一个矩形分割成 \(n\) 个小矩形,每个小矩形的总分为这个矩形内所有数的和。求各矩形总分均方差最小值。 具体思路 先来几个定义。 均方差:$$\sqrt{\frac{1}{n} \times \sum_{i=1}^n (a_i-avg)^2}$$ 方差:$$\frac{1}{n} \t ......