Cauphenuny's blog

20210206~07 考试总结

发表于 更新于 分类于 ，

这两天考的都是 USACO 的题

USACO 2019 December Contest, Platinum

pieaters

区间 dp ，注意枚举端点 i，j，k 的顺序，模拟一下就好了，如果使用了未更新的状态，就是错的

sorry for that i don’t have a chinese input method

Functions:

g(x, l, r) means we have the largest cow which can eat pos(x) , and it can only affect pies in [l, r]

f(x, l, r) means the weight summary that we can get from a sequence of cows, and it only affect pies in [l, r]

So we have the things below:

1
2
3
4
5
6
7
8
9
10
11
12
13
foreach cow_i
  foreach x in range[l_i, r_i]
  	g(x, l_i, r_i) = w_i;

foreach k in [1 -> n]
  foreach i in [k -> 1], j in [k -> n]
    g(k, i - 1, j) = max(~, g(k, i, j))
    g(k, i, j + 1) = max(~, g(k, i, j))

foreach i in [n -> 1]
  foreach j in [1 -> n]
    foreach k in range[i, j]
      f(i, j) = min(~, f(i, k - 1) + f(k + 1, j) + g(k, i, j))

完整代码：

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
//author: ycp | https://ycpedef.github.io
//#pragma GCC diagnostic error "-std=c++11"
//#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdarg>
#define debug(x) cerr << #x << " = " << x << endl
#define debugf(...) fprintf(stderr, __VA_ARGS__)
#define debugs(x) fputs(x"\n", stderr)
using namespace std;
template <class T> bool cmax(T &a, T b) { return b > a ? (a = b, 1) : 0; }
template <class T> bool cmin(T &a, T b) { return b < a ? (a = b, 1) : 0; }
template <class T> void read(T &a) {
    a = 0; char c = getchar(); int f = 0;
    while (!isdigit(c)) { f ^= c == '-',  c = getchar(); }
    while (isdigit(c)) { a = a * 10 + (c ^ 48),  c = getchar(); }
    a *= f ? -1 : 1;
}
struct Fastin {
    template <class T> Fastin& operator >> (T &x) {read(x); return *this;}
} fastin;

const int MAXN = 310;

int f[MAXN][MAXN], g[MAXN][MAXN][MAXN], ans;
int n, m;

int main() {
    freopen("pieaters.in", "r", stdin);
    freopen("pieaters.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1, w, l, r; i <= m; i++) {
        scanf("%d%d%d", &w, &l, &r);
        for (int x = l; x <= r; x++) {
            g[x][l][r] = w;
        }
    }
    for (int k = 1; k <= n; k++) {
        for (int i = k; i >= 1; i--) {
            for (int j = k; j <= n; j++) {
                g[k][i - 1][j] = max(g[k][i - 1][j], g[k][i][j]);
                g[k][i][j + 1] = max(g[k][i][j + 1], g[k][i][j]);
            }
        }
    }
    for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= n; j++) {
            for (int k = i; k <= j; k++) {
                f[i][j] = max(f[i][j], f[i][k - 1] + f[k + 1][j] + g[k][i][j]);
            }
            ans = max(ans, f[i][j]);
        }
    }
    printf("%d\n", ans);
    return 0;
}

snowcow

考虑将整棵树按 dfs 序拍扁，子树染色变为区间染色。

维护染色信息时保证不出现两个点 u,vu,v 满足 v∈subtree⁡uv\in\operatorname{subtree}u ，两个点同时出现颜色 cc 的染色信息。换言之，染色信息不能包含。

染色 vv 点时对某个点 uu 的答案有两种贡献，一种是 vv 点是 uu 点的子树，这时 uu 的答案加上 size⁡v\operatorname{size} v ，第二种则是 vv 染色时 uu 是其子节点，则 uu 的答案加上 size⁡u\operatorname{size}u

