CF Round: GoodBye2022 题解参加了孟爷爷的蓝桥杯训练营，奉旨写题解（本套题是CF的2022告别题，没有现场打，但既然要作为蓝桥杯的练习，那自然要用java多熟悉一下用java来写算法辣（u1s1 用Java写算法是真的蛋疼经过孟爷爷评测，本场的难度是div1+2，是打不过的难度，

概念状态压缩是一种利用二进制数来对状态进行压缩的方式。状态压缩之后，我们可以通过整数的加减来表示状态之间的转移。整数和状态一一对应。一般而言，状态压缩用于解决非常多阶段的动态规划问题。二进制状压的可以将状态数压至 $ 2n * n $ ，时间复杂度为状态数X决策数n，所以时间复杂度为 $2n*n^2

快速幂快速幂用于快速计算指数（$$2^n$$），主要思想是二分。由于计算机计算单个乘法比多个乘法快得多，所以利用二分的思想来减少乘法运算次数可以提高速度。例：$$7{10} = 777*...*7$$ 需要计算9次乘法，而先计算$$75$$再计算$$7{10}$$，就只用计算$$75 = 77777

翻洛谷的时候发现好多例题都做过，但谁让我过了两年啥都记不得了呢，只能复(预)习一下了（ 笑二分查找二分查找是一种利用二分的思想快速在有序数列里查找指定数位置的方法。模板题：P2249 【深基13.例1】查找 - 洛谷 | 计算机科学教育新生态当然这个题要求用C的unsigned int而java没有

动态规划-java语言练习一：暴力DP重新进行算法的一个卷，主要复习高二学的动态规划知识（练习题目参考洛谷提单：【动态规划】普及~省选的DP题 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)练习暴力DP主要是先找回DP的感觉，练习推转移方程。T1. 乌龟棋 线性DP[P1

数学上乘法逆元的定义是 $$ax=1，则x是a的乘法逆元$$。我们这里讨论关于取模运算的乘法逆元。定义：满足 $$ax\mod b = 1$$时，称 $$x为a关于模b的逆元$$。所以逆元有什么用呢？题目中可能会出现操作中间树很大的情况，如求解：$$3 * 6 / 3 \mod 7$$规定中间变量不

依然是复习以前学过的内容hhh一、01背包题目一共有N件物品，第i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？分状态和转移方程显然变量为装入的物品和背包的质量，所求的目标是最大的价值。因此设dp[i][j]来表示将前i件物

差分是前缀和的逆运算。差分数列，由该位置元素和前一个元素的差构成。例子：2 3 5 7 11 13 17 19差分数列：2 1 2 2 4 2 4 2作用：用于将区间操作转换成单点操作，原本对区间的操作在差分数列上体现的是对1-2个单点的操作。例如，对数列的前k项同时-1，差分数列上表现为对第1项减

最近公共祖先：在有根树中，两个节点的最近的公共祖先也就意味着，树上两个节点的最短距离就是他们的最近公共祖先到这两个节点距离之和朴素算法我们可以通过一遍dfs记录下每个节点的深度信息。在查询的时候，先让深度大的点往上跳，直到两点深度相等。两点深度相等以后就一起一步一步往上跳，直到跳到同一个点。显然这样

题面：给你一个 n 个点，m* 条边的无向图简单图。求割点数量，割边数量，极大点双连通分量数量，极大点双连通分量包含边数的最大值。割点：在图中移除这个点后，存在一个点对在原图中连通在新图中不连通。割边：在图中移除这条边后，存在一个点对在原图中连通在新图中不连通。点双连通分量：原图的一个点数大于 1