2018-2019 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)
在北美都出不了线啊?
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)
Problem J
Solved by . 00:39 (+)
Problem K
Solved by . 02:31 (+1)
Problem L
Solved by kblack. 00:19 (+1)
温暖的签、咳咳、签到。
Problem M
Solved by kblack. 01:10 (+)
题意:给一堆向量,求加权后横纵坐标积的最大值。
题解:能产生的向量一定在凸壳内,目标函数的极值一定在右上凸壳上,扫过去维护个凸壳,边中间的做个初中数学题。