文章

考虑设 $f(i,j)$ 表示 $i$ 行每行都有至少一格黑色的大小为 $i\times j$ 的表格的方案数。 最终的答案就是 $\sum {n\choose i}f(i,m)$ 。 考虑如何转移，每一次加入一列，并且加入若干行，最终的行数分成小于等于 $i$ 和大于 $i$ 两种。 考虑小于等于 阅读更多…

可以猜测，对于最优的 $\rm{B}$ 中的区间 $[L,R]$ 满足该区间内所有数相等，那么如果这个数为 $x$ ，则 $A_L$ 到 $A_R$ 的平均数为 $x$ ，显然这个猜测成立。 然后还有一个显然的结论：区间 $[L,R]$ 的长度越小越好，这也是显然的。 我们考虑没有修改的情况，用单调 阅读更多…

前言 在 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 阅读更多…