题解 战争p4557 2018

题意： 思路： 由于 $ k ∈ [1，3] $ ，分类讨论： 当 $ k = 1 $ 时，有人结点自身即为好结点，每种情况的期望为 $ \frac{1}{n} $ ， $ n $ 种情况的期望和为 $ 1 $ 。最终答案即为 $ 1 $ 。 当 $ k = 2 $ 时，$ 2 $ 个有人结点之间的 ......

给出一个长为 \(n\) 的字符串和非负整数 \(k\)。你可以进行以下操作若干次，使得最终字符串长度最小。 选择一个字串 of。然后删掉 of 以及这之后的 \(i\) 个字符。\(i\) 由你决定，但要满足 \(0\leq i\leq k\)。 输出这个最小长度。\(1\leq n,k\leq ......

互异关系容斥即将不等号容斥成等号，对于连通块内的 \(\text{GF}\) 形式即为 \(\ln(x+1)\) 的展开级式，即令 \(F=\sum_{i=1}^{\infty}\frac{a_{i}(-1)^{i-1}x^i}{i}\)，对 \(F\) 直接 \(\exp\) 即可。 而非常神奇的 ......

题目链接 点击打开链接 题目解法 题目中的操作可以理解为一个点移动位置 首先给出一个结论：每个点只会动至多一次 考虑 \(dp\) 一个比较妙的状态设定是 \(f_i\) 表示 \(i\) 不动的方案数 不妨枚举 \(j\) 表示上一个不动点，限制是 \(j<i\) 且 \(p_j<p_i\) 中间 ......

题目链接 点击打开链接 题目解法 从后往前推一下，可以得到 \(C\) 一定要把每一行的数都归位到那一行，\(B\) 一定要每一列的目标行数互不相同 考虑构造 \(B\) 这个限制看起来略有些网络流，所以考虑如何建图 令 \(a_{i,j}\) 的目标行数为 \(ln_{i,j}\)，我们由 \(i ......

题目链接 点击打开链接 题目解法 这题看起来很 \(flow\)，不难想到边数 \(nm\) 的建图方法： 具体来说，边为 \((S,i,c_i)(i\in [1,m])\)，\((i,j,b_i)(i\in [1,m],\;j\in [1,n])\)，\((j,T,a_i)(j\in [1,n]\ ......

P9686 Judg. 题解 Part 1 提示 题目传送门 欢迎大家指出错误并私信这个蒟蒻 欢迎大家在下方评论区写出自己的疑问（记得 @ 这个蒟蒻） Part 2 更新日志 2023-10-02 15:50 文章完成 2023-10-04 12:37 文章通过审核 Part 3 解析 一道简单模拟 ......

P9517 drink 题解 Part 1 提示 题目传送门 欢迎大家指出错误并私信这个蒟蒻 欢迎大家在下方评论区写出自己的疑问（记得 @ 这个蒟蒻） Part 2 更新日志 2023-08-12 18:06 文章完成 2023-08-14 15:53 文章通过审核 Part 3 解析 这道题考场上 ......

P8679 [蓝桥杯 2019 省 B] 填空问题 题解 题目传送门 欢迎大家指出错误并联系这个蒟蒻 更新日志 2023-05-25 21:02 文章完成 2023-05-27 11:34 文章通过审核 2023-06-20 21:03 优化了文章代码格式 试题 A ：组队 【解析】 本题是一道经典 ......

P8741 [蓝桥杯 2021 省 B] 填空问题 题解 题目传送门 欢迎大家指出错误并联系这个蒟蒻 更新日志 2023-05-09 23:19 文章完成 2023-05-09 23:20 通过审核 2023-06-20 21:03 优化了文章代码格式 试题 A ：空间 【解析】 本题考察计算机存储 ......

P8684 [蓝桥杯 2019 省 B] 灵能传输 题解 Part 1 提示 题目传送门 欢迎大家指出错误并私信这个蒟蒻 欢迎大家在下方评论区写出自己的疑问（记得 @ 这个蒟蒻） Part 2 更新日志 2023-06-20 21:46 文章完成 2023-07-03 08:57 文章通过审核 20 ......

题目传送门 [JXOI2018] 守卫 思路 区间dp。 设状态 $f_{l,r}$ 为在区间 $[l,r]$ 内要放的最少保镖数量。 看到题面第一眼的感觉是不会判两点能否连接。 第二眼发现可以用斜率判。 令 $k_{l,r}$ 为横坐标为 $l,r$ 的两点连线斜率。 有 $k_{l,r}=\fr ......

题目传送门 一道暴力题。 度数和 \(k\) 那么小？直接暴力 \(n\) 遍 bfs，注意 bfs 的队列只能 push 距离不超过 \(3\) 的点。但有个问题，每次 bfs 都需要清空一次距离数组，这样子的时间复杂度是 \(O(n^2)\) 的。但也不难想到，距离数组中被赋值的地方不会很多，记 ......

题目链接 点击打开链接 题目解法 很思维的题，需要用好所有的特殊性质 暴力的做法是建出图，然后求包含点 \(i\) 的最长反链，但这明显过不了 上面的做法没用到 \(a_i<2m\) 的性质 如何用？把 \(a_i\) 拆分成 \(q\times 2^k\;(k\) 为奇数\()\) 的形式，那么对 ......

题目链接 点击打开链接 题目解法 比较套路的题 首先画个图，然后把 \(y-x\) 相同的变成一个点（使 \(y>x\)） 然后再两个点之间连有权边 那么问题就变成求新图的每个连通块中形成的原图的连通块数量 手玩几个数据发现，原图的连通块数量即为新图的所有环长的 \(\gcd\)，再和 \(n\) ......

https://codeforces.com/contest/1902/problem/F 方法一 可以从树上路径想到轻重链剖分（也可以用其他种类的LCA算法），然后从数的异或表示很容易想到线性基。 然后因为是无修改的，所以可以轻重链剖分+ST表+线性基。具体来说就是： 先进行轻重链剖分。然后把每次 ......

题目链接 点击打开链接 题目解法 易知总情况数为 \(2^n\) 考虑重复计算的情况为：存在 \([l_i,r_i]\)，满足没有 \([l_j,r_j](i\neq j)\) 选在此区间中 可以得到一个容斥的 \(dp\) 做法 这个转移虽然感觉很显然，但卡了我一个晚上，一直调不出 令 \(f_i ......

[CF1902] Educational Codeforces Round 159 A~E 题解 A. Binary Imbalance 很快观察到如果有不同的相邻元素，那么一定有解，意味着如果全是 1 无解，其他有解 B. Getting Points 题面很长，可以发现，最好的偷懒方式一定是把所 ......

题意： 思路： 当 $ n \not \equiv 0 \space (mod \space 3) $ 时，无解； 当 $ n \equiv 0 \space (mod \space 3) $ 时，设 $ size_u $ 表示以 $ u $ 为根的子树还剩余的节点个数，自根节点向叶子节点递归，返回 ......

题意： 思路： $ BFS $ ： 对于每一个数 $ x $ ，枚举其数位 $ num \space (0 \le num \le 9) $ ，将 $ x $ 与 $ num $ 的乘积 $ y $ 放入队列。重复该过程，直至 $ y $ 的位数与 $ n $ 相同。 剪枝： $ 1 $ . 对于重 ......

题意： 思路： 设 $ minv $ 表示路径最小权值和， $ maxv $ 表示路径最大权值和。 当且仅当路径长度 $ n + m - 2 \equiv 0 \space (mod \space 2) $ 且 $ minv \le 0 \le maxv $ 时，一定有权值和为 $ 0 $ 的路径； ......

提供二分+DP做法。 Solution 题意 给出 \(n(\le 2\times 10^5)\) 个单调递增偶整数 \(a_i\)，求最小的 \(k\) 满足每一个 \(i\) 都可以在 \(k\) 时刻之前（含）与相邻的数相遇。每个单位时间可以移动一个单位距离。 思路 启发式思考 在想到正解之前 ......

题意： 思路： 对于满足条件的区间 $ [1，x] $ ，有如下三种情况： $ 1 $ . 所有元素出现次数都为 $ 1 $ ； $ 2 $ . 除了一个元素出现次数为 $ 1 $ 之外，其余元素出现次数都相等； $ 3 $ . 除了一个出现次数比其他数的出现次数多 $ 1 $ 的元素之外，其余元素 ......

题意： 有一个长度为 $ n $ 的序列 $ a $ ，给定 $ q $ 次操作，每次操作为以下两种之一： $ 1 $ . $ 1 $ $ p $ $ x $： $ a_p = x $ $ 2 $ . $ 2 $ $ x $： $ a_i $ $ = $ $ max $$($$ a_i $ ，$ x ......

盒子里有 \(n\) 张 \(m\) 种卡片，第 \(i\) 种卡片有 \(c_i\) 张。\(\sum c_i=n\)。 每次均匀随机选一张，再放回去。求拿出过的卡片包含全部种类所需要的取出次数的期望。 对 \(998244353\) 取模。 \(1\leq n,m\leq 2e5,c_i\gt0 ......

题目链接 点击打开链接 题目解法 \(n^3\) 的 \(dp\) 是显然的 但我们没用到 \(a\) 不降的性质 考虑一个很妙的结论：最优选法中，至多只有一个序列取了且未取满 为什么？ 如果最优情况下，存在选且未选满的序列为 \(a,b\)，第一个未选的元素为 \(x,y\) 如果 \(a_x>a ......

洛谷 P1044 [NOIP2003 普及组] 栈 题解 Sol 本题通过分析可得： 假设现在进行 \(12\) 次操作，我们把 push 认为是在地图上向右走，pop 向上走，那么其中一个合法的步骤可以是（\(p1\) 代表 push，\(p2\) 代表 pop)：\(p1, p1, p2, p1 ......

题意： 思路： 必要性： 对于任意一个符合条件的区间[l，r]，任意相邻两项，满足a_i < 2 * a_{i + 1}(l \le i \le r - 1)。 充分性： 对于任意一个长度为k + 1的区间[l，r]，如果任意相邻两项满足a_i < 2 * a_{i + 1}(l \le i \le ......

Link CF1901 C Add, Divide and Floor Question 给定一个长度为 \(n\) 的序列，每次操作你需要选择一个整数 \(x\) ，并将所有 \(a_i\) 替换为 \(\lfloor \frac{a_i+x}{2} \rfloor\) 。求至少多少次操作后能将所 ......

Link CF1902 D Robot Queries Question Robot 初始在 \((0,0)\) ，有一个字符串 \(s\) ，表示运行列表 \(U\)：y+1 \(D\)：y -1 \(L\) ：x -1 \(R\) ：x+1 之后有 \(Q\) 次询问，有\(L,R,x,y\)， ......