2018-2019 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)

From EOJ Wiki
Jump to navigation Jump to search

在北美都出不了线啊?

Problem A

Solved by zerol. 00:11 (+)

签到。

Problem B

Solved by zerol. 01:06 (+)

题意:求两个区间内各挑出一个数的互素对数。

题解:枚举 gcd 反演。

Problem C

Solved by zerol. 00:50 (+)

签到。

Problem D

Solved by ultmaster. 00:16 (+)

看错题都能 AC?

Problem E

Solved by ultmaster. 01:52 (+1)

题意:要建一座城墙把强盗围住。每个点建城墙有一定开销,求最小开销。

题解:由题意很显然是最小割,但是问题是开销在点上。那么,就拆点咯。读入 n m 反了,莫名其妙 WA 了一发。

Problem F

Solved by kblack. 02:30 (+3)

题意:给一堆矩形,求面积异或并。

题解:扫描线扫一扫,线段树区间翻转维护。这每次写这种扫描线都能把 i j 写倒也是把自己牛逼坏了。

Problem G

Solved by zerol. 00:34 (+)

签到。

Problem H

Solved by ultmaster. 01:20 (+)

随便搞一搞。

Problem I

Solved by ultmaster. 04:22 (+2)

题意:给一个长度为 $n$ 的 $1$ 到 $k$ 组成的序列,有一些位置可以乱填。使得填完以后的序列逆序对个数尽可能多。

题解:首先这些数字肯定从大到小填,易证。然后记状态 f(i,j) 为到第 $i$ 个数为止填的是一块 $j$ 的最大逆序对数(对已有的数产生的贡献)。把 DP 式子写出来会发现有一项 i 和 j 交织在一起。感谢队友教了我 斜率优化。

Problem J

Solved by zerol. 00:39 (+)

签到。

Problem K

Solved by zerol. 02:31 (+1)

简单概率记忆化搜索。

Problem L

Solved by kblack. 00:19 (+1)

温暖的签、咳咳、签到。

Problem M

Solved by kblack. 01:10 (+)

题意:给一堆向量,求加权后横纵坐标积的最大值。

题解:能产生的向量一定在凸壳内,目标函数的极值一定在右上凸壳上,扫过去维护个凸壳,边中间的做个初中数学题。