divisor 1864c chain cf
CF1826F
[原题](https://codeforces.com/contest/1826/problem/F) [翻译](https://www.luogu.com.cn/problem/CF1826F) 一道很~~难想~~巧妙的交互题 首先如果他给出点的顺序是有序的,那我们显然可以问一个与$x$轴平行的和 ......
【拆贡献】CF1422F Boring Queries
考虑质因数分解,我们求区间的 $lcm$ 就是 $\prod a_i$ 除以一些东西。 不难发现如果算 $x^k \in lcm$ 那么我们只能算一次,那么我们直接把这个东西挂在前一个出现的位置即可。 使用主席树维护即可。这个题,很难。 ```cpp // LUOGU_RID: 123092767 ......
CF1826E
[原题](https://codeforces.com/contest/1826/problem/E) [翻译](https://www.luogu.com.cn/problem/CF1826E) ~~傻卵~~$bitset$题 高位偏序,直接套CDQ分治显然不可行 但是解决高维偏序还有一种常见的 ......
CF1826D
[原题](https://codeforces.com/contest/1826/problem/D) [翻译](https://www.luogu.com.cn/problem/CF1826D) 这题乍一看不太好做,当时还想了单调栈或改变枚举顺序之类的做法,但都不可做 但仔细一想,我们发现答案的$ ......
CF1851F - Lisa and the Martians
## 题目描述 Lisa was kidnapped by martians! It okay, because she has watched a lot of TV shows about aliens, so she knows what awaits her. Let's call inte ......
CF1586 f1,f2 Korney Korneevich and XOR 思维+dp
## CF1586 f1 f2 Korney Korneevich and XOR 思维+dp ### [题目链接](https://codeforces.com/problemset/problem/1582/F2) ### 题意: 给出长度为n的数组a,对于数组的严格递增子序列,计其异或和为xo ......
【1165D】Almost All Divisors(数论)
**题目大意:** 给出一个数的所有因数(除了$1$和这个数本身),判断这个数是否存在。 *** 先将所有因数排序,然后计算最小因数和最大因数的积,我们设这个数为$x$。 如果$x$满足了以下的任意一个条件,则答案为不存在: 1. 存在一个$k$,第$k$大的数和第$k$小的数之积不等于$x$。 2 ......
【CF1519D】Maximum Sum of Products
```cpp #include using namespace std; typedef long long ll; ll n,a[5000+10],b[5000+10],abpre[5000+10],absuf[5000+10],ans; int main(){ cin >> n; for(ll ......
CF1385 F. Removing Leaves 换根dp
## CF1385 F. Removing Leaves 换根dp ### [题目链接](https://codeforces.com/problemset/problem/1385/F) ### 题意: 给你一棵树,有一种操作,选择k个叶子,若叶子节点的父亲相同,则可删去这k个节点,问你最多能操作 ......
CF231E Cactus
[CF231E Cactus](https://www.luogu.com.cn/problem/CF231E) 点仙人掌的性质:每个点最多只在一个环里。 ![image.png](https://s2.loli.net/2023/08/28/JBc4Dr8FA5imX6R.png) 对于 $u,v ......
CF1864F. Exotic Queries
我 是 傻 逼。 先不管那个限制。如果有一个序列 $a$,怎么求答案? 假设我们一个一个减,那么答案就是序列长度;但是,我们不一定会一个一个减:如果有 $x 点击查看代码 ```cpp #include #define int long long using namespace std; const ......
[CF1830D] Mex Tree
[CF1830D](https://www.luogu.com.cn/problem/CF1830D) 贪心地想,黑白交替染色,这样每条大于1的路径的值都为2。但有些情况不优,树的形态是两棵子树中间由一条边相连,这样的最优方案是这条边上两点染1,其余点染0。 并且我们发现只用把每个同色连通块的贡献算 ......
CF1763F Edge Queries
[CF1763F Edge Queries](https://www.luogu.com.cn/problem/CF1763F) 圆方树板子题,~~这题真的有3000吗~~。 首先想到的是缩边双,但是以下情况边双不好处理: ![image.png](https://s2.loli.net/2023/ ......
CF1864C
记录一道昨天卡住的题[问题链接](https://codeforces.com/contest/1864/problem/C) 给你一个整数$n$,你可以进行最多$1000$次操作,使得$n$减去它的一个因数,要求每种减数至多出现两次 我们考虑先把$n$进行质因数分解,得到质因数序列$P$ $\{ ......
CF1444A Division
## 思路 首先特判特殊情况,若 $p_i$ 本身不可被 $q_i$ 整除,那么 $x_i$ 就直接取 $p_i$ 最大。 否则的话,$p_i=q_i\times k$。所以 $q$ 的质因数,$p$ 都有,并且数量一定大于等于 $q$ 的这个质因数的数量。 那么如果 $x_i$ 的某个质因数个数小 ......
CF1823C Strongly Composite
## 思路 我们可以思考一下什么样子的合数是强合数。 首先一个数可以表示为 $p_1^{c_1}\times p_2^{c_2}\times \cdots \times p_x^{c_x}$。 那么这个数的约数个数为 $s=(c_1+1)\times (c_2+1)\times \cdots \ti ......
CF1423K Lonely Numbers
## 思路 因为对于 $\gcd(a,b)$,$\frac a{\gcd(a,b)}$,$\frac b{\gcd(a,b)}$ 中 $a$ 和 $b$ 是等价的,可以交换的。所以我们先令 $a>b$。 令 $\gcd(a,b)=d$,因为 $\frac a{\gcd(a,b)}$ 有除法,所以我们 ......
CF1862G The Great Equalizer
## 思路 对于一个数组,每次操作会缩短排序后的数组的相邻两个数的差距,所以总共会执行 $k$ 次操作,其中,$k$ 为排序后的数组的相邻两个数的最大差距。 因为每次操作都会对最大数加 $1$,所以答案就是 $\text{数组中的最大数} + \text{排序后的数组的相邻两个数的最大差距}$。 因 ......
CF1862F Magic Will Save the World
## 思路 假设总共耗时是 $s$ 秒,那么最多可以消灭的总生命值是 $s\times(w+f)$。 所以我们可以先求出所有怪物的生命值之和 $sum$,那么,至少需要时间 $t=\lfloor \frac{sum}{w+f} \rfloor$。 然后我们可以算出用这些时间最多可以用水魔法消灭的生命 ......
CF3C Tic-tac-toe
AC 后逛了逛题解,发现好像自己的代码比大佬都短很多? ## 思路 数据范围很小,先暴力求得 ```X```,```0```,```.``` 的个数,然后暴力求得连着的三个 ```X```,```0``` 的个数。 然后,我们来分类讨论: - 非法的情况一定优先判断,只有不非法才可能是其他情况,那么 ......
CF979D Kuro and GCD and XOR and SUM
### 题目大意 初始有一个空的集合,和 $Q$ 个操作。对于每个操作,有两种类型,分别用如下的两种形式表示: `1 u`:加入 $u$ 到集合 `2 x k s`:求一个最大的 $v$,使得: 1. $v+x \leq s$ 2. $k \mid \gcd(v,x)$ 3. $x \oplus v ......
CF894 div3
### A. Gifi Carpet 给一个n行m列的字符矩阵,问能否找到四列,第一列中要有字符'v' , 第二列要有字符'i' , 第三列要有字符'k',第四列要有字符'a'. $1 using namespace std; char s[30][30]; void Solve() { int n ......
【主席树】CF813 E. Army Creation
# 【主席树】CF813 E. Army Creation 题目链接:https://codeforces.com/contest/813/problem/E ## 题意 多次询问,求一个区间内,所有数个数的总和,但相同的数最多被计算k次,强制在线。 ## 题解 这道题和牛客一道题很像,是那道题的加 ......
CF1801 题解
## A 首先考虑 $4\times 4$ 的矩阵构造。 $$\begin{bmatrix}0 & 1 & 4& 5 \\ 2 &3 &6 &7 \\ 8 & 9 & 12 & 13 \\ 10 & 11 &14 & 15 \end{bmatrix}$$ 我们发现每个矩阵的异或和都是 $0$,那么不 ......
CF626F 题解
简要题意: 有$n$个学生,每个学生有一个能力值$a_i$。现在要把这些学生分成一些(任意数量的)组,每一组的“不和谐度”是该组能力值最大的学生与能力值最小的学生的能力值的差。求所有不和谐度之和不超过$k$的分组方案总数。 首先,无论我们怎么选,每个组的不和谐度只与他们组内的能力值最大者和能力值最小 ......
CF1858D Trees and Segments
[一道考查预处理技巧的 dp。](https://codeforces.com/problemset/problem/1858/D "一道考查预处理技巧的 dp。") 观察式子 $a\times L_0+L_1$,一个显然的想法是“定一求一”,即预处理求出对于每个 $L_1$ 最大的 $L_0$,然 ......
【题解】CF1413C Perform Easily(双指针)
# 【题解】CF1413C Perform Easily 写篇题解水水经验~顺便增加一下 RP~ 比较套路和简单的一道绿题。 ## 题目链接 [Perform Easily - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/prob ......
[CF1794E] Labeling the Tree with Distances 题解
# [CF1794E] Labeling the Tree with Distances 题解 ## 题目描述 给你一个树,边权为 $1$。给定 $n-1$ 个数,你需要将这些数分配到 $n-1$ 个节点上。 一个点 $x$ 是好的,当且仅当存在一种分配方案,所有被分配数的点到 $x$ 的最短路径长 ......
CF1746F
[题目链接](https://codeforces.com/problemset/problem/1746/F)。 这个数据范围,显然出题人出这题的本意不是让我们用带修莫队过题(当然有人过),而我们又难以找到很好的 $\text{DS}$ 维护方法。 故考虑另辟蹊径。对于所有 $a_i,x$,不妨把 ......