文章

最小割树是啥树, 能吃吗 (话说树怎么吃) 最小割树 (Gomory-Hu tree)，是可以将一张网络流图通过膜法变成一棵树的算法，这棵树上两两点之间最小权值的边是原图这两个点的最小割。 你可能会想，最小割辣么多，照你这样说一张图所有点对的最小割的权值只会存在 $n-1$种可能喽？ 的确是这样的， 阅读更多…

题面 题目数据标程包下载↓ 众所周知的蜂鸣器 时间限制 : 10 Sec 空间限制 : 512 Mb 众所周知，Boshi 是个喜欢弹琴的妹子。 TA 经常在世界各地弹琴，比如 APIO/CTSC 赛场。 众所周知，[数据已删除] 是个喜欢唱歌的妹子。 TA 经常在世界各地唱歌，比如各种模拟考现场。 阅读更多…

地震后的幻想乡 题意 一幅图的每条边的权值为互不相关的 $[0,1]$内的连续随机变量。求图的最小生成树的最大边的权值的期望，结果保留 6 位小数。 概率密度函数 在研究连续型随机变量的过程中，我们一般用概率密度函数 $\rho_a(x)$描述一个随机变量的取值。 $\rho_a(x)$在 $x$处 阅读更多…

从卷积到反演 狄利克雷卷积 对于卷积，我们应该并不陌生。最简单的卷积从我们常见的竖式乘法开始，再到生成函数 (多项式) 的相乘，无处不在。 多项式相乘就是一种卷积。次数为 a 和 b 的项的系数相乘得到系数为 $(a+b)$项的系数。 $$ C[n]=\sum_{i=0}^{n}A[i]B[n-i] 阅读更多…

扩展 CRT 突然发现博客里中国剩余定理的文章少之又少。。。 然后昨天考场上忘了 CRT… 然后就自己 YY 了一个扩展 CRT 发现是对的。。。（换句话说就是我想了半天想起来了）于是印象加深了很多，就写篇文章记录一下。。。 首先扩展 CRT 是用来解决模数不互质情况下的模意义一元线 阅读更多…

题面 切此题建议配的 BGM：おしおき feat.アーケードラビット（七海千秋处刑专用）七海千秋是希望之峰学院 77 级 1 班的班长，其能力为 “超高校级的游戏玩家”，擅长除了恋爱游戏以外的全类型游戏，尤其喜欢 $gyara-\omega$一类的弹幕射击游戏。 最近七海又在攻略一款弹幕射击游戏， 阅读更多…

拉格朗日解题报告 (思路来源：BZOJ 滑行) 题意 在无穷大的水平面上有一个平面直角坐标系。N-1 条垂直于 x 轴的直线将空间分为了 N 个区域。 你被要求把 $(0,0)$处的箱子匀速推到 $(x,y)$。 箱子受水平面的摩擦力与正压力正相关，所以在每个区域的摩擦力可以表示为 $f_i$。$[ 阅读更多…

1. 题面 题目描述 boshi 是 Rayment 的好朋友。 Rayment 最近迷上了一个叫 Just Shapes & Beats 的音游，于是就推荐给了 boshi(网易云上也有这个游戏部分音乐的歌单)。可 boshi 有点着迷于游戏音乐难以集中精神，有时反应慢了半拍，导致他在第二 阅读更多…