2021HDU暑期多校第八场¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 73/750 | 6 | 9 | 10 |
A¶
upsolved by JJLeo
题意¶
问 \([l,r]\) 不包含 \(7\)，存在一个非空前缀或非空后缀，使得其对应的数字被 \(x\) 整除的数有多少个。
题解¶
反向考虑，只需算出不存在非空前缀或非空后缀，使得对应的数字被 \(x\) 整除的数有多少个。
先枚举整个数模 \(x\) 是的值 \(y\)，再从高到低考虑，知道前缀模 \(x\) 是多少就能知道后缀模 \(x\) 是多少，最后只统计那些模 \(x\) 确实是 \(y\) 的方案。
最后用所有不包含 \(7\) 的数的数量减掉这些即为答案，这可以枚举贴上界的前缀，后面随便选因此是 \(9^i\)，扫一遍即可得到。
需要注意非空前缀，因此记一下当前是不是还是前导 \(0\) 即可。
B¶
upsolved by JJLeo
题意¶
\(n\) 个物品，每个物品可以选择买小的、买大的、或不买，价格分别为 \(0,1,2\)。此外，相邻的两个物品，如果都买了，可以选择将它们打包在一起，这样价格就会减少 \(1\)。每个物品只能被打进一个包里。问恰好花费 \(k\) 元钱的方案数，打包不同或者某一个物品买的不同都算不同方案。(\(1 \le n \le 10^9\)，\(1 \le m \le 2 \times 10^4\))
题解¶
设 \(f_{i,j}\) 是 \(i\) 个物品花费 \(j\) 元的方案数，则有 \(f_{i,j}=f_{i-1,j}+f_{i-1,j-1}+f_{i-1,j-2}+f_{i-2,j-1}+2f_{i-2,j-2}+f_{i-2,j-3}\)，设 \(f_{i}(x)=\sum \limits _{j=0} ^ \infty f_{i,j}x^j\)，则有 \(f_i(x)=\left(x^2+x+1\right)f_{i-1}(x)+(x^3+2x^2+x)f_{i-2}(x)\)，将矩阵快速幂的数换成保留 \(m+1\) 项的多项式，即可在 \(O(m \log m \log n)\) 的复杂度内完成，但是常数大飞了，板子常数巨大的我拒绝尝试。
考虑随便选一个分界点，考虑前 \(i\) 个物品和后 \(j\) 个物品对合起来 \(i+j\) 个物品的贡献，如果第 \(i\) 个物品和第 \(i+1\) 个物品没有打包，那两部分独立，贡献为 \(f_i(x)f_j(x)\)，否则枚举打包情况，贡献为 \(\left(x^3+2x^2+x\right)f_{i-1}(x)f_{j-1}(x)\)。因此有 \(f_{i+j}(x)=f_i(x)f_j(x)+\left(x^3+2x^2+x\right)f_{i-1}(x)f_{j-1}(x)\)。
维护 \([f_{i-2}(x),f_{i-1}(x),f_{i}(x)]\)，其和 \([f_{j-2}(x),f_{j-1}(x),f_{j}(x)]\) 可以通过数次多项式乘法转移到 \([f_{i+j-2}(x),f_{i+j-1}(x),f_{i+j}(x)]\)，那么类似快速幂的方法即可求出 \(f_n(x)\)，初始单位元为 \([0,0,f_0(x))]\)。
复杂度不变，但常数小很多。
E¶
solved by JJLeo
题意¶
将一个长度为 \(n\) 的数字串分为 \(k\) 个非空部分，权值即为将每个部分单独看作一个数加起来。求所有方案的权值和。(\(1 \le n \le 10^6\)，\(1 \le k \le n\))
题解¶
考虑每个位置的贡献，其贡献为 \(10^i\) 说明它距离下一个分割点差 \(i\) 个数字，那么剩下的位置就是随便切，一个组合数即可。对 \(i\) 求和是一个组合数关于 \(n\) 的部分和，随着位置的移动也只有 \(n\) 变化，维护两个前缀和，使用组合数前缀和的移步法即可解决。
G¶
upsolved by JJLeo
题意¶
给定一个长度为 \(n\) 的序列，定值 \(k\)，有 \(m\) 次以下两种操作：
- 区间加。
- 询问区间所有长度为 \(k\) 的子区间最大值的最小值是多少，保证区间长度不小于 \(k\)。
(\(2 \le k \le n \le 5 \times 10^8\)，\(1 \le m \le 10^5\))
题解¶
\(n\) 有亿点大，因此下面所有线段树都是动态开点的。
把原序列分为每段长度为 \(k\) 的 \(\left\lceil\dfrac{n}{k}\right\rceil\) 段，后面的段补什么都行，反正询问不到，也不会修改。
考虑对于相邻两段，如何求出位于这两段的最小值区间。容易发现每一个区间都是由前一段的一个后缀加后一段的一个前缀所组成的，随着其向右移动，后缀最大值单调不增，前缀最大值单调不减，找到最后一个后缀最大值大于前缀最大值的位置，该位置和下一个位置 (如果有) 即为可能的最小值位置。
求出这个位置可以直接二分加线段树 \(O\left(\log ^2 n\right)\) 完成，但是注意到前缀和后缀长度之和恰为 \(k\)，因此对每段建一个线段树，两棵线段树结构相同，可以直接在线段树上二分，只需 \(O(\log n)\)。
具体来说，如果第一棵线段树
之后再维护一棵线段树，整块直接区间查询，边角则用上面的方法单独询问
看起来我的实现实在太丑陋了，人都 de 没了，常数还老大。
J¶
upsolved by
题意¶
题解¶
记录¶
这场娱乐场来着
0h：MJX和CSK打着玩，边打边看其他集训队训练的榜，MJX看A巨蠢，然后写了，发现读错题了，MJX和CSK秒了仨签到。
1h：MJX看E巨水写了半天，WA了两发发现读错题了，CSK看H和MJX想了个解法就是对不上样例，看了快1h，MJX发现输入反了然后过了
2h：ZYF出现，MJX给ZYF喂D题，喂着喂着发现题又读错了，是个傻逼题，直接写了，ZYF看E发现也很好写，直接冲了。
3h：MJX给ZYF喂了个A题意，ZYF开冲，MJX推B式子，和CSK看那边集训队训练，然后CF爆炸了，开始挂机
4h：ZYF冲了好几次，然后寄了
After end：MJX B题式子改成递推的就很好写了，非得写成和式；ZYF A想太复杂了，直接寄，完全不好de