洛谷5364 [SNOI2017]礼物
Luogu LOJ 分析 设 $f_n$ 表示第 $n$ 个人带来的礼物数，$s_n$ 表示 $f_n$ 的前缀和，显然有 $s_n=s_{n-1}+f_n=2s_{n-1}+n^k$。 我们只要求出 $s_{n-1}$ 即可求出 $f_n=s_{n-1}+n^k$。 考虑矩阵快速幂。这个 $n^k$ 不是很好转移，可以考虑二项式定理 可能需要特判 $n\leq 2$ 的情况。 代码 //...
Luogu LOJ 分析 设 $f_n$ 表示第 $n$ 个人带来的礼物数，$s_n$ 表示 $f_n$ 的前缀和，显然有 $s_n=s_{n-1}+f_n=2s_{n-1}+n^k$。 我们只要求出 $s_{n-1}$ 即可求出 $f_n=s_{n-1}+n^k$。 考虑矩阵快速幂。这个 $n^k$ 不是很好转移，可以考虑二项式定理 可能需要特判 $n\leq 2$ 的情况。 代码 //...
Luogu 分析 容易想到拆位。则我们需要计算有多少对 $(i,j)$ 满足 $s_j-s_{i-1}$ 的第 $k$ 位是 $1$。 那么有两种情况： 如果 $s_j$ 的 $0\sim k-1$ 位小于等于 $s_{i-1}$ 的 $0\sim k-1$ 位，则 $s_j$ 和 $s_{i-1}$ 的第 $k$ 位不同时满足条件。 否则，$s_j$ 和 $s_{i-1}$ 的第 $k$...
Luogu 分析 考虑每个数的贡献。假设 $x$ 在 $[l,r]$ 中出现了 $c$ 次，则有 $2^{r-l+1}-2^{r-l+1-c}$ 个子序列包含 $x$，所以其贡献为 $x(2^{r-l+1}-2^{r-l+1-c})$。 考虑把出现次数相同的放到一起，即求出每种出现次数对应的数的和。显然可以直接莫队。 注意到出现次数最多只有 $\mathcal{O}(\sqrt{n})$ 种...
Codeforces Luogu 分析 设 $dp_{l,r,0/1/2,0/1/2}$ 表示 $[l,r]$ 段，$l$ 没有颜色/红色/蓝色、$r$ 没有颜色/红色/蓝色的方案数。 当 $r-l+1=2$ 时为边界，有 $dp_{l,r,1,0}=dp_{l,r,2,0}=dp_{l,r,0,1}=dp_{l,r,0,2}=1$。 考虑转移。 如果 $l,r$ 是一对匹配的括号，直接从...
Luogu LOJ 分析 考虑沿用 $x=0$ 时的贪心，则我们需要判断是否存在 $a_i+x$ 在某个区间内。 具体地，假设当前位是 $1$，则我们需要判断是否有一个 $a_i+x$ 的这一位为 $0$。假设前面已经确定的位加上当前位的最优解是 $t$，则 $a_i+x\in[t,t+2^i-1]$ 都满足条件，我们只需要判断是否存在 $a_i\in[t-x,t+2^i-1-x]$，主席树...
Luogu LOJ 分析 考虑求出卖了 $i$ 个蔬菜时的最大收益 $ans_i$。 容易想到，我们要先卖贵的菜，且要尽量靠后卖。 用一个堆维护所有还有存货的蔬菜，然后每次选一个收益最大的放在能放的最后的一天。 通过并查集维护每一天往前到哪一天才有没有用掉卖的额度即可求出这一天。 假设最多能卖 $cnt$ 个蔬菜，则前 $i$ 天的答案为 $ans_{\min\left\{cnt,m\tim...
Luogu 分析 这样就很好杜教筛了。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #defi...
Codeforces Luogu 分析 有一个显然的状压 DP：设 $dp_{i,S}$ 表示前 $i$ 个人，$S$ 中的位置被选中时的最大力量值，转移枚举当前这个人当观众还是进某个位置即可。 然而 $p+k\leq n$，所以这个做法不太行。 注意到我们一定会选择 $a_i$ 较大的那些人当观众。将所有人按 $a_i$ 从大到小排序，当 $i-|S|>k$ 时 $i$ 显然不会被选...