题解1071 cf

## 思路 CF 典型的诈骗题。 假设分出来的 $a$ 和 $b$ 都有因子 $k$，那么 $a+b$ 也一定有因子 $k$，并且至少还存在另一个最小为 $2$ 的因子，才能分出 $a$ 和 $b$。 所以可以发现，质数是不满足要求的，考虑一个合数，一定可以拆成 $k\times a$ 的形式，那么 ......

## 思路 假设第 $0$ 时刻走进有陷阱的房间，那么必须在第 $t_i$ 时刻前返回到这个房间之前，因为出去还需要回来，假设到达这个房间后的第 $k$ 个房间，那么到达需要 $k$ 的时间，回来需要 $k+1$ 的时间，因为陷阱会困住当前在房间里的人，所以我们需要提前回去。 那么如果走到一个有陷阱 ......

## Description 奶牛旅馆可以被看作一个 $N$ 个节点 $M$ 条边的无向简单图，其中每个房间有一个颜色 $C_i$，以及一个钥匙，颜色为 $S_i$， FJ 最初在 $1$ 号节点，手上一把钥匙都没有。 FJ 可以进行无数次以下操作： - 捡起当前房间的钥匙。（FJ 可以同时手持多个 ......

### A 诈骗题，看起来有点高大上，其实只要将$k$减$1$即可。 ### B 此时序列中的递增子序列是不需要移动的，所以此时本题就满足一个贪心，设不在这个递增子序列中的数的个数是$x$,则答案为$\lfloor \frac{x}{k} \rfloor$ ### C 这破比赛怎么这么喜欢排列。 此 ......

