Blog
I use blog to record something.
【概率期望】CF398B Painting The Wall
题面 有一个 $n \times n$的网格，其中 $m$ 个格子上涂了色。每次随机选择一个格子（有可能是涂过色的格子）涂色，求让网格每一行每一列都至少有一个格子涂了色的操作次数期望。 输入输出样例 输入 5 2 2 3 4 1 输...
oi-HAOI2008硬币购物
题面 硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。 输入 第一行 c1,c2,c3,c4,tot 下面tot行 d1,d...
容斥原理小记
容斥原理 公式 $|\bigcup\limits_{i = 1}^na_i| = \sum\limits_{k = 1}^{n}(-1)^{k-1}\times\sum\limits_{1\leq i_1\le i_2\le i_3…...
【贪心】购买书籍
题面 L的书籍被M偷了以后伤心欲绝，决定再购买一些回来，现在有 N 本书可以买，每本书的价格是 a[i]元。 现在L总共有 M 元，以及 K 张优惠券。 对于每本书，如果使用一张优惠券，则可以用b[i]的优惠价格购买。 注意每本书只能...
unknown title
测试 T1 求由 1 到 n 一共 n 个数字组成的所有排列中，逆序对个数为 k 的有多少个 解答 动态规划： dp[i][j]表示长度为i，逆序对个数为j的方案数，那么有如下转移： $dp[i][j] = dp[i-1][j]+\s...