2021牛客暑期多校训练营8¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 64/1357（校内6/19） | 5 | 9 | 11 |
A¶
solved by JLK
题意¶
垃圾题意
题解¶
垃圾签到题
B¶
upsolved by JLK
题意¶
有\(n\)个敌人，排成一列，每个人有生命\(h_i\)。有五种攻击方式：花费\(m_i\)对从前往后第\(i\)个敌人造成\(d_i\)伤害\((i \le 4)\)，花费\(m_E\)对前四个敌人同时造成40000伤害。一个敌人被打倒后就从队列里消失。求打倒所有敌人的最小花费。
\(1 \le n \le 20,1 \le d \le 20000,1 \le m \le 500,1 \le h \le 10^5\)
题解¶
这种问题很难贪心，而且范围很小，考虑DP。
一个敌人被打倒的过程可能有单体伤害和全体伤害的混合。但是由数据范围，受到全体伤害一定不超过三次。如果知道这个人受到几次全体伤害，就可以剩下只考虑单体伤害。
而一个敌人可能受到的单体伤害和这个人在敌人队伍里的位置有关。假设在整个过程中，这个敌人先后在队伍的第4/3/1个位置。（由于全体伤害，敌人在某两次攻击之间变化的位置可能不是连续的。）
如果这个人最终是被单体伤害打倒的，那么可以看做是这个人受到若干次全体伤害，在⅓/4位置受到对应的单体伤害若干次，最终在1位置受到致命一击。
如果这个人最终是被全体伤害打倒的，那么可以看做是这个人受到若干次全体伤害，在⅓/4位置受到对应的单体伤害若干次，血量到达了40000以下，最后受到全体伤害而死。
由于\(h \le 10^5\)，可以预处理出对于指定血量、指定位置集合的条件下，上面两种情况的最少花费（只考虑单体伤害）。即：随便攻击的最小花费，和最后一击一定是在最小位置上的最小花费。
在DP中记录前四个敌人的编号，他们经过的位置集合，以及分别受到了多少全体伤害。
经过的位置集合可以用二进制表示，由于自己这一位已经确定，只需要记录之前经过了哪些位置，这可以用3+2+1+0=6个二进制位表示。受到全体伤害的次数不超过两次，只需要记录当前的前多少个人受到了一次和二次伤害。
这样状态一共是\(n^4\times2^6\times 15\)。由于\(n\)很小，可以实现。
考虑转移。对于第一种情况，每次可以枚举被打倒的敌人，通过预处理的数据算出花费。对于第二种情况，就是整体施加一次全体伤害，但此时不止有只受到全体伤害而死的敌人，也有先受到一些单体伤害，再受到全体伤害而死的敌人。那么可以枚举一次全体伤害打倒的敌人集合，对于目前还没倒的，通过预处理的数据算出让他倒的最小花费。
转移的时候也比较麻烦，需要模拟找到到下一个状态。
可以让最终状态为\(n+1,n+2,n+3,n+4\)四个敌人，这样最后统计答案方便，但是在转移的时候也要注意不能打倒大于\(n\)的敌人。
总复杂度就是\(O(n^4\times 2^6\times 15\times 2^4+h\times 2^4)\)，还有若干常数。
C¶
upsolved by JLK
题意¶
有一个\(n\)个点的无向联通图，需要给每个点染成RGB三种颜色之一。如果一条边两端的颜色相同，边的颜色就变成它们的颜色，否则边的颜色是黑色。
要求染色后的图可以用黑边联通，并且要达成下列条件之一：
1.每个颜色的点数相同。
2.存在某一个颜色有着最多的点数，但没有这个颜色的边。
输出方案或判定无解。
\(3 \le n \le 3\times 10^5,3 \le m \le 5\times 10^5,n\mod3=0\)
题解¶
比较巧妙的性质题。
由于黑边的限制，可以考虑原图的一棵dfs树，对树上所有点用两种颜色（设为RG）染色，这样保证了一定黑边联通。
1.如果两种颜色的点数都小于\(\frac {2n}3\)，考虑第一种情况。
按结点深度从大到小枚举，如果点的当前颜色数量\(\gt \frac n3\)而且儿子都不是B，就把当前点的颜色改成B。
证明（感性）：首先这样可以保证黑边联通。主要是这样能否改成三个颜色均为\(\frac 3n\)。极端情况是链，由于至多改\(\frac n3\)个点，每次隔一个也只需要\(\frac {2n}3\)个点就能改好。而对于树，每个点的儿子多了，可以改的点也多了，故更容易改到目标状态。
2.如果有一种颜色的点数大于\(\frac{2n}3\)，考虑第二种情况。
将所有叶子结点染成B即可。
证明：首先这样可以保证黑边联通。设\(R \gt \frac {2n}3\)，\(G \lt \frac n3\)。肯定是有很多黑色的叶子。在这样的dfs树上，如果删去所有的叶子结点，就变成了\(R \lt G \lt \frac n3\)。（因为每一层的点数一定大于等于上一层的点数。）这样删去的叶子结点就大于\(\frac n3\)，如果把他们染成B，B就是最多的颜色。
而且dfs树上的叶子肯定构成一个独立集。故满足第二个条件。
没有无解的情况，复杂度\(O(n)\)。
D¶
solved by YZW
题意¶
给出两个长为 \(n\) 的非负整数序列 \(b_2,\dots,b_n\) 与 \(c_2,\dots,c_n\)，求满足以下条件的长为 \(n\) 的序列 \(a\) 的数量：
- \(b_i=a_{i-1}\,\text{or}\,a_i\)
- \(c_i=a_{i-1}+a_i\)
\(2\leq n\leq 10^5\)，\(0\leq b_i < 2^{30}\)，\(0\leq c_i < 2^{31}\)
题解¶
容易得到：\(a\,\text{and}\,b=(a+b)-(a\,\text{or}\,b)\)，而 and 和 or 的结果可以推出 xor，因此 \(a_i\) 都由 \(a_1\) 唯一确定。
拆位考虑，判断每一位取 0/1 是否符合条件即可求出方案数。
\(O(n\log b)\)
E¶
solved by TYB
题意¶
问\(x\)是否同时是质数和闰年。
题解¶
如果\(x\)是闰年，则\(x\)是\(4\)的倍数，所以不可能。
F¶
upsolved by JLK
题意¶
有一个\(n\times m\)的方格，0表示能走，1表示障碍物。\(q\)次询问，每次询问只往右或只往下或往右往下都可以时，一个点能否到达另一个点。
\(1 \le n,m \le 500,1 \le q \le 5 \times 10^5\)
题解¶
使用分治解决，比较巧妙。
首先只往右、只往下的情况可以直接for一遍。剩下只有距离大于等于两行的情况。
对行数分治。在分治的时候，把询问存在某个刚好使得询问被切开的地方。
显然，从起点如果可以到终点，一定会经过分界线，而且经过的时候，一定经过mid和mid+1两行的同一列的格子。预处理出上半部分和下半部分通过向右向下可以到达哪些分界线上的列。
回答询问的时候只需要定位到这个区间，然后枚举分界线上的列，判断起点能否到达分界线上某个点，再到达终点。
预处理用bitset加速，可以做到\(O(n^2mlogn/w)\)，每个询问\(O(qm)\)。
G¶
upsolved by
题意¶
题解¶
H¶
upsolved by TYB
题意¶
定义函数：
\(G(N)=\sum_{k_1+k_2+\cdots+k_t=N}F(p_1^{k_1}p_2^{k_2}\cdots p_t^{k_t})\)
\(F(n)=\sum_{a_1a_2\cdots a_m=n}\phi(a_1)\phi(a_2)\cdots\phi(a_m)\)
求\(G(N)\)。
\(N\le10^9,t\le10^5,m\le5,p_i\le10^5,\)结果对\(998244353\)取模。
题解¶
可以对\(m\)用归纳法证明，\(F(n)\)为积性函数，所以可以拆开计算。
两个函数的形式都类似于生成函数，\(F(p^{k})\)实际上为\((\sum_{i\ge0}\phi(p^i)x^i)^m\)的第\(k\)项系数，这个其实是一个等比数列求和，其封闭形式为\((\frac{1-x}{1-px})^m\)。定义\(G_{p_i}=(\frac{1-x}{1-p_ix})^m\)，则\(G(N)\)为\(\Pi_{i=1}^tG_{p_i}\)的第\(N\)项系数。
形如\(\frac{f(x)}{g(x)}\)的第\(n\)项是可以直接用常系数齐次线性递推算的，由于分子分母都大概有\(tm\)项，所以需要用NTT优化。
I¶
upsolved by JLK
题意¶
在普通德扑规则下给定自己的两张底牌和五张公共牌，另外有五人，他们的底牌是剩下的牌里随机分配，问自己赢过所有人的概率。
题解¶
首先可以通过枚举、模拟来比较出可以赢过哪些两张牌的组合。
接下来就是计数。如果把一张扑克牌看做点，两张牌的组合比自己小的在两者之间连边，那么就是问这个图里选五对点匹配的方案数。
点数\(n=45\)，边数\(m \le 990\)。
一种比较暴力的方法是，枚举两个匹配，剩下三个匹配用容斥来计算。也就是删去枚举的匹配里的四个点后，剩下的图里要找到三个匹配，考虑三条边的位置关系来容斥。
\(O(m^3/6+m^2n)\)，勉强可以通过。
学习其他队伍的代码时发现有使用记忆化搜索通过的。也就是\((i,j,k)\)表示选了\(i\)个匹配，当前考虑到了第\(j\)条边，选的点的状态为\(k\)。速度似乎略快一些。
J¶
solved by JLK&TYB
题意¶
给定一棵\(n\)个点的树，两个人分别站在\(s\)点和\(t\)点。轮流走路，每次必须走到旁边的没有被任何一个人走过的点，除非无路可走。每个人都要最大化自己走过的点数-对手走过的点数。求最优策略下先手的这个值的大小。
\(1 \le n \le 5\times 10^5\)
题解¶
首先肯定把\(s \to t\)的链抽出来，然后对于链上每个点预处理出往子树里走的最大距离。
考虑用\((i,j,0/1)\)表示两人分别在链上\(i,j\)的位置，当前是先手还是后手动。假设先手动，那么每次要么在链里向对方的方向走一格，要么跳到这个点的子树里。
如果向对方走一格，就从\((i+1,j,1)\)转移。如果走到子树里，那么先手不可能再在链上走了，后手可以在\([i+1,j]\)这一段任意走一个最长的链。
后手同理。转移的时候，对于先手要取max，而对于后手由于要让后手的值最大，就要让先手的值最小，取min。一个区间上走一个最长的链实际上可以看做区间最值问题。而询问的区间又是两个端点单调的，可以暴力移动。
总状态数\(O(n)\)，时间复杂度也为\(O(n)\)。
K¶
solved by YZW
题意¶
平面被分为 \(w\times d\) 的无限个区域，问一条长为 \(\pi\) 的路径最多经过多少个区域。
\(0<w,d\leq 5\)，保证 \(w,d\) 最多八位有效数字。
题解¶
注意到 \(\forall p/q \in \mathbb{Q}, \exists \varepsilon >0:|\pi-p/q|>\varepsilon\)，所以可以转化为在格点上行走的问题，经过的格点周围的四个区域纳入答案。
不难发现只会走 \(\min\{w,d\}\) 的边与 \(\sqrt{w^2+d^2}\) 的边，并且以某种边为主时另一种边至多出现两次，答案不难计算，枚举方案取答案最大值即可。
记录¶
TYB签E(0:07)。JLK不确定A的题意，尝试了一发WA。
YZW过D(0:38)。
随后一直讨论A的题意，没有搞懂，又试了一发WA。
YZW写K，没有考虑到一些情况，WA2后AC(1:19)。
JLK看了一万年A之后，发现\(x=0\)的条件，然后AC(1:28)。
然后JLK写J，一开始写法不对，WA1之后改过了(2:35)。
然后一起看F，YZW说了个假算法，都没有看出问题。结果调了2小时一直WA。后来对拍出错，才发现做法有问题。
还剩二十多分钟，TYB莽了个较为暴力的bitset写法，最后RE/TLE没调出来。
总结¶
JLK:还是要学会判断做法的正确性。不过今天的F确实有点抽象，不好判断。
Dirt¶
A(-2)
J(-1)
K(-2)