Difference between revisions of "2019 Multi-University,Nowcoder Day 8"

From EOJ Wiki
Jump to navigation Jump to search
 
(26 intermediate revisions by 3 users not shown)
Line 24: Line 24:
  
 
Solved by Kilo_5723. 00:38:06 (+1)
 
Solved by Kilo_5723. 00:38:06 (+1)
 +
 +
题意:构造一个 $2^k \times 2^k$,只含有 $1,-1$ 的矩阵,使得其任意两行点积为 $0$。
 +
 +
题解:对于一个 $2^k$ 的方阵,考虑如何将其推广到 $2^{k+1}$ 的情况:
 +
 +
我们发现,对合法的矩阵 $A,B$,$-A$ 和 $\left( A \; B\right)$ 也肯定合法。
 +
 +
因此,对 $2^k \times 2^k$ 的合法矩阵 $A$,构造
 +
$\left(
 +
\begin{array}\\
 +
A&A\\
 +
A&-A\\
 +
\end{array}
 +
\right)$,可以证明它一定合法。
  
 
== Problem D ==
 
== Problem D ==
  
Unsolved.
+
Upsolved by Xiejiadong.
 +
 
 +
题意:每次插入一个点,或者询问已经存在的点中离一个点曼哈顿距离最近的点的距离。
 +
 
 +
题解:尝试把曼哈顿距离的绝对值拆掉,比如对于点 $(a,b,c)$ ,如果拆掉绝对值以后是 $a+b+c-x-y-z$ 那么一定满足 $x\le a,y\le b,z\le c$ ,也就是我们可以通过询问前缀子长方体询问最大值得到。
 +
 
 +
同样的,如果拆掉绝对值以后是 $a+b-c-x-y+z$ 那么一定满足 $x\le a,y\le b,c\le z$  ,我们可以通过在 $(x,y,h-z)$ 位置打上值,查询前缀子长方体的最大值得到。
 +
 
 +
其余的六种情况的枚举也是类似的,直接开 $8$ 个树状数组维护一下就好了。
  
 
== Problem E ==
 
== Problem E ==
  
 
Solved by Kilo_5723. 02:44:17 (+)
 
Solved by Kilo_5723. 02:44:17 (+)
 +
 +
题意:给定一个无向图,第 $i$ 条边连接 $u_i,v_i$ 且可以让重量在 $[l_i,r_i]$ 中的人通过,求有多少种不同的重量的人可以从 $1$ 走到 $n$。
 +
 +
题解:将 $l_i,r_i$ 离散化后剩下了 $m$ 个关键点,我们可以看作一共有 $m$ 张图,每条边要加入 $[l_i,r_i]$ 中的图。
 +
 +
我们可以用线段树维护这些图,每条边插入时,我们把边加到线段树对应的节点上,这样一条边最多被加到 $log(m)$ 个节点上,而对于每一个叶节点,其对应的图就是其到根节点路径上每一个节点的所有边的集合。
 +
 +
因此,如果我们可以按序撤回加边的操作,我们从根节点开始做一遍 dfs 就能求出所有叶节点上 $1$ 到 $n$ 的连通性。可以用可回滚并查集维护图的连通性,到叶节点判断是否连通,在返回的时候将并查集回滚到进入当前结点之前的状态即可。
  
 
== Problem F ==
 
== Problem F ==
  
Unsolved.
+
Upsolved by Kilo_5723.
 +
 
 +
题意:给定平面上 $1000$ 个点,求其中有多少四元组 $a,b,c,d$ 满足其中一个点严格在另外三个点构成的三角形的内部。
 +
 
 +
题解:枚举每一个点 $a$ 作为原点的情况。先将其他点按极角排序,我们发现剩下的三个点中非法的三元组很容易枚举。
 +
 
 +
非法的三元组有两种情况:其中两点 $b,c$ 构成的直线经过 $a$,或者 $a$ 在 $bc,cd,db$ 的同侧。
 +
 
 +
对第一种情况,枚举经过 $a$ 点的 $bc$ 二元组,则剩下的 $d$ 可以任意选取。注意对如果有 $bc,bd$ 同时经过 $a$ 要去重。
 +
 
 +
