头部背景图片
Decaku 's Blog |
Decaku 's Blog |

2019 nowcoder Muti-school training

$这是牛客暑期多校共十场的题单,会慢慢补题。\\
代码都会放在github仓库 \\
$


$\checkmark A:给你两个数组,要求最长前缀的长度,满足对于任意一个子区间最小值位置相同 \\
先单调栈预处理,然后枚举每一个位置i肯定是必须两个数组的l[i]都必须相同 \\
然后右边肯定应该有个border,i必须小于border,维护时border更新为r[i]中较小值。 \\$

$\checkmark B:让你算一个积分,发现可以裂项相减,然后可以推出公式。\\$

$C:算一个式子在限制条件下的最小值,不太懂。 \\$

$D:沃尔什变换,不太懂。\\$

$\checkmark E:对序列计数,满足能拆成n个’AB’和m个’BA’的子序列。考虑贪心,如果能 \\
满足要求一定是把前缀里的A先给’AB’用,同理B先给’BA’用,然后dp[i][j] \\
表示i个A和j个B组成的合法序列数,合法时转移为dp[i][j]=dp[i-1][j]+dp[i][j-1] \\
否则dp[i][j]=0。\\$

$\checkmark F:在三角形内随机取一点把三角分成三部分,然后问最小部分面积的期望。 \\
用微积分推倒一下发现36乘以期望等于22倍的三角形面积。\\$

$G:可持久化数组维护字符串后缀,不太懂。\\$

$\checkmark H:给一个数集,询问所有能异或出0的子集大小的和。 \\
考虑每个数出现在几个满足条件的集合中,所有数的贡献和就是答案。先求线性基, \\
非线性基里的每个元素的贡献是2^{B-1},B是非线性基空间大小。对于线性基中元素x, \\
可以让其它n-1个元素再求一遍线性基如果其它n-1个元素不能异或出x,说明x没有贡献 \\
否则贡献应该是2^{C},C是新的n-1个元素消元后非线性基空间的大小。\\$

$\checkmark I:给一些点,每种点有两类属性,要求你把点分成两部分,一部分只贡献第一属性,\\
其它贡献第二属性,求最大值。首先满足条件的划分是单调不减的直线,为了方便 \\
把它想成折线且轨迹是沿着一类点的边界画的,然后设dp[i]为排序后选到第i个点时 \\
的答案,发现dp[i]可以由dp[1]到dp[i-1]转移,然后决策点是区间最值询问,更新需要 \\
区间更新,我i们用线段树维护即可。\\$

$\checkmark J:比较分数大小。交叉相乘即可.\\$


$\checkmark A:有一个长度为n的环,开始时人在0号点,每次都等概率向左或向右移动一 \\
走过所有点后就停下,询问最后停在m号点的概率。可以通过打表发现,一般结论是除了 \\
起点以外其它点都是等概率停下的,证明可能较为复杂。\\$

$\checkmark B:从0号点出发,给出一个k,每次有1/k的概率走1步,2步…k步,询问走到 \\
n号点的概率,n很大。设dp[i]表示走到i号点的概率,不难推出dp[i]=\sum_{j=i-k}^{i-1}dp[j]/k \\
这个式子可以用BM线性递推优化,然后打表观察n为无穷大时答案是2/(k+1)。 \\$

$C:待补。 \\$

$\checkmark D:有一个点带权的图,求第k大的完全子图,使用优先队列做BFS爆搜,用bitset \\
或int128做位压,为了防止搜重复的子图,强制让后加入的点都比当前图里的点编号更大。 \ $

$\checkmark E:有一个n行m列的矩阵,m最大10,1表示不可通,0表示可通,每次只能向 \\
左,右,下走一步且不可回头,询问从第一行x列走到第n行第y列的方案。设dp[i][j]表示 \\
走到第i行j列的方案,发现dp[i][j]=\sum_{k=l}^{k=r}dp[i-1][k],且必须满足区间[l,r] \\
都是0,那把每行看成一个向量,相邻行之间的转移其实是乘了一个矩阵,因为还有单点修改, \\
用线段树维护区间的矩阵乘积即可,注意下矩阵乘法的方向,wa惨了。 \\$

$\checkmark F:把至多28人分成人数相同的两组,不同组之间两两对答案有贡献,求最大贡献。 \\
用位压爆搜即可。 \\$

$\checkmark G:有n条之间,求直线围成的第k大区域的面积。不会。 \\$

$\checkmark H:有一个01矩阵,求只含1的第二大矩阵的面积。 \\
固定下边界,然后就变成了广告牌问题,单调栈扫即可,第二大哈希和优先队列搞搞就好。 \\$

$I:待补。 \\$

$\checkmark J:有一个长度为1e9的1和-1序列,给至多1e6个区间都包含1,1的数量总共最多1e7。 \\
询问有多少子区间的和大于0。把子序列看成前缀和形式的话,就是看有多少(i,j),满足i<j且 \\
sun[i]<sum[j],对每个子区间向左和右处理出各自能延展的最长位置,然后扫过去即可。 \\
因为和不会很大,所以可以用桶计数。 \\$


avatar Decaku 菜菜菜