用两个 std::set 维护即可。

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
//author: ycp | https://ycpedef.github.io
//#pragma GCC diagnostic error "-std=c++11"
//#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdarg>
#include <set>
#define debug(x) cerr << #x << " = " << x << endl
#define debugf(...) fprintf(stderr, __VA_ARGS__)
#define debugs(x) fputs(x"\n", stderr)
using namespace std;
template <class T> bool cmax(T &a, T b) { return b > a ? (a = b, 1) : 0; }
template <class T> bool cmin(T &a, T b) { return b < a ? (a = b, 1) : 0; }
template <class T> void read(T &a) {
    a = 0; char c = getchar(); int f = 0;
    while (!isdigit(c)) { f ^= c == '-',  c = getchar(); }
    while (isdigit(c)) { a = a * 10 + (c ^ 48),  c = getchar(); }
    a *= f ? -1 : 1;
}
struct Fastin {
    template <class T> Fastin& operator >> (T &x) {read(x); return *this;}
} fastin;

#define int long long

const int MAXN = 2e5 + 10;

template <typename T, int n>
class binary_indexed_tree {
    T c[n + 10]; public:
    void add(int p, T v) { p++; for (; p <= n; p += p & -p) c[p] += v; }
    T query(int p) { p++; T v = 0; for (; p; p -= p & -p) v += c[p]; return v; }
    T range(int l, int r) { return (r >= l) ? query(r) - query(l - 1) : 0; }
};

int n, q;
int in[MAXN], out[MAXN], id[MAXN], siz[MAXN];
set <int> pos[MAXN]; // pos where color appears
binary_indexed_tree <int, MAXN> a, b;

class Graph {
    int tot = 0, head[MAXN] = {0}, dfx = 0;
    struct Edge {
        int to;
        int next;
    } e[MAXN << 1] = {0};
    public:
    void addEdge(int x, int y) {
        tot++;
        e[tot].to = y;
        e[tot].next = head[x];
        head[x] = tot;
    }
    int dfs(int u, int f) {
        //debugf("dfs(%lld, %lld)\n", u, f);
        in[u] = ++dfx;
        id[in[u]] = u;
        siz[u] = 1;
        for (int i = head[u], v; i; i = e[i].next) {
            v = e[i].to;
            if (v == f) continue;
            siz[u] += dfs(v, u);
        }
        out[u] = ++dfx;
        return siz[u];
    }
} G;

void add(int p, int d) {
    //debugf("add (%lld, %lld)\n", p, d);
    a.add(in[p], d), a.add(out[p] + 1, -d);
    //debugf("a.add(%lld, %lld), a.add(%lld, %lld)\n", in[p], d, out[p] + 1, -d);
    b.add(in[p], siz[p] * d);
    //debugf("b.add(%lld, %lld)\n", in[p], siz[p] * d);
    //b.add(in[p], (out[p] - in[p] + 1) / 2 * d);
}

int mid = 0;
void modify(int p, int c) {
    //debugf("\n[-----modify #%lld (%lld, %lld)-----]\n", ++mid, p, c);
    auto it = pos[c].upper_bound(in[p]);
    if (it != pos[c].begin() && out[id[*prev(it)]] >= out[p]) {
        //debugs("skip");
        return;
    }
    while (it != pos[c].end() && *it <= out[p]) {
        add(id[*it], -1);
        it = pos[c].erase(it);
    }
    add(p, 1);
    pos[c].insert(in[p]);
}

int qid = 0;
int query(int p) {
    //debugf("\n[-----query #%lld (%lld)-----]\n", ++qid, p);
    //debugf("ancestor: a.range(%lld, %lld): %lld\n", 1ll, in[p], a.range(1, in[p]));
    //debugf("subtree:  b.range(%lld, %lld): %lld\n", in[p], out[p], b.range(in[p], out[p]));
    return a.range(1, in[p]) * siz[p] + b.range(in[p] + 1, out[p] - 1);
}

signed main() {
    fastin >> n >> q;
    for (int i = 1, x, y; i < n; i++) {
        fastin >> x >> y;
        G.addEdge(x, y);
        G.addEdge(y, x);
    }
    G.dfs(1, 0);
    //for (int i = 1; i <= n; i++) {
    //    debugf("[%lld: %lld/%lld]\n", i, in[i], out[i]);
    //}
    for (int i = 1, op, x, c; i <= q; i++) {
        fastin >> op;
        if (op == 1) {
            fastin >> x >> c;
            modify(x, c);
        } else {
            fastin >> x;
            cout << query(x) << endl;
        }
    }
    return 0;
}

treedepth

总路径减去不合法的路径条数。

不合法的可以通过卷积求出。

USACO 2019 February Contest, Platinum