Q779’s Blog

洛谷P4294 [WC2008]游览计划 题解 题目链接：P4294 [WC2008]游览计划 题意： 从未来过绍兴的 cxy 有幸参加了 Winter Camp 2008 ，他被这座历史名城的秀丽风景所吸引，强烈要求游览绍兴及其周边的所有景点。 主办者将绍兴划分为 \(n\) 行 \(m\) 列共 \(n \times m\) 个方块，如下图 \((8\times 8)\)： 景点含于方块内（图中的灰色部分），且一个方块至多有一个景点。无景点的方块视为路。 为了保证安全与便利，主办方依据路况和治安状况，在非景点的一些方块内安排不同数量的志愿者；在景点内聘请导游（导游不是志愿者）。在选择旅游方案时，保证任意两个景点之间，存在一条路径，在这条路径所经过的每一个方块都有志愿者或者该方块为景点。既能满足选手们游览的需要，又能够让志愿者的总数最少。 例如，在上面的例子中，在每个没有景点的方块中填入一个数字，表示控制该方块最少需要的志愿者数目： 图中用红色标出的方块区域就是一种可行的志愿者安排方案，一共需要 \(20\) 名志愿者。 由图可见，两个相邻的景点是直接（有景点内的路）连通...

斯坦纳树 学习笔记 斯坦纳树问题是组合优化问题1 ，其中最常见的是最小斯坦纳树问题。 我们一般使用状压dp来求解最小斯坦纳树的问题，当然也有不用状压dp的题啦（ 最小斯坦纳树 题目链接：P6192 【模板】最小斯坦纳树 题意： 给定一个包含 \(n\) 个结点和 \(m\) 条带权边的无向连通图 \(G=(V,E)\)。 再给定包含 \(k\) 个结点的点集 \(S\)，选出 \(G\) 的子图 \(G^{\prime}=(V^{\prime},E^{\prime})\)，使得： \(S\subseteq V^{\prime}\)； \(G^{\prime}\) 为连通图； \(E^{\prime}\) 中所有边的权值和最小。 你只需要求出 \(E^{\prime}\) 中所有边的权值和。 数据范围： \(1\leq n\leq 100,~1\leq m\leq 500,~1\leq k\leq 10,~1\leq u,v\leq n,~1\leq w\leq 10^6\)。 保证给出的无向图连通，但 可能 存在重边和自环。 \(\mathcal{Part\ 1}\) ...

洛谷P5210 [ZJOI2017]线段树 题解 题目链接：P5210 [ZJOI2017]线段树 题意： 线段树是九条可怜很喜欢的一个数据结构，它拥有着简单的结构、优秀的复杂度与强大的功能，因此可怜曾经花了很长时间研究线段树的一些性质。 最近可怜又开始研究起线段树来了，有所不同的是，她把目光放在了更广义的线段树上：在正常的线段树中，对于区间 \([l, r]\)，我们会取 \(m = \lfloor \frac{l+r}{2} \rfloor\)，然后将这个区间分成 \([l, m]\) 和 \([m + 1, r]\) 两个子区间。在广义的线段树中，\(m\) 不要求恰好等于区间的中点，但是 \(m\) 还是必须满足 \(l \le m < r\) 的。不难发现在广义的线段树中，树的深度可以达到 \(O(n)\) 级别。 例如下面这棵树，就是一棵广义的线段树： 为了方便，我们按照先序遍历给线段树上所有的节点标号，例如在上图中，\([2, 3]\) 的标号是 \(5\)，\([4, 4]\) 的标号是 \(9\)，不难发现在 \([1, n]\) 上建立的广义线段树，...

UOJ49 【UR #3】铀仓库 题解 题目链接：#49. 【UR #3】铀仓库 题意： 顽皮的 cxy 潜入了著名核物理专家 Picks 的研究所，走进了存放浓缩铀的仓库。 浓缩铀存放在一个个箱子里，一共有 \(n\) 叠箱子排成一条直线，不妨想象一根数轴，第 \(i\) 叠箱子坐标为 \(x_i\)，竖直方向叠着 \(a_i\) 个箱子。 cxy 脑洞大开，决定进行一项游戏。她会先选择一个整数坐标 \(s\)（可以不和任意一个 \(x_i\) 相等），然后初始时她两手空空站在坐标 \(s\) 处，进行至多 \(t\) 秒的行动。 这段时间内她的行动方式包括： 向左移动单位 \(1\) 的距离，花费 \(1\) 秒。 向右移动单位 \(1\) 的距离，花费 \(1\) 秒。 如果现在手上是空的，那么可以从当前位置拿起一个装有浓缩铀的箱子，瞬间完成。 如果现在拿着一个装有浓缩铀的箱子，那么可以把这个箱子放在当前位置所有箱子的顶部，瞬间完成。 由于 cxy 很小，任意时刻她只能拿着至多一个箱子。她希望进行至多 \(t\) 秒的行动后，初始位置 \(s\) 叠着的箱子尽量多。 ...

