文章

前言 在 NOI2016D1T2 国王饮水记中有一个叫定理 10 的东西，picks 讲课的 PPT 中并没有给出详细的推导过程。本人根据 PPT 中所说的大致思想，尝试证明了定理 10，现写在下方。如有错误或不严谨之处，麻烦指出，万分感激。 证明 假设我们的最优解有 l 段长度大于 1，这些段的长 阅读更多…

神仙 Remmina 学长跑到国外读大学去了…… 从今天开始，窝将是 MiNa! 的站长，如果遇见什么问题请找我。 qwq

各位亲爱的 OIer 们： 由于我即将高中毕业，并且计划出国读 (zhong) 书 (tian)，不太方便打理 MiNa! 了，我想是时候和信息竞赛 say goodbye 了。 在高中阶段，OI 给我带来了无穷的欢乐，在 MiNa! 上和大家一起写文章也是。 至今我还很怀念当年的那一幕幕—— 全机 阅读更多…

这个题题面好可爱嘛~ 那我们考虑简化一下~ 第一问是求每个文本串中含有的模式串个数。 第二问是求每个模式串是多少个文本串的子串。 看到多串匹配肯定想到广义 $SAM$啦，所以我们建出广义 $SAM$，建立的同时标记 $size$，就是每次 $upd$的时候 $size[rt]++$; 第一问呢，直接 阅读更多…

[ZJOI2014] 力 题意 给出 $n$ 个数 $q_i$, 定义 $$ F_j = \sum_{i=1}^{j-1} \frac{q_i \times q_j}{(i-j)^2} – \sum_{i=j+1}^{n} \frac{q_i \times q_j}{(i-j)^2} $ 阅读更多…

题目传送门 qwq $op=0$ 考虑如果一条边在 $(u,v)$ 在红蓝两树中都出现过的话，意味着将 $u,v$ 两点看作一个整体进行染色，故答案为： $$ y^{n-|T_1\cap T_2|} $$ 其中 $T_1$ 表示蓝树的边集，$T_2$ 表示红树的边集。 期望得分 $28\ pts$ 阅读更多…

本文参考资料: From yyb:Link 正文：关于 SPLAY 其实我更偏向于把 splay 叫做 cosplay 讲平衡树总逃不过 BST(Binary Search Tree)，二叉搜索树，以下是 BST 的性质： 一棵合法的 BST 每个节点上都带有一个数值，我们将其称为节点的 “关键码” 阅读更多…

题目传送门 pwp 首先我们可以想到一个显而易见的 $\rm{DP}$ ： 设 $dp_{u,w}$ 表示点 $u$ 的权值为 $w$ 的概率，考虑转移： $$ dp_{u,w}=dp_{a,w}\times\left(p_u\sum_{w'<w}dp_{b,w’}+(1-p_{u 阅读更多…

题目传送门 qwq 发现并不需要求出期望，之需要求出所有方案的和即可。考虑 $\rm{DP}$ ： 设 $f(i,j)$ 表示选出的 $m$ 张牌中有 $i$ 张是强化牌，一共打出了 $j$ 张强化牌时所有方案的倍率和。 设 $g(i,j)$ 表示选出的 $m$ 张牌中有 $i$ 张是攻击牌，一共打 阅读更多…

题目传送门 qwq 设 $f(S)$ 表示考虑过的集合为 $S$ 的方案数。 如果当前的最大独立集为 $A$ ，$B$ 代表所有与 $A$ 集合中的点有边相连的点的集合，那么当前状态下 $S=A\cup B$ 。 设 $P_u$ 表示与 $u$ 距离不超过 $1$ 的点集。 考虑转移，首先确定一点 阅读更多…