对第二种情况,对每一个 $l$ 找到距离其最远的 $r$,使得 $a$ 在 $lr$ 的右侧。这样,$l,r$ 之间任意的 $b,c,d$ 都满足条件。为了去重,对每一对 $l,r$,只记录 $b=l$,$c,d$ 任取的情况数。
  
 
== Problem G ==
 
== Problem G ==
Line 55: Line 95:
 
== Problem I ==
 
== Problem I ==
  
Unsolved.
+
Upsolved by Xiejiadong.
 +
 
 +
题意:建树的过程是,给一个区间所有树的结点 $u$ 产生孩子 $v$ (保证存在这样的 $u$ ),在完成全部建树以后,每次询问一个区间里面所有树中以 $x$ 为根节点的子树的大小总和。
 +
 
 +
题解:因为每次产生的新节点 $v$ 编号都不同,我们可以把所有的 $v$ 建在同一棵树上,每个结点保存区间信息。
 +
 
 +
把这棵树按照 dfs 序重新标号以后,所有的询问操作就变成了询问一个 dfs 序的区间,询问一个子树的区间。
 +
 
 +
我们把这两维信息投射到坐标系,就变成了求二位的区间和,每次增加一个平行于 $y$ 轴的直线。
 +
 
 +
把询问通过拆分拆成两个,离线,直接线段树维护一下就好了。
  
 
== Problem J ==
 
== Problem J ==
  
 
Solved by Weaver_zhu. 04:58:42 (+8)
 
Solved by Weaver_zhu. 04:58:42 (+8)
 +
 +
题意:踩石头过河,某些时刻某些石头不能踩,跳的距离至少为 $d$,求有多少种跳法
 +
 +
题解:组合数学,非法情况包括之前合法或非法的情况刚好走 $t_i$ 步到 $p_i$,或者是之前是非法的刚好不走 $t_i$ 步到 $p_i$。
 +
 +
枚举第一个踩雷的情况就行了,这部分容斥减去之前踩过雷的情况。任意走 $t$ 步过 $p$ 距离可以用插板法公式直接搞出来。

Latest revision as of 13:11, 19 August 2019

Problem A

Solved by Xiejiadong. 03:52:19 (+1)

题意:求极大全 $1$ 矩阵的个数,极大全 $1$ 矩阵的定义是不被其他的全 $1$ 矩阵包含的全 $1$ 矩阵。

题解:和求面积最大的全 $1$ 矩阵类似的。枚举矩阵的下边界,就变成了最大广告牌覆盖问题。

连续相同高度的的一段只需要处理其中一个,但也有特殊的,比如 $1\;2\;2\;1$ 的情况,两边的 $1$ 也认为是相同的。

也就是对应于同一个区间的相同高度只能处理一次。

保证当前行处理的,前面没有处理过,计数即可。

Problem B

Solved by Kilo_5723. 00:12:03 (+)

题意:给定一个数串 $\{a_n\}$,求其所有子串中不同数字的数量之和。

题解:考虑每种数字对串的贡献,发现除了所有在这种数字的相邻两个位置的间隔中的子串都能得到 $1$ 的贡献,所以对每种数字统计其间隔中的子串即可。

Problem C

Solved by Kilo_5723. 00:38:06 (+1)

题意:构造一个 $2^k \times 2^k$,只含有 $1,-1$ 的矩阵,使得其任意两行点积为 $0$。

题解:对于一个 $2^k$ 的方阵,考虑如何将其推广到 $2^{k+1}$ 的情况:

我们发现,对合法的矩阵 $A,B$,$-A$ 和 $\left( A \; B\right)$ 也肯定合法。

因此,对 $2^k \times 2^k$ 的合法矩阵 $A$,构造 $\left( \begin{array}\\ A&A\\ A&-A\\ \end{array} \right)$,可以证明它一定合法。

Problem D

Upsolved by Xiejiadong.

题意:每次插入一个点,或者询问已经存在的点中离一个点曼哈顿距离最近的点的距离。

题解:尝试把曼哈顿距离的绝对值拆掉,比如对于点 $(a,b,c)$ ,如果拆掉绝对值以后是 $a+b+c-x-y-z$ 那么一定满足 $x\le a,y\le b,z\le c$ ,也就是我们可以通过询问前缀子长方体询问最大值得到。

