OI
17 minutes read (About 2573 words)

「模拟测试」20171019

T1 打牌

给出一些数字，求最多能组成多少个对子 $(x, x)$ 或顺子 $(x, x + 1, x + 2)$。

题解

我最开始就想了一个错误的贪心，考虑到有 $1, 2, 3, 3, 4, 5, 5, 6, 7$ 这样的情况下，顺子会优于对子，就先选这种情况，再选对子，然后是顺子，然而这么做会有问题。

正确的做法是先让 $1, 2$ 直接组成对子，$3 \sim n$ 先判断能不能和前面组成顺子，若前两个数的个数为奇数才组成顺子，然后剩余的组成对子。

代码

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
/**
 * Copyright (c) 2017, xehoth
 * All rights reserved.
 * 「SuperOJ 1992」打牌 19-10-2017
 * 贪心
 * @author xehoth
 */
#include <bits/stdc++.h>

namespace IO {

inline char read() {
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
    return s == t ? -1 : *s++;
}

template <typename T>
inline bool read(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
        if (c == -1) return false;
        c == '-' ? iosig = true : 0;
    }
    for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
    iosig ? x = -x : 0;
    return true;
}

inline void read(char &c) {
    while (c = read(), isspace(c) && c != -1)
        ;
}

inline int read(char *buf) {
    register int s = 0;
    register char c;
    while (c = read(), isspace(c) && c != -1)
        ;
    if (c == -1) {
        *buf = 0;
        return -1;
    }
    do
        buf[s++] = c;
    while (c = read(), !isspace(c) && c != -1);
    buf[s] = 0;
    return s;
}

const int OUT_LEN = 1000000;

char obuf[OUT_LEN], *oh = obuf;

inline void print(char c) {
    oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
    *oh++ = c;
}

template <typename T>
inline void print(T x) {
    static int buf[30], cnt;
    if (x == 0) {
        print('0');
    } else {
        x < 0 ? (print('-'), x = -x) : 0;
        for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
        while (cnt) print((char)buf[cnt--]);
    }
}

inline void print(const char *s) {
    for (; *s; s++) print(*s);
}

inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }

struct InputOutputStream {
    template <typename T>
    inline InputOutputStream &operator>>(T &x) {
        read(x);
        return *this;
    }

    template <typename T>
    inline InputOutputStream &operator<<(const T &x) {
        print(x);
        return *this;
    }

    ~InputOutputStream() { flush(); }
} io;
}

namespace {

const int MAXN = 1000000;

int n, x, ans;
int cnt[MAXN + 1];

using IO::io;

inline void solve() {
    io >> n;
    for (register int i = 1; i <= n; i++) io >> x, cnt[x]++;
    ans += cnt[1] / 2, cnt[1] %= 2, ans += cnt[2] / 2, cnt[2] %= 2;
    for (register int i = 3; i <= MAXN; i++) {
        if ((cnt[i - 2] & 1) && (cnt[i - 1] & 1) && cnt[i])
            ans++, cnt[i - 2]--, cnt[i - 1]--, cnt[i]--;
        ans += cnt[i] / 2, cnt[i] %= 2;
    }
    io << ans;
}
}

int main() {
    solve();
    return 0;
}

T2 弹球

有一个 $m \times n$ 的矩形，一个球从左上角开始向右下四十五度方向弹出，碰到边界会反弹，直到到达某个角落停下，问有多少个格子恰好经过了一遍。

题解

直接找规律并不简单，我们先把格子缩小一格，把边转化成点，然后就找规律就好了。

代码

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
/**
 * Copyright (c) 2017, xehoth
 * All rights reserved.
 * 「SuperOJ 1993」弹球 19-10-2017
 *
 * @author xehoth
 */
#include <bits/stdc++.h>

namespace IO {

inline char read() {
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
    return s == t ? -1 : *s++;
}

template <typename T>
inline bool read(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
        if (c == -1) return false;
        c == '-' ? iosig = true : 0;
    }
    for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
    iosig ? x = -x : 0;
    return true;
}

inline void read(char &c) {
    while (c = read(), isspace(c) && c != -1)
        ;
}

inline int read(char *buf) {
    register int s = 0;
    register char c;
    while (c = read(), isspace(c) && c != -1)
        ;
    if (c == -1) {
        *buf = 0;
        return -1;
    }
    do
        buf[s++] = c;
    while (c = read(), !isspace(c) && c != -1);
    buf[s] = 0;
    return s;
}

const int OUT_LEN = 1000000;

