## 六年级 第一次接触信竞。 当时是罗俊辉在教我们，罗俊辉教的真的不评价，一直考试考试，我当时经常垫底，主要是一进去就和比我大一届和大两届的一起训练。虽然考试经常垫底，但是感觉每次训练都很开心，当时真的觉得信竞很有趣，一有时间就跑去机房。 后来打第一场csp，好像初赛差了4分还是3分，有点可惜。当时挺不开心的，居然没…

## [题目传送门](https://www.luogu.com.cn/problem/P2157) ## 题目大意 有 $n$ 个学生，每个学生有一个时间 $t_i$，所花费的真实时间为 $t_i$ 异或上前一个吃饭的同学的 $t_i$。每个学生有一个忍耐度，最多可以让后面 $b_i$ 个同学比自己先吃饭。问在不违反…

## 前置算法 二分，动态规划 ## 题目分析 我们先考虑怎么暴力 $dp$，因为每次只能往右或者往下，那我们定义 $dp_{i,j}$ 表示从 $(x_1,y_1)$ 走到 $(i,j)$ 的最小权值总和，转移如下： $$ dp_{i,j}=\min(dp_{i-1,j},dp_{i,j-1})+a_{i,j} $$…

## 前置算法 并查集 ## 题目分析 首先想到删边不好维护。就应该想到把操作离线下来，按 $k$ 从大到小排序，这样删边就转换成了加边，很好维护。每次只需要把边权大于等于 $k$ 的边加入图中，再用并查集维护一下联通快即可。 考虑处理连边操作，每次连边都会让 $a$ 和 $b$ 两个点的度数都加一，我们先判断它们连边…

## [题目传送门](https://www.luogu.com.cn/problem/P4350) ## 题目大意 给出一个 $n$ 个点 $m$ 条边的无向图，每一条边有边权。每次会给出一个数 $k$，先把所有边权小于 $k$ 的都删去。再重复进行一个操作，依照编号从小到大进行操作，如果第 $i$ 个点度为 $0$…

## [题目传送门](https://codeforces.com/problemset/problem/1413/F) ## 题目大意 给出一颗树，每一条边的边权位 $0$ 或 $1$，一共有 $m$ 次修改，每次对一条边的边权取反，每次修改后求出树上最长的一条路径使得路径异或和为 $0$。 ## 解题思路 首先有一…

## [题目传送门](https://www.luogu.com.cn/problem/CF1819D) ## 题目大意 给出 $n$ 个集合 $S_i$，每个集合有一个大小 $siz_i$ 和集合中的数，如果 $siz_i=0$ 表示这个集合可以为 $1\sim m$ 的任意可空子集。现在有一个操作，从第一个集合开始…

## [题目传送门](https://www.luogu.com.cn/problem/AT_arc163_d) ## 题意 给出 $n$ 和 $m$，表示有一个 $n$ 个点的竞赛图，要求从编号小的点向编号大的点的连边恰好 $m$ 条，询问在所有满足条件的竞赛图中，强连通分量的个数之和。 ## 分析 首先要知道什么事…

## [题目传送门](https://www.luogu.com.cn/problem/AT_abc306_h) ## 题意 给出一个无向图定向，有三种定向方式，分别是 $u->v$ 和 $v->u$ 和 $u=v$，要求最终的图是一个有向无环图，求出所有合法的定向图的数量。 ## 思路 首先我们先考虑这道题的简单版本…

## [题目传送门](https://www.luogu.com.cn/problem/AT_agc019_d) ## 题意 给出两个 $01$ 序列 $A$ 和 $B$，有三种操作：把序列 $A$ 左移一位，把序列 $A$ 右移一位，选择序列 $B$ 中的一个位置 $i$，满足 $B_i=1$，把 $A_i$ 变成…

在文章《题解：CF1225F Tree Factory》发表评论：

长链剖分时判断的if语句中是siz[v]>siz[son[u]]

## [题目传送门](https://www.luogu.com.cn/problem/P4516) ## 题意简述 给出一颗树，有 $k$ 个传感器需要装到树的节点上，每一个传感器可以控制与当前节点距离为一的所有节点，但是不能控制当前节点，询问在这颗树上布置满 $k$ 个传感器且控制树上所有节点的合法方案数。 ##…

## [题目传送门](https://www.luogu.com.cn/problem/CF2048F) ## 题目大意 给出两个序列 $A$ 和 $B$，每次操作可以选择一个区间 $[l,r]$，记 $x$ 为序列 $B$ 在这个区间内的最小值，把 $A$ 区间对应的位置上的数都除以 $x$ 向上取整，求把 $A$…

## [题目传送门](https://www.luogu.com.cn/problem/CF1225F) ## 题意 给出一棵树，要求构造一条链，和一个操作序列，使得经过这些操作后，这条链可以变成给定的树。只有一种操作，把自己变成自己父亲的兄弟，即断开自己和父亲的连边，和父亲的父亲连边。 ## 思路 考虑到正着做不好做…

## [题目传送门](https://www.luogu.com.cn/problem/CF878C) ## 题意 有 $n$ 个人和 $k$ 个项目，要求每次比赛会随机选两个人，在一个随机项目上比拼，在该项目上能力值较小的人会被淘汰，直到剩下一个人，那么他就是冠军。现在要求求出只有前 $i$ 个人时，冠军的可能数量。…

