Difference between revisions of "2019 Multi-University,HDU Day 6"

From EOJ Wiki
Jump to navigation Jump to search
(Created page with "== Problem A == Unsolved. == Problem B == Unsolved. == Problem C == Unsolved. == Problem D == Solved by Kilo_5723. 03:09:30 (+) == Problem E == Solved by Xiejiadong....")
 
 
(12 intermediate revisions by 3 users not shown)
Line 5: Line 5:
 
== Problem B ==
 
== Problem B ==
  
Unsolved.
+
Upsolved by Xiejiadong.
 +
 
 +
题意:给出一个排列,每次激活其中一个位置,询问当前数列的 LIS 。
 +
 
 +
题解:倒着看,每次删除排列中的一个数,询问当前数列的 LIS 。
 +
 
 +
因为是随机的,所以 LIS 的期望长度是 $\sqrt{n}$ 。
 +
 
 +
随机删除一个数,正好删到当前 LIS 所在元素的概率是 $\frac{1}{\sqrt{n}}$ ,所以一旦删到了,暴力重构即可。
  
 
== Problem C ==
 
== Problem C ==
Line 14: Line 22:
  
 
Solved by Kilo_5723. 03:09:30 (+)
 
Solved by Kilo_5723. 03:09:30 (+)
 +
 +
题意:有 $n$ 个工作,第 $i$ 个给甲做会花 $a_i$ 的时间,给乙做会花 $b_i$ 的时间。但是甲乙可以各做一部分工作,花费的时间为 $x\cdot a_i+y \cdot b_i(x+y=1)$。对每个 $i(1 \le i \le n)$,求出前 $i$ 个工作,两个人做完,花费时间最多的人需要花费至少多少时间。
 +
 +
题解:我们考虑 $n$ 个工作的情况:
 +
 +
如果工作全部分给甲,那么此时甲要花 $A=\sum_{i=1}^n a_i$ 的时间,乙要花费 $0$ 的时间,记为 $(A,0)$。
 +
 +
而接下来甲要把工作分给乙,那么甲肯定会分 $\frac{a_i}{b_i}$ 最大的工作,设这个工作为 $p$。如果这个工作全部分给乙,此时的情况是 $(A-a_p,b_p)$。而这之间的所有情况,都分布在 $(A,0)$ 和 $(A-a_p,b_p)$ 的连线上。
 +
 +
再接下来,甲肯定会分 $\frac{a_i}{b_i}$ 第二大的工作,然后是第三大,直到最后情况会变成 $(0,B)$。
 +
 +
自此,我们得到了一系列点,我们要求的就是这些点形成折线段和直线 $x=y$ 的交点,我们只要二分找到直线 $x=y$ 上下的两个点求交点就可以了。
 +
 +
现在考虑怎么维护的问题。我们发现,去掉一个工作 $a_i,b_i$ 之后,其对应的线段右方的点会全部平移 $(-a_i,0)$,而上方的点会全部平移 $(0,-b_i)$。我们要求解,仍是二分找到直线 $x=y$ 上下的两个点,再求交点。这可以用线段树的区间加和二分维护。
 +
 +
因此,我们需要先对工作按斜率排序,并记录每个工作排序后的位置,用线段树来维护 $n+1$ 个点。其中线段树需要支持的操作有区间加一个向量,以及线段树上二分查找直线 $x=y$ 上下的两个点。
  
 
== Problem E ==
 
== Problem E ==
  
 
Solved by Xiejiadong. 04:42:02 (+2)
 
Solved by Xiejiadong. 04:42:02 (+2)
 +
 +
题意:在二维平面内框一个矩阵,使得框内权值和最大。
 +
 +
题解:离散以后,枚举行的上下边界,然后把列的元素都压在一起,问题就变成了求连续子序列的最大和。
 +
 +
考虑用线段树维护前缀和,每次都是在某个位置加入一个点和他的权值,相当于后缀区间的修改,维护区间最大最小值。
 +
 +
每次 Pushup 的时候,顺便维护连续子序列的最大和,如果两个端点分属于两个子树,用右子树的最大值减最小值更新答案,如果属于同一个子树,直接通过孩子节点的连续子序列最大和更新即可。
  
 
== Problem F ==
 
== Problem F ==
  
 
Solved by Weaver_zhu. 04:01:16 (+2)
 
Solved by Weaver_zhu. 04:01:16 (+2)
 +
 +
题意:给 $x_i, y_i$,求多少种可能的 $x_e,y_e$ 使得所有 $|x_i-x_e| + |y_i-y_e| \equiv t_i ( mod \  k_i)$
 +
 +
题解:枚举绝对值正负号,然后 CRT 搞起来,只有 $x_e + y_e$ 或 $x_e - y_e$ 的情况可以枚举值,否则可以解出二元一次模线性方程组,然后 $O(1)$ 搞一下就行了
  
 
== Problem G ==
 
== Problem G ==
Line 30: Line 66:
  
 
Solved by Weaver_zhu. 00:28:26 (+)
 
Solved by Weaver_zhu. 00:28:26 (+)
 +
 +
温暖的签到
  
 
== Problem I ==
 
== Problem I ==
Line 41: Line 79:
 
== Problem K ==
 
== Problem K ==
  
Unsolved. (-3)
+
Upsolved by Xiejiadong. (-3)
 +
 
 +
题意:给出一个数字串,可以在 `?` 的地方填入任意数字,要求出是 $m$ 的倍数第 $k$ 小的数。
 +
 
 +
题解:可以发现,因为 $m$ 比较小,所以不需要很多的位数就能得到答案。
 +
 
 +
