Div1

Div2

Karen and Morning

暴力枚举即可。

代码

Karen and Coffee

差分求出每个点被覆盖的次数,再求一个被覆盖次数是否 $\geq k$ 的前缀和即可。

代码

Karen and Game

先把行尽量删完,再把列尽量删完,如果最后剩下了则无解。

但这不一定是最优的,还有可能先把列尽量删完,再把行尽量删完。两种情况比一下即可。

代码

Karen and Test

$n$ 为偶数时,手玩一下可以发现,倒数第二行的两个数一定是

$$ \sum_{i=0}^{n/2-1}{n/2-1\choose i}a_{2i+1} $$

$$ \sum_{i=0}^{n/2-1}{n/2-1\choose i}a_{2i+2} $$

而最后是 + 还是 - 取决于 $n$ 是否能被 $4$ 整除。

$n$ 为奇数时,模拟一遍转成 $n$ 为偶数的情况即可。

代码

Karen and Supermarket

设 $dp_{i,j,0/1}$ 表示以 $i$ 为根的子树选了 $j$ 个点,$i$ 是否用了券的最小花费,转移类似于树形背包。

求答案时找到最大的满足 $\min\left\{dp_{1,x,0},dp_{1,x,1}\right\}\leq b$ 的 $x$ 即可。

代码

Karen and Cards

考虑枚举 $x$,那么 $a_i<x$ 的三元组要满足 $b_i<y\lor c_i<z$,$a_i\geq x$ 的三元组要满足 $b_i<y\land c_i<z$。

设 $mxc_j$ 表示 $b_i\geq j$ 的三元组中最大的 $c_i$,$mx3$ 表示 $a_i\geq x$ 的三元组中最大的 $c_i$,那么 $z$ 要满足 $z>mxc_y,z>mx3$,方案数为 $r-\max\left\{mxc_y,mx3\right\}$。

这样子要枚举 $x,y$,是 $\mathcal{O}(n^2)$ 的,我们考虑优化掉枚举 $y$。

可以发现 $mxc$ 是单调不升的,所以一定存在一个分界点 $k$,使得 $mxc_k\leq mx3,mxc_{k-1}>mx3$。我们只要在枚举 $x$ 时维护一下 $k$,然后利用 $mxc$ 的前缀和即可求出方案数。

代码

Karen and Neighborhood

不会做 /dk

最后修改:2020 年 09 月 23 日 09 : 26 AM