首页 程序设计 AtCoder

# E

# 题目大意

给定 nn 个点，每个点的坐标是 (xi,yi)(x_i, y_i)
然后给定 mm 个询问，每个询问代表，我当前站在原点，给定其从 AA 和 BB
请问，我当前由原点指向 (xA,yA)(x_A, y_A) 的射线，转到由原点指向 (xB,yB)(x_B, y_B) 的射线，一共会扫过多少个点

# 数据范围

  • 2≤n≤2×1052 \le n \le 2 \times 10^5
  • 1≤q≤2×1051 \le q \le 2 \times 10^5
  • −109≤xi,yi≤109-10^9 \le x_i, y_i \le 10^9

# 题解

为了解决这道题（不用浮点数的做法）需要掌握：向量与叉积、极角排序

# 向量与叉积

对于向量 a⃗=(x1,y1),b⃗=(x2,y2)\vec{a} = (x_1, y_1), \vec{b} = (x_2, y_2)
cross(a, b) = x1 * y2 - y1 * x2

  • cross(a, b) > 0 ：b⃗\vec{b}在 a⃗\vec{a}的逆时针方向
  • cross(a, b) < 0 ：b⃗\vec{b}在 a⃗\vec{a}的顺时针方向
  • cross(a, b) = 0 ：b⃗\vec{b}和 a⃗\vec{a}共线
    注意，这里的顺、逆时针是指从 a⃗\vec{a}转到 b⃗\vec{b}，旋转角度 <180°< 180° 的旋转

这是第一个点，但是需要注意的是，这里的方向，并不是射线方向，而是向量所在直线的方向，如果需要同方向的话，还需要点积 dot(a, b) > 0

# 极角排序

极角排序模板：

C++
1
2
3
4
5
6
7
8
9
bool upper(v) {
	return (v.y > 0) || (v.y == 0 && v.x > 0)
}

bool cmp(a, b) {
	if (upper(a) != upper(b))
		return upper(a) > upper(b);
	return cross(a, b) > 0;
}

# 综合

排序后，我们合并下同向的
然后呢，有个问题就是，可能会跨过 0°0°，跨过的不好计算，所以可以双倍计算前缀和

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
using namespace std;
#define int long long

struct Pt {
    int x, y, id, gid;
};

int cross(Pt &a, Pt &b) {
    return a.x * b.y - a.y * b.x;
}

int dot(Pt &a, Pt &b) {
    return a.x * b.x + a.y * b.y;
}

bool upper(Pt &p) {
    return p.y > 0 || (p.y == 0 && p.x > 0);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q; cin >> n >> q;
    vector<Pt> pts(n);
    for (int i = 0; i < n; i++) {
        cin >> pts[i].x >> pts[i].y;
        pts[i].id = i;
        pts[i].gid = -1;
    }

    // 极角排序
    sort(pts.begin(), pts.end(), [](Pt &a, Pt &b) {
        bool ua = upper(a), ub = upper(b);
        if (ua != ub) return ua > ub;
        return cross(a, b) > 0;
    });

    // 合并同方向
    vector<int> cnt; // 每组怪物数
    int gid = -1;
    Pt rep;
    
    for (int i = 0; i < n; i++) {
        if (gid == -1) {
            gid = 0;
            cnt.push_back(1);
            rep = pts[i];
            pts[i].gid = gid;
        } else if (cross(rep, pts[i]) == 0 && dot(rep, pts[i]) > 0) {
            cnt[gid]++;
            pts[i].gid = gid;
        } else {
            gid++;
            cnt.push_back(1);
            rep = pts[i];
            pts[i].gid = gid;
        }
    }

    // 拉直圆环前缀和
    int M = cnt.size();
    vector<int> pre(2 * M + 1, 0);
    for (int i = 0; i < 2 * M; i++)
        pre[i + 1] = pre[i] + cnt[i % M];

    // 排回原输入顺序
    sort(pts.begin(), pts.end(), [](Pt &a, Pt &b){
        return a.id < b.id;
    });

    // 查询
    while (q--) {
        int A, B; cin >> A >> B;
        A--; B--;
        
        int pa = pts[A].gid, pb = pts[B].gid;
        
        if (pa == pb)
            cout << cnt[pa] << "\n";
        else {
            int l = pb, r = pa;
            
            if (r < l) r += M;
            
            cout << pre[r + 1] - pre[l] << "\n";
        }
    }
}

