ZJOI 2015 大赏

2020-04-21

做这套题纯粹是为了好玩… 结果惨遭吊打 = =

「ZJOI2015」幻想乡战略游戏

题目链接

解题思路

点分树是不可能的, 这辈子不可能写的. 数据结构又不会, 只能写写模板这样子.

考虑重链剖分.

不妨钦定 $1$ 为根. 记 $s_u$ 为 $u$ 子树内 $d$ 值之和. 对于一条边 $(u, v)$, 如果选择 $v$ 比 $u$ 更优, 也就是最终花费的变化量为负, 即

因此有一个在线段树上二分 DFS 序, 找出最优点 $v$ 的做法.

同时记 $\text{dist}(u)$ 为点 $u$ 到根节点的距离, 那么最小花费可以表示为

前两项很好维护, 记录 $d_v$ 和 $d_v \cdot \text{dist}(v)$ 的和即可.

注意到 $u$ 的子树内的点, 同 $u$ 的 LCA 一定是 $u$, 而其他点和 $u$ 的 LCA 一定在 $u$ 到根的路径上.

考虑使用重链剖分统计这些可能成为 LCA 的点对答案的贡献.

每次 $d_v$ 改变时, 从 $v$ 到根节点依次修改, 将变化量 $e$ 加入子树内包含 $v$ 的节点上. 设这些节点为 $u$, $u$ 的父亲节点为 $f$, 此时对答案贡献的变化即为 $e \cdot \big( \text{dist}(u) - \text{dist}(f) \big)$, 即 $u$ 到 $f$ 的边贡献的变化量. 用线段树维护就好了.

查询直接对统计的这些贡献求和即可.

