little 1333a artem cf

`2023-07-18 20:49:31` ## 思路： 一开始的思路是每次存两个值，因为任意两个斐波那契数列合并之后仍然满足斐波那契的基本性质 $f[x]=f[x-1]+f[x-2]$。 但是发现这样子每次修改直接的总和得暴力递推求，复杂度爆炸。 为了解决这个突破口，稍微借鉴了一下题解的斐波那契数 ......

`2023-07-19 10:59:11` 思路来源于题解:https://www.luogu.com.cn/problem/solution/CF1806E 算法：根号分治+记忆化搜索。 因为每一个查询都是同层的，我们可以只记忆层数少的（小于$\sqrt n$）,对于层数多的层，如果大于$ \sq ......

`2023-03-01 16:50:41` ```cpp #include using namespace std; typedef long long ll; inline ll read(){ ll x=0;char c=getchar(); for(;!isdigit(c);c=getchar ......

一道贪心题。 根据题意，我们需要在原序列中找出一条从 $1$ 到 $n$ 的路径，这条路径能被分成几个长度为 $k$ 且颜色相等的连续段。我们可以将这个问题简单化，那么这个问题就能被转化为从 $1$ 开始向后找一个颜色连续段，从 $n$ 开始向前找一个颜色相同的连续段，只要这两个连续段不相交即可，代 ......

我们首先可以观察到这道题的 $m$ 很大，所以要考虑这么多列里面是否存在一个性质，让我们求出前 $n$ 列之后快速求出后 $m$ 列的答案。观察一下可以发现第 $i,j$ 两列的答案等价时满足 $i \equiv j \pmod n$。这样的话我们只需要求出前 $n$ 列的答案即可。记 $s_i$ ......

这道题显然是一道 dp。转移方程式也很好推，我们记 $f_{i,j}$ 为前 $i$ 位且第 $i$ 位为 $j$ 的 DNA 序列数量。而对于输入的字符串，我们用 $vis_{i,j}=0$ 表示第 $i$ 个字母后面不能放第 $j$ 个字母。那么转移方程式即为： $$f_{i,j}= \sum ......

# CF1178F1题解 根据题意，每次选择一个区间染色，我们可以发现这道题满足了区间 dp 的一些性质，即区间答案可以合并，大区间的答案可以由小区间的答案更新而来。那么我们就可以设 $f_{i,j}$ 表示区间 $i$ 到 $j$ 的答案，那么接下来就考虑如何转移。然后考虑到题目要求从 $1$ 到 ......

显然，我们可以先忽略两个串已经一样的部分，只考虑剩下不一样的部分，然后我们就可以将它抽象成一个链上游走问题。我们记 $g_i$ 为从第 $i-1$ 个到第 $i$ 个点的期望步数，此时 $g_1=1$。且 $g$ 满足： $$g_i=\frac{n}{n-i}+\frac{i \cdot g_{i- ......

题目传送门——[Long Number](https://www.luogu.com.cn/problem/CF1157B) ## 简单思路 由题意得我们要改变一个区间内的数，使得最后的结果最大，所以显而易见，根据数学规则，位数越高的数越大，最后的数越大，所以我们要尽可能早的开始更改数字，所以当我们 ......

## [B. The Corridor or There and Back Again](https://codeforces.com/contest/1872/problem/B) 由题意可知，对于每一个***d~i~***和***s~i~***，必须要在进入房间***d~i~***的***s~i ......

## [A. Two Vessels](https://codeforces.com/contest/1872/problem/A) 简单题。先计算杯子a和杯子b里水的差值，在计算需要用c杯子舀几次水就行 $$Ans=ceil(|a-b|/2c)$$ #### 代码 ```cpp #include ......

[比赛链接](https://codeforces.com/problemset/problem/1829/H) # 题解 **知识点：线性dp，位运算。** 考虑设 $f_{i,j}$ 表示考虑了前 $i$ 个数字，与和为 $j$ 的方案数。转移方程显然。 注意初值为 $f_{0,63} = 1$ ......

[比赛链接](https://codeforces.com/problemset/problem/1833/F) # 题解 **知识点：组合数学，枚举，双指针。** 注意到，长度为 $m$ 且数字各不相同的子序列，那么最大值与最小值的差至少为 $m-1$ 。因此，对于任意子序列，它是合法的，当且仅当 ......

[题目链接](https://codeforces.com/problemset/problem/1850/H) # 题解 **知识点：贪心，图论建模。** 考虑对约束 `a b d` 建边 $a \mathop{\to}\limits^d b$ 与 $b \mathop{\to}\limits^{ ......

## 思路 又又又是一道 CF 诈骗题。 对于 $x$ 选出来的数，我们尽量放大的，对于 $y$ 选出来的数，我们尽量放小的，但是呢，存在同时被 $x$ 和 $y$ 选出来的数，就随便放。 但是可以发现按照题目给的数据范围，这么找选择的数，然后放最大或者是放最小，肯定是超时。 所以我们可以直接算出有 ......

## 思路 一眼顶真，这不就是线段树吗？还挺板的，然后速打了一个线段树。 就是用两个变量分别存这个区间的两个异或值，修改就是交换这两个变量的值，询问都是询问整体的，应该很好写，就不细讲了。 ## AC code ```cpp #include using namespace std; struct ......

## 思路 对于每一个动物，我们都尽量让它比它害怕的动物先被卖。 考虑拓扑排序，每次输出出度为 $0$ 的点，然后再删点删边。 但是 $n$ 个点，$n$ 条边，必然存在环，所以只用拓扑排序是不行的。 自然想到 tarjan 缩点，对于环外，就拓扑排序好了，对于一个环，显然无法满足所有的点，所以我们 ......

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

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

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

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

第一步 安装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。 * 不然就判断给出的字符串*** ......

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

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

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

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