cf

题意 给定一棵根为 \(1\) 的 有根树。 每个节点有颜色，求每个节点子树内出现最多的颜色编号之和。 Sol Dsu on tree板子题。 首先对于整棵树进行轻重链剖分，注意到一个关键性质：轻边只有 \(log\) 条。 \(n ^ 2\) 的暴力是 \(trivial\) 的，不再赘述。 注意 ......

C.Koxia and Number Theory 题意:给定 n 个数,问是否存在一个正整数 x ,使得对 \(\forall \ i,j \in [1,n]\) ,有 \(\gcd(a_i+x,a_j+x)=1\) 题解: 感觉这题挺难的,想了很多次也没想出来. 若两个数互质,一定不存在质数 \ ......

思路 首先可以知道答案的下界就是序列 \(a\) 原来的 LIS，现在需要做的就是尽可能地保持答案不增加。 可以肯定的是，将序列 \(b\) 从大到小地插入序列 \(a\) 是不劣的，并且如果在 \(a_i\) 前插入的都是 \(\ge a_i\) 的不会使答案增加，可以感性理解，如果原来的 LIS ......

CF907 div2 A.Sorting with Twos 题意 给一个长度为n的序列，可以进行的操作是，选取一个i，令前\(2^i\)个元素减1,问若干次操作之后能否使得序列成为不降序列。 数据范围 多组数据\(1<=T<=10^4\),\(1 <= n <= 20\),\(0 <= a_i < ......

标签格式 思路 算法 特殊 CF1155F 标签 分析性质 图论，状压 DP，枚举 记录方案， 思路 做的时候想了几个错误做法，还看错题了。 因为边双的形态必然是由一个点加多条链组成的（耳分解）（一个环 = 一个点 + 一条链），即糖葫芦型。 又因为 \(n\le 14\) 考虑暴力。 先预处理出 ......

前言 传送门 本题思维难度：橙。 本题代码难度：橙或红。 综合难度：橙。 本人代码码量位居第二，但是呢，我的空格多，所以，还不来看一下？ 题意 根据题目，若两人一人有 $j$，一人没 $j$，则异或后，第 $j$ 位为 $1$。 那么，题目转化为：已知有 $m + 1$ 个数，求出满足 $a_i$ ......

好喜欢 SA + DS。 洛谷 CF 给出序列 \(a_1\sim a_n\)，有 \(q\) 次询问，每次询问给出 \([l,r]\)，求有多少个区间 \([x,y]\) 满足 \(y-x=r-l\)，\([x,y] \bigcap \,[l,r]=\varnothing\) 且 \(\foral ......

Yet Another Array Counting Problem 给你一个长度为 \(n\) 的序列和一个数 \(m\)，求有多少个长度为 \(n\) 的序列 \(b\) 满足： \(\forall i \in [1, n], b_i \in [1, m]\)。 对于每个区间 \([l, r]\ ......

题目描述： 有一个 \(n\) 个点的图，对于每两个点 \((i,j)\) 之间都有一条长度为 \(w_{i,j}\) 的无向边。 给你一个点 \(t\)，你需要构造一棵以 \(t\) 为根的生成树，使得\(\sum\limits_{i=1}^{n}s(i,t)\) 尽量小。\(s(i,t)\) 为 ......

【题解】CF1891E - Brukhovich and Exams https://www.luogu.com.cn/problem/CF1891E 我们考虑把区间分段：若两个相邻的数不互素，中间分开；若两个相邻的数中有且仅有一个 \(1\)，中间分开。那么我们得到了两种区间：全 \(1\) 区间 ......

Special Segments of Permutation 给你一个排列 \(p\)，求有多少个区间 \([l, r]\) 满足 \(p_l + p_r = \max_{i \in [l, r]} p_i\)。 \(n \le 2 \times 10^5\)。 按最大值分治，记当前的分治中心为 ......

先把存在性容斥一下。变成 \([0,\infty]\) 减去 \([0,x-1]\) 和 \([x+k,\infty]\)。 \([0,x-1]\) 的答案显然可以矩阵快速幂 \(\mathcal O(x^3\log n)\) 求。考虑剩下两个。注意到两个单拎出来都不好求，所以直接求这两个的差。 注 ......

sqrt technology, sqrt faith. 洛谷 CF 定义一个数为幸运数字，当且仅当其十进制数位中仅有 \(4\) 和 \(7\) 组成。 给出长度为 \(n\) 的序列 \(p_1\sim p_n\)，有 \(q\) 次操作，分为两种类型： \(\texttt{add }l\tex ......

闲话 调了好一会，甚至还重构了一次代码才对，但是还是很喜欢并查集，并查集可爱捏。 题意省流 $n$ 个学生分成 $3$ 人一组，要满足 $m$ 个条件，每个条件给出两个数 $x,y$，要求 $x$ 和 $y$ 必须在一个组里。 正文 要使学生三人一组，一眼使用并查集。 首先考虑无解（输出 $-1$ ......

思路 实际上，如果你会简单版本，那么困难版本也没有那么难了。 同样考虑构造一种通解，如下， 红色的格子改为 X，绿色的格子改为 O，就是一种通解，同样的，这样改可能会超过棋子总数的 \(\frac 1 3\)。 将方案整体向上挪一格和两格可以得到一共三种通解，这三种通解需要改的棋子总数就是棋盘上的棋 ......

思路 如果去考虑 O 的摆放，再考虑那些改为 X，这样不好思考，实现也很不好写，所以我们可以考虑构造一种通解。 如果将上图所有标红的位置都放上 X，那么无论 O 如何放，都不可能胜利，而 X 因为原本就没有，所以摆上后也不可能胜利。 不过，因为更改的次数不能超过棋子总数的 \(\frac 1 3\) ......

改进了一下 @\(\bf{ \color{black}\text{唐}\color{red} \text{一文}}\) 大佬的做法。 tags： \(\text{strings}\) \(\color{red}*2900\) 洛谷 CF 给出一个字符串 \(s\)，求 \(s\) 有多少对相交的回文 ......

题目描述： 给出一个数列,有q个操作,每种操作是把区间[l,r]中等于x的数改成y.输出q步操作完的数列. 数据范围： \(1\le n\le 2\times 10^5\) \(1\le a_i\le 100\) \(1\le q\le 2\times 10^5,1\le l,r\le n,1\le ......

题意 给定一张有向无环图，一个合法方案定以为每个点拓扑序满足对应限制，求每个点所有合法方案中的最小拓扑序。 \(1 \leq n, m \le 2000\) ，数据保证存在合法方案。 solution: 对拓扑序的字典序的限制可以用优先队列维护，这道题也可以直接开桶。倒着考虑每个时刻能让那些点成为答 ......

题目描述： 给你一个有\(n\)个点的树。当每一个点的度不超过\(4\)时这棵树是合法的。现在让你再添加一个点，在树仍然合法的情况下，一共有多少种树。 当两棵树同构时视作同一种。 保证输入的树是合法的。 数据范围： \(1\leq n\leq 10^5\) \(1\leq u_i,v_i\leq n ......

题目描述： 有一个\(n×n(n≤300)\)的棋盘和\(1~m(n^2≤m≤100000)\) 这些数字。棋盘首先会被随机生成,即从“填着值域\(1 \sim m\)的数字且\(n^2\)个数字两两不同”的所有方案中随机选一个。 然后你会从\(1\sim m\)中随机选出\(k(n≤k≤m)\)个 ......

CF895 div3 A. Two Vessels 题意 有两杯水，一杯有a毫升，另一杯有b毫升，被子的容积无限大。另外还有一个容量为c毫升的杯子，可以用这个杯子在前两个杯子之间舀水，问最少需要几次可以令前两个杯子内的水一样多，舀水的时候不必舀整数毫升。 样例输入 6 3 7 2 17 4 3 17 ......

设 \(m\) 次选的位置分别为 \(b_{1\sim m}\)。 于是答案为 \(\mathbb E(\prod\limits_{i = 1}^{n}(a_i + \sum\limits_{j = 1}^{m}[b_j \le i]\cdot v)) = \frac{S}{n^m}\)。 首先考虑 ......

CF1322E - Median Mountain Range 考虑分别对每个位置求出最后的数字。先枚举出这个数 \(x\)，并将 \(a_i \ge x\) 的数设为 \(1\)，\(a_i < x\) 的数设为 \(0\)，然后做题目中的操作，若为 \(0\)，则最终结果小于 \(x\)，为 \ ......

LEGOndary Grandmaster https://www.luogu.com.cn/problem/CF1615F 神题！看到题解一眼就知道自己大概率想不出来了。 主要还是积累两个套路： Trick 1 考虑将原序列的奇数位位置上的数取反，惊讶地发现操作简化为了每次交换相邻两个数。显然地， ......

此篇题解可以通过 \(1\le t\le 2\times10^5,1\le n,k\le10^{18}\) ，不保证 \(\sum n\le2\times 10^5\) 的数据（绝对不是因为没仔细看数据范围）。 题意 \(t\) 组询问，每组给出 \(n\) 和 \(k\)，求有多少个单调不递减且非 ......

题意 给出具有依赖关系的 \(n\) 个任务，每个任务只能在某一天的第 \(h_i\) 小时做。只要满足了依赖关系，一个小时可以做很多任务。求最小的完成时间。 分析 结合题目条件，很快发现这是一个有多个联通块的 DAG。 拆分一下问题，先考虑怎么求单个联通块的所有开始时间和结束时间，然后再合并起来。 ......

题面 给出一个大小为 \(n(1≤n≤10^5)\) 的三角形图（\(n=3\) 时如图），每个方向有 \(n\) 层由有向边构成的路径。可以翻转任意条边的方向，求把让图中每个点都可以到达其他所有点的最小翻转次数。 分析 注意到一个关键点：内部的一排点构成一条路径。这意味着如果外围成环，那么整个图满 ......

分析 很明显，有一个贪心的性质，对于每一次选择路线，一定会选择从当前点能走得最远的一条。 这样就得到了一个暴力做法：预处理好每个点向祖先走得最远的一条路，对于每次询问，两个点暴力上跳，在最近公共祖先处特判一下是否可以一下走完即可。 考虑优化这个过程，找最近公共祖先和上跳都可以倍增处理。唯一的问题是最 ......

分析 遇到难的题都可以考虑一下弱化版。对于这道题，弱化版很简单，就是排序后对应位置的点匹配。那么加入限制后，可能就会需要微调一下（这种微调的想法也是很有价值的）。 考虑什么时候会需要调整，无非就是匹配到了自己的马。既然要调整，那必然会和另一个人的马交换，在这个基础上，还希望距离原来的尽可能近。 不妨 ......