## [题目传送门](https://www.luogu.com.cn/problem/CF1651F) ## 题目大意 给出 $n$ 个塔，排列在数轴 $1\sim n$ 的位置上，每个塔有一个魔力值上限 $c_i$ 和一个恢复速度 $r_i$，每秒魔力值 $a_i$ 会变成 $\min(c_i,a_i+r_i)$…

## [题目传送门](https://www.luogu.com.cn/problem/AT_arc076_d) ## 题目大意 给出 $m$ 把椅子，排在数轴 $1\sim m$ 的位置上，有 $n$ 个人，每个人对自己坐的位置有要求，这个人不能坐在 $l_i\sim r_i$ 的位置上，其余都可。 ## 题目分析…

## [题目传送门](https://www.luogu.com.cn/problem/CF954H) ## 题意 给出一颗树，树的每一层的节点的儿子数目相同。求出当 $k$ 等于 $1 \sim 2\times n-2$ 时，树上有多少条不同路径满足路径长度等于 $k$。 ## 思路 一道非常有意思的推式子题。 首先…

## [题目传送门](https://www.luogu.com.cn/problem/CF1647F) ### 题意 给定一个长度为 $n$ 的序列 $a$，要求把这个序列分成两个子序列使得这两个子序列都为单峰序列，问有多少种划分方案，两种划分方案不同时，当且仅当存在一个序列的峰值不同。 ### 思路 注意到，序列中…

## [题目传送门](https://www.luogu.com.cn/problem/CF1720E) ## 题意 给定一个大小为 $n\times n$ 的矩阵，每个位置上有一个数字 $a_{i,j}$，每次操作可以选择一个子矩阵，将子矩阵中的所有数字变为 $0$ 到 $n\times n$ 中的任意一个数，求满足…

# [题目传送门](https://www.luogu.com.cn/problem/P8339) ## 题意 给出一棵树，树上每个节点有一把钥匙或宝箱，钥匙和宝箱都有颜色，颜色要一一对应才能打开宝箱。现在给出 $m$ 趟旅程，每次给定 $s$ 和 $t$ 求一路上最多能开多少宝箱。 ## 思路 注意到每种颜色之间互不…

## [题目传送门](https://www.luogu.com.cn/problem/CF543B) ### 题目大意 求两对点的路径中重复的部分的最大值。 ### 解法 首先要求出全源最短路，可以用 `bfs` 做到 $O(nm)$ 的复杂度。 然后考虑枚举重合部分的左右端点 $x$ 和 $y$。为什么只可能有一个…

## [题目传送门](https://www.luogu.com.cn/problem/CF49E) ### 题目大意 给出两个字符串，给出 $n$ 种转换方式，求出两个字符串通过若干次转换后，能变成的最短的且相同的字符串长度。 ### 思路 注意到 $n\le 50$，所以我们考虑区间 $dp$。先预处理出一个 $v…

## [题目传送门](https://www.luogu.com.cn/problem/CF33D) ### 题意 给出 $n$ 个坐标，给定 $m$ 个互不交叉的圆，给出 $k$ 个询问，每次询问两个坐标的连线与圆有多少个交点。 ### 思路 注意到 $n$ 和 $m$ 的范围都很小，所以我们可以枚举所有圆和坐标，定…

## [题目传送门](https://www.luogu.com.cn/problem/CF207B3) ## 题目大意 每个坦克有一个接收半径 $r_i$，每次要从最前面的坦克把信号传给最后一个，最后一个在跑到前面来，重复执行，每两个坦克之间传输信号所需时间为 $1$，求总的最小时间。 ## 思路 考虑 $n\le…

## [题目传送门](https://www.luogu.com.cn/problem/CF182C) ### 题目大意 有一个长度为 $n$ 的数列 $a$，可以对它进行最多 $k$ 次操作，每次操作可以将一个数变为它的相反数，输出最后所有长度为 $len$ 的数列的和的绝对值的最大值。 ### 思路 根据贪心，我们…

## [题目传送门](https://www.luogu.com.cn/problem/CF279C) ### 题目大意 给出一个数列，每次询问一段区间 $[l,r]$，判断这段区间中的数是否能组成一个山峰。 ### 思路 注意到，题目中的山峰是不一定要单调递增和递减的，是先不降后不增的，即平地也属于山峰。我们考虑两种…

## [题目传送门](https://www.luogu.com.cn/problem/CF269C) ### 题目大意 给出一个无向图，给出每条边的流量，要求给每条边定向，使得这个图成为一个合格的网络流图。 ### 思路 因为最终的图一定是一个有向无环图，所以我们可以使用拓扑排序来解决这个问题。首先，求出经过每条边的…

## [题目传送门](https://codeforces.com/gym/619107/problem/E) ### 题意 给定一个排列，有两个人轮流操作，第一个人每次可以减少一个逆序对，第二个人每次有 $50\%$ 的概率减少一个逆序对，也有 $50\%$ 的概率增加一个逆序对，求让这个序列不含逆序对的最小操作期望…

## [题目传送门](https://codeforces.com/gym/619107/problem/C) ### 题意 给出一个长度为 $n$ 的序列 $a$，有 $m$ 个集合，每个集合包含原序列中的 $s_i$ 个元素，元素所对应的在原序列中的下标分别是 $p_{i,1},p_{i,2},...,p_{i,s…