2020-2021:teams:legal_string:jxm2001:other:错题集_2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:other:错题集_2 [2020/08/08 23:11] jxm2001 |
2020-2021:teams:legal_string:jxm2001:other:错题集_2 [2020/08/09 00:16] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 23: | 行 23: | ||
| 考虑倒序枚举每个最小距离，求出该最小距离至少需要的关键点个数，然后更新该关键点个数对应的答案。 | 考虑倒序枚举每个最小距离，求出该最小距离至少需要的关键点个数，然后更新该关键点个数对应的答案。 | ||
| - | 总操作数为 $O(\sum_{i=1}^{n-1} \frac ni)=O(n\log n)$，删除子树和查询祖先操作时间复杂度为 $O(\log n)$，于是总时间复杂度为 $O\left(n\log^2 n\right)$。 | + | 总操作数为 $O(\sum_{i=1}^{n-1} \frac ni)=O(n\log n)$，删除子树和查询祖先操作时间复杂度为 $O(\log n)$。 |
| + | |||
| + | 于是总时间复杂度为 $O\left(n\log^2 n\right)$。 | ||
| 注意每次枚举完成可以给整棵树打上子树还原标记，不能暴力重建树，否则时间复杂度过高。 | 注意每次枚举完成可以给整棵树打上子树还原标记，不能暴力重建树，否则时间复杂度过高。 | ||
| 行 666: | 行 668: | ||
| 求 $\sum_{i=l}^rf(i)$。 | 求 $\sum_{i=l}^rf(i)$。 | ||
| - | ==== 题解 ==== | + | ==== 题解一 ==== |
| - | 考虑枚举 $a_1$，当 $a_1\lt m$ 时，考虑 $\text{dp}$。$\text{dp}(s,i,pos)$ 表示当前和为 $s$，同时 $a_1=i$，并且已经选择了 $i\sim i+pos$ 的数的方案数。 | + | 考虑枚举 $a_1$，当 $a_1\lt k$ 时，考虑 $\text{dp}$。$\text{dp}(s,i,pos)$ 表示当前和为 $s$，同时 $a_1=i$，并且已经选择了 $i\sim i+pos$ 的数的方案数。 |
| $\text{dp}$ 状态数为 $3nm$，于是时间复杂度为 $O(nm)$。 | $\text{dp}$ 状态数为 $3nm$，于是时间复杂度为 $O(nm)$。 | ||
| - | 当 $a_1\le m$ 时，记 $a_1=\text{lef},a_1+1=\text{mid},a_1+2=\text{rig}$，$\text{lef}$ 的个数为 $l$，$\text{mid}$ 的个数为 $m$，$\text{rig}$ 的个数为 $r$。 | + | 当 $a_1\le k$ 时，记 $a_1=\text{lef},a_1+1=\text{mid},a_1+2=\text{rig}$，$\text{lef}$ 的个数为 $l$，$\text{mid}$ 的个数为 $m$，$\text{rig}$ 的个数为 $r$。 |
| 于是考虑先将 $\text{lef},\text{rig}$ 合并为 $\text{mid}$，然后如果 $l\gt r$，则枚举 $l$ 与 $m$，然后再考虑拆分 $m$ 的方案，有 $\lfloor\frac {m-1}2\rfloor$ 种。 | 于是考虑先将 $\text{lef},\text{rig}$ 合并为 $\text{mid}$，然后如果 $l\gt r$，则枚举 $l$ 与 $m$，然后再考虑拆分 $m$ 的方案，有 $\lfloor\frac {m-1}2\rfloor$ 种。 | ||
| 行 718: | 行 720: | ||
| int l=read_int(),r=read_int(); | int l=read_int(),r=read_int(); | ||
| printf("Case #%d: %lld\n",++kase,ans[r]-ans[l-1]); | printf("Case #%d: %lld\n",++kase,ans[r]-ans[l-1]); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ==== 题解二 ==== | ||
| + | |||
| + | 考虑差分维护，观察 $a_1=1,k=7$ 的表格。 | ||
| + | |||
| + | ^ n ^ 10 ^ 11 ^ 12 ^ 13 ^ 14 ^ 15 ^ 16 ^ 17 ^ 18 ^ 19 ^ 20 ^ 21 ^ | ||
| + | |5个3| | | | | | | | | 1233333 | | | | | ||
| + | |4个3| | | | | | | 1123333 | 1223333 | | | | | | ||
| + | |3个3| | | | | 1112333 | 1122333 | 1222333 | | | | | | | ||
| + | |2个3| | | 1111233 | 1112233 | 1122233 | 1222233 | | | | | | | | ||
| + | |1个3| 1111123 | 1111223 | 1112223 | 1122223 | 1222223 | | | | | | | | | ||
| + | |num| 1 | 1 | 2 | 2 | 3 | 2 | 2 | 1 | 1 | 0 | 0 | 0 | | ||
| + | |一阶差分| 1 | 0 | 1 | 0 | 1 | -1 | 0 | -1 | 0 | -1 | 0 | 0 | | ||
| + | |二阶隔项差分| 1 | 0 | 0 | 0 | 0 | -1 | -1 | 0 | 0 | 0 | 0 | 1 | | ||
| + | |对应位置| $a_1k+3$ | 0 | 0 | 0 | 0 | $(a_1+1)k+1$ | $(a_1+1)k+2$ | 0 | 0 | 0 | 0 | $(a_1+2)k$ | | ||
| + | |||
| + | 于是考虑枚举 $a_1,k$ 即可，时间复杂度 $O(n\log n)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e5+5; | ||
| + | LL sum[MAXN]; | ||
| + | int main() | ||
| + | { | ||
| + | _for(i,1,MAXN) | ||
| + | for(int k=3;i*k<MAXN;k++){ | ||
| + | if(i*k+3<MAXN)sum[i*k+3]++; | ||
| + | if((i+1)*k+1<MAXN)sum[(i+1)*k+1]--; | ||
| + | if((i+1)*k+2<MAXN)sum[(i+1)*k+2]--; | ||
| + | if((i+2)*k<MAXN)sum[(i+2)*k]++; | ||
| + | } | ||
| + | _for(i,2,MAXN)//二阶隔项差分还原一阶差分 | ||
| + | sum[i]+=sum[i-2]; | ||
| + | _for(i,1,MAXN)//一阶差分还原原序列 | ||
| + | sum[i]+=sum[i-1]; | ||
| + | _for(i,1,MAXN)//前缀和 | ||
| + | sum[i]+=sum[i-1]; | ||
| + | int t=read_int(),kase=0; | ||
| + | while(t--){ | ||
| + | int l=read_int(),r=read_int(); | ||
| + | printf("Case #%d: %lld\n",++kase,sum[r]-sum[l-1]); | ||
| } | } | ||
| return 0; | return 0; | ||
2020-2021/teams/legal_string/jxm2001/other/错题集_2.1596899499.txt.gz · 最后更改: 2020/08/08 23:11 由 jxm2001
