2015 ICPC 上海站

排名	当场过题数	至今过题数	总题数
47/829	6	?	12

A

upsolved by

题意

题解

B

upsolved by

题意

题解

C

upsolved by

题意

题解

D

upsolved by

题意

题解

E

upsolved by

题意

题解

F

upsolved by

题意

题解

G

upsolved by

题意

题解

H

upsolved by

题意

题解

I

upsolved by 2sozx

题意

给出二维空间里 \(n\) 个点的坐标，求有多少个不同的子点集不是无限点集。无限点集的定义是，将点集中的点两两相连，线段产生的交点加入点集中，继续上面的操作，如果操作能够无限地进行下去，则称之为无限点集。\(n\le 1000, x_i,y_i\le 10^4\)

题解

• 任取1，2，3，4个点组成的点集一定可以，组合数算一下即可
• 对于超过5个点组成的点集的情况
• k点共线一定可以
• k点共线并且一侧有一个点可以

• k点共线并且两侧各有一个点可以

• 对于最后一种情况会产生重复，需要进行去重，即类似 \(X\) 型会被重复计算，需要去重，只需要记录每个点能够产生多少条直线即可。

超过5个点的具体可以对每个点做一次极角排序，每个点会被相同的直线重复算与直线上的关键点个数有关的次数，每次统计只算 $\frac{1}{次数} $ 即可。

J

upsolved by

题意

题解

K

upsolved by

题意

题解

L

solved by 2sozx

题意

每个点 \((x, y)\) 可以移动到 \((x + lcm(x, y), y)\) 或者 \((x, y + lcm(x, y))\) 给定终点，问有多少种起点。终点坐标 \(\le 10^9\)

题解

令 \(x = p_1 * gcd(x, y), y = q_1 * gcd(x,y)\) 因此 \(lcm(x, y) = p_1 * q_1 * gcd(x, y)\)
假定只用第一种（第二种同理），\((x + lcm(x, y), y) = (p_1 * gcd(x, y) + p_1 * q_1 * gcd(x, y), q_1 * gcd(x, y)) = gcd(x, y) * (p_1 *(q_1 + 1), q_1)\) ，因此对于终点 \(O(log)\) 进行逆向递推即可。

记录

总结