LG-P3562 [POI2013] LAS-Laser Solution

更好的阅读体验戳此进入

（建议您从上方链接进入我的个人网站查看此 Blog，在 Luogu 中图片会被墙掉，部分 Markdown 也会失效）

题面

给定平面上的 $n$$n$ 条线段（用点 $(x_1,y_1),(x_2,y_2)$$(x_1, y_1), (x_2, y_2)$ 表示），你可以从原点引出最多 $k$$k$ 条射线，使其穿过尽可能多的线段，且每条线段最多被穿过 $1$$1$ 次，求最多可以穿过多少条线段。

$1\le n\le 5\times {10}^5,1\le k\le 100,1\le x_1,y_1,x_2,y_2\le {10}^5$$1 \le n \le 5 \times 10^5, 1 \le k \le 100, 1 \le x_1, y_1, x_2, y_2 \le 10^5$。

输入格式

$n,k$$n, k$

$x_1,y_1,x_2,y_2$$x_1, y_1, x_2, y_2$

$\cdots$$\cdots$ (n lines in total)

Solution

首先本题有一个比较显而易见的贪心，即最优的情况下每条射线至少穿过一条线段的端点，感性理解一下，如果不穿过端点那么移动到端点一定是不劣的。

我们可以考虑一个类似极角排序的思想，把每一个点当成一个向量的坐标表示，按照角度进行排序离散化并尝试寻找性质：

可以看下图：

排序离散化后，每个点旁边的数字即为其离散化后的坐标，于是我们发现，每一条线段都变成了一个区间：

$[1,1],[7,8],[3,6],[4,5],[5,5],[2,9]$$\left[ 1, 1 \right], \left[ 7, 8 \right], \left[ 3, 6 \right], \left[ 4, 5 \right], \left[ 5, 5 \right], \left[ 2, 9 \right]$。

同时注意，离散化后的每一个点都是至少一个区间的端点！

而我们从原点引出的每一条射线，也可以抽象成一个向量的坐标，或者换句话说，是这些区间中的一个点。

于是此时我们便可以发现问题变成了在给定区间中选择一些点，使这些点涉及的区间尽可能多，且每个区间中最多只有一个点。

对于这个问题应该是一个显然的 DP，我们考虑设 $dp(i,j)$$dp(i, j)$ 表示在前 $i$$i$ 个点（等同于区间端点）中选择 $j$$j$ 个点最多可以涉及多少个区间。

考虑转移，显然可以通过 $dp(i-1,j)$$dp(i - 1, j)$ 转移，同时我们也可以考虑如果选择第 $i$$i$ 个点，那么应该从什么区间转移而来？

显然选择第 $i$$i$ 个点后，其所涉及的所有区间都不能有其它的点，所以我们应该记录 $i$$i$ 所涉及的所有的区间中最左的端点，记其为 $lft(i)$$lft(i)$，同时记点 $i$$i$ 涉及的区间的数量为 $cnt(i)$$cnt(i)$，那么也就是从 $dp(lft(i)-1,j-1)+cnt(i)$$dp(lft(i) - 1, j - 1) + cnt(i)$ 转移而来。

于是我们的方程便为 $dp(i,j)=max(dp(i-1,j),dp(lft(i)-1,j-1)+cnt(i))$$dp(i, j) = \max(dp(i - 1, j), dp(lft(i) - 1, j - 1) + cnt(i))$。

通过差分预处理一下 $lft$$lft$ 和 $cnt$$cnt$ 即可。

然后注意观察到 $i$$i$ 的值域是 $5\times {10}^5$$5 \times 10^5$，$j$$j$ 的值域是 ${10}^2$$10^2$，所以空间占用为 ${\displaystyle \frac{5\times {10}^5\times {10}^2\times 4}{{1024}^2}}>128$$\dfrac{5 \times 10^5 \times 10^2 \times 4}{1024^2} \gt 128$，空间会炸，发现 $j$$j$ 只会从 $j$$j$ 或 $j-1$$j - 1$ 转移而来，所以可以以类似写背包时候的思想把 $j$$j$ 的维度去掉，将不同版本考虑好即可。