# F

# 题目大意

给定一个 n×mn \times m 的网格，由 # 和 . 组成，其中， # 代表黑色， . 代表白色
现在问，能不能找到一种改色方案，使得改后

  • 对于每一行，存在一个整数 k(0≤k<N)k~(0 \le k < N)，使得该行左侧的 kk 个方块是白色，右侧其余的是黑色
  • 对于每一列，存在一个整数 k(0≤k<N)k~(0 \le k < N)，使得该列上方的 kk 个方块是白色，下方其余的是黑色

注意，行 和 行 和 列 和 列的 kk 可以不相同

# 数据范围

  • 1≤n≤50001 \le n \le 5000

# 题解

我们先维护好一个 prei,jpre_{i, j} 数组，表示第 ii 行前 jj 个格子中 . 的个数
那么，对于第 ii 行，如果以 jj 点为分界，那么

  • 前 jj 个格子，需要把 # 改为 . ，也就是要花费 j - pre[i][j]
  • 后面 n−jn - j 个格子，需要把 . 改为 # ，也就是要花费 pre[i][n] - pre[i][j]

总花费为： cost[i][j] = j + pre[i][n] - 2 * pre[i][j]

观察有，如果最终矩阵合法，那么矩阵的行分界点一定是越来越前的
也就是，i−1i-1 行的分界点 kk 必须满足 k≥jk \ge j
那么我们可以搞出一个 dpi,jdp_{i,j}，表示第 ii 行以 jj 点为最后一个白色的最小修改代价，那么可以推导出以下状态转移方程

dpi,j=min⁡j≤k≤ndpi−1,k+costi,jdp_{i,j} = \min_{j \le k \le n} dp_{i - 1,k} + cost_{i,j}

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void solve() {
    cin >> n;
    c = vector<vector<char>>(n + 10, vector<char>(n + 10));
    pre = vector<vector<int>>(n + 10, vector<int>(n + 10));
    cost = vector<vector<int>>(n + 10, vector<int>(n + 10));
    dp = vector<vector<int>>(n + 10, vector<int>(n + 10));

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            cin >> c[i][j];
            pre[i][j] = pre[i][j - 1] + (c[i][j] == '.');
        }

    // cout << '\n';
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= n; j++) {
            cost[i][j] = j + pre[i][n] - 2 * pre[i][j];
            // cout << cost[i][j] << (j == n ? "\n" : " ");
        }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = cost[i][j];

            int minn = 1e18;
            for (int k = j; k <= n; k++)
                minn = min(minn, dp[i - 1][k]);

            dp[i][j] += minn;
        }
    }

    int res = 1e18;
    for (int j = 0; j <= n; j++)    res = min(res, dp[n][j]);

    cout << res << '\n';
}

但是这样写代码，复杂度是 O(n3)O(n^3) 的，数据范围是 50005000，所以还得优化
显然，我们每次只需要求 min⁡j≤k≤ndpi−1,k\min_{j \le k \le n} dp_{i - 1,k}，那我们不妨维护一个 sufMinsufMin 数组，去记录后 jj 个的 dpdp 的最小值
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void solve() {
    cin >> n;
    c = vector<vector<char>>(n + 10, vector<char>(n + 10));
    pre = vector<vector<int>>(n + 10, vector<int>(n + 10));
    cost = vector<vector<int>>(n + 10, vector<int>(n + 10));
    dp = vector<vector<int>>(n + 10, vector<int>(n + 10));
    sufMin = vector<int>(n + 10);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> c[i][j], pre[i][j] = pre[i][j - 1] + (c[i][j] == '.');

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= n; j++) 
            cost[i][j] = j + pre[i][n] - 2 * pre[i][j];


    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = cost[i][j] + sufMin[j];
        }

        sufMin[n] = dp[i][n];
        for (int j = n - 1; j >= 0; j--)
            sufMin[j] = min(dp[i][j], sufMin[j + 1]);
    }

    int res = 1e18;
    for (int j = 0; j <= n; j++)    res = min(res, dp[n][j]);

    cout << res << '\n';
}

更新于 阅读次数 次

请我喝[茶]~(￣▽￣)~*

duoxichangan 微信支付

微信支付

duoxichangan 支付宝

支付宝