只选择最后的 $30$ 位,前面的全部填 $0$ 。预处理每一个 `?` 位置的后缀模情况,然后贪心的选择每一位填的数。
 +
 
 +
其实场上就写出来了。一开始的阈值设大了, TLE 了几发,最后 WA 了,以为假了,就扔了,谁知道,有一个模数写错导致假了。
  
 
== Problem L ==
 
== Problem L ==
Line 51: Line 97:
 
题解:显然两个人的策略就是取当前剩下的里面叶子中最大的。
 
题解:显然两个人的策略就是取当前剩下的里面叶子中最大的。
  
又显然,当前堆中的最大元素一定是叶子,所以排序以后,两个人一次从大到小取就好了。
+
又显然,当前堆中的最大元素一定是叶子,所以排序以后,两个人依次从大到小取就好了。

Latest revision as of 13:06, 14 August 2019

Problem A

Unsolved.

Problem B

Upsolved by Xiejiadong.

题意:给出一个排列,每次激活其中一个位置,询问当前数列的 LIS 。

题解:倒着看,每次删除排列中的一个数,询问当前数列的 LIS 。

因为是随机的,所以 LIS 的期望长度是 $\sqrt{n}$ 。

随机删除一个数,正好删到当前 LIS 所在元素的概率是 $\frac{1}{\sqrt{n}}$ ,所以一旦删到了,暴力重构即可。

Problem C

Unsolved.

Problem D

Solved by Kilo_5723. 03:09:30 (+)

题意:有 $n$ 个工作,第 $i$ 个给甲做会花 $a_i$ 的时间,给乙做会花 $b_i$ 的时间。但是甲乙可以各做一部分工作,花费的时间为 $x\cdot a_i+y \cdot b_i(x+y=1)$。对每个 $i(1 \le i \le n)$,求出前 $i$ 个工作,两个人做完,花费时间最多的人需要花费至少多少时间。

题解:我们考虑 $n$ 个工作的情况:

如果工作全部分给甲,那么此时甲要花 $A=\sum_{i=1}^n a_i$ 的时间,乙要花费 $0$ 的时间,记为 $(A,0)$。

而接下来甲要把工作分给乙,那么甲肯定会分 $\frac{a_i}{b_i}$ 最大的工作,设这个工作为 $p$。如果这个工作全部分给乙,此时的情况是 $(A-a_p,b_p)$。而这之间的所有情况,都分布在 $(A,0)$ 和 $(A-a_p,b_p)$ 的连线上。

再接下来,甲肯定会分 $\frac{a_i}{b_i}$ 第二大的工作,然后是第三大,直到最后情况会变成 $(0,B)$。

自此,我们得到了一系列点,我们要求的就是这些点形成折线段和直线 $x=y$ 的交点,我们只要二分找到直线 $x=y$ 上下的两个点求交点就可以了。

现在考虑怎么维护的问题。我们发现,去掉一个工作 $a_i,b_i$ 之后,其对应的线段右方的点会全部平移 $(-a_i,0)$,而上方的点会全部平移 $(0,-b_i)$。我们要求解,仍是二分找到直线 $x=y$ 上下的两个点,再求交点。这可以用线段树的区间加和二分维护。

因此,我们需要先对工作按斜率排序,并记录每个工作排序后的位置,用线段树来维护 $n+1$ 个点。其中线段树需要支持的操作有区间加一个向量,以及线段树上二分查找直线 $x=y$ 上下的两个点。

Problem E

Solved by Xiejiadong. 04:42:02 (+2)

题意:在二维平面内框一个矩阵,使得框内权值和最大。

题解:离散以后,枚举行的上下边界,然后把列的元素都压在一起,问题就变成了求连续子序列的最大和。

考虑用线段树维护前缀和,每次都是在某个位置加入一个点和他的权值,相当于后缀区间的修改,维护区间最大最小值。

每次 Pushup 的时候,顺便维护连续子序列的最大和,如果两个端点分属于两个子树,用右子树的最大值减最小值更新答案,如果属于同一个子树,直接通过孩子节点的连续子序列最大和更新即可。

Problem F

Solved by Weaver_zhu. 04:01:16 (+2)

题意:给 $x_i, y_i$,求多少种可能的 $x_e,y_e$ 使得所有 $|x_i-x_e| + |y_i-y_e| \equiv t_i ( mod \ k_i)$

题解:枚举绝对值正负号,然后 CRT 搞起来,只有 $x_e + y_e$ 或 $x_e - y_e$ 的情况可以枚举值,否则可以解出二元一次模线性方程组,然后 $O(1)$ 搞一下就行了

Problem G

Unsolved.

Problem H

Solved by Weaver_zhu. 00:28:26 (+)

温暖的签到

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Upsolved by Xiejiadong. (-3)

题意:给出一个数字串,可以在 `?` 的地方填入任意数字,要求出是 $m$ 的倍数第 $k$ 小的数。

题解:可以发现,因为 $m$ 比较小,所以不需要很多的位数就能得到答案。

只选择最后的 $30$ 位,前面的全部填 $0$ 。预处理每一个 `?` 位置的后缀模情况,然后贪心的选择每一位填的数。

其实场上就写出来了。一开始的阈值设大了, TLE 了几发,最后 WA 了,以为假了,就扔了,谁知道,有一个模数写错导致假了。

Problem L

Solved by Xiejiadong && Kilo_5723. 00:14:59 (+)

题意:两个人轮流取小根堆的叶子,两个人都希望自己获得的价值最大,求两个人获得的价值。

题解:显然两个人的策略就是取当前剩下的里面叶子中最大的。

又显然,当前堆中的最大元素一定是叶子,所以排序以后,两个人依次从大到小取就好了。