2020牛客暑期多校第五场¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 87/1116 | 5 | 10 | 11 |
A¶
upsolved by JJLeo
题意¶
给出一个\(n\)个点\(m\)条边的图，从\(1\)号点出发，依次经过\(2k\)个点，途中经过一点时可以在这点放传送门，任意时刻只能存在最多两个传送门，两个传送门可以瞬间互达，求途径的最短距离。\((n, k \le 300, m \le 40000)\)
题解¶
设\(f_{i,j}\)为目前已经到第\(i\)个目标点，传送门位于\(j\)点所经历的最短路程。转移有以下几种：直接走到下一个目标点；直接传送到传\(j\)的位置，然后走到一个位置放传送门，再走到下一个目标点；直接走到一个位置放传送门，走到这个位置然后传送到\(j\)的位置，再走到下一个目标点。两点间最短距离跑一遍floyd即可，注意有重边，总复杂度\(O(n^2k)\)。
B¶
solved by JJLeo
题意¶
给出一棵\(n\)个点的树，每条边有权值，可以删边或加边任意次，要求任意时刻满足图联通且所有环的边权异或值为\(0\)，求最终所有边权之和的最小值。\((n \le 100000)\)。
题解¶
XOR-MST。
C¶
upsolved by JJLeo
题意¶
设两个长度为\(k\)的正整数序列\(a\)和\(b\)，他们的和分别为\(N\)和\(M\)，求所有可能的\(a\)和\(b\)的\(\prod_{i=1}^k\min(a_i,b_i)\)之和。\((1 \le N,M \le 10^6,1\ \le k \le \min(N,M))\)
题解¶
构造二元生成函数\(f(x,y)=\sum{\min(n,m)x^ny^m}\)，\(f^k(x,y)\)中\(x^Ny^M\)的系数即为答案。差分后可以凑出\(f(x,y)\)的和函数为\(\dfrac{xy}{(1-x)(1-y)(1-xy)}\)，因此只需求\(\dfrac{1}{{(1-x)}^k{(1-y)}^k{(1-xy)}^k}\)展开式中\(x^{(N-k)}y^{(M-k)}\)的系数即可。枚举\(\dfrac{1}{{(1-xy)}^k}\)的次数，即可得到\(\dfrac{1}{{(1-x)}^k}\)和\(\dfrac{1}{{(1-y)}^k}\)对应的次数，最后答案为数个三组合数乘积的和，时间复杂度\(O(\min(N-k,M-k))\)。
D¶
solved by 2sozx JJLeo
题意¶
给定一个\(1\)到\(n\)的排列，有两种操作，第一种操作为将倒数第二个操作移动到第一个；第二种操作为将第一个元素移动到最后一个。设连续的第一种操作为一个大操作，问将排列变为有序最少需要几次大操作。\((n \le 500)\)
题解¶
可以发现第二种操作相当于进行循环同构，因此连续的第一种操作等价于将某个元素放到任意一个位置。因此只需要找所有循环同构中找一个最长上升子序列，调整其它数字位置即可。
E¶
solved by Bazoka13
题意¶
给定一个排序，每次将第\(i\)位数字移动到\(b[i]\)位，问有几种数列按照该方法进行足够多次可以完成排序。
题解¶
求所有循环节结点数的\(lcm\)即可，注意高精，python除法用\(//\)
F¶
solved by Bazoka13
题意¶
题解¶
按照题意模拟的水题，不过题面描述貌似不太通顺导致卡到10min才过
G¶
upsolved by JJLeo
题意¶
给定一棵有根树，每个点有一个颜色\(c_i\)，每个点可以取一个权值\(d_i\)，设以其为根的子树中颜色为\(d_i\)的点的数量为\(x\)，则该点权值为\(xd_i\)。现在问所有点权值组成集合的\(\operatorname{mex}\)最大为多少。\((n \le 20000)\)
本题时限8s，空间64MB。
题解¶
时限很大，因此直接\(O(n^2)\)找每个点可能的权值（直接dfs一次记录dfn序常数更小），然后二分图跑最大匹配。但是本题卡空间，所以拿bitset存边，然后用增广路算法跑，虽然复杂度是\(O(n^3)\)的但是跑不满可以卡过。
H¶
upsolved by JJLeo
题意¶
给出一个长度为\(n\)的序列，\(q\)次询问一个区间所有子区间\(AND\)值所组成集合的大小，强制在线。\((n,q \le 10^5)\)
题解¶
固定右端点，有可能的取值为\(O(\log n)\)种，因此我们可以从左到右，固定右端点，将\(a_i\)与右端点为\(i-1\)的所有值进行\(AND\)操作，得到所有可能的取值及其左端点的范围，这一部分总复杂度为\(O(n \log n)\)。接下来以每个点为右端点为根，建立主席树，对于\([l,r],[l+1,r],\cdots , [L,r]\)均为某一个值\(x\)，直接在\(r\)为根对应的线段树上给\(l\)位置加一即可。考虑去重：如果相同的数上一次加一的位置若\(< l\)，则在老的位置减一即可，否则不做加一操作，直接用上次的值即可。
I¶
solved by 2sozx
题意¶
定义三种颜色 \(G,H,E\) ，与 \(H\) 相邻的四个格子中至少有 \(G,E\) 各一个，现在考虑无限大的平面，问 \(H\) 所占的比例最大是多少。
题解¶
按对角线排，两行H，一行GE交错为最优，答案即为\(\frac{2}{3}\)
J¶
upsolved by
题意¶
题解¶
K¶
upsolved by JJLeo
题意¶
合并一个代码的两个分支使得总代码行数最短，代码中有的部分是分支1，有的部分是分支2，还有公用的部分。要求两个分支合并后代码执行顺序要和合并前相同，且只有完全相同的行才可以放在公共部分，否则必须出现在#ifdef branch1 和 #ifdef branch的代码块内，当然也可以用#else 和 #endif。
题解¶
设\(f_{i,j,k}\)表示此时到分支1的第\(i\)行，分支2的第\(j\)行，此时处于分支1/分支2/公用的代码块内。限定分支1可以到分支2，分支2不能切到分支1，且只有两行完全一致才能在共用代码块，具体行数变化分类讨论一下即可。另外要给每个转移标个号最后逆序记录方案输出。
记录¶
0min：开局分题
10min：CSK秒F，MJX ZYF看I，WA
35min：MJX AC I
63min：MJX Python 写E，写崩了
73min：MJX 和 ZYF看D，CSK接手E
138min：ZYF AC D，看B
144min：CSK AC E
204min：ZYF AC B
till end：集体看K没调出来
总结¶
- MJX：熟悉熟悉Python，别犯低级错误
- ZYF：前期梦游，昏昏欲睡。最后一个多小时K题完全理解错题意，被之前某括号匹配误导，难受。
- CSK：熟悉熟悉python+1，白给一发才发现除号错误，甚至跑去用java白给了一发