char obuf[OUT_LEN], *oh = obuf;

inline void print(char c) {
    oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
    *oh++ = c;
}

template <typename T>
inline void print(T x) {
    static int buf[30], cnt;
    if (x == 0) {
        print('0');
    } else {
        x < 0 ? (print('-'), x = -x) : 0;
        for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
        while (cnt) print((char)buf[cnt--]);
    }
}

inline void print(const char *s) {
    for (; *s; s++) print(*s);
}

inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }

struct InputOutputStream {
    template <typename T>
    inline InputOutputStream &operator>>(T &x) {
        read(x);
        return *this;
    }

    template <typename T>
    inline InputOutputStream &operator<<(const T &x) {
        print(x);
        return *this;
    }

    ~InputOutputStream() { flush(); }
} io;
}

namespace {

using IO::io;

#define long long long

int n, m;

inline void solveCase() {
    io >> n >> m, n--, m--;
    register long t = std::__gcd(n, m);
    io << n / t * m / t * (t - 1) + n / t + m / t << '\n';
}

inline void solve() {
    register int T;
    io >> T;
    while (T--) solveCase();
}
}

int main() {
    solve();
    return 0;
}

T3 放盒子

同 51NOD 1392

有 $n$ 个长方形盒子，第 $i$ 个长度为 $L_i$，宽度为 $W_i$，我们需要把他们套放。注意一个盒子只可以套入长和宽分别不小于它的盒子，并且一个盒子里最多只能直接装入另外一个盒子（但是可以不断嵌套），例如 $1 \times 1$ 可以套入 $2 \times 1$，而 $2 \times 1$ 再套入 $2 \times 2$。套入之后盒子占地面积是最外面盒子的占地面积。给定 $n$ 个盒子大小，求最终最小的总占地面积。

题解

一种简单的做法就是费用流，先对盒子去重，将每个盒子拆点为 $x, x’$，$S \rightarrow x$ 连 $(1, 0)$ 的边，$x’ \rightarrow T$ 连 $(1, 0)$ 的边，对于两个盒子 $i, j$，若 $i$ 能放进 $j$，$j \rightarrow i’$ 连 $(1, -L_i \cdot W_i)$ 的边，答案就是 $\sum\limits_{i = 1} ^ n L_i \cdot W_i - \text{costflow}(S, T)$。

参考 唐老师题解

我们发现盒子 $i$ 能装入盒子 $j$ 当且仅当 $W_i \leq W_j, L_i \leq L_j$，所以根据这个关系，我们可以构成一个 DAG，我们就可以将答案表示成最小权路径覆盖，每个路径的权为最后一个到达盒子的面积。
考虑如何计算最小权路径覆盖，不考虑权的时候，也就是留下最少的点使得它们不存在一个后继节点在某个路径上，也就是最多的点存在后继节点，这个后继关系可以看作是匹配，由于是有向无环图，这个匹配可以看作是二分图上的匹配，现在考虑最小权路径覆盖，也即最大化有后继节点的权值之和，用 KM 算法即可解决。

代码

费用流
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
/**
 * Copyright (c) 2017, xehoth
 * All rights reserved.
 * 「SuperOJ 1994」放盒子 19-10-2017
 * 费用流
 * @author xehoth
 */
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>

using namespace __gnu_pbds;

namespace {

inline bool relax(int &x, int v) { return v < x ? (x = v, true) : false; }

const int MAXN = 410;
const int INF = 0x3f3f3f3f;

struct Node {
    int v, f, w, index;

    Node(int v, int f, int w, int index) : v(v), f(f), w(w), index(index) {}
};

struct Graph {
    typedef std::vector<Node> Vector;
    Vector edge[MAXN + 1];

    inline void addEdge(const int u, const int v, const int f, const int w) {
        edge[u].push_back(Node(v, f, w, edge[v].size()));
        edge[v].push_back(Node(u, 0, -w, edge[u].size() - 1));
    }

    inline Vector &operator[](const int i) { return edge[i]; }
};

struct PrimalDual : Graph {
    int h[MAXN + 1], d[MAXN + 1];
    bool vis[MAXN + 1];

    typedef Vector::iterator Iterator;

    typedef std::pair<int, int> Pair;
    typedef __gnu_pbds::priority_queue<Pair, std::greater<Pair> > PriorityQueue;

