doge的个人site
0%

下午茶 1010-1014

Posted on Edited on

下午茶10.10-10.14
总结: 多维dp + 特殊BFS + 经典dp

当你想不出来的时候不妨将思维 “逆转过来”

下午茶合集

10.14-1407D

10.13-1286A

本质：1-n排列挖掉几个数字，求一种放法，使得相邻的数，奇偶性不同的数量最小。

考虑奇数&偶数可以放的数量, 以及看到相邻，立刻反应过来这是一个序列dp的问题

状态定义:

  • f[i][j][k][0/1] 表示 [0:i]位置，取了[j]个奇数，[k]个偶数，末尾取值是奇数1/偶数0的最小操作数；最终答案就是f[n][*][*][0/1]的最小值

  • 实际上可以优化成 f[i][j][0/1],考虑到题目中写明了’是一个$1-n$的排列’，所以一定是有$n/2$个偶数，剩下都是奇数，因此可以去掉上面的一个维度；最终答案就是f[n][n/2][0/1]的最小值

  • 更进一步，这里f[i][j][0/1]只和前一个状态f[i-1][**][**]有关系，所以实际上可以压缩这个维度

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
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int maxn = 0x3f3f3f3f;

int n;
int p[105];

// f[i][j][0/1]
// 前i个数, 填了j个偶数, 末尾是偶数/奇数的最小对数
int f[105][105][2];

// if: [i] = 0, could fill
// f[i][j][0] <- f[i - 1][j - 1][0] + 0, f[i - 1][j][1] + 1, 
// f[i][j][1] <- f[i - 1][j - 1][1] + 0, f[i - 1][j][0] + 1,

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
    }
    memset(f, 0x3f, sizeof(f));
    f[0][0][0] = 0;
    f[0][0][1] = 0;
    for (int i = 1; i <= n; ++i) {
        // number of evens
        for (int j = 0; j <= n / 2; ++j) {
            // p[i] is even, or p[i] is 0 and filled even
            if (j > 0 && p[i] % 2 == 0) {
                f[i][j][0] = min(f[i - 1][j - 1][0], f[i - 1][j - 1][1] + 1);
            }
            if (p[i] == 0 || p[i] % 2 > 0) {
                f[i][j][1] = min(f[i - 1][j][0] + 1, f[i - 1][j][1]);
            }
        }
    }

    cout << min(f[n][n / 2][0], f[n][n / 2][1]) << '\n';
    return 0;
}

10.12-1651D

输入 $n(\lt 2e5)$ 和 $n$ 个二维平面上的互不相同的整点，坐标范围 $[1,2e5]$。
对每个整点，输出离它曼哈顿距离最近的，且不在输入中的整点。

两点的曼哈顿距离=横坐标之差的绝对值+纵坐标之差的绝对值。

  1. 可能有些点，它的四周就是空的，那么对于这些点而言直接返回其中一个就行了

  2. 内侧的点怎么找到最近? 从与它相邻的外部点转移过来就是最近了

  3. 特别的BFS技巧，从外部点(可行解)向内(待求解)的方向进行BFS，保证内部点的解是最优的。

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
#include <bits/stdc++.h>
#define ll long long
#define PII pair<int,int>

using namespace std;

int n;
map<PII, int> vis;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
PII ans[200050];

// a: new Pair, b: old Pair
struct node {
    PII a, b;
    node(PII _a, PII _b): a(_a), b(_b) {}
};

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x, y;
        cin >> x >> y;
        vis.insert({{x, y}, i});
    }

    queue<node> q, qq;

    for (auto& v: vis) {
        auto p = v.first;   // current point
        auto idx = v.second;    // index
        for (int i = 0; i < 4; ++i) {
            int nx = p.first + dx[i];   // around points
            int ny = p.second + dy[i];
            PII np = {nx, ny};
            if (vis.count(np) == 0) {   // not in
                ans[idx] = np;
                qq.push(node(p, np));   // [in-vis points, out-vis points]
                break;
            }
        }
    }

    q = qq;
    while (!qq.empty()) {
        auto pqq = qq.front();
        qq.pop();
        // erase old pairs
        vis.erase(pqq.a);
    }

    while (!q.empty()) {
        auto pq = q.front();
        q.pop();
        auto in_p = pq.a;
        auto out_p = pq.b;
        for (int i = 0; i < 4; ++i) {
            int nx = in_p.first + dx[i];
            int ny = in_p.second + dy[i];
            PII cur_p = {nx, ny};
            if (vis.count(cur_p)) {       // find!
                ans[vis[cur_p]] = out_p;  // current point's surroundings is 
                vis.erase(cur_p);         // remove visited points
                q.push(node(cur_p, out_p));
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        cout << ans[i].first << ' ' << ans[i].second << '\n';
    }

    return 0;
}

10.11-988F

10.10-38E

弹珠游戏

题目大致的含义就是求最小的一个代价, 使得所有的珠子可以滑动到对应位置。

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
#include <bits/stdc++.h>
#define ll long long
using namespace std;

struct node {
    int x, c;
    node(int _x=0, int _c=0): x(_x), c(_c) {}
    bool operator <(const node& a) const {
        return x < a.x;
    }
};

int n;
ll ans = LLONG_MAX;
ll f[3005][3005];
node m[3050];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x, c;
        cin >> x >> c;
        m[i] = node(x, c);
    }
    sort(m + 1, m + n + 1);

    // f[i][j]: 前i个位置, 最后固定位置为j的最小代价
    // 固定最左侧的    
    f[1][1] = m[1].c;


    for (int i = 2; i <= n; ++i) {
        ll oo = LLONG_MAX;
        for (int j = 1; j < i; ++j) {
            f[i][j] = f[i - 1][j] + (m[i].x - m[j].x);
            oo = min(oo, f[i - 1][j]);
        }
        f[i][i] = oo + m[i].c;
    }

    for (int ed = 1; ed <= n; ++ed) {
        ans = min(ans, f[n][ed]);
    }
    cout << ans << '\n';
    return 0;
}