说好的蓝蓝紫紫呢……
矩阵
我直接和哈希做了。
正解是这样的,随机一个列向量 \(\mathbf{x}\) ,则如果 \(A\times B=C\) ,则 \(\mathbf x \times A \times B = \mathbf x \times C\) 。
列向量与方阵相乘是 \(O(n^2)\) 的。
这样判定的错误率是 \(\frac{1}{mod}\) 的(我也不知道为什么,反正很小)。
Code
长野原龙势流星群
据说本来是 Minkowski ,但是赛时被贪心爆标了。下面来介绍贪心。
当前树上权值最大的节点答案以及固定了,即其本身,因为加入任意一个点都不会使其更优。
如果其存在父亲,那么其一定在父亲的连通块内,因为这样不会使答案变劣,所以我们可以直接将其与父亲合并。
使用小根堆和并查集维护这个过程即可。复杂度 \(O(n\log n)\) 。
Code
序列与查询
注意 __int128
。
我们发现询问对于一个子段的影响和其长度有关。
我们设 \(f_i\) 为长度为 \(i\) 的最大子段和,则 \(ans=\max\{f_i+x\cdot i\}\) 。
典型的斜率优化形式,求出 \((i, f_i)\) 的凸包,然后用斜率为 \(-x\) 的直线去切,切点即最优决策点。
现在我们的问题是求出 \(f_i\) ,\(O(n^2)\) 枚举听起来不太行。而现在我们面临一个需要处理所有子段的问题。
分治 。
将序列分成 \([l, mid]\) 和 \((mid, r]\) 两部分递归,然后处理之间的贡献。
即左侧距离 \(mid\) 长度为 \(i\) 的和是 \(L_i\) ,右侧同理定义 \(R_i\) 。
则 \(f_i=\max_j\{L_j+R_{i-j}\}\) ,这是一个 Minkowski 和的形式。
同时发现,最后我们要求的就是凸包,不在目前凸包上的一定不需要,所以直接 Minkowski 合并即可。
同时发现我们只需要求 \(f_i\) ,最后再统一求一次凸包就好了,不需要合并凸包。
Code
Hills and Pits
先假定 \(l=1,r=n\) ,且 \(s<t\) 。记 \(\{a\}\) 前缀和 \(sum\) 。
总和 \(<0\) 不合法,先判掉。
然后路径就变成了这样:
发现 \(s\rightarrow t\) 的这一段是可以折返的,而折返就意味着遇到一段 \(sum<0\) ,然后在之后的第一个 \(sum\ge 0\) ,折返回去填平。
也就意味着,\(sum>0\) 可以少走一遍, \(sum<0\) 需要多走一遍,我们想要确定一个子段 \(s\rightarrow t\) 使得这样的情况最优。
我们定 \(sum\ge0\) 权值为 \(1\) ,\(sum<0\) 权值为 \(-1\) ,问题就是求 \([1, n)\) 最大子段和。
同时发现,左端点一定是 \(1\) ,这也满足了我们最初那张图的限制。
现在问题搬到了区间上,则 \(sum\ge sum_{l-1}\) 权值为 \(1\) ,\(sum<sum_{l-1}\) 权值为 \(-1\) 。
根据值域扫描线,需要支持单点修改,区间查询最大子段和,这不就 小白逛公园 。
然后再倒过来做一遍就好了。
Code