洛谷P5299 [PKUWC2018]Slay the Spire 题解 题目链接：P5299 [PKUWC2018]Slay the Spire 题意： 九条可怜在玩一个很好玩的策略游戏：Slay the Spire，一开始九条可怜的卡组里有 \(2n\) 张牌，每张牌上都写着一个数字\(w_i\)，一共有两种类型的牌，每种类型各 \(n\) 张： 攻击牌：打出后对对方造成等于牌上的数字的伤害。 强化牌：打出后，假设该强化牌上的数字为 \(x\)，则其他剩下的攻击牌的数字都会乘上 \(x\)。 保证强化牌上的数字都大于 1。 现在九条可怜会等概率随机从卡组中抽出 \(m\) 张牌，由于费用限制，九条可怜最多打出 \(k\) 张牌，假设九条可怜永远都会采取能造成最多伤害的策略，求她期望造成多少伤害。 假设答案为 \(\text{ans}\) ，你只需要输出 \[ \left (\text{ans}\times \frac{(2n)!}{m!(2n-m)!}\right) ~\bmod 998244353 \] 即可。其中 \(x!\) 表示 \(\prod_{i=1}^{x...

容斥原理 学习笔记 容斥原理 容斥原理(principle of inclusion-exclusion)：令 \(X\) 为一个有限集合，\(P_1, P_2,\dots , P_m\) 是一些性质的集合。 对于任意 \(S \subseteq [m]\) ，即 \(S\subseteq \{1,2,\cdots,m\}\) ，定义 \(N(S) = \{x \in X \mid \forall i \in S : x \text{ has } P_i\}\) 。 那么 \(X\) 中满足性质 \(P_{1\sim m}\) 的元素个数为 \[ \sum_{S \subseteq [m]} (-1)^{|S|+1} \left|N(S)\right| \] 如果是不满足任何一个性质的话，把指数中的 \(|S|+1\) 改成 \(|S|\) 即可。 特别地，对于任意的 \(S \subseteq [m]\) ，如果 \(N(S)\) 只和 \(S\) 的大小（即 \(|S|\) ）有关，那么式子可以化简为 \[ \sum_{i=0}^{m} (-1)^{i+1} \binom...

洛谷P3349 [ZJOI2016]小星星 题解 题目链接：P3349 [ZJOI2016]小星星 题意： cxy 是一个心灵手巧的女孩子，她喜欢手工制作一些小饰品。她有 \(n\) 颗小星星，用 \(m\) 条彩色的细线串了起来，每条细线连着两颗小星星。 有一天她发现，她的饰品被破坏了，很多细线都被拆掉了。这个饰品只剩下了 \(n-1\) 条细线，但通过这些细线，这颗小星星还是被串在一起，也就是这些小星星通过这些细线形成了树。cxy 找到了这个饰品的设计图纸，她想知道现在饰品中的小星星对应着原来图纸上的哪些小星星。如果现在饰品中两颗小星星有细线相连，那么要求对应的小星星原来的图纸上也有细线相连。cxy 想知道有多少种可能的对应方式。 只有你告诉了她正确的答案，她才会把小饰品做为礼物送给你呢。 输入格式： 第一行包含 \(2\) 个正整数 \(n,m\)，表示原来的饰品中小星星的个数和细线的条数。 接下来 \(m\) 行，每行包含 \(2\) 个正整数 \(u,v\)，表示原来的饰品中小星星 \(u\) 和 \(v\) 通过细线连了起来。这里的小星星从 \(1\) 开始标号。保...

Splay rotate操作 图解 Splay 的旋转操作比较难理解，因此我在这里画了一张详细的图解。 首先是旋转部分的代码，完整代码见 OI模板-数据结构 void rotate(int x) { int y=t[x].fa, z=t[y].fa, k=t[y].ch[1]==x; t[z].ch[t[z].ch[1]==y]=x; t[x].fa=z; t[y].ch[k]=t[x].ch[k^1]; t[t[x].ch[k^1]].fa=y; t[x].ch[k^1]=y; t[y].fa=x; push_up(y); push_up(x); // 维护子树信息，图里没有画 } 这里是图解，我们只要考虑一般的情况即可（记起来方便 qwq） Powered by Diagrams

洛谷P5369 [PKUSC2018]最大前缀和 题解 题目链接：P5369 [PKUSC2018]最大前缀和 题意： cxy 是一个算法竞赛爱好者，有一天 cxy 遇到了一个非常难的问题：求一个序列的最大子段和。 但是 cxy 并不会做这个题，于是 cxy 决定把序列随机打乱，然后取序列的最大前缀和作为答案。 cxy 是一个非常有自知之明的人，她知道自己的算法完全不对，所以并不关心正确率，她只关心求出的解的期望值，现在请你帮她解决这个问题，由于答案可能非常复杂，所以你只需要输出答案乘上 \(n!\) 后对 \(998244353\) 取模的值，显然这是个整数。 注：最大前缀和的定义：\(\forall i \in [1,n],~\sum_{j=1}^{i}a_j\)的最大值。 输入格式： 第一行一个正整数 \(n\)，表示序列长度。 第二行 \(n\) 个数，表示原序列 \(a\)，第 \(i\) 个数表示 \(a_i\) 。 输出格式： 输出一个非负整数，表示答案。 数据范围： 满足\(1\leq n\leq 20,~\sum_{i=1}^{n}|a_i|\leq 10^9...

洛谷P3830 [SHOI2012]随机树 题解 题目链接：P3830 [SHOI2012]随机树 题意： 给定一棵随机有根二叉树的叶节点数 \(n\) ，求 叶子结点深度的期望 树深度的期望（根节点深度为 \(0\) ） 每组数据将给出 \(\mathtt{op=1/2}\) ，表示询问的子问题。 随机方式如下 初始只有根节点 每次选择一个叶结点，为其添加两个子结点 重复步骤 2 （共 \(n-1\) 次），得到一棵随机树。 例如下图为 \(n=5\) 的一种生成方式。 输入格式： 输入仅有一行，包含两个正整数 \(\mathtt{op},n\) ，分别表示问题编号以及叶结点的个数。 输出格式: 输出仅有一行，包含一个实数 \(d\)，四舍五入精确到小数点后 \(6\) 位。如果 \(\mathtt{op = 1}\)，则 d 表示叶结点平均深度的数学期望值；如果 \(\mathtt{op = 2}\) ，则 \(d\) 表示树深度的数学期望值。 数据范围： \(\mathtt{op=1/2}, ~2 \le n \le 100\) 。 注意到生成这棵树的方式于叶...

竞赛图及其性质 咕咕咕… 竞赛图的定义 若有向简单图 \(G=(V,E)\) 满足任意不同两点间都有恰好一条边（单向），则称 \(G\) 为 竞赛图。 注意与 有向完全图 作区分，有向完全图是任意 \(u,v \in V\) 均有边 \(u \to v\) 和 \(v \to u\) 。而竞赛图只有其中一条。 竞赛图的性质 竞赛图不存在自环。若竞赛图存在环，则一定存在三元环。 任意竞赛图均有哈密顿路径（经过每一个点的路径 \(\langle v_1,v_2,\cdots,v_k\rangle\) 且 \(v_i \ne v_j\) ） 竞赛图存在哈密顿回路当且仅当其为强连通图。 竞赛图缩点后为呈单向链状，每个点向其后所有点连边 判断竞赛图是否强连通可以将点的出度按升序排序 若不存在 \(k<n\) 使得前 \(k\) 个出度之和等于 \(\binom{k}{2}\) ，则原图强连通 时间复杂度为 \(\mathcal{O}(n \log n)\) 。朴素的 \(\mathtt{Tarjan}\) 做法是 \(\mathcal{O}(n^2)\) 的（因为 \(m = n...

CF913F Strongly Connected Tournament 题解 题目链接：CF913F Strongly Connected Tournament 题意： 有 \(n\) 个人，编号为 \(1, 2, \cdots, n\) ，他们想要通过打架的方式决定他们的排名。 具体地，对于 \(i < j\)，\(i\) 获胜的概率恒为 \(p\)。\(p\) 通过给你两个非负整数 \(A, B~(A \leq B),~p = \frac{A}{B}\) 的方式给出。 初始时，所有人都还没决出胜负。每一轮，对还未决出胜负的每一对人进行打架，得到一张竞赛图。将其进行缩点后，得到若干个 SCC（强连通分量）。 此时，如果两个人处在不同的 SCC 中，则它们已经决出胜负。否则，它们还未决出胜负 (下一轮还要继续)。 如果某一时刻所有人都决出胜负，则比赛结束，否则进行下一轮比赛。 你需要求出，这 \(n\) 个人的比赛中打架次数的期望。 输入格式： 第一行包含一个正整数 \(n~(n\le 3000)\)，表示总人数。 第二行包含两个非负整数 \(A, B~(0 \le A...