Q779’s Blog

洛谷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...

洛谷P1809 过河问题 题解 题目链接：P1809 过河问题 题意： 有一个大晴天，cxy 与同学们一共 \(n\) 人出游，他们走到一条河的东岸边，想要过河到西岸。而东岸边有一条小船。 船太小了，一次只能乘坐两人。每个人都有一个渡河时间 \(a_i\) ，船划到对岸的时间等于船上渡河时间较长的人所用时间。 现在已知 \(n\) 个人的渡河时间 \(a_i\) ，cxy 想要你告诉他，他们最少要花费多少时间，才能使所有人都过河。 注意，只有船在东岸（西岸）的人才能坐上船划到对岸。 输入格式： 输入文件第一行为人数 \(n\) ，以下有 \(n\) 行，每行一个数。 第 \(i+1\) 行的数为第 \(i\) 个人的渡河时间 \(a_i\) 。 输出格式： 输出文件仅包含一个数，表示所有人都渡过河的最少渡河时间 数据范围： 对于 \(100\%\) 的数据满足 \(n \le 10^5\) 。 这道题和经典的过河问题不一样，经典的过河问题是 \(a+b\) ，而它是 \(\max\{a,b\}\) 。 因此用最小花费的人去送不一定是最优方案了。 不失一般性，假设 \(a_i\...

洛谷P4071 [SDOI2016]排列计数 题解 题目链接：P4071 [SDOI2016]排列计数 题意： 求有多少种 \(1\) 到 \(n\) 的排列 \(a\)，满足序列恰好有 \(m\) 个位置 \(i\)，使得 \(a_i = i\)。 答案对 \(10^9 + 7\) 取模。 输入格式： 输入的第一行是一个整数 \(T\)，代表测试数据的整数。 以下 \(T\) 行，每行描述一组测试数据。 对于每组测试数据，每行输入两个整数，依次代表 \(n\) 和 \(m\)。 输出格式： 共输出 \(T\) 行，对于每组测试数据，输出一行一个整数代表答案。 数据范围： \(1 \leq T \leq 5 \times 10^5\)，\(1 \leq n \leq 10^6\)，\(0 \leq m \leq 10^6\)。 答案： \[ \dbinom{n}{m}\times D(n-m) \] 其中 \(D(n)\) 为 \(n\) 个数的错排公式，有 \[ D(1)=0,~D(2)=1 \\[6pt] D(n) = (n-1)\times [D(n-1) + D(n-...

洛谷P4860 Roy&October之取石子II 题解 题目链接：P4860 Roy&October之取石子II 题意： 游戏规则是这样的：共有 \(n\) 个石子，两人每次都只能取\(p^k\)个（ \(p\) 为质数，\(k=0\) 或 \(1\)，且 \(p^k\) 小于等于当前剩余石子数），谁取走最后一个石子，谁就赢了。 现在October先取，问她有没有必胜策略。 若她有必胜策略，输出一行 October wins! ；否则输出一行 Roy wins! 。 输入格式: 第一行一个正整数T，表示测试点组数。 第 \(2\) 行 \(\sim\) 第 \((T+1)\) 行，一行一个正整数 \(n\) ，表示石子个数。 输出格式： \(T\) 行，每行分别为 October wins! 或 Roy wins!。 数据范围： \(1\le n\le 5\times 10^7,~1\le T\le 10^6\) 可以先做一下 P4018 Roy&October之取石子 结论：当石子数 \(n\) 不为 \(4\) 的倍数时，先手必胜，否则先手必输。...

洛谷P2114 [NOI2014] 起床困难综合症 题解 题目链接：P2114 [NOI2014] 起床困难综合症 题意： cxy 的防御战线由 \(n\) 扇防御门组成。每扇防御门包括一个运算 \(\mathrm{op}\) 和一个参数 \(t\)，其中运算一定是 \(\text{OR},\text{XOR},\text{AND}\) 中的一种，参数则一定为非负整数。如果还未通过防御门时攻击力为 \(x\)，则其通过这扇防御门后攻击力将变为 \(x~\mathrm{op}~t\)。最终 cxy 受到的伤害为对方初始攻击力 \(x\) 依次经过所有 \(n\) 扇防御门后转变得到的攻击力。 由于 atm 水平有限，他的初始攻击力只能为 \(0\) 到 \(m\) 之间的一个整数（即他的初始攻击力只能在 \(0,1,\ldots,m\) 中任选，但在通过防御门之后的攻击力不受 \(m\) 的限制）。为了节省体力，他希望通过选择合适的初始攻击力使得他的攻击能让 cxy 受到最大的伤害，请你帮他计算一下，他的一次攻击最多能使 cxy 受到多少伤害。 输入格式： 输入文件的第 \(1\...