2021牛客多校第一场¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 53/1351 | 6 | 11 | 11 |
A¶
solved by 2sozx JJLeo
题意¶
\(T\) 组询问，Alice 和 Bob 玩游戏，两堆石子，每次可以从一堆石子拿 \(k\) 个，另一堆石子拿 \(sk\) 个，这里 \(k>0,s \ge 0\)。问谁必胜？(\(1 \le T\le 10^4\)，\(1 \le n \le m \le 5 \times 10^3\))
题解¶
赛时直接暴力，暴力转移打表 SG 函数，复杂度为 \(O(n^3 \log n)\)，花了 \(15\) 分钟。
正解为对于一堆石子数为 \(x\) 时，至多存在一个 \(y\) 使得当另一堆石子数为 \(y\) 时 SG 函数为 \(0\)。若存在两个 \(y_1>y_2\)，显然这一堆拿 \(y_1-y_2\) 个另一堆不拿就可以转移到一个必败态，因此 \(y_1\) 时 SG 函数不为 \(0\)。从而必败态只有 \(O(n)\) 个，使用这些必败态去转移即可做到 \(O(n^2 \log n)\)。
C¶
upsolved by JJLeo
题意¶
给定一颗 \(n\) 个节点的树，每个节点有一个权值，求删去一个节点后剩下子树中所有路径最长上升子序列长度的最小值。(\(2 \le n \le 10^5\))
题解¶
树所有路径中的最长上升子序列可以使用线段树合并来求解：
对于每个子树，线段树维护最大值在 \([l,r]\) 之间「向上走」的最长子序列长度，以及最小值在 \([l,r]\) 之间「向下走」的最长子序列长度。
对于以 \(x\) 为 lca 的路径但是最长子序列不包括 \(x\) 的情况，可以在其子树的线段树合并过程中统计答案，对于区间 \([l,r]\) 不断地将最大值在 \([l,\textit{mid}]\) 之间「向上走」的最长子序列 和 最小值在 \([\textit{mid}+1,r]\) 之间「向下走」的最长子序列进行以及两者反过来的情况进行合并。
对于以 \(x\) 为 lca 的路径且最长子序列包括 \(x\) 的情况，设其权值为 \(a_x\)，可以使用简单的线段树查询子树中 \([1,a_x-1]\) 的「向上走」序列和 \([a_x+1,n]\) 的「向下走」序列来完成。
最后，等所有子树合并完成后，更新以 \(x\) 为结尾「向上走」序列和为开头的「向下走」序列，同时这两种情况也可能是答案，使用其长度进行更新即可。
每个节点至多增加 \(O(\log n)\) 个节点，从而总时间复杂度为 \(O(n \log n)\)。
首先我们找出原树上最长子序列所在的链 \(A\)，考虑删掉其中点，再对每个子树求最长子序列，设其所在链为 \(B\)，那么如果答案要比此时更优，所删的点必然是 \(A\) 和 \(B\) 的交点，使用简单的 dfs 求出 \(A \cap B\)，显然也是一条链，且因为取的是中点，其长度不超过 \(A\) 的一半。再取 \(A \cap B\) 的中点，不断重复上述过程，至多重复 \(O(\log n)\) 次，总时间复杂度为 \(O(n \log ^2 n)\)。
E¶
upsolved by JJLeo
题意¶
\(n \times m\) 的格子每个格子有一堆水管，每种形态的水管连结两个方向，每次从一个方向进来那必须得从另一个方向出去，每次行走前可以有一次机会选择任意个水管（除自己脚下的水管外），将其统一转动 \(0 ^\circ,90 ^\circ,180 ^\circ,270 ^\circ\)，给出一种不超过 \(20nm\) 次操作（包括行走和转动）的方案从左上角走到右下角。(\(2 \le n,m \le 1000\))
题解¶
每次转到下一次要走的格子所在水管即可，状态只有所处格子及当前所走的方向，共 \(4nm\) 个。
bfs 记录转移方案后输出即可，比较坑的一点是有可能重复用到一个是水管，但是方向不同，但你之前可能转过它了，因此输出时记录一下每个水管之前的转动方案，再转动时要进行偏移。
G¶
upsolved by 2sozx JJLeo
题意¶
给定两个序列 \(A, B\)，要求交换 \(A\) 中元素恰好 \(k\) 次，最大化 \(\sum\limits_{i=1}^{n}\left|A_i-B_i\right|\) 。(\(n\le 5\times 10^5\)，\(0\le k \le 10^8\))
题解¶
假设能交换无限次，显然将 \(A,B\) 所有数排序，前 \(n\) 个为正，后 \(n\) 个为负即为最大，按这个顺序给每个数标正负号。
考虑交换至多 \(k\) 次，显然对于一个位置，如果 \(A,B\) 正好应该是一正一负，则不需要交换，否则交换一定会使答案更优。由于总体来看一定是 \(n\) 正 \(n\) 负，那么 \(A,B\) 同正与同负的个数是相同的，因此我们每次可以取 \(\min(A_i,B_i)\) 最大的正对与 \(\max(A_i,B_i)\) 最小的负对交换，这样答案一定是最大的，每次交换的代价 \(2\big(\min(A_i,B_i)-\max(A_j,B_j)\big)\)。
考虑恰好交换 \(k\) 次，若 \(n \ge 3\) 则与至多交换 \(k\) 次是等价的，因为 \(A\) 中至少存在两个是正 / 负的，可以选择这两个进行交换而不改变答案。若 \(n = 2\) 则每次只能交换这两个位置，因此与 \(k\) 的奇偶有关。
H¶
solved by JJLeo
题意¶
给出非负整数集合 \(S\)，求最小正整数的 \(p\) 使得 \(\forall x,y \in S,(x\ne y) \to (x \not \equiv y \pmod p)\)。(\(1 \le |S| \le 5 \times 10^5\)，\(\forall x \in S,0 \le x \le 5 \times 10^5\))
题解¶
设 \(A=\{x-y \mid x,y \in S\}\)，则有 \(\forall x \in A, x \bmod p \ne 0\)。
设 \(m = 5 \times 10^5\)，将 \(f_i=[i \in S]\) 和 \(g_i=[m-i\in S]\) 卷积即可得到 \(A\)，再调和级数复杂度枚举倍数即可排除不合法的 \(p\)，总时间复杂度为 \(O(m \log m)\)。
I¶
upsolved by JJLeo
题意¶
给定一个排列 \(a_1,a_2, \cdots, a_n\)，Alice 和 Bob 轮流拿数，Alice 先手。两个人的第一个数随便取，但 Bob 必须保证拿的数比 Alice 大。接下来每个人取的数必须比之前两人拿的所有数都要大，且对于 Alice 和 Bob 来说他们各自拿的数的下标要递增，一个人不能选数时游戏结束。每次选数时若有多种选择则等概率选择一个，求两个人一共期望拿多少个数。(\(1 \le n \le 5000\))
题解¶
考虑将游戏放到值域上，则不用考虑两个人，相当于一个人不断拿越来越大的数，只要保证此时拿的数的位置比上上次拿的数的位置大即可。
设 \(f_{i,j}\) 为上一次拿了值为 \(i\) 这一次拿了值为 \(j\) 后到结束的期望游戏次数，为了适应一开始的边界条件我们规定 \(a_0=0\)。对于 \((i,j)\) 的下一个状态 \((j,k)\) 必然有 \(i<j<k\) 且 \(i\) 的位置在 \(k\) 之前，也就是说：
两层循环，第一层倒序枚举 \(j\)，第二层倒序枚举 \(i\)，即可完成上述转移。
最终答案即为 \(f_{0,0}\)，时间复杂度为 \(O(n^2)\)。
J¶
solved by 2sozx JJLeo
题意¶
\(n\) 个车站，车站 \(i\) 只能在 \([u_i,v_i]\) 时段停靠，一辆车从第 \(i\) 个车站到第 \(i+1\) 车站要 \(c_i\) 的时间。
\(q\) 次询问，每次 \(u_l\) 时刻从 \(l\) 车站出发，问能否到达 \(r\) 车站。
(\(1 \le n,q \le 10^6\))
题解¶
过了就完事了。
记录¶
0h：双人作战，CSK在高铁上，MJX开局先把B签到秒了，看D也签到也写了，F过的挺多的MJX和ZYF想了想数位DP，ZYF突然想到r-l大一点就一定有解，就直接冲了，MJX看H题半天没看懂题意。看人过的挺多的让ZYF也来看看，发现反着卷一下就完了
1h：把H过了，MJX开始打A的表，一点优化都没有搁哪打表，打半天了才想起啦优化，懒得改了，把表交上去就过了。MJX和ZYF讨论讨论J看起来挺可写的，就冲了
2-3h：调J，MJX搁哪写K，没乱搞明白
4h：发现J出来负数了，直接和0取max，然后就过了(?，彳亍