isolation 1129d cf
[题解} 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]\)。然后每一次操作都是把最后的一位数字移到整个排列的最前面,并把最后一位隐藏,所以直接取模就能求出最后的排列。 代码 ......
CF758F
题目链接 description 求满足长度为 \(n\),所有项都是 \([l,r]\) 间的正整数且公比为非 1 有理数的等比数列的数量。 \(n\leq 10^7,1\leq l\leq r\leq 10^7\) solution 先不考虑公比不能为 1 的限制,对于 \([l,r]\) 间的 ......
CF1570D 题解
思路分析 前言 题解区好似没有用哈希的啊。 发现大家都在用 map 来存是否出现过数字,但是需要注意的是,map 的单次查询时间复杂度是 \(\mathcal O(\log n)\) 的,对于大规模的数据就很可能会 TLE。所以,我们可以使用哈希的方法来判断数字是否出现过。 浅谈哈希 哈希,是通过哈 ......
【题解】Educational Codeforces Round 143(CF1795)
A.Two Towers 题目描述: 有 \(a,b\) 两座由红蓝色方块垒成的塔,其中 \(a\) 的高度为 \(n\) ; \(b\) 的高度为 \(m\) ,用 R 代表红色;用B代表蓝色。 你可以多次把其中一座顶端的方块移到另一座的顶端(可以不移动)。问有没有一种方法可以使两座塔中均没有连续 ......
【CF1364C】Ehab and Prefix MEXs(构造)
题目大意: 给出长度为\(n(1\le n\le 10^5)\)的数组\(a\),构造数组\(b\)使得\(a_i=MEX\{b_1,b_2,...,b_1\}\) 首先考虑当\(b_1,b_2,...,b_n\)为什么数时,\(a_n=MEX\{b_1,b_2,...,b_n\}\)。 然后再考虑 ......
CF1866
待补 CF1866 C 考虑在每个边权为 1 的边 \((u,v)\) 计算贡献。考虑 \((u,v)\) 被经过 \(m\) 次,表示为 \(r_1,\dots,r_m\) 。\(r_1,r_2\) 之间的 0 边被计算 \(1\) 次,\(r_2,r_3\) 之间的 0 边被计算 \(2\) 次 ......
CF1823D Unique Palindromes
题目链接 题解 知识点:构造。 首先反证法容易证明一个结论:每次增加一个字符,本质不同的回文子串至多增加一个。 那么无解的条件就是,\(c_i - c_{i-1} > x_i -x_{i-1}\) ,即距离不够数量的增加。 其他情况均有解,可以考虑利用 abc 作尾部填充,因为其只在一开始提供 \( ......
[题解] CF29D Ant on the Tree
CF29D Ant on the Tree 题目知识点:LCA。 题目传送门 题意 给定一棵以 \(1\) 为节点的树,再给定树的所有叶子节点的一个序列。 现在执行一个操作:从 \(1\) 开始遍历每个节点,并返回根,要求每条边经过的次数一定为 \(2\) 。 问是否能够使得访问节点序列中叶子节点的 ......
CF1834E
题目链接 description 给定一个长度为 \(n\) 的序列 \(a\),求一个最小的正整数 \(x\),使得它不是这个序列任意区间的最小公倍数。 值域 \(W=10^9\) solution 显然答案最大的数量级为 \(O(n\log n)\),记 \(m=n\times (\lfloor ......
CF982E
题目链接 description 如上图,\((0,0),(0,m),(n,0),(n,m)\) 是四个口袋。一个台球从整点 \((x,y)\) 按照给定的初始方向出发(方向只可能平行于坐标轴或和坐标轴呈 45° 夹角),当它和一个口袋的坐标重合时游戏结束。 给定 \(n,m,x,y\) 以及球初始 ......
CF1513C题解
一道递推 由于对于一个数 x ,可得 x+10-x=10(废话) 于是问题就变成了 0+m 次,然后 x+m 就变成 0+x+m (还是废话) 于是可以写一个递推。 首先对于函数 f(m) 可分为 m ≤ 9 和 m>9 ,然后可得出递推式结果为 1 或 f(m-9)+f(m-10) ,所以我们可以 ......
CF1106F
题目链接 description 定义数列 \(f\),当 \(i>k\) 时,\(f_i=\prod\limits_{j=1}^k f_{i-j}^{b_k}\) 模 998244353 。 已知数组 \(b\) 且 \(f_1,f_2,\dots,f_{k-1}\) 均等于 1,给定 \(n,m ......
CF1872
Link A Two Vessels 十分甚至九分地简单 #include<bits/stdc++.h> using namespace std; int t; int a,b,c; int main(){ scanf("%d",&t); while(t--){ scanf("%d%d%d",&a, ......
CF915G
题目链接 description \(f_k(x)\) 表示所有长度为 \(x\) ,元素取值范围为 \([1,k]\) 中的整数的序列 \(\{a\}\),满足 \(\gcd(a_1,a_2,\dots,a_x)=1\) 的序列的个数。 给定 \(n,k\leq 2\times 10^6\) 分别 ......
CF812B题解
康了康唯一的题解,说没必要用DP,我就给出DP的解法。 这其实是道水题,唯一的坑是有可能楼上没有开的灯,坑了我们机房的一堆人( WA on test 4 ),剩下的就是DP。 我们用 a[n][0],表示第 n 层的第一个房间,用 a[n][1],表示第 n 层的最后一个房间。 这里提供一个收集型的 ......
CF1690E题解
## 主要题意:有 $n$ 个礼物,要两两合并,然后除以 $k$ 最后求和最大。 ## 思路:先加入每个数除以 $k$ 的商(单独组成 $k$ 的个数),然后全部 $ \bmod \ k$ 存入数组,排序,最后双指针一个前一个后求两个余数可以大于等于 $k$ 的两个礼物。 ## 代码: ```cpp ......
CF1690C题解
## 主要题意:> 有 $n$ 个任务,必须在 $s_i$ 到 $t_i$ 之间完成,求每个任务最大可以完成多久(优先前面的最大)。## 思路> 就拿一个变量记录当前时间,然后贪心选择 $a[i].t$ 和 $ a[i + 1].t$ 中的最小值,(应为至少也要给下一个任务留 $1$ 的时间),最后 ......
CF446C
题目链接 description 写个数据结构,支持区间加斐波那契数列和区间求和。 模 1e9+9。 solution 设 \(A=\begin{bmatrix}1&1 \\ 1 & 0 \end{bmatrix}\)。 则 \(\begin{bmatrix} F_{n+1}& F_{n} \end ......
CF896B Ithea Plays With Chtholly
原题 翻译 Chtholly可爱捏 我们先考虑如果\(n \cdot c \leq m\)我们要怎么做,我们可以发现里面一定存在一个数出现了\(\geq \lceil \frac{m}{c} \rceil\),不妨设这个数为\(x\),因此我们只需要把所有数都改成\(x\)就可以了 等等好像不对,我 ......
CF710D
题目链接 description 给定 \(0\leq a_1,a_2\leq 2*10^9, -2*10^9\leq b_1,b_2,L,R \leq 2* 10^9\) 求 \(\sum\limits_{x=\max(L,b1,b2)}^R [a_1\mid x-b_1][a_2\mid x-b ......
CF 1864 C
C. Divisor Chain 看到样例2中的\(5\xrightarrow{-1}4\xrightarrow{-2}2\xrightarrow{-1}1\)想到了是不是应该把\(x\)向着\(2^n\)去凑,凑到了之后通过不断的减去\(2^{n-1}\)最后达到\(1\),然后就可以朝着这个方向 ......
【CF1527C】Sequence Pair Weight
题目大意: 给出一个长度为\(n(1\le n\le 10^{5})\)的序列\(a_1,a_2,...,a_n\),计算\(\sum_{1\le l<r\le n}\sum_{l\le i<j\le r}[a_i=a_j]\) \(\sum_{1\le l<r\le n}\sum_{l\le i< ......