题解：8.15 模拟赛

· · 个人记录

组别：B

A. 积木 box

题意：给一些积木，每个积木都有承重值，表示它上面最多能放几个积木。把所有积木堆起来，求最少堆几列。

从下往上考虑并不好做，要考虑很多东西。那我们从上往下考虑，发现这是无后效性的。所以可以给积木按承重值从小到大排序，每个积木找底部承重值小于它且最接近它的堆并加入底部即可。容易证明这很对。复杂度O(n^2)。

对这题的评价：3.5+2（黄）

B. 购物 market

题意：给一些商店，所有商店只卖一种物品，且每个商店的有物品单价、价值和开门时间几个属性。多次询问在t时刻用m块钱最多能买到多少东西。

直接对时间扫描线，把商店和询问都挂在每个时间点上。从小到大枚举时间，把每个时间点的商店加入01背包转移一下，对这个时间点的询问直接查dp数组即可。

但直接做是会炸空间的。发现价值和重量不同级，所以我们反过来对价值dp，设f(i)为用i价值能凑出的最小重量，转移类似，查询的时候二分重量即可。复杂度O(qmv)。

对这题的评价：4+3（绿）

C. 和式 sum

题意：给定序列a,b，对每个i求：

\sum_{j=1}^i a_{\lfloor\frac{i}{j}\rfloor} b_{i\bmod j}

考虑对每个i求答案。这个东西一眼看上去就能整除分块，尝试着推一下，设当前区间[l,r]：

\begin{aligned} Ans&=\sum_{j=l}^r a_{\lfloor\frac{i}{l}\rfloor} b_{i\bmod j}\\ &=a_{\lfloor\frac{i}{l}\rfloor}\sum_{j=l}^r b_{i\bmod j}\\ &=a_{\lfloor\frac{i}{l}\rfloor}\sum_{j=l}^r b_{i-\lfloor\frac{i}{j}\rfloor\times j} \end{aligned}

设t={\lfloor\frac{i}{l}\rfloor}，则：

\begin{aligned} Ans&=a_t\sum_{j=l}^r b_{i-tj} \end{aligned}

问题转化为求\sum_{j=l}^r b_{i-tj}。考虑预处理一个前缀和，sum_{i,j}表示b_j+b_{j-i}+b_{j-2i}...，也就是b数组从j开始每次往前跳i格的和，则式子化为：

\begin{aligned} Ans&=a_t(sum_{t,i-tl}-sum_{t,i-t(r+1)}) \end{aligned}

复杂度O(n\sqrt n)，但预处理前缀和是O(n^2)的，不如暴力。看到这个“跳”的操作，想到根号分治。我们只预处理i\leq \sqrt n的前缀和，对t\leq \sqrt n的部分用上面的做法，其余部分直接暴力，复杂度仍为O(n\sqrt n)，可以通过。

比赛的时候根号分治写错了，但块长取的\sqrt n，没有爆炸。

神·cszhpdx得到了一个求答案和的线性做法：

我们把余数和商联系起来，取i=pj+q，枚举j,p,q：

\begin{aligned} \sum_{i=1}^n\sum_{j=1}^i a_{\lfloor\frac{i}{j}\rfloor} b_{i\bmod j}&=\sum_{j=1}^n\sum_{q=0}^{j-1}\sum_{p=1}^{\lfloor\frac{n-q}{j}\rfloor}a_pb_q\\ &=\sum_{j=1}^n\sum_{q=0}^{j-1}b_q\sum_{p=1}^{\lfloor\frac{n-q}{j}\rfloor}a_p \end{aligned}

对a做前缀和，记为A，并设t={\lfloor\frac{n-q}{j}\rfloor}，则：

\begin{aligned} \sum_{j=1}^n\sum_{q=0}^{j-1}b_q\sum_{p=1}^{\lfloor\frac{n-q}{j}\rfloor}a_p&=\sum_{j=1}^n\sum_{q=0}^{j-1}b_qA_{\lfloor\frac{n-q}{j}\rfloor}\\ &=\sum_{j=1}^n\sum_{t=n-j+1}^nb_{n-t}A_{\lfloor\frac{t}{j}\rfloor} \end{aligned}

发现确定\lfloor\frac{t}{j}\rfloor即可确定t的范围，进而可以用前缀和优化。枚举\lfloor\frac{t}{j}\rfloor，设B_{l,r}=\sum_{i=l}^rb_i，则：

\begin{aligned} \sum_{j=1}^n\sum_{t=n-j+1}^nb_{n-t}A_{\lfloor\frac{t}{j}\rfloor}&=\sum_{j=1}^n\sum_{k=\lfloor\frac{n-j+1}{j}\rfloor}^{\lfloor\frac{n}{j}\rfloor}A_k\sum_{t=\max(kj,n-j+1)}^{\min(k(j+1)-1,n)}b_{n-t}\\ &=\sum_{j=1}^n\sum_{k=\lfloor\frac{n-j+1}{j}\rfloor}^{\lfloor\frac{n}{j}\rfloor}A_kB_{{n-\min(k(j+1)-1,n)},{n-\max(kj,n-j+1)}} \end{aligned}

容易发现内层和式枚举次数不超过2，所以复杂度O(n)。

对这题的评价：(6.5~7)+3.5（蓝~紫）