同样的,如果拆掉绝对值以后是 $a+b-c-x-y+z$ 那么一定满足 $x\le a,y\le b,c\le z$ ,我们可以通过在 $(x,y,h-z)$ 位置打上值,查询前缀子长方体的最大值得到。

其余的六种情况的枚举也是类似的,直接开 $8$ 个树状数组维护一下就好了。

Problem E

Solved by Kilo_5723. 02:44:17 (+)

题意:给定一个无向图,第 $i$ 条边连接 $u_i,v_i$ 且可以让重量在 $[l_i,r_i]$ 中的人通过,求有多少种不同的重量的人可以从 $1$ 走到 $n$。

题解:将 $l_i,r_i$ 离散化后剩下了 $m$ 个关键点,我们可以看作一共有 $m$ 张图,每条边要加入 $[l_i,r_i]$ 中的图。

我们可以用线段树维护这些图,每条边插入时,我们把边加到线段树对应的节点上,这样一条边最多被加到 $log(m)$ 个节点上,而对于每一个叶节点,其对应的图就是其到根节点路径上每一个节点的所有边的集合。

因此,如果我们可以按序撤回加边的操作,我们从根节点开始做一遍 dfs 就能求出所有叶节点上 $1$ 到 $n$ 的连通性。可以用可回滚并查集维护图的连通性,到叶节点判断是否连通,在返回的时候将并查集回滚到进入当前结点之前的状态即可。

Problem F

Upsolved by Kilo_5723.

题意:给定平面上 $1000$ 个点,求其中有多少四元组 $a,b,c,d$ 满足其中一个点严格在另外三个点构成的三角形的内部。

题解:枚举每一个点 $a$ 作为原点的情况。先将其他点按极角排序,我们发现剩下的三个点中非法的三元组很容易枚举。

非法的三元组有两种情况:其中两点 $b,c$ 构成的直线经过 $a$,或者 $a$ 在 $bc,cd,db$ 的同侧。

对第一种情况,枚举经过 $a$ 点的 $bc$ 二元组,则剩下的 $d$ 可以任意选取。注意对如果有 $bc,bd$ 同时经过 $a$ 要去重。

对第二种情况,对每一个 $l$ 找到距离其最远的 $r$,使得 $a$ 在 $lr$ 的右侧。这样,$l,r$ 之间任意的 $b,c,d$ 都满足条件。为了去重,对每一对 $l,r$,只记录 $b=l$,$c,d$ 任取的情况数。

Problem G

Solved by Xiejiadong. 00:18:27 (+1)

题意:如果有三个连续的字母可以消掉,消掉以后前后相连,问最多能消除几次。

题解:如果连续的有一段字母,且个数不是 $3$ 的倍数,无论怎么消,都无法使得这一连续字母前后相连,也就是无论如何都会断掉,所以就可以贪心的消了。

用栈维护贪心消除即可。

开局智商下线,白送一发。

Problem H

Unsolved.

Problem I

Upsolved by Xiejiadong.

题意:建树的过程是,给一个区间所有树的结点 $u$ 产生孩子 $v$ (保证存在这样的 $u$ ),在完成全部建树以后,每次询问一个区间里面所有树中以 $x$ 为根节点的子树的大小总和。

题解:因为每次产生的新节点 $v$ 编号都不同,我们可以把所有的 $v$ 建在同一棵树上,每个结点保存区间信息。

把这棵树按照 dfs 序重新标号以后,所有的询问操作就变成了询问一个 dfs 序的区间,询问一个子树的区间。

我们把这两维信息投射到坐标系,就变成了求二位的区间和,每次增加一个平行于 $y$ 轴的直线。

把询问通过拆分拆成两个,离线,直接线段树维护一下就好了。

Problem J

Solved by Weaver_zhu. 04:58:42 (+8)

题意:踩石头过河,某些时刻某些石头不能踩,跳的距离至少为 $d$,求有多少种跳法

题解:组合数学,非法情况包括之前合法或非法的情况刚好走 $t_i$ 步到 $p_i$,或者是之前是非法的刚好不走 $t_i$ 步到 $p_i$。

枚举第一个踩雷的情况就行了,这部分容斥减去之前踩过雷的情况。任意走 $t$ 步过 $p$ 距离可以用插板法公式直接搞出来。