2021 BUAA Spring Training 8¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| ⅛ | 10 | 11 | 12 |
A¶
solved by JLK
题意¶
过于签到，略
题解¶
略
B¶
solved by JLK
题意¶
有\(n\)个广告，一开始有\(m\)个观众，每个广告可以选择播放或者不播放。若不播放则无影响。若播放，假设播放前有\(x\)个观众，那么有\(x\times p_i\)的收益，并且在之后观众个数变为\(\lfloor\frac {x}{d_i}\rfloor\)，求最大收益。
\(1 \le n,m \le 10^5,1 \le p_i \le 10^6,1 \le d_i \le m\)
题解¶
首先把\(d_i=1\)的忽略，因为必选。
若\(d_i,d_j\gt 1\)，则\(\lfloor \frac{\lfloor\frac {x}{d_i}\rfloor}{d_j}\rfloor=\lfloor\frac {x}{d_i d_j}\rfloor\)。
那么变化得到的结果一定只有\(2\sqrt m\)种。DP时只需要记\(2\sqrt m\)个状态即可。
我实现的时候是小于等于\(\sqrt m\)的直接用滚动DP数组维护，大于的按从大到小排列，转移到一行新的然后类似归并。
更好的实现方法是把大于\(\sqrt m\)的\(x\)放到\(\lfloor \frac m x \rfloor\)，用两个DP数组维护。
\(O(n\sqrt m)\)
C¶
solved by JLK
题意¶
有\(n\)个事件，在二维平面上，每个事件是出现一个人或一只怪。怪有生命值和坐标。人有坐标和攻击半径、攻击力。出现时会找到最近的怪当中编号最小的移动过去（若没有则不移动），对半径\(r\)范围内的怪造成\(3\times atk\)的伤害。如果怪死了则消失，没死则会在结束攻击后使人离开战场。
最后对于怪或人输出是否还在战场上。
\(1 \le n \le 2 \times 10^3,0 \le \lvert x\rvert,\lvert y \rvert,r \le 10^8,1 \le atk,h \le 10^8\)
题解¶
按题意模拟即可。由于坐标不大，直接用long long存平方即可。
\(O(n^2)\)
D¶
upsolved by TYB
题意¶
给出\(n,h\)和\(n-1\)个形如\(a_i>a_{i+1}\)或\(a_i<a_{i+1}\)限制，求每个数都在\([1,h]\)范围内，且满足\(n-1\)个限制条件的正整数序列\(\{a_n\}\)有多少个。答案对\(10^9+7\)取模。
\(n\le 3000,h\le 10^6\)
题解¶
考虑容斥，如果把原来的全部看作限制条件，那只是\(>\)变成\(\le\)，\(<\)变成\(\ge\)，与原问题没有本质区别，仍然难以计算。所以换一种思路，容斥算至少有\(i\)个\(>\)不满足条件的方案数，也就是把其中的\(i\)个变成\(\le\)的方案数。这样之后，剩下的\(>\)作为分界点，就把原序列分为了若干段，每一段都是形如\(<.\le,<,<,\dots,\le,\le\)这样的序列（若两个\(>\)相邻则为没有限制的空序列），这个方案数是可以直接用组合数算的。考虑怎么算这个东西，可以带着容斥系数DP。\(f_i\)表示填完第\(i\)个数带容斥系数的方案数，那么枚举下一段的终点\(j\)，计算\([i+1,j]\)这一段的方案数即可转移。注意终点后的限制条件必须为\(>\)或终点就是\(n\)，否则两段是可以拼在一起的。复杂度\(O(n^2)\)。
E¶
solved by TYB
题意¶
过于签到，略
题解¶
略
F¶
solved by TYB
题意¶
给出一个\(n\)个点\(m\)条边的无向连通图，为每个点选择一个权值\(a_i\)或\(b_i\)，使最后图中由边直接相连的两点权值差的绝对值最大值最小。
\(1\le n ,m\le 10^5\)
题解¶
显然可以二分答案转化为判定性问题。
然后相当于每个点必须取\(0/1\)两种取值之一，然后给出一些限制，形如点\(x\)选了\(0\)，那么点\(y\)必须选\(1\)。这是一个\(2-sat\)模型，把原图的每个点拆成两个点，然后新图中一条\(x->y\)的有向边意义为选了\(x\)就必须选\(y\)，\(Tarjan\)求强连通分量后判断原图拆出来的两个点是否在同一个强连通分量内即可。
G¶
solved by JLK/hack data by YZW
题意¶
有两个由\(n\)行小写字母字符串组成的文本，每行左对齐，右边不一定对齐。两个文本每行的宽度相同。给出形如\(a2b3\)的形式表示\(aabbb\)字符串。现在要在第一个文本里从一格开始，走四联通，可以重复，并把整个路径变成一个字母，问是否能一次操作变成第二个文本。
\(1 \le n \le 5\times 10^5, 1 \le d \le 10^5,1 \le \sum t_j \le 10^9\)
\(d\)为形如\(ax\)的个数总和，\(t\)为长度。
题解¶
如果\(t\)很小，可以直接把文本建出来，然后找不同。如果目标字母大于一个，则无解。否则把所有不同的格子用并查集连起来。注意到不用变的格子有可能也会被走过。判断是否所有要变的格子构成一个连通块。
而题目给的\(t\)巨大，需要根据给出的区间讨论。那么就类似归并讨论一下相邻区间的交之类的。细节较多。
需要注意的是，\(a1a1\)这样的输入也是合法的。
\(O(d)\)
H¶
solved/upsolved by
题意¶
题解¶
I¶
solved by Snakes
题意¶
圆心位于原点，半径为 \(R_1\) 的圆作为目标。一次攻击的落点等概率散布在圆心位于原点，半径为 \(R_2\) 的圆内，攻击范围为以落点为圆心，半径为 \(r\) 的圆。当目标与攻击范围相交时造成 \(a\) 伤害，伤害大于等于 \(h\) 时目标摧毁。
求 \(n\) 次攻击摧毁目标的概率对 \(10^9+7\) 取模的结果。
\(1\leq n\leq 5\times 10^6\)，\(1\leq R_1,R_2,r\leq 10^8\)，\(1\leq a,h\leq 10^8\)。
题解¶
易见单次攻击造成伤害的概率 \(p=\min\left\{1,{(R_1+r)^2\over R_2^2}\right\}\)。
至少造成 \(t=\left\lceil {a\over h}\right\rceil\) 次伤害可摧毁目标。
答案即为 \(\sum_{i=t}^n \binom n i p^i (1-p)^{(n-i)}\)。
时间复杂度 \(O(n)\)。
J¶
solved by Snakes
题意¶
给定长为 \(n\) 的非负整数序列 \(a_1,\dots,a_n\)。有以下两种操作：
- 给定 \(l,r,x\)，区间 \(a_l,\dots,a_r\) 二进制与 \(x\)；
- 给定 \(l,r\)，查询 \(\sum_{i=l}^r a_i^2\) 对 \(998244353\) 取模的结果。
操作共 \(q\) 次。
\(1\leq n\leq 3\times 10^5\)，\(0\leq a_i<2^{24}\)，\(1\leq q\leq 3\times 10^5\)。
题解¶
注意到每个数至多会被与 \(24\) 次。
线段树维护每个区间的或和以及平方和，修改时只修改与 \(x\) 后有变化的区间，查询时直接查询即可。
可以分析得到时间复杂度为 \(O(n(\log n+\log a))\)
K¶
solved by TYB
题意¶
给出字符串\(S\)，判断是否可以仅翻转一个区间，使该字符串变为回文串。
多组数据，\(\sum |S|\le 5\times 10^5\)
题解¶
显然可以把首尾相同的字符一起去掉，直到字符串首尾不同，且新串和原串的答案一样（是/否可以变为回文串）。
然后新串的翻转区间必须至少包含左端点和右端点其中之一，否则首尾不同，一定不是回文串。
这样可能的翻转区间是只有\(2n-1\)个，直接枚举然后用\(hash\)判断即可。
注意不要用自然溢出，尽量双\(hash\)。
L¶
solved by JLK
题意¶
有\(n\)栋楼，楼之间有无向边，每栋楼有一个外卖订单，从\(q_i\)下单，之后有\(t_{i,1},t_{i,2} \cdots t_{i,d_i}\)个时间节点，过\(j\)时间节点后收益会变成\(p_{i,j+1}\)。不能在下单之前送达，可以原地不动。求送完所有外卖（不需要回去）的最大收益。
\(1 \le n \le 14,0 \le q_i \le 200,1 \le d_i ,t_{i,j}\le 200,0 \le p_{i,j} \le 10^8\)
题解¶
很明显可以状压。注意到给的时间节点最大是200，那么可以直接把时间看成是DP的一个状态。大于200时所有收益都固定，记为201时间即可。
\(dp[2^n-1][n][200]\)第一维代表已经送过的楼，第二维代表现在在哪，第三维是时间。预处理一下最短路和某个时间的在每个楼的收益即可。
\(O(200\times 2^nn^2)\)
记录¶
2min: JLK AC A
8min: TYB AC E
18min: YZW TLE I (-1)
22min: YZW AC I
33min: JLK AC C
47min: YZW RE J (-1)
56min: YZW AC J
1h40min: TYB WA K (-1)
1h48min: TYB AC K
1h52min: JLK AC B
2h06min: TYB AC F
2h30min: JLK AC L
3h41min: JLK WA G (-1)
3h51min: JLK WA G (-2)
4h22min: JLK AC G
总结¶
I 不要以为评测机看起来快就写 \(\log\)，追求好写 + 小常数 / 复杂度。
K 哈希可做就不必考虑 Manachar 等其他算法了。
B 常用的如 \(\sqrt n\) 一类的性质需要熟练运用 QAQ
D/H 注重分析性质，把握解题方向，练习精准的 observation（？
Dirt¶
G (-2)
I (-1)
J (-1)
K (-1)