2021牛客暑期多校训练营9¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 60/1238（校内2/19） | 4 | 10 | 10 |
A¶
upsolved by TYB
题意¶
求\(\sum_{i=0}^n\sum_{j=1}^{\lfloor\frac{ai+b}{c}\rfloor}i^pj^q\)
\(1\le n,c\le10^9,0\le a,b\le10^9,0\le p,q\le50\)
题解¶
我们知道类欧几里德算法可以求解形如\(\sum_{i=0}^ni^p\lfloor\frac{ai+b}{c}\rfloor^q\)的式子，详情见【LOJ138】类欧几里得算法_cz_xuyixuan的博客-CSDN博客。
那么对于本题，只需要将后面的\(\sum_{j=1}^{\lfloor\frac{ai+b}{c}\rfloor}j^q\)拆成多项式，然后套用模板即可。
B¶
upsolved by JLK
题意¶
给定一个\(n\)个点\(m\)条边的图。定义一个子图\(S\)是k-degree的，当且仅当所有点度数都大于等于\(k\)，并且\(S\)是联通的，并且\(S\)是最大的。（即，\(S\)除了自己的的任何一个子图都不是k-degree的）
再给出\(M,N,B\)三个参数。\(m(S)\)表示\(S\)里的边数，\(n(S)\)表示\(S\)里的点数，\(b(S)\)表示\(S\)里的点连到\(S\)外的点的边数。求出所有k-degree的子图中\(M\times m(S)-N\times n(S)+B \times b(S)\)的最大值。（\(k \gt 0\)）
\(1 \le n,m \le 10^6,-10^9 \le M,N,B \le 10^9\)
题解¶
首先考虑如何确定一个k-degree的子图。不难发现，一个(k+1)-degree的子图一定被包括在一个k-degree的子图里。也就是\(k\)从大到小，k-degree子图的范围是越来越大的。那么就要处理出一个点最早成为k-degree子图的一部分的\(k\)。
首先每个连通块都是1-degree子图。对于一个k-degree子图，如果删去所有度数为\(k\)的点（删去旁边的一个点后变得小于\(k\)了也算），就是(k+1)-degree。
这样扫一遍可以得到每个点的最早的\(k\)，设其为\(rk_i\)。
接下来需要计算答案。
删点不便于计算，考虑加点，即按\(rk_i\)从大到小加入。计算加入每个点的贡献。
设点\(x\)通过一条边到达的点里\(rk\)比它小的为\(E(\lt)\)，等于大于同理
一个点对\(n(S)\)的贡献就是1，对\(m(S)\)的贡献是\(E(\gt)+\frac{E(=)}2\)（如果同\(rk\)的两个点连边，当做各贡献一半），对\(b(S)\)的贡献是\(E(\lt)-E(\gt)\)（加入新的边界边，删去老的边界边）。
再用并查集维护一下联通信息即可。每次遍历边的时候，把已经是k-degree的连通块并到当前点里，然后把连通块的答案也累加过来。
由于还需要保证\(S\)是最大的，那么对于每个\(k\)，加入所有点之后，扫一遍k-degree的所有连通块，把连通块的答案和最终答案比较。
排序可以使用基数排序，或者直接用vector之类的，做到线性。
\(O(n\alpha(n)+m)\)
C¶
upsolved by JLK
题意¶
二维平面的\(y\)轴上有\(n\)个点，对于每个\(i\)，每次只能往右或者往下，要从\((0,a_i)\)走到\((i,0)\)且所有路径不能相交，求方案数。
\(1 \le n \le 5\times 10^5,0 \le a_i \le 10^6,a_i \le a_{i+1}\)
题解¶
由LGV引理，答案为
每列提出阶乘，经过初等变换，可以得到
再每行提出\(a_i+1\)，就是范德蒙行列式的转置形式。
那么\(Ans=\prod\limits_{i=1}^n\frac{1}{i!}\times \prod\limits_{i=1}^n(a_i+1)\times \prod\limits_{1 \le j \lt i \le n}(a_i-a_j)\)
只需要算出最后一部分即可。这可以使用FFT，分别将\(a_i\)和\(-a_i\)设置为下标，卷积后取大于零的部分，卷积后的\(c_i\)即为\(i\)这个数的指数，再用快速幂计算即可。
\(O(a_n\log a_n)\)
D¶
**upsolved by **
题意¶
题解¶
E¶
solved by JLK
题意¶
有一棵以1为根的树，每个点有权值，从根开始，越远权值越小。\(q\)次询问，每次询问从\(x\)点开始，经过权值在\([L,R]\)的点，总共可以到达多少个点。
\(1 \le n \le 10^5\)
题解¶
由于保证了深度越小权值越大，那么找到最浅的满足条件的点后，就相当于是在子树里找所有\([L,R]\)的点，这些点肯定都能到达。
找这个点可以通过倍增。离线之后按dfs序建主席树即可查询。
\(O((n+q)\log n)\)
赛时为了方便是用的DSU on tree+BIT，也并不太慢。
F¶
upsolved by JLK
题意¶
买或卖股票，总共有240分钟，每分钟可以进行交易。第\(i\)分钟成交价格为一股\(p_i\)，最多成交\(v_i\)股。每次交易股数一定要是100的倍数，而且每次交易要付交易额\(0.03\%\)的手续费（不足5元的当做5元，四舍五入到分）。求买/卖\(a\)股后最大的钱变化量。（开始为0，可以为负）保留两位小数。
\(100 \le a \le 5\times 10^6,0 \le v_i \le 5\times 10^5,0.01 \le p_i \le 3550\)
题解¶
可以把数量除100，把一股的价格乘100，再在整个过程中乘100，最后除100，过程中避免小数。（注意乘100的时候需要round）
首先列出递推式，以买入为例：
\(dp_{i,j}\)表示前\(i\)分钟，买了\(j\)股的最大钱变化量。
\(dp_{i,j}=\max\limits_{j-v_i \le k \lt j}\{dp_{i-1,k}-100(j-k)p_i-\max\{\left[ \frac{3}{100}(j-k)p_i\right] ,500\}\}\)
（也可以这一分钟完全不买）
难点在于不足5元的情况。将上面的max拆掉，再将取整拆掉，可以得到
\(dp_{i,j}=\max \begin{equation} \left\{ \begin{array}{lr} dp_{i-1,k}-100jp_i+100kp_i-500, & 3(j-k)p_i \le 50000 \\ dp_{i-1,k}-100.03jp_i+100.03kp_i, & 3(j-k)p_i \gt 50000 \end{array} \right. \end{equation}\)
由于最大购买量和不足5元的限制，dp被分成两个区间，分别是这两种转移。可以用两个单调队列来维护（因为转移时\(j,k\)不会互相影响）。求出两种转移最优的\(k\)然后取max即可。
需要注意的是，单调队列里判断的时候可以直接用上式判断，即不取整。最后算的时候取整。因为只有这个取整部分会出现小数，其他都是整数，所以去掉取整符号对决策点的选择没有影响。
\(O(240\times \frac a{100})\)
G¶
solved by TYB
题意¶
一颗\(n\)个结点的以\(1\)为根的树，每个结点上有一个小球，每个小球会同时向父亲结点移动。每个结点都有\(p\)的概率成为吸收点，特别地，\(1\)号结点一定为吸收点，小球到了吸收点后会马上消失。若两个小球同时到达某个结点，不论该结点是否为吸收点，则视为发生碰撞，整个过程马上结束，获得的分数为\(0\)。若不发生碰撞，获得的分数为\(\sum_{i=1}^nf_i\)，\(f_i\)为初始在\(i\)结点的小球在到达吸收点前经过的边数。求期望分数。
\(n\le5\times10^5\)
题解¶
首先注意到一个性质，每个结点最多有一个儿子不是吸收点，否则一定会发生碰撞。考虑如何计算贡献，我的方法是枚举每个结点作为吸收点，计算被这个点吸收掉的所有小球的贡献。为方便起见，以下称吸收点为黑点，非吸收点为白点。树形DP，\(g[x]\)表示从\(x\)开始的一条白点的链的期望长度，\(f[x]\)表示从\(x\)开始的一条白点的链的期望贡献。注意\(f\)是一个二次的东西，要配合\(g\)进行转移。最后计算答案的时候，因为我们DP的时候仅考虑了那条链，所以还要乘上除了这条链外其它结点上都不会发生碰撞的概率。细节较多，实现时要头脑清晰。
H¶
solved by TYB
题意¶
定义仅由\(2,3,6\)组成的数为happy numbers，求出第\(n\)个happy number。
\(n\le10^9\)
题解¶
求出位数后逐位确定即可。
I¶
solved by JLK
题意¶
晦涩难懂，略
题解¶
十分简单，略
J¶
**upsolved by **
题意¶
题解¶
记录¶
开局签H(0:21)。JLK写E(0:39)。
然后想了ACJ，都没有什么想法。
JLK看了F巨长题面之后，以为是水题，交了一发WA(1:29)。然后发现题目中有个限制，想不出来，于是扔了。
TYB写G，中间调试多花了一点时间，一发AC(2:56)。
觉得A是个推式子题，扔了，继续想CJ。JLK想到了C以前做过类似的题是用行列式，但是没有想下去。J想过用带花树、模拟退火，最后YZW尝试用线性规划。
YZW对着板子尝试，WA1(4:00)。
JLK和TYB尝试理解I的题意。在发了clar之后推出了式子，但是式子没推完全，没有考虑分母为0的情况，WA了4发后AC(4:32)。
之后YZW还在尝试J，没有成功。
总结¶
JLK：可能对板子确实不太熟悉。J这种题应该多观察一下图的性质。
Dirt¶
I(-4)