    inline void bellmanFord(const int s, const int n) {
        memset(h, 0x3f, sizeof(int) * (n + 1));
        static std::queue<int> q;
        q.push(s), h[s] = 0;
        for (register int u; !q.empty();) {
            vis[u = q.front()] = false, q.pop();
            for (Iterator p = edge[u].begin(); p != edge[u].end(); p++)
                if (p->f > 0 && relax(h[p->v], h[u] + p->w) && !vis[p->v])
                    q.push(p->v), vis[p->v] = true;
        }
    }

    inline void dijkstra(const int s, const int n) {
        memset(vis, 0, sizeof(bool) * (n + 1));
        static PriorityQueue::point_iterator id[MAXN + 1];
        static PriorityQueue q;
        memset(id, 0, sizeof(PriorityQueue::point_iterator) * (n + 1));
        memset(d, 0x3f, sizeof(int) * (n + 1));
        id[s] = q.push(Pair(d[s] = 0, s));
        for (register int u; !q.empty();) {
            register Pair now = q.top();
            q.pop(), u = now.second;
            if (vis[u] || d[u] < now.first) continue;
            vis[u] = true;
            for (Iterator p = edge[u].begin(); p != edge[u].end(); p++) {
                if (p->f > 0 && relax(d[p->v], d[u] + p->w + h[u] - h[p->v])) {
                    if (id[p->v] != NULL)
                        q.modify(id[p->v], Pair(d[p->v], p->v));
                    else
                        id[p->v] = q.push(Pair(d[p->v], p->v));
                }
            }
        }
    }

    int iter[MAXN + 1];

    int dfs(int v, int flow, int s, int t, int &cost) {
        if (v == t) return cost += h[t] * flow, flow;
        vis[v] = true;
        register int rec = 0;
        for (register int i = iter[v]; i < edge[v].size(); i++) {
            Node *p = &edge[v][i];
            if (!vis[p->v] && p->f > 0 && h[v] == h[p->v] - p->w) {
                register int ret =
                    dfs(p->v, std::min(flow - rec, p->f), s, t, cost);
                p->f -= ret, edge[p->v][p->index].f += ret, iter[v] = i;
                if ((rec += ret) == flow) return rec;
            }
        }
        return rec;
    }

    inline void primalDual(int s, int t, int n, int &flow, int &cost,
                           int f = INF) {
        for (bellmanFord(s, n), cost = 0, flow = 0; f > 0;) {
            dijkstra(s, n);
            if (d[t] == INF) break;
            for (register int i = 0; i <= n; i++)
                h[i] = std::min(INF, h[i] + d[i]);
            memset(iter, 0, sizeof(int) * (n + 1));
            memset(vis, 0, sizeof(bool) * (n + 1));
            flow += dfs(s, INF, s, t, cost);
        }
    }
} g;

struct Data {
    int l, w, s;

    inline bool operator<(const Data &p) const {
        return l < p.l || (l == p.l && w < p.w);
    }

    inline bool operator==(const Data &p) const { return l == p.l && w == p.w; }
} d[MAXN + 1];

inline void solve() {
    register int n, ans = 0, flow = 0, cost = 0;
    std::cin >> n;
    for (register int i = 1; i <= n; i++)
        std::cin >> d[i].l >> d[i].w, d[i].s = d[i].l * d[i].w;
    std::sort(d + 1, d + n + 1);
    register int cnt = std::unique(d + 1, d + n + 1) - d - 1;
    n = cnt;
    register const int S = 0, T = n << 1 | 1;
    for (register int i = 1; i <= n; i++) {
        g.addEdge(S, i, 1, 0), g.addEdge(i + n, T, 1, 0);
        for (register int j = i + 1; j <= n; j++)
            if (d[i].l <= d[j].l && d[i].w <= d[j].w)
                g.addEdge(j, i + n, 1, -d[i].s);
        ans += d[i].s;
    }
    g.primalDual(S, T, T + 1, flow, cost);
    std::cout << ans + cost;
}
}

int main() {
    std::ios::sync_with_stdio(false), std::cin.tie(NULL), std::cout.tie(NULL);
    solve();
    return 0;
}
KM
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/**
 * Copyright (c) 2017, xehoth
 * All rights reserved.
 * 「SuperOJ 1994」放盒子 19-10-2017
 * KM
 * @author xehoth
 */
#include <bits/stdc++.h>

const int MAXN = 210;
const int MAX_NL = 210;
const int MAX_NR = 210;
const int INF = 0x3f3f3f3f;

template <class T>
inline bool relax(T &a, const T &b) {
    return b > a ? (a = b, true) : false;
}

template <class T>
inline bool tense(T &a, const T &b) {
    return b < a ? (a = b, true) : false;
}