时间复杂度 $O(n + q \log ^ 2 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
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
150
151
152
153
154
155
156
157
158
159
160
// LOJ #2135
// DeP
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

typedef long long LL;
const int MAXN = 1e5 + 5;

int n, q;
LL A[MAXN], dist[MAXN];
int dfn[MAXN], rnk[MAXN];

namespace Graph {
    struct Edge { int nxt, to, w; } edges[MAXN << 1];
    int head[MAXN], eidx;

    inline void init() { memset(head, -1, sizeof head), eidx = 1; }
    inline void AddEdge(int from, int to, int w) {
        edges[++eidx] = (Edge){ head[from], to, w }, head[from] = eidx;
    }
}

namespace SGT {
#define lc (nd<<1)
#define rc (nd<<1|1)
    LL s[MAXN << 2], w[MAXN << 2], datSum[MAXN << 2], tagAdd[MAXN << 2];

    inline void maintain(int nd) {
        s[nd] = max(s[lc], s[rc]);
        datSum[nd] = datSum[lc] + datSum[rc];
    }

    inline void pushAdd(const int& nd, const int& v) {
        s[nd] += v, tagAdd[nd] += v, datSum[nd] += w[nd] * v;
    }
    inline void pushdown(int nd) {
        if (tagAdd[nd] != 0)
            pushAdd(lc, tagAdd[nd]), pushAdd(rc, tagAdd[nd]), tagAdd[nd] = 0;
    }

    void build(int nd, int L, int R) {
        if (L == R) return void( w[nd] = A[L] );
        int Mid = (L + R) / 2;
        build(lc, L, Mid), build(rc, Mid+1, R);
        w[nd] = w[lc] + w[rc];
    }

    void Mdy(int nd, int L, int R, const int& opL, const int& opR, const int& d) {
        if (opL <= L && R <= opR) return pushAdd(nd, d);
        int Mid = (L + R) / 2;
        pushdown(nd);
        if (opL <= Mid) Mdy(lc, L, Mid, opL, opR, d);
        if (opR > Mid) Mdy(rc, Mid+1, R, opL, opR, d);
        maintain(nd);
    }

    LL Qry(int nd, int L, int R, const int& opL, const int& opR) {
        if (opL <= L && R <= opR) return datSum[nd];
        int Mid = (L + R) / 2;
        pushdown(nd);
        if (opR <= Mid) return Qry(lc, L, Mid, opL, opR);
        if (opL > Mid) return Qry(rc, Mid+1, R, opL, opR);
        return Qry(lc, L, Mid, opL, opR) + Qry(rc, Mid+1, R, opL, opR);
    }

    int Qry() {
        int Mid, nd = 1, L = 1, R = n;
        while (L < R) {
            Mid = (L + R) / 2, pushdown(nd);
            if (2 * s[rc] >= s[1]) nd = rc, L = Mid + 1;
            else nd = lc, R = Mid;
        }
        return rnk[L];
    }
#undef lc
#undef rc
}

namespace HLD {
    using namespace Graph;
    int size[MAXN], son[MAXN], pre[MAXN], topfa[MAXN], clk;

    void dfs1(int u, int fa) {
        pre[u] = fa, son[u] = -1, size[u] = 1;
        for (int v, i = head[u]; ~i; i = edges[i].nxt) {
            if ((v = edges[i].to) == fa) continue;
            dist[v] = dist[u] + edges[i].w;
            dfs1(v, u), size[u] += size[v];
            if (son[u] == -1 || size[v] > size[son[u]]) son[u] = v;
        }
    }

    void dfs2(int u, int top) {
        topfa[u] = top, rnk[dfn[u] = ++clk] = u;
        A[clk] = dist[u] - dist[pre[u]];
        if (~son[u]) dfs2(son[u], top);
        for (int v, i = head[u]; ~i; i = edges[i].nxt)
            if ((v = edges[i].to) != pre[u] && v != son[u]) dfs2(v, v);
    }

    inline void solve(int rt = 1) { dfs1(rt, 0), dfs2(rt, rt); }

    void Mdy(const int& p, const int& d) {
        for (int u = p; u > 0; u = pre[topfa[u]])
            SGT::Mdy(1, 1, n, dfn[topfa[u]], dfn[u], d);
    }

    LL Qry(const int& p) {
        LL ret = 0;
        for (int u = p; u > 0; u = pre[topfa[u]])
            ret += SGT::Qry(1, 1, n, dfn[topfa[u]], dfn[u]);
        return ret;
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // init
    Graph::init();
    // input
    read(n), read(q);
    for (int u, v, w, i = 1; i < n; ++i) {
        read(u), read(v), read(w);
        Graph::AddEdge(u, v, w), Graph::AddEdge(v, u, w);
    }
    // solve
    HLD::solve(1), SGT::build(1, 1, n);
    // output
    LL sumd = 0, sumdd = 0;
    for (int rt, u, e; q; --q) {
       read(u), read(e);
       sumd += e, sumdd += e * dist[u];
       HLD::Mdy(u, e), rt = SGT::Qry();
       LL ret = sumdd + sumd * dist[rt] - 2 * HLD::Qry(rt);
       printf("%lld\n", ret);
    }
    return 0;
}

「ZJOI2015」地震后的幻想乡

题目链接

解题思路

套 Min/Max 容斥结果越想越偏是屑…

这里是一个平民做法.

考虑如何运用提示给出的公式. 模拟 Kruskal 的过程, 假定第 $k$ 次加入边后恰好得到一棵生成树, 那么对答案的贡献为 $\frac{k}{m + 1}$, 同时概率可以用合法方案数除以总方案数得出.

注意到一棵生成树的权值是对所有边取 $\max$. 那么对于一个连通图, 在该连通图恰好连通时内部边权的最大值, 和生成树的边权最大值是相同的, 因此可以从图的连通上考虑.

但是在恰好第 $k$ 次加入边得到连通图的情况不好统计, 做一步转化: 恰好加入第 $k$ 条边后图连通的方案数, 为: 加入这条边前不连通的方案数 - 加入这条边后不连通的方案数.

考虑用状压 DP 来求这个东西. 设 $f(S, i)$ 为当前选择的点集为 $S$, 已经使用了 $i$ 条边, 点集不连通的方案数.

记点集的全集为 $U$, $d(S)$ 为同点集 $S$ 相关的边的个数, 那么答案为

化简, 得

同时, 点集连通的方案数为 $\binom{d(S)}{i} - f(S, i)$, 其中 $d(S)$ 可以通过枚举子集算出, 而点集连通时的方案数在转移 $f$ 时会用到.

点集不连通的情况可看作由一个连通非空子集上加边, 并保证新加入的点中存在不连通情况得出的. 因此有

枚举子集转移即可. 注意转移时, 需要钦定 $S$ 中某个点, 使得 $T$ 必须包含该点, 否则会重复计算一些情况. 实现时可使用 lowbit.

至于为什么钦点一个点是对的, 可参看 command_block 的题解

时间复杂度大概是 $O(m3 ^ 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
// LOJ #2136
// DeP
#include <cstdio>
using namespace std;

typedef long long LL;
const int MAXN = 10, MAXM = MAXN * (MAXN - 1) / 2;

int n, m;
int c[1 << MAXN], d[1 << MAXN];
LL f[1 << MAXN][MAXM], C[MAXM][MAXM];

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    scanf("%d%d", &n, &m);
    for (int u, v, i = 0; i < m; ++i)
        scanf("%d%d", &u, &v), ++c[1 << (u-1) | 1 << (v-1)];
    // predone
    for (int i = C[0][0] = 1; i <= m; ++i)
        for (int j = C[i][0] = 1; j <= i; ++j)
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    int U = (1 << n) - 1;
    for (int s = 1; s <= U; ++s)
        for (int t = s; t; t = (t-1) & s) d[s] += c[t];
    // solve
    for (int s = 1; s <= U; ++s) for (int i = 0; i <= d[s]; ++i)
        for (int t = (s - 1) & s; t; t = (t-1) & s) if (t & (s & -s))
            for (int j = 0; j <= i && j <= d[t]; ++j)
                f[s][i] += (C[d[t]][j] - f[t][j]) * C[d[s ^ t]][i - j];
    // output
    double ans = 0.0;
    for (int k = 0; k < m; ++k) ans += f[U][k] / double(C[d[U]][k]);
    printf("%.6lf\n", ans / (m + 1.0));
    return 0;
}

「ZJOI2015」诸神眷顾的幻想乡

题目链接

解题思路

考虑广义 SAM, 以及不要读错题, 这题没了.

显然本质不同子串个数可以通过 SAM 来求.

注意到一个重要的条件: “一个空地相邻的空地数量不超过 $20$ 个”, 即叶子个数不超过 $20$. 那么从每个叶子开始, 遍历整棵树, 同时建广义 SAM 即可. 本质上大概是在 Trie 上建 SAM?

设叶子个数为 $L$, 那么时间复杂度为 $O(nL)$.

代码实现

> 点击显示 / 隐藏 
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
// LOJ #2137
// DeP
#include <cctype>
#include <cstdio>
#include <cstring>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

typedef long long LL;
const int MAXN = 1e5 + 5;

int n, C; LL ans;
int A[MAXN], deg[MAXN];

namespace SAM {
    const int MAXN = ::MAXN * 40, SIGMA = 10;
    int ch[MAXN][SIGMA], lnk[MAXN], len[MAXN], nidx;

    inline void init() { nidx = 1; }

    inline int Ins(int val, int lst) {
        int p = lst;
        if (ch[p][val] && len[ch[p][val]] == len[p] + 1)
            return ch[p][val];
        int nd = ++nidx, flag = false;
        len[nd] = len[lst] + 1;
        while (p && !ch[p][val]) ch[p][val] = nd, p = lnk[p];
        if (!p) lnk[nd] = 1;
        else {
            int q = ch[p][val];
            if (len[q] == len[p] + 1) lnk[nd] = q;
            else {
                int nxt = ++nidx;
                if (p == lst) flag = true;
                len[nxt] = len[p] + 1, lnk[nxt] = lnk[q];
                memcpy(ch[nxt], ch[q], sizeof ch[nxt]);
                while (p && ch[p][val] == q) ch[p][val] = nxt, p = lnk[p];
                lnk[nd] = lnk[q] = nxt;
                if (flag) return nxt;
            }
        }
        ans += len[nd] - len[lnk[nd]];
        return nd;
    }
}

namespace Graph {
    struct Edge { int nxt, to; } edges[MAXN << 1];
    int head[MAXN], eidx;

    inline void init() { memset(head, -1, sizeof head), eidx = 1; }
    inline void AddEdge(int from, int to) {
        edges[++eidx] = (Edge){ head[from], to }, head[from] = eidx;
    }

    void dfs(int u, int fa, int lst) {
        int nd = SAM::Ins(A[u], lst);
        for (int v, i = head[u]; ~i; i = edges[i].nxt)
            if ((v = edges[i].to) != fa) dfs(v, u, nd);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // init
    SAM::init(), Graph::init();
    // input
    read(n), read(C);
    for (int i = 1; i <= n; ++i) read(A[i]);
    for (int u, v, i = 1; i < n; ++i) {
        read(u), read(v), ++deg[u], ++deg[v];
        Graph::AddEdge(u, v), Graph::AddEdge(v, u);
    }
    // solve
    for (int u = 1; u <= n; ++u)
        if (deg[u] == 1) Graph::dfs(u, 0, 1);
    // output
    printf("%lld\n", ans);
    return 0;
}

「ZJOI2015」黑客技术

题目链接

解题思路

玩一个上午结果不如随缘乱敲分高是屑…

奥妙啊.

「ZJOI2015」醉醺醺的幻想乡

题目链接

解题思路

很厉害的一道题, 以及一个很厉害的题解: http://c-sunshine.blog.uoj.ac/blog/563.

如果单位酿酒量 $x$ 只能是整数, 那么就很好解决了: 将费用差分, 根据差分后的结果将原有边拆为 $c_i$, 也就是容量条边.

但是这里的 $x$ 可以是非负实数, 且最后的结果要求没有精度误差. 因此要使用上述题解的做法. 大体是对费用求导, 然后再积分计算…

注意到每次跑网络流时得到的是一个一次函数, 容易在残量网络中得出斜率 $k$ 以及截距 $b$, 通过斜截式就比较容易理解代码中的式子.

以及上述题解代码将半平面上的点和线都写为 pair<frac, frac>, 我的代码将两者区分开了, 这样就会清晰许多.

记网络流建图时点数为 $V$, 边数为 $E$, 时间复杂度为 $O(n V ^ 2 E)$.

代码实现

> 点击显示 / 隐藏 
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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
// LOJ #2138
// DeP
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

const int MAXN = 1e2 + 5, MAXV = 2 * MAXN;
const double eeps = 1e-9, EPS = 1e-6, INFD = 1e9;

inline LL gcd(LL a, LL b) { return !b? a: gcd(b, a % b); }

inline int dcmp(const double& p) {
    return (fabs(p) < eeps)? 0: (p < 0? -1: 1);
}

struct Frac {
    LL x, y;
    Frac(LL _x = 0, LL _y = 1) {
        if (_x == 0) x = 0, y = 1;
        else x = _x / gcd(_x, _y), y = _y / gcd(_x, _y);
    }

    Frac operator + (const Frac& rhs) const {
        return Frac(x * rhs.y + y * rhs.x, y * rhs.y);
    }
    Frac operator - (const Frac& rhs) const {
        return Frac(x * rhs.y - y * rhs.x, y * rhs.y);
    }
    Frac operator * (const Frac& rhs) const { return Frac(x * rhs.x, y * rhs.y); }
    Frac operator / (const Frac& rhs) const { return Frac(x * rhs.y, y * rhs.x); }
    Frac operator += (const Frac& rhs) { return *this = *this + rhs; }

    inline double val() const { return 1.0 * x / y; }
};

struct Line {
    Frac k, b; // y = kx + b;
    Line(Frac _k, Frac _b): k(_k), b(_b) { }
    bool operator == (const Line& rhs) const {
        return k.x == rhs.k.x && k.y == rhs.k.y && b.x == rhs.b.x && b.y == rhs.b.y;
    }
};

struct Point {
    Frac x, y;
    Point(Frac _x, Frac _y): x(_x), y(_y) { }
};

int n, m, S, T;
int M[MAXN][MAXN];
int A[MAXN], B[MAXN], C[MAXN], D[MAXN];

vector<Point> P;

namespace Graph {
    struct Edge {
        int to; double cap, flow;
        Edge(int _v, double _c, double _f): to(_v), cap(_c), flow(_f) { }
    };
    vector<Edge> edges;
    vector<int> G[MAXV];

    inline void init(int _n) {
        edges.clear();
        for (int i = 0; i < _n; ++i) G[i].clear();
    }

    inline void AddEdge(int from, int to, double c) {
        edges.push_back(Edge(to, c, 0.0));
        edges.push_back(Edge(from, 0.0, 0.0));
        int eidx = edges.size() - 1;
        G[from].push_back(eidx - 1), G[to].push_back(eidx);
    }
}

namespace Dinic {
    using namespace Graph;
    size_t cur[MAXV];
    int depth[MAXV], vis[MAXV], Time;

    bool BFS() {
        queue<int> Q;
        Q.push(S), vis[S] = ++Time, depth[S] = 0;
        while (!Q.empty()) {
            int u = Q.front(); Q.pop();
            for (size_t i = 0; i < G[u].size(); ++i) {
                const Edge& e = edges[G[u][i]];
                if (vis[e.to] != Time && dcmp(e.cap - e.flow) > 0)
                    vis[e.to] = Time, depth[e.to] = depth[u] + 1, Q.push(e.to);
            }
        }
        return vis[T] == Time;
    }

    double DFS(int u, double a) {
        if (u == T || !dcmp(a)) return a;
        double f, flow = 0.0;
        for (size_t& i = cur[u]; i < G[u].size(); ++i) {
            Edge& e = edges[G[u][i]];
            if (depth[e.to] == depth[u] + 1 &&
                    dcmp(f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
                flow += f, a -= f, e.flow += f, edges[G[u][i] ^ 1].flow -= f;
                if (!dcmp(a)) break;
            }
        }
        return flow;
    }

    inline double Maxflow() {
        double flow = 0.0;
        while (BFS())
            memset(cur, 0, sizeof cur), flow += DFS(S, INFD);
        return flow;
    }
}

Line calc(const double& limit) {
    // init
    Graph::init(T + 1);
    // build graph
    for (int i = 1; i <= n; ++i) {
        if (A[i] == 0) {
            if (B[i] <= limit) Graph::AddEdge(S, i, C[i]);
        } else if (B[i] <= limit) {
            double c = (limit - B[i]) / (2.0 * A[i]);
            Graph::AddEdge(S, i, min(1.0 * C[i], c));
        }
    }
    for (int j = 1; j <= m; ++j)
        Graph::AddEdge(n + j, T, D[j]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (M[i][j]) Graph::AddEdge(i, n + j, INFD);
    // check
    Dinic::Maxflow();
    Frac k = 0, b = 0;
    for (int i = 1; i <= n; ++i) {
        if (Dinic::vis[i] == Dinic::Time) continue;
        if (A[i] == 0) {
            if (B[i] <= limit) b += C[i];
        } else if (B[i] <= limit) {
            if (2.0 * A[i] * C[i] + B[i] > limit)
                k += Frac(1, 2 * A[i]), b += Frac(-B[i], 2 * A[i]);
            else b += C[i];
        }
    }
    for (int j = 1; j <= m; ++j)
        if (Dinic::vis[n + j] == Dinic::Time) b += D[j];
    return Line(k, b);
}

void Divide(const Line& L, const Line& R) {
    if (L == R) return;
    Frac px = (L.b - R.b) / (R.k - L.k);
    Line mL = calc(px.val() - EPS), mR = calc(px.val() + EPS);
    if (L == mL)
        return void( P.push_back(Point(px, px * L.k + L.b)) );
    Divide(L, mL), Divide(mR, R);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d%d%d", A + i, B + i, C + i);
    for (int j = 1; j <= m; ++j) scanf("%d", D + j);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) scanf("%d", M[i] + j);
    // solve 1
    S = 0, T = n + m + 1;
    Graph::init(T + 1);
    for (int i = 1; i <= n; ++i) Graph::AddEdge(S, i, C[i]);
    for (int j = 1; j <= m; ++j) Graph::AddEdge(n + j, T, D[j]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (M[i][j]) Graph::AddEdge(i, n + j, INFD);
    printf("%0.lf\n", Dinic::Maxflow());
    // solve 2
    for (int x = 1; x <= 4; ++x) {
        double L = x - 1, R = (x <= 3)? x: INFD;
        Line l1 = calc(L + EPS), l2 = calc(R - EPS);
        P.push_back(Point(Frac(L), l1.k * Frac(L) + l1.b));
        Divide(l1, l2);
        P.push_back(Point(Frac(R), l2.k * Frac(R) + l2.b));
    }
    P.pop_back();
    Frac ans = 0;
    for (size_t i = 1; i < P.size(); ++i)
        ans += (P[i].y + P[i - 1].y) * (P[i].x - P[i - 1].x);
    const Point& p = P.back();
    ans = p.x * p.y - Frac(1, 2) * ans;
    printf("%lld/%lld\n", ans.x, ans.y);
    return 0;
}

「ZJOI2015」幻想乡 Wi-Fi 搭建计划

题目链接

解题思路

对着费用流建半天图还调半天结果发现假了是屑…

首先第一问容易有在 $O(nm)$ 的时间复杂度内计算的方法, 下文不再考虑覆盖不到的景点.

先考虑架设点只在一边的情况. 有一个结论: 将架设点和景点分别按照 $x$ 坐标排序, 那么在最优的方案下, 选择的架设点覆盖到的景点一定是排序后连续的一段.

证明大概是利用长方形宽为 $R$, 同时覆盖半径为 $R$, 恰好不能构造出反例吧… 不大会证.png

有了这个条件, 直接记录选择到第几个架设点 DP 即可.

那么架设点在两侧的情况, 直接在 DP 时多记录一维, 即在另一侧选择到第几个架设点, 对于一个景点分别考虑在两侧架设的情况.

具体地, 设 $f(i, j, k)$ 表示已经覆盖到第 $i$ 个景点, 两侧架设点分别选择到 $j$, $k$. 转移比较显然, 看代码理解就好了.

时间复杂度 $O(nm^3)$, 但是跑不满.

代码实现

> 点击显示 / 隐藏 
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
// LOJ #2139
// DeP
#include <cstdio>
#include <climits>
#include <cstring>
#include <algorithm>
using namespace std;

template<typename T> inline void ckmin(T& a, const T& b) { if (a > b) a = b; }

typedef long long LL;
const int MAXN = 1e2 + 5;

namespace Geo {
    struct Vector {
        int x, y;
        Vector(int _x = 0, int _y = 0): x(_x), y(_y) { }
        Vector operator - (const Vector& rhs) const {
            return Vector(x - rhs.x, y - rhs.y);
        }
    };
    typedef Vector Point;

    bool operator < (const Point& A, const Point& B) {
        return (A.x < B.x) || (A.x == B.x && A.y < B.y);
    }

    inline LL Dot(const Vector& A, const Vector& B) {
        return 1LL * A.x * B.x + 1LL * A.y * B.y;
    }
    inline LL Length2(const Vector& A) { return Dot(A, A); }
    inline LL Dist2(const Point& p1, const Point& p2) { return Length2(p1 - p2); }
}
using namespace Geo;

struct Item {
    Point p; int w;
    bool operator < (const Item& rhs) const { return p < rhs.p; }
} U[MAXN], D[MAXN];

int n, m; LL R;
Point P[MAXN];
int f[MAXN][MAXN][MAXN];

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    scanf("%d%d%lld", &n, &m, &R), R *= R;
    for (int x, y, i = 1; i <= n; ++i)
        scanf("%d%d", &x, &y), P[i] = Point(x, y);
    int nU = 0, nD = 0;
    for (int x, y, c, i = 1; i <= m; ++i) {
        scanf("%d%d%d", &x, &y, &c);
        if (y < 0) D[++nD] = (Item){ Point(x, y), c };
        else U[++nU] = (Item){ Point(x, y), c };
    }
    // solve
    int nP = 0;
    for (int i = 1; i <= n; ++i) {
        bool flag = false;
        for (int j = 1; !flag && j <= nD; ++j)
            if (Dist2(P[i], D[j].p) <= R) flag = true;
        for (int j = 1; !flag && j <= nU; ++j)
            if (Dist2(P[i], U[j].p) <= R) flag = true;
        if (flag) P[++nP] = P[i];
    }
    sort(P + 1, P + nP + 1);
    sort(D + 1, D + nD + 1), sort(U + 1, U + nU + 1);
    memset(f, 0x3f, sizeof f);
    f[0][0][0] = 0;
    for (int i = 1; i <= nP; ++i)
        for (int j = 0; j <= nU; ++j) for (int k = 0; k <= nD; ++k) {
            if (j > 0 && Dist2(P[i], U[j].p) <= R) ckmin(f[i][j][k], f[i - 1][j][k]);
            if (k > 0 && Dist2(P[i], D[k].p) <= R) ckmin(f[i][j][k], f[i - 1][j][k]);
            for (int l = j + 1; l <= nU; ++l)
                if (Dist2(P[i], U[l].p) <= R) ckmin(f[i][l][k], f[i - 1][j][k] + U[l].w);
            for (int l = k + 1; l <= nD; ++l)
                if (Dist2(P[i], D[l].p) <= R) ckmin(f[i][j][l], f[i - 1][j][k] + D[l].w);
        }
    int Mn = INT_MAX;
    for (int j = 0; j <= nU; ++j)
        for (int k = 0; k <= nD; ++k) ckmin(Mn, f[nP][j][k]);
    // output
    printf("%d\n%d\n", nP, Mn);
    return 0;
}
© 2019-2023 DepletedPrism's Blog - Powered by Hexo - Theme Chan