洛谷4091 [HEOI2016/TJOI2016]求和
Luogu LOJ 分析 后面显然是卷积的形式，直接 NTT 即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/std...
分类 题解 下的文章
- 首页
- 题解
洛谷4770 [NOI2018]你的名字
Luogu LOJ 分析 先考虑 $l=1,r=|S|$ 的情况。 对 $S$ 和 $T$ 建 SAM。 设 $lim_i$ 表示 $T[1..i]$ 最长的是 $S$ 的子串的后缀的长度，可以在 $S$ 的 SAM 的 Parent 树上跳来求出： 如果有对应的转移直接走过去，匹配长度加 $1$； 否则跳 Parent 树，直到某个点有对应的转移，匹配长度变为该点的 $len$； 如果跳...
洛谷2178 [NOI2015]品酒大会
Luogu [LOJ](https://loj.ac/problem/2133） 分析 如果两个位置是 $r$ 相似的，则它们也是 $k\in[0,r)$ 相似的。我们可以只求出 LCP 为 $r$ 时的答案，再求一遍后缀和/后缀 max 即可得到答案。 考虑两个位置的 LCP 实际上是一段区间的 $height$ 的最小值。我们可以将 $height_i$ 从大到小排序，每次加入一个 $h...
洛谷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$ 的情况。 代码 //...
洛谷3760 [TJOI2017]异或和
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$...
洛谷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})$ 种...
CF149D Coloring Brackets
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$ 是一对匹配的括号，直接从...
洛谷3293 [SCOI2016]美味
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]$，主席树...
洛谷3826 [NOI2017]蔬菜
Luogu LOJ 分析 考虑求出卖了 $i$ 个蔬菜时的最大收益 $ans_i$。 容易想到，我们要先卖贵的菜，且要尽量靠后卖。 用一个堆维护所有还有存货的蔬菜，然后每次选一个收益最大的放在能放的最后的一天。 通过并查集维护每一天往前到哪一天才有没有用掉卖的额度即可求出这一天。 假设最多能卖 $cnt$ 个蔬菜，则前 $i$ 天的答案为 $ans_{\min\left\{cnt,m\tim...
洛谷3768 简单的数学题
Luogu 分析 这样就很好杜教筛了。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #defi...