题解

先求出初始时绿连通块数量。 将一个绿色格子染成红色，会改变绿连通块数量，当且仅当这个绿色格子是孤点或割点。如果是孤点，会使得绿连通块数量减少一；如果是割点，会使得绿连通块数量增加它所在的点双数量减一。根据上述规则可以求出每个绿色格子染红后的绿连通块数量，求平均值即可。 时间复杂度 \(O(nm)\) ......

Description P 哥有一棵树，根节点是 \(1\)，总共有 \(n\) 个节点，从 \(1\) 到 \(n\) 编号。 他想从根节点开始进行深度优先搜索。他想知道对于每个节点 \(v\)，在深度优先搜索中，它出现在第 \(j\) 个位置的方式有多少种。深度优先搜索的顺序是在搜索过程中访问节 ......

## 题目描述 世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才，A 市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的 $150\%$ 划定，即如果计划录取 $m$ 名志愿者，则面试分数线为排名第 $m \times 150\ ......

P3893 [GDOI2014] Beyond 题解 思路 称第一个字符串为 \(A\)，第二个字符串 \(B\)。 考虑枚举环长 \(L\)，那么如果 \(L\) 是可行的，当且仅当存在一个位置 \(i\)，使得 \(A_{1\sim i} = B_{L - i + 1, L}, A_{i + 1 ......

题目链接 期望 dp 板子题，我们直接设 \(dp_i\) 为怪物血量只剩下 \(i\) 时的概率即可，状态转移方程也很简单了，详见代码。 参考代码： 点击查看代码 /* Tips: 你数组开小了吗？ 你MLE了吗？ 你觉得是贪心，是不是该想想dp？ 一个小时没调出来，是不是该考虑换题？ */ #i ......

题解：【XR-3】核心城市 思路一：考虑由特例推广到一般 1、很容易想到先考虑一个关键点的情况，然后再推广到一般情况。 2、一个点肯定选距离上最平衡的那个点，即树的中心。接着在中心周围贪心的选剩下的(k-1)个关键点即可。 3、这里有一个误区： 各点到某点的距离最小，是找树的中心而不是重心！！！ 各 ......

题目描述 计算一个 \(10 \times 10\) 矩阵中由 \(1\) 围成的图形的面积。如下所示，在 \(10 \times 10\) 的二维数组中，\(1\) 围住了 \(15\) 个点，因此面积为 \(15\)。 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 ......

因为白点对 \(f_i\) 没有贡献，所以可以重构出一棵原树的子树，使得所有的叶子都为标记点且标记点数量不变（没有删去标记点）。因为没有标记被删去且结构不变，所以这棵树的答案与原树答案相同。 现在，对于所有节点，到它距离最大的标记点一定在叶子上。那么问题就变为：求出树上任意一点到所有叶子节点的最大距 ......

WEB: 圣杯战争 !!! （题解：结局别说遗憾 Zn. ） 解题思路：打开题目链接，代码如下： <?php highlight_file(__FILE__); error_reporting(0); class artifact{ public $excalibuer; public $arrow ......

题意： 给定一个字符串，求能盖出这个字符串的印章的最小长度。 分析： 显然，这个印章一定是 \(s\) 的 border。 记 \(dp_{i}\) 表示盖满前 \(i\) 个的最小印章大小，那么答案只可能为 \(i\)，或者 \(dp_{kmp_{i}}\)。 证明如下： 显然答案为 \(i\) ......

[CF17E] Palisection 题解 思路 直接统计相交的字符串很难数，考虑正难则反。 用总共的回文串对数减去相离的回文串个数。 设总共有 \(tot\) 个回文串，用 manacher 跑出来每个位置的最大回文半径后，使用差分的技巧保存两个数组： \(f_i\) 表示以 \(i\) 为开头 ......

原题传送门 题目大意 如题意翻译。 思路分析 很水的一道题目，可以将第一个排列 \(a\) 看作最终排列，接下来每输入一个数，让它与 \(a_m\) 进行比较，直到两个排列相同。 最后看题目范围，\(1≤n≤2\times10^5\)，时间复杂度 \(\mathcal{O(n)}\)，空间复杂度 \ ......

原题传送门 题目大意 有一个仅有 0 和 L 构成的序列，求出一种方案，使得左部分的 0 数量不等于右部分的 O 数量，且左部分的 L 数量不等于右部分的 L 数量，若不存在输出 -1。 思路分析 首先看题目范围，\(2≤n≤200\)，数据很小，考虑暴力。 可以使用字符串截取函数 s.substr ......

27 htppy Spring 评价: 相对简单，放出来的晚，做的出来的人相对比较少 大致流程是可以上传.pebble模板文件，然后通过访问上传的恶意模板文件进行rce。 首先上传恶意模板文件，经过几次尝试，黑名单过滤了，org.springframework.context.support.Cla ......

题目链接 点击打开链接 题目解法 题意比较复杂，形式化一下题意是： 一些人和一些城市，每个人属于一个城市，每个人属于 \(A/B/C/D\) 队，需要满足：每个城市中的人要么都属于 \(AC\) 或 \(BD\)，且 \(A+C\le C_0,\;B+D\le C_1,\;A+B\le D_0,\; ......

题目大意 你需要对每一个长度的区间，求出以他为长度的区间的 \(mex\) 构成集合的 \(mex\) \(n\le10^5\) 大致思路 有一个神奇的结论：对于点 \((l,r)\) 为 \(mex_{l,r}\) 的矩形，其中按颜色分割得到的矩形数是 \(O(n)\) 级别的 证明&实现：我们考 ......

非常厉害的一道交互题。 思路 由于交互库会说谎，我们考虑把两次询问划分成一组。 结论：假如一个集合在两次询问中都为不成立，那么这个集合也就一定不成立。 证明显然，因为这两次中总有一次时真话。 那么我们就可以想到一个比较暴力的想法。 每一次把集合划分为四个，\(S_{0,0},S_{0,1},S_{1 ......

题面 鉴于这题目前还没题解，提供一种时间 \(\Theta(n\sqrt{m})\)，空间 \(\Theta(n+m)\) 的做法。 询问 1 可以直接上树分块或者树上莫队，见 P6177 Count on a tree II/【模板】树分块。 但是因为本题询问 2 的做法，所以我采用了树上莫队的做 ......

Link CF1914 D Array Collapse Question 初始给出一个数组 \(\{P\}\) ，数组中每个值都不相同，我们可以选中 \(P\) 数组中连续的一段，然后删除除了最小值以外的所有元素，求删除多次（包括 \(0\) 次）后，剩下的数组的数量 Solution 当时就没怎 ......

题目链接 点击打开链接 题目解法 很有技巧的一道题 观察数据范围发现 \(a_i,b_i\) 很小，所以考虑和值域有关的做法 从组合意义上考虑组合数，不难想到 \(\binom{a_i+b_i+a_j+b_j}{a_i+a_j}\) 为 \((0,0)\) 到 \((a_i+a_j,b_i+b_j) ......

难度极低。显然，句子开头是You are right, but即为人工智能。 #include <iostream> #include <string> #include <cstdio> namespace io{ template <typename T> inline void read(T& ......

本题是我的第一道蓝题，故我认为这道题稍难。 在本题解中，会列出一些坑点供大家参考。 这道题由优先制作这一关键词可知是一道拓扑排序的题，于是我想用邻接矩阵，但是我交之后错了，那是因为普通的数组会爆，但我不喜欢写链式前向星，故使用了vector的二维数组。 但是这道题比较特殊，由教练提醒，这道题需要跑反 ......

这道题非常板，如你所见，大概思路是打表回文数加上完全背包求方案数，但是需要注意取余问题。 从英文题面上（题目翻译没有给出数据范围）可以看到 \(1 \leq n \leq 4 \cdot 10 ^ {4}\)，所以只要用完全背包来预处理这一范围即可。如果你还是不懂，可以去搜完全背包字样并学习该算法。 ......

这道题比较水。大概思路是使用循环，之后检查 \(a_{i}\) 是否达到 \(x\) 且 \(b_{i}\) 是否达到 \(y\) 且 \(a_{i} + b_{i}\) 是否达到 \(z\)。 代码如下。 #include <iostream> namespace io{ template <ty ......

每次按一个开关就会改变两盏灯的状态，考虑把这种关系在一张图上表示出来。在图上把所有可能同时改变状态的灯连边，让亮灯的点的值为 \(1\)，不亮的为 \(0\)，那么每次按灯就是把连接一条边的两点的值都异或上 \(1\)，最终要让所有点的值都为 \(0\)。 由于每个点的度都大于 \(1\) 且图上共 ......

每次在数组中找大于 \(s\) 的数太麻烦了，将数组排序后，每次能删去的数一定是一个前缀，就只需要对于每个 \(i\)，考虑它能删去的数的右端点在哪。设 \(r_i\) 为初始删除 \(i\) 能删到的数的右端点的编号，那么有： \[r_i= \begin{cases} n & \text{ if ......

题意：求出 \(a+b+c=n\) 且 \(d(a)+d(b)+d(c)=d(n)\) 的三元组 \((a,b,c)\) 的个数。其中 \(d(x)\) 等于 \(x\) 的各位数位之和。 根据直觉和样例解释可以知道，如果 \(a+b+c\) 没有发生进位，那么三元组 \((a,b,c)\) 一定合 ......

注意到，\(x_i\) 取 \(k\) 的概率是 \(p(1-p)^{k-1}\)，是和为 \(1\) 的等比数列，下面考察数列前缀和的性质。 不难想到，概率每次乘以 \(1-p\) 像是概率的分步乘法，每一步正是加一的操作。于是可以得到如下转化：初始时 \(S=0\)，每一时刻 \(S\) 先增加 ......

注意到，\(x_i\) 取 \(k\) 的概率是 \(p(1-p)^{k-1}\)，是和为 \(1\) 的等比数列，下面考察数列前缀和的性质。 不难想到，概率每次乘以 \(1-p\) 像是概率的分步乘法，每一步正是加一的操作。于是可以得到如下转化：初始时 \(S=0\)，每一时刻 \(S\) 先增加 ......

P4147 玉蟾宫 题解 题目链接 P4147 玉蟾宫 简要思路 很容易发现，这是最大子矩形问题的板子题。 定义一个二维的 \(dp\) 数组，\(dp_{i,j}\) 代表以坐标 \((i,j)\) 为底的线段，最长能向上延伸多少个单位长度的 F（如果自身为 R，值则为 \(0\)）。 对于 \( ......