双倍经验 [CF559C](https://www.luogu.com.cn/problem/CF559C) 前置知识：网格图内任意两点间的路径数量。这个我们可以通过组合数的方法计算出来。假设我们从点 $(1,1)$ 走到点 $(i,j)$，在这个过程中我们的移动步数是 $|i-1+j-1|=|i+ ......

被 C 卡了。 最后被 E 的各种分讨劝退，但是同时也学习到了一种换根 dp 的简单写法。 评价：It's educational for me. ## A.Typical Interview Problem ### 题目描述： 有一个包含 F 和 B 的字符串，最开始是空的。我们开始从 $1$ 向 ......

## 前置知识： ### 1. [P3376 【模板】网络最大流](https://www.luogu.com.cn/problem/P3376) ### 2.[P4897 【模板】最小割树（Gomory-Hu Tree）](https://www.luogu.com.cn/problem/P489 ......

第一步 安装FastOlympic插件和Fira Code字体 安装FastOlympic插件和Fira Code字体 第二步 配置competitive-companion和另一个插件来爬取测试数据 U173674 注意是在C盘下，然后就能愉快地用sublime打洛谷cf啦 rp++ ......

[原题](https://codeforces.com/problemset/problem/1266/D) [翻译](https://www.luogu.com.cn/problem/CF1266D) 其实这题的翻译反而不如原题好理解，建议先阅读原题后重新思考做法 $$ \large{\color ......

## [C. Game on Permutation](https://codeforces.com/contest/1860/problem/C) 这道题需要求出**先手必胜**点 通过分析可知，每个位置结尾的最大上升子序列长度为**2**的点为先手必胜点，**≥3**的点为先手必败点。即只需要求 ......

## [Fancy Coins](https://codeforces.com/contest/1860/problem/B) 这道题使用贪心。 先使用***a1***个常规硬币，补足**m%k**的金额，不够的使用花色硬币补上，并最大化***a1***硬币的价值。再计算剩余需要价值为**k**的硬 ......

## [A. Not a Substring](https://codeforces.com/contest/1860/problem/A) 这道题为简单构造题 只需要考虑给出的字符串***s***是否为“**()**”的必要组成成分 * 若是则无法生成，输出NO。 * 不然就判断给出的字符串*** ......

某网站的题解标点符号的要求真是a piece of bloody shit. 在这里会自由一些. ## 0. 题目大意 题目的大意是模拟黑白棋游戏。简单而言有如下的要求： - 列出可能的移动。合法移动的规则是：新下的棋子必须 "夹住" 原来的。所谓夹住，其实就是一段横向、竖向、斜向的棋子之间的两段必 ......

# CF893F 首先，我们发现，这个题只需要子树内的答案，且只需要维护最小值。 注意到对于两个点 $i,j$，若 $dep_i>dep_j$，且 $val_i\ge val_j$，则对于 $lca(i,j)$ 及其它的父亲，$i$ 都是一个无用的点。 注意到 $n\le 10^5,m\le 10^ ......

# AtCoder Beginner Contest 308 A~G ## A. New Scheme ```cpp void Main() { vector a(8); for (auto &x : a) cin >> x; if (!is_sorted(a.begin(), a.end()) & ......

# CF1374E2 Reading Books(hard version) 这道题是在 [CF1374E1 Reading Books(easy version)](https://www.luogu.com.cn/problem/CF1374E1) 的基础上出的，而且仅仅增加了一个 $m$ 的限 ......

[原题](https://codeforces.com/problemset/problem/1054/C) [翻译](https://www.luogu.com.cn/problem/CF1054C) $$ \large{\color{#ff0000}{\text{被xjk搏杀了，%%%}}} $ ......

[题目链接](https://www.luogu.com.cn/problem/P5021) 挺综合的一道题目。 询问最小值最大，考虑二分最小值，二分上下界是 $[最小边权,树的直径]$，但是为了方便我们直接设为 $[1,5\times 10^8]$ 即可。 考虑如何 $check$，可以采用类似树 ......

# CF1328E Tree Queries ## 题意 给定一棵以 $1$ 为根节点的有根树。 现在有 $q$ 次询问，每次询问给定 $m$ 个节点，问是否存在一条从根节点开始的链，使得每个节点到这条链的距离不超过 $1$ 。 ## 思路 我们首先可以给出一个结论：如果节点 $v$ 与一条链的距离 ......

题目链接：[https://hydro.ac/d/bzoj/p/3732](https://hydro.ac/d/bzoj/p/3732) 题目大意： 给定一个图，每次询问两个点 $u$ 和 $v$，在 $u$ 到 $v$ 的所有路径中找一条路径，且这条路径上的所有边的边权最大值最小。 解题思路： ......

# CF1835 题解 ### A 考虑到 $a,b,c > 3$ 的最多只有 $5$ 个，可以直接循环枚举 $A$ 。首先将 $B$ 取到最小值，然后判断 $C$ 是否达到了最小值，如果没有就将 $B$ 和 $C$ 同时补齐。此时特判如果 $C$ 大于上限（就是 $\geq 10^{c}$ ），就 ......

# 9.6 CF1830 题解 ## A. Copil Copac Draws Trees [链接](https://www.luogu.com.cn/problem/CF1830A) 真弱智题不用讲 ## B. The BOSS Can Count Pairs ### 题意 每组数据给你一个 $n ......

[题目链接](https://codeforces.com/problemset/problem/665/F) ## description 给定 $n\leq 10^{11}$ 求 1 到 $n$ 中恰有 4 个因数的数的个数。 ## solution 这个数据范围容易想到筛子。 题目相当于让求 ......

[题目链接](https://codeforces.com/problemset/problem/1036/F) ## description $10^5$ 次询问 每次给定 $n\leq 10^{18}$, 求 2 到 $n$ 内质因子分解结果为 $p_{a_1}^{b_1}p_{a_2}^{b_ ......

[题目链接](https://codeforces.com/problemset/problem/1174/E) ## description 给定 $n\leq 10^6$, 求有多少个 $1$ 到 $n$ 的排列，对于一个 1 到 $n$ 的排列 $p$，$f(p)$ 表示 $p$ 的任意前缀内 ......

*2400 https://codeforces.com/problemset/problem/1852/C 如果没有 $\mod k$ 的限制的话，我们都会做，因为都是正数，那么 $\sum_i^n d_i>0$，因此，答案即为 $\sum[d_i>0]d_i$。 但是现在多了一个操作，即为区间加 ......

低情商：感觉是比较套路的 高情商：十分 educational！！！ ## CF258D Little Elephant and Broken Sorting ### 题目描述： 有一个 $[1,n]$ 的排列 $a$，会进行 $m$ 次操作，操作为交换 $(a_i,a_j)$。每次操作都有 $50 ......

# 驯龙高手 题解 原题题目不是这个但是我实在看不懂他起的这个题目是什么含义所以就重新起了。题目里的主角的名字我也换成了一个朋友的设定名字。 ## 题目描述： 咪唑有 $n$ 条龙 ，第 $i$ 条龙的力量值为 $x_i$。咪唑想与这些龙交朋友。 但是龙很好斗，如果咪唑交上的朋友中，有两条龙力量值不 ......

[题目链接](https://www.luogu.com.cn/problem/AT_arc032_3) 只和区间相对位置有关，先离散化。时间点上倒序贪心，设 $f_i$ 表示第 $i$ 个时间点最多能选几个区间，$g_i$ 表示在最大 $f_i$ 的前提下转移过来最小的字典序标号，可以顺便记录前驱 ......

发现直接做非常困难，考虑将能力值排序后从小到大插入。 令 $f_{i,j,l}$ 表示前 $i$ 个人，有 $j$ 组需要继续加人，不和谐度之和**恰好**为 $l$ 的方案数。此时加入一个人对不和谐度之和产生的贡献为 $t=j\times(a_{i+1}-a_i)$。分三种情况转移： - 组数加一 ......