struct KuhnMunkres {
    int map[MAX_NL][MAX_NR], n, labL[MAX_NL], labR[MAX_NR], slackR[MAX_NR];
    int mateL[MAX_NL], mateR[MAX_NR], faR[MAX_NR], qSize, q[MAX_NL];
    bool bookL[MAX_NL], bookR[MAX_NR];

    inline void augment(int v) {
        for (register int u = faR[v]; v > 0;)
            mateR[v] = (u = faR[v]), std::swap(v, mateL[u]);
    }

    inline bool isOnFoundEdge(int v) {
        if (mateR[v]) {
            q[++qSize] = mateR[v], bookR[v] = true, bookL[mateR[v]] = true;
            return false;
        } else {
            augment(v);
            return true;
        }
    }

    inline void match(int sv) {
        memset(bookL, 0, sizeof(bool) * (n + 1));
        memset(bookR, 0, sizeof(bool) * (n + 1));
        memset(slackR, 0x3f, sizeof(int) * (n + 1));
        memset(faR, 0, sizeof(int) * (n + 1));
        bookL[q[qSize = 1] = sv] = true;
        for (;;) {
            for (register int i = 1; i <= qSize; ++i) {
                register int u = q[i];
                for (register int v = 1; v <= n; v++) {
                    register int d = labL[u] + labR[v] - map[u][v];
                    if (bookR[v] || d > slackR[v]) continue;
                    faR[v] = u;
                    if (d > 0)
                        slackR[v] = d;
                    else if (isOnFoundEdge(v))
                        return;
                }
            }
            register int nv = 0, delta = INF;
            for (register int v = 1; v <= n; v++)
                if (!bookR[v] && tense(delta, slackR[v])) nv = v;
            for (register int u = 1; u <= n; u++)
                if (bookL[u]) labL[u] -= delta;
            for (register int v = 1; v <= n; v++) {
                if (bookR[v])
                    labR[v] += delta;
                else
                    slackR[v] -= delta;
            }
            qSize = 0;
            if (isOnFoundEdge(nv)) return;
        }
    }

    inline void addEdge(const int u, const int v, const int w) {
        map[u][v] = w, relax(labL[u], w);
    }

    inline int km(const int nL, const int nR) {
        this->n = std::max(nL, nR);
        for (register int u = 1; u <= nL; u++) match(u);
        register int ret = 0;
        for (register int u = 1; u <= nL; u++) ret += labL[u];
        for (register int v = 1; v <= nR; v++) ret += labR[v];
        return ret;
    }
} km;

struct Node {
    int l, w, s;

    inline bool operator<(const Node &p) const {
        return l < p.l || (l == p.l && w < p.w);
    }

    inline bool operator==(const Node &p) const { return l == p.l && w == p.w; }
} d[MAXN + 1];

int main() {
    std::ios::sync_with_stdio(false), std::cin.tie(NULL), std::cout.tie(NULL);
    register int n;
    std::cin >> n;
    register int ans = 0;
    for (register int i = 1; i <= n; i++)
        std::cin >> d[i].l >> d[i].w, d[i].s = d[i].l * d[i].w;
    std::sort(d + 1, d + n + 1), n = std::unique(d + 1, d + n + 1) - d - 1;
    for (register int i = 1; i <= n; i++) ans += d[i].s;
    for (register int i = 1; i <= n; i++)
        for (register int j = i + 1; j <= n; j++)
            if (d[i].l <= d[j].l && d[i].w <= d[j].w) km.addEdge(i, j, d[i].s);
    std::cout << ans - km.km(n, n);
    return 0;
}
「SuperOJ 1998」「模拟测试」矩阵-DP
「UVA 11404」Palindromic Subsequence-DP

Comments

Follow

Tag Cloud

Algorithm CG DP Data Structure Frontend Geometry Graph Theory Hash Hexo Language Math Note Ray Tracing Rendering STL String Test

Recent

Categories

Tags

Algorithm 2
CG 11
DP 26
Data Structure 68
Frontend 1
Geometry 7
Graph Theory 28
Hash 6
Hexo 1
Language 3
Math 42
Note 37
Ray Tracing 8
Rendering 8
STL 11
String 44
Test 1

Links

Recent

Categories

Tags

Algorithm 2
CG 11
DP 26
Data Structure 68
Frontend 1
Geometry 7
Graph Theory 28
Hash 6
Hexo 1
Language 3
Math 42
Note 37
Ray Tracing 8
Rendering 8
STL 11
String 44
Test 1

Links

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×