demonlover的博客

前言

好久以前就想学来着, 咕了大概快两年…

概念

二项式反演为一种反演形式, 通常用于 指定某若干个 求 恰好若干个 的问题.

二项式反演虽然形式上和多步容斥类似, 但并不等价, 只是形式上都叫多步容斥.

简要题意

有一个长度为 $n$ 的 $01$ 串, 将第 $i$ 个位置变为另外一个数字的代价是 $v_i$ .

简要题意

有 $m$ 个人要去健身房健身, 健身房总共开放 $n$ 天, 第 $i$ 天的票价为 $a_i$ , 每个人可以在任意一天买任意张票, 若一张票在第 $t$ 天生效, 则它只会在 $[t,t+k-1]$ 的时间内有效.

简要题意

给定长度为 $n$ 的仅含有小括号和中括号的括号序列.

简要题意

一张有 $n$ 个点的图, 对于所有的 $i < j$ , 都有一条 $i$ 到 $j$ 的有向边. 要求给这 $\frac{n(n-1)}{2}$ 条边染色, 使得任意长度大于 $k$ 的路径都有至少两种颜色.

简要题意

山初始高度为 $d$ , 有 $n$ 个登山者, 每个登山者有技巧 $s_i$ 和整洁度 $a_i$ 两个值, 在 $d \leqslant s_i$ 时此登山者可登上山, 登上山后山的高度变为 $a_i$ , 求最多能有多少个登山者登顶.

考场甚至没能看到这题属实是拉了, 于是记录一下这个巧妙的题.

简要题意

给定一个长度为 $n$ 的序列, 序列中的每个数不大于 $K$ , 每次可交换相邻的两个数, 求最小交换次数使序列存在子区间满足 $a_i = 1, a_{i+1} = 2, \dots a_{i+K-1} = K$ .

矩阵树定理是利用矩阵行列式计算图的生成树个数的一个定理.