Difference between revisions of "2018 Multi-University, HDU Day 3"

From EOJ Wiki
Jump to navigation Jump to search
 
(10 intermediate revisions by 3 users not shown)
Line 2: Line 2:
  
 
Solved by kblack. 01:45 (+5)
 
Solved by kblack. 01:45 (+5)
 +
 +
题意:在长度为 $n$,部分随机的序列中,求大小为 $m$ 的滑动窗口滑过的每个区间的最大值及最大值变化次数。
 +
 +
题解:从后往前即可获得每个数的下一跳,再正着并查集维护即可。辣鸡出题人卡常,体验极差!
 +
 +
zerol:如果看过题解,你就会发现没有那么麻烦。从后往前单调队列维护最大值,其中 count 恰好就是队列中的元素个数。
  
 
== Problem C ==
 
== Problem C ==
Line 24: Line 30:
  
 
Solved by zerol. 00:26 (+)
 
Solved by zerol. 00:26 (+)
 +
 +
温暖的签到。
  
 
== Problem G ==
 
== Problem G ==
  
 
Solved by ultmaster. 02:27 (+)
 
Solved by ultmaster. 02:27 (+)
 +
 +
题意:给一些点,让你选其中一些点,从左到右,然后和 $(0,0)$ 组成一把扇子,使得扇子的有向面积最大。
 +
 +
题解:其实就是求一个上凸壳。魔改凸包的单调栈即可。注意本题要求输出字典序最小,还会有重点。不过都是小问题,稍微注意一点不会写错。
 +
 +
== Problem H ==
 +
 +
Upsolved by ultmaster.
 +
 +
题意:经典月赛题 大鱼吃小鱼 又来了。现在有一棵树,要求吃的顺序满足树的偏序。
 +
 +
题解:像大鱼吃小鱼那样排序,然后注意到两件事情
 +
 +
1. 如果排在最前面的正好是树的根,那么直接拿走;
 +
 +
2. 如果不是,那么吃完这个东西的父亲之后一定直接吃它,所以可以把这个节点和它的父亲合并,用并查集和 set 维护即可。
 +
 +
两件事情都把 $n$ 的问题变成了 $n-1$ 的子问题。
 +
 +
以上基本把题解朗读了一遍。补这题的时候有点不在状态,蛋疼了好久。
 +
 +
1. 偏序里面有个地方忘了 return(为什么没警告啊)。
 +
2. int 改 LL 改了一半,WA1。
 +
 +
另外合并的时候式子如下:
 +
 +
$father.a_{new} = \max(father.a, father.a - father.b + victim.a)$.
 +
$father.b_{new} = victim.b - victim.a + father.b - father.a + father.a_{new}$.
  
 
== Problem I ==
 
== Problem I ==
  
 
Solved by kblack. 03:24 (+4)
 
Solved by kblack. 03:24 (+4)
 +
 +
题意:给出一个序列,其中部分值从 $1$ ~ $m$ 随机,求整个序列价值的期望,价值为 $ \prod_{i=1}^{n-3} v[\gcd(a_i,a_{i+1},a_{i+2},a_{i+3})] $。
 +
 +
题解:构建 dp 状态,[上三个数的 gcd][上两个数的 gcd][上一个数],因为状态的限制,实际存在的状态小于 $1500$,那就可以枚举那些不确定的数了。
  
 
== Problem J ==
 
== Problem J ==
  
Unsolved. (-2)
+
Upsolved by zerol. (-2)
 +
 
 +
题意:二维平面上有若干点 $(i, y_i) \forall i \in [1,n]$,并有点权 $w_i$,每次询问一个矩形内的点权积,点权最大值最小值。
 +
 
 +
题解:维护的信息是不满足区间减法的,没法直接搞个大数据结构。比赛时写了个莫队处理 x +线段树维护 y 的信息,但事实上慢得很。正确的做法是对于所有询问按照 x 进行分治,不跨过中线的左右递归,跨过的分别从中线向左向右计算并合并左右的查询结果。注意修改要撤销,重新 build 会慢一些(虽然本地不会 T)。
  
 
== Problem L ==
 
== Problem L ==
  
 
Solved by kblack. 00:22 (+)
 
Solved by kblack. 00:22 (+)
 +
 +
画图,温暖的签到。
  
 
== Problem M ==
 
== Problem M ==
  
 
Solved by zerol. 03:40 (+)
 
Solved by zerol. 03:40 (+)
 +
 +
题意:给一个有向图,每次询问从 u 到 v 至少经过 k 条边的最短路是多少。
 +
 +
题解:考虑 M[k] 是一个 n*n 的矩阵,表示恰好经过 k 条边的每两个点之间的最短路。可以用 $O(n^3)$ 的代价由 M[a], M[b] 计算出 M[a+b]。对于询问 u, v, a+b,可以用 O(n) 的时间从 M[a] 和 M[b] 计算得到。所以取 k 的最大值的平方根 100,计算 k = 1, 2, ..., 100, 200, 300, ..., 10000 的时候的 M[k]。最后还有一个问题就是把恰好 k 条变成至少 k 条,方法就是计算 k=1, 2, ...100, 101, ...150 的 M[k] 并向前依次取 min,因为至少 k 条边的最优解的经过边数不会超过 k+n(否则必定成简单环可删去)。

