洛谷5072 [Ynoi2015]盼君勿忘
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})$ 种，所以我...
M_sea 发布的文章
- 首页
- M_sea
洛谷3707 [SDOI2017]相关分析
LuoguLOJ分析前两个用平方和公式求，后两个用等差数列求和求，并打一个赋值标记即可。实现起来细节比较多。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #inc...
CF149D Coloring Brackets
CodeforcesLuogu分析设 $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$ 是一对匹配的括号，直接从 $dp_{l...
洛谷3293 [SCOI2016]美味
LuoguLOJ分析考虑沿用 $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]$，主席树即可。当...
洛谷3826 [NOI2017]蔬菜
LuoguLOJ分析考虑求出卖了 $i$ 个蔬菜时的最大收益 $ans_i$。容易想到，我们要先卖贵的菜，且要尽量靠后卖。用一个堆维护所有还有存货的蔬菜，然后每次选一个收益最大的放在能放的最后的一天。通过并查集维护每一天往前到哪一天才有没有用掉卖的额度即可求出这一天。假设最多能卖 $cnt$ 个蔬菜，则前 $i$ 天的答案为 $ans_{\min\left\{cnt,m\times i\ri...
洛谷3768 简单的数学题
Luogu分析这样就很好杜教筛了。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #define fi...
CF1316E Team Building
CodeforcesLuogu分析有一个显然的状压 DP：设 $dp_{i,S}$ 表示前 $i$ 个人，$S$ 中的位置被选中时的最大力量值，转移枚举当前这个人当观众还是进某个位置即可。然而 $p+k\leq n$，所以这个做法不太行。注意到我们一定会选择 $a_i$ 较大的那些人当观众。将所有人按 $a_i$ 从大到小排序，当 $i-|S|>k$ 时 $i$ 显然不会被选为观众，改...
CF1354G Find a Gift
CodeforcesLuogu分析蓝题都不会做了 /kk因为 $k\leq \frac{n}{2}$，所以随机一个盒子是石头的概率 $\geq\frac{1}{2}$。那么我们可以先通过若干次随机来较高正确率地判断第一个盒子是不是石头。如果不是的话直接输出即可；否则，可以通过倍增找到第一个礼物所在的区间 $[2^k+1,2^{k+1}]$，在这个区间中二分即可。代码// ==========...