时间复杂度是 $O(n(\log n+k))$$O(n(\log n + k))$ 的，显然可以通过。

Tips：对于具体的离散化实现，可以通过向量的外积，大于零则前者在后者的顺时针方向，反之亦然，可以考虑写个结构体重载小于号和等于号，或者在 sort 和 unique 和 lower_bound 的时候写个 lambda 函数也行，亦或自己纯手搓一个离散化也可以实现，具体可以看代码。

Code

xxxxxxxxxx
98
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
/******************************
12
abbr
13
segl => line segment
14
lft => left
15
******************************/
16

17
using namespace std;
18
using namespace __gnu_pbds;
19

20
mt19937 rnd(random_device{}());
21
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
22
bool rnddd(int x){return rndd(1, 100) <= x;}
23

24
typedef unsigned int uint;
25
typedef unsigned long long unll;
26
typedef long long ll;
27
typedef long double ld;
28

29
template<typename T = int>
30
inline T read(void);
31

32
struct Point{
33
    int x, y;
34
    friend ll operator * (const Point &a, const Point &b){
35
        return (ll)a.x * b.y - (ll)a.y * b.x;
36
    }
37
    friend bool operator < (const Point &a, const Point &b){
38
        return a * b < 0;
39
    }
40
    friend bool operator == (const Point &a, const Point &b){
41
        return a * b == 0;
42
    }
43
};
44
int K, N;
45
pair < Point, Point > segl[510000];
46
pair < int, int > seg[510000];
47
vector < Point > arr;
48
int cnt[1100000];
49
int lft[1100000];
50
int dp[1100000];
51

52
int main(){
53
    K = read(), N = read();
54
    for(int i = 1; i <= N; ++i){
55
        int x1 = read(), y1 = read(), x2 = read(), y2 = read();
56
        segl[i] = {Point{x1, y1}, Point{x2, y2}};
57
        arr.push_back(Point{x1, y1}), arr.push_back(Point{x2, y2});
58
    }
59
    sort(arr.begin(), arr.end(), [](const Point &a, const Point &b)->bool{return a * b < 0;});
60
    auto endpos = unique(arr.begin(), arr.end());
61
    int siz = distance(arr.begin(), endpos);
62
    for(int i = 1; i <= N; ++i){
63
        seg[i].first = distance(arr.begin(), lower_bound(arr.begin(), endpos, segl[i].first) + 1);
64
        seg[i].second = distance(arr.begin(), lower_bound(arr.begin(), endpos, segl[i].second) + 1);
65
        if(seg[i].first > seg[i].second)swap(seg[i].first, seg[i].second);
66
    }
67
    for(int i = 1; i <= siz; ++i)lft[i] = siz;
68
    for(int i = 1; i <= N; ++i){
69
        ++cnt[seg[i].first], --cnt[seg[i].second + 1];
70
        lft[seg[i].second] = min(lft[seg[i].second], seg[i].first);
71
    }
72
    for(int i = 1; i <= siz; ++i)cnt[i] += cnt[i - 1];
73
    for(int i = siz - 1; i >= 1; --i)lft[i] = min(lft[i], lft[i + 1]);
74
    for(int j = 1; j <= K; ++j){
75
        for(int i = siz; i >= 1; --i)dp[i] = max(dp[i], dp[lft[i] - 1] + cnt[i]);
76
        for(int i = 1; i <= siz; ++i)dp[i] = max(dp[i], dp[i - 1]);
77
    }
78
    printf("%d\n", dp[siz]);
79

80
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
81
    return 0;
82
}
83

84
template<typename T>
85
inline T read(void){
86
    T ret(0);
87
    short flag(1);
88
    char c = getchar();
89
    while(c != '-' && !isdigit(c))c = getchar();
90
    if(c == '-')flag = -1, c = getchar();
91
    while(isdigit(c)){
92
        ret *= 10;
93
        ret += int(c - '0');
94
        c = getchar();
95
    }
96
    ret *= flag;
97
    return ret;
98
}

UPD

update-2022_10_04 初稿