2021-2022 BUAA XCPC Team Supplementary Training 04¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 4/15 | 7 | 13 | 13 |
A¶
solved by TYB
题意¶
给一棵\(n\)个点的树，\(C\)种颜色，初始所有边都无颜色，只有一种操作，给出三元组\((u,c,m)\)，把\(u\)到\(1\)路径上的边染成颜色\(c\)，询问有多少种颜色的出现次数恰好为\(m\)。
\(n,C,Q\le2\times 10^5\)
题解¶
初看毫无头绪，考虑暴力，直接树剖，线段树维护区间是否是同一种颜色，如果区间不是同一种颜色则暴力递归到两个子树处理，这样单次操作的复杂度是\(\mathcal{O}(\log^2n+\)\(u\)到根颜色数\(\times \log n)\)，因为每种颜色最多被拆成\(\log n\)个区间。颜色数这个东西乍看是\(\mathcal{O}(n)\)的，但基于均摊分析（？）类似的东西考虑一下，每次只会多一种颜色，而且把原来的颜色全部覆盖了，应该总和才是\(\mathcal{O}(n)\)的。所以最后的复杂度是\(\mathcal{O}(Q\log^2n)\)。
B¶
upsolved by JLK
题意¶
有一个迷宫，从一个点开始，每次往一个方向走直到碰壁才能停下换方向。要收集地图上所有的星星，问是否可行。
\(1 \le H,W \le 50\)
题解¶
首先把地图上所有点拆成四个方向，便于处理转向的限制。然后可以在方向之间连有向边，表示现在在某个点以某个方向走，可以走到哪些状态。
那么找到强连通分量，同一个SCC里面的点肯定可以互相到达。
问题是不同SCC之间如何考虑。相当于是要从起点SCC出发，走一条路径，使得经过的SCC包括了所有星星。
一种做法是直接用bitset维护，在缩点后的DAG上跑，每个点选含有星星最多的一条路径，但我觉得这个做法并不很靠谱。
更加科学的一个做法是使用2-sat判断。也就是选择一些SCC进行遍历。
可以发现一个性质：一个点的四个方向最多属于两个不同SCC。因为向左和向右肯定是可以走到底再返回的，向上向下也是。
有如下的限制条件：
1.起点一定要选
2.对于两个互相不能到达的SCC（平行关系），不能同时选
3.对于星星的不同方向，如果只有一个SCC就必选，如果有两个就至少选一个。
跑一边2-sat即可。点数\(nm\)，边数\(n^2m^2\)级别。
\(O(n^2m^2)\)
C¶
upsolved by TYB
题意¶
数轴上\([1,n]\)每个整点上有一个左箭头或右箭头，每个箭头都会以相同速度朝着各自方向移动。当一个左箭头和一个右箭头相遇时会有一个固定的概率使得其中一方消失，问在无穷多的时间后留下恰好\(a\)个右箭头和\(b\)个左箭头的概率。
\(n\le5000\)
题解¶
首先可以发现，最后一定存在一个分界点，使得左边恰有\(b\)个左箭头存活，右边恰有\(a\)个右箭头存活。考虑DP。状态的设计很巧妙，以左箭头为例，\(f[i][j]\)表示考虑了前\(i\)个箭头，右边再来\(j\)个左箭头，最后恰有\(b\)个左箭头存活的概率。
若第\(i\)位为左箭头：\(f[i][j]=f[i-1][j+1]\)。这个转移比较显然。
若第\(i\)位为右箭头：\(f[i][j]=f[i-1][j]\times q+f[i][j-1]\times p\)，其中\(q\)为右箭头消失的概率，\(p\)为左箭头消失的概率。前一项含义为该右箭头在第一次与左箭头相遇时即消失，后一项的含义为该右箭头在第一次与左箭头相遇时，左箭头消失。这样巧妙地避免了枚举多少个左箭头消失，加快了转移。
然后用相同的方式计算出\(g[i][j]\)，最后答案即为\(\sum_{i=0}^nf[i][0]\times g[i+1][0]\)。
时间复杂度\(\mathcal{O}(n^2)\)。
D¶
upsolved by TYB
题意¶
给出\(n\)个变量，第\(i\)个的范围是\([L_i,R_i]\)，还有\(m\)个限制条件，形如第\(i\)个小于第\(j\)个，问是否能找到一组解使得\(n\)个变量都在\([1,n]\)范围且互不相同，如果可以输出一组方案。
\(n\le3\times10^5,m\le10^6\)
题解¶
如果没有\(m\)个限制条件，可以直接按左端点从小到大排序，相同则按右端点从小到大排序，依次填即可。有了那\(m\)个限制条件，直观的想法是根据这个再约束一下左右端点，比如\(d\)要大于\(a,b,c\)，则让\(L_d=\max(L_d,\max(L_a,L_b,L_c)+1)\)，可以通过拓扑排序完成。但这样会有一个问题，假如\(L_a=L_b=L_c=1\)，则\(L_d\)会被约束到\(2\)，但由于有不重复的限制，\(d\)至少为\(4\)，解决方法是把所有这些点的\(L\)值放在一起排个序，每次标记对应的位置，若已经标记则标记下一个即可。注意重边对这种做法的影响，一定要处理。复杂度是\(\mathcal{O}(n+m\log m)\)，不太优秀，3000ms的题2900ms卡过。
E¶
solved by TYB
题意¶
题解¶
F¶
solved by YZW
题意¶
题解¶
G¶
solved by TYB
题意¶
\(n\)个位置排成一列，每个位置上有权值，可以交换两个位置上的权值，至多交换\(k\)次，交换完后，要求\(\forall i\in[1,n],i-1,i,i+1\)这三个位置上的权值至少要选择一个（\(0\)和\(n+1\)都视为没有选择），求最小的权值和。
\(n\le250000,k\le9\)
题解¶
很经典的套路，交换可以视为选择某个位置，但那个位置免费，用某个未选择位置的权值补上。\(f[i][j][k][S]\)表示到第\(i\)个位置，后面有\(j\)个位置可以免费/前面有\(-j\)个位置的花费需要补上，用了\(k\)次交换机会的，最后两位的选择情况为\(S\)的最小花费，直接DP即可。
H¶
solved by JLK
题意¶
签到
题解¶
I¶
solved by YZW
题意¶
题解¶
J¶
upsolved by JLK
题意¶
有\(n\)列格子，每列高\(H_i\)。对于每个\([l,r]\)，都找出最大的一个矩形\((r-l+1)\times \min\limits_{i=l}^r\{H_i\}\)。并按面积排序。现在给定\(L,R\)，输出面积最小的第\(L\)个到第\(R\)个矩形的面积。
\(1 \le n \le 3\times 10^5,1 \le H_i \le 10^9,1 \le L \le R \le \frac{n(n+1)}2,R-L+1\le 3\times 10^5\)
题解¶
首先肯定要找到面积的上界和下界。这可以二分出来。现在要计算面积小于等于\(mid\)的矩形个数。
从大到小枚举点，不断加入，那么当前加入的点一定是\(H_i\)最小的点。看左边和右边有多少连续可选的点（即高度比当前高度大的点，这可以用并查集预处理出来）。对于面积小于等于\(mid\)，高度为\(H_i\)的矩形，那么算上\(i\)，一共最多取\(\frac{mid}{H_i}\)个连续的列作为矩形的底。这样的方案数可以通过分类讨论计算等差数列的和得出。
现在找到了面积上界\(ls\)和下界\(rs\)，可以用类似的办法依次找出符合要求的矩形。先求出上界和下界的值在答案里各有多少个，这个套用前面二分的计算就可以得出。然后就是找到面积在\([ls+1,rs-1]\)的矩形。
用类似的方法枚举加入点，现在相当于是取的列数有上界和下界，要找到这些矩形。由于\(R-L+1\)有限制，可以直接枚举经过最低点的左右各取多少。只要把枚举的上下界设置好，复杂度就是线性的。全部挑出来然后排序输出即可。
\(O(n\log\sum H_i+(R-L+1)\log(R-L+1))\)
K¶
upsolved by TYB
题意¶
\(n\)个位置排成一条直线，从某个位置出发，可以任意向左向右走，若第一次经过某个位置则把位置编号记下来，最后走完这\(n\)个位置，得到一个位置编号的排列。一种排列的权值定义为\(\sum_{i=1}^nD_i[p_{C_i}=i]\)，求\(\forall i\in[1,n]\)，从\(i\)位置出发得到的所有排列中权值的最大值。
\(n\le3\times10^5\)
题解¶
有一个显然的\(\mathcal{O}(n^2)\)DP做法：\(f[l][r]\)表示已经走完了\([l,r]\)这段区间权值的最大值，每次枚举拓展左端点或右端点转移。考虑优化，可以将每个DP状态看作一个二维平面上的点，\(f[x][y]\)看作\((x,y)\)，那么\(i\)的答案相当于找一条\((i,i)\)到\((1,n)\)的路径使边权之和最大。注意到非零的边最多只有\(2n\)条，所以可以一列一列地进行DP，用树状数组优化即可。
L¶
solved by YZW
题意¶
题解¶
M¶
upsolved by TYB
题意¶
\(n\)个点的树，边有边权，边权有正负，要求选出恰好\(k\)条边，满足选出来的边没有公共点，且权值和最大，判断无解或输出答案。
\(n\le2.5\times10^5\)
题解¶
显然随着\(k\)的增长，答案会增长的越来越慢，令\(g(x)\)表示恰好选\(x\)条边的答案，则\(g\)为一个上凸函数。
所以可以用wqs二分解决。
这个算法用得还是比较少，比赛时也没有想起来，还是要多练。
记录¶
开局TYB看到G可做，写了一会，发现有些麻烦。
换JLK写H，WA1后AC(0:21)。
YZW写L(0:50)。
JLK和TYB讨论后改对了G(0:56)。
JLK尝试B，但是搞到某一步之后不会写了，暂且搁置。
之后看I，没有什么特别好的想法。YZW试了一发SG函数然后过了(1:25)。
然后三人看EF，在题意理解方面出了问题。讨论很久后发现都不难。E(2:21)F(2:31)都过了。
TYB发现A暴力即可，写了一发，但由于CF炸了不知道结果。(3:02)
然后BDM轮流想，没有特别好的想法。
JLK提出了D的一个猜想，TYB写了一发，但没结果。(4:22)
JLK想J，发现可以写，开始写J。
此时CF评测姬好了，AD都炸了。TYB对拍过了A(4:40)。但D一直没过。
比赛结束前J写完了，但是没调完。
总结¶
JLK:中间卡题意太久了，但这个好像也没办法避免。B和D都接近正确做法，B一是没有大胆猜想，二是2-sat没有继续想下去，D是没处理好。J开的晚了点，早点写完应该能过。M被卡知识点。
Dirt¶
A(-1)
H(-1)