Latest revision as of 17:09, 31 July 2018

Problem A

Solved by kblack. 01:45 (+5)

题意:在长度为 $n$,部分随机的序列中,求大小为 $m$ 的滑动窗口滑过的每个区间的最大值及最大值变化次数。

题解:从后往前即可获得每个数的下一跳,再正着并查集维护即可。辣鸡出题人卡常,体验极差!

zerol:如果看过题解,你就会发现没有那么麻烦。从后往前单调队列维护最大值,其中 count 恰好就是队列中的元素个数。

Problem C

Solved by ultmaster. 00:53 (+)

题意:若干加边删边操作,每次操作后,询问图中 $1,2,\ldots,n/2$ 匹配的数目。

题解:由于 $n$ 很小,维护每一个子图 ($2^n$) 的匹配数目。加边的时候,把含有那条边的子图都加上去掉那条边的子图的部分的现有的值。删边同理。

ultmaster: 总觉得有什么地方不大对,但出乎意料地输出了正确的答案。(运气真好)

Problem D

Solved by ultmaster. 00:17 (+)

题意:求第 $k$ 个欧拉函数是合数的数。

题解:经典的打表找规律签到。

Problem F

Solved by zerol. 00:26 (+)

温暖的签到。

Problem G

Solved by ultmaster. 02:27 (+)

题意:给一些点,让你选其中一些点,从左到右,然后和 $(0,0)$ 组成一把扇子,使得扇子的有向面积最大。

题解:其实就是求一个上凸壳。魔改凸包的单调栈即可。注意本题要求输出字典序最小,还会有重点。不过都是小问题,稍微注意一点不会写错。

Problem H

Upsolved by ultmaster.

题意:经典月赛题 大鱼吃小鱼 又来了。现在有一棵树,要求吃的顺序满足树的偏序。

题解:像大鱼吃小鱼那样排序,然后注意到两件事情

1. 如果排在最前面的正好是树的根,那么直接拿走;

2. 如果不是,那么吃完这个东西的父亲之后一定直接吃它,所以可以把这个节点和它的父亲合并,用并查集和 set 维护即可。

两件事情都把 $n$ 的问题变成了 $n-1$ 的子问题。

以上基本把题解朗读了一遍。补这题的时候有点不在状态,蛋疼了好久。

1. 偏序里面有个地方忘了 return(为什么没警告啊)。 2. int 改 LL 改了一半,WA1。

另外合并的时候式子如下:

$father.a_{new} = \max(father.a, father.a - father.b + victim.a)$. $father.b_{new} = victim.b - victim.a + father.b - father.a + father.a_{new}$.

Problem I

Solved by kblack. 03:24 (+4)

题意:给出一个序列,其中部分值从 $1$ ~ $m$ 随机,求整个序列价值的期望,价值为 $ \prod_{i=1}^{n-3} v[\gcd(a_i,a_{i+1},a_{i+2},a_{i+3})] $。

题解:构建 dp 状态,[上三个数的 gcd][上两个数的 gcd][上一个数],因为状态的限制,实际存在的状态小于 $1500$,那就可以枚举那些不确定的数了。

Problem J

Upsolved by zerol. (-2)

题意:二维平面上有若干点 $(i, y_i) \forall i \in [1,n]$,并有点权 $w_i$,每次询问一个矩形内的点权积,点权最大值最小值。

题解:维护的信息是不满足区间减法的,没法直接搞个大数据结构。比赛时写了个莫队处理 x +线段树维护 y 的信息,但事实上慢得很。正确的做法是对于所有询问按照 x 进行分治,不跨过中线的左右递归,跨过的分别从中线向左向右计算并合并左右的查询结果。注意修改要撤销,重新 build 会慢一些(虽然本地不会 T)。

Problem L

Solved by kblack. 00:22 (+)

画图,温暖的签到。

Problem M

Solved by zerol. 03:40 (+)

题意:给一个有向图,每次询问从 u 到 v 至少经过 k 条边的最短路是多少。

题解:考虑 M[k] 是一个 n*n 的矩阵,表示恰好经过 k 条边的每两个点之间的最短路。可以用 $O(n^3)$ 的代价由 M[a], M[b] 计算出 M[a+b]。对于询问 u, v, a+b,可以用 O(n) 的时间从 M[a] 和 M[b] 计算得到。所以取 k 的最大值的平方根 100,计算 k = 1, 2, ..., 100, 200, 300, ..., 10000 的时候的 M[k]。最后还有一个问题就是把恰好 k 条变成至少 k 条,方法就是计算 k=1, 2, ...100, 101, ...150 的 M[k] 并向前依次取 min,因为至少 k 条边的最优解的经过边数不会超过 k+n(否则必定成简单环可删去)。