Asusetic
0%

2021.06.13模拟赛

发表于 分类于 Valine：
本文字数： 400 阅读时长 ≈ 1 分钟

忘了写了，补一下

2021.06.13 模拟赛

T1 理想路径

理想路径

找路径直接贪心找是没问题的，但是有问题的是查询太大了

所以考虑二进制拆分一下记录倍增点，空间比较离谱，需要用 short 卡一波

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
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int N = 2005;
struct Graph {
    struct Node {
        int v, nxt;
    } edge[N * 3];
    int head[N];
    int ecnt;
    void add(int u, int v) {
        edge[++ecnt].v = v;
        edge[ecnt].nxt = head[u];
        head[u]        = ecnt;
    }
} G;
bool vis[N], inq[N];
short int fa[N][N][12], dis[N][N];
bool dfs(int x, int _fa, int dep, const int &now) {
    if (vis[x]) {
        return inq[x];
    }
    vis[x] = inq[x] = 1;
    fa[now][x][0]   = _fa;
    dis[now][x]     = dep;
    for (int i = 1; i <= 11; i++) {
        fa[now][x][i] = fa[now][fa[now][x][i - 1]][i - 1];
    }
    for (int i = G.head[x]; i; i = G.edge[i].nxt) {
        int v = G.edge[i].v;
        if (dfs(v, x, dep + 1, now)) {
            inq[x] = 0;
            return 1;
        }
    }
    inq[x] = 0;
    return 0;
}
int n, m, q;
bool g[N][N];
int main() {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u][v] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = n; j >= 1; j--) {
            if (g[i][j]) {
                G.add(i, j);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        memset(vis, 0, sizeof(vis));
        memset(dis[i], -1, sizeof(dis[i]));
        dfs(i, 0, 0, i);
    }
    while (q--) {
        int s, t, k;
        scanf("%d%d%d", &s, &t, &k);
        if (dis[s][t] - k + 1 < 0) {
            printf("-1\n");
            continue;
        }
        k = dis[s][t] - k + 1;
        for (int i = 11; ~i; i--) {
            if ((k >> i) & 1) {
                t = fa[s][t][i];
            }
        }
        printf("%d\n", t);
    }
}

T2 旅游观光

旅游观光

缩点板子题啊…

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
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
using namespace std;
const int N = 3e4 + 5;
int n, m;
struct Graph {
    vector<int> edge[N];
    void add(int u, int v) {
        edge[u].emplace_back(v);
    }
} G, G1;
int c[N], v[N];
set<pair<int, int>> g;
namespace Tarjan {
int dfn[N], low[N], dfnid, st[N], top;
int scc[N], scc_cnt, siz[N];
bool vis[N];
void Tarjan(int x) {
    dfn[x] = low[x] = ++dfnid;
    st[++top]       = x;
    vis[x]          = 1;
    for (auto v : G.edge[x]) {
        if (!dfn[v]) {
            Tarjan(v);
            low[x] = min(low[x], low[v]);
        } else if (vis[v]) {
            low[x] = min(low[x], dfn[v]);
        }
    }
    if (low[x] == dfn[x]) {
        scc_cnt++;
        int now = 0;
        do {
            now      = st[top];
            vis[now] = 0;
            scc[now] = scc_cnt;
            siz[scc_cnt] += v[now];
            top--;
        } while (now != x);
    }
}
} // namespace Tarjan
int in[N], ans[N];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> c[i] >> v[i];
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        G.add(u, v);
    }
    for (int i = 1; i <= n; i++) {
        if (!Tarjan::dfn[i]) {
            Tarjan::Tarjan(i);
        }
    }
    using Tarjan::scc;
    for (int i = 1; i <= n; i++) {
        for (auto v : G.edge[i]) {
            if (scc[v] != scc[i] && !g.count(make_pair(scc[i], scc[v]))) {
                g.insert(make_pair(scc[i], scc[v]));
            }
        }
        G.edge[i].clear();
    }
    for (auto p : g) {
        G.add(p.first, p.second);
        in[p.second]++;
    }
    queue<int> q;
    for (int i = 1; i <= Tarjan::scc_cnt; i++) {
        if (!in[i]) {
            q.push(i);
        }
    }
    vector<int> topo;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        topo.push_back(x);
        for (auto v : G.edge[x]) {
            --in[v];
            if (!in[v]) {
                q.push(v);
            }
        }
    }
    reverse(topo.begin(), topo.end());
    for (auto x : topo) {
        ans[x] += Tarjan::siz[x];
        int tmp = 0;
        for (auto v : G.edge[x]) {
            tmp = max(tmp, ans[v]);
        }
        ans[x] += tmp;
    }
    double res = 0;
    for (int i = 1; i <= n; i++) {
        res = max(res, 1.0 * ans[Tarjan::scc[i]] / (1.0 * c[i]));
        // printf("%d %d\n", i, ans[Tarjan::scc[i]]);
    }
    printf("%.2lf", res);
}

T3 抵抗白宇（雾）

抵抗白蚁

虚树板子，同SDOI消耗战

数据范围看起来很鬼但其实时间开大了十倍

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
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
namespace IO {
template <typename T> void read(T &x) {
    x     = 0;
    int f = 1;
    static char ch;
    while (!isdigit(ch = getchar())) {
        if (ch == '-')
            f = -1;
    }
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        x = x * 10 + ch - '0';
    x *= f;
}
template <typename T, typename... Args> void read(T &x, Args &... args) {
    read(x);
    read(args...);
}
} // namespace IO
using IO::read;
typedef long long ll;
const int N = 500004;
struct Graph {
    struct Node {
        int v, w, nxt;
    };
    vector<Node> edge;
    vector<int> head;
    void add(int u, int v, int w) {
        edge.emplace_back(Node{v, w, head[u]});
        head[u] = edge.size() - 1;
    }
} Tr;
struct Graph_QAQ {
    struct Edge {
        int v;
        int w, nxt;
    } edge[N * 2];
    int head[N * 2], ecnt;
    void add(int u, int v, int w) {
        edge[++ecnt].v = v;
        edge[ecnt].w   = w;
        edge[ecnt].nxt = head[u];
        head[u]        = ecnt;
    }
} vTr;

int n, m;
int tim, id[N], dep[N];
int fa[N][20];
ll mmin[N][20];
void dfs1(int x, int _fa) {
    dep[x]   = dep[_fa] + 1;
    id[x]    = ++tim;
    fa[x][0] = _fa;
    for (int i = 1; i <= 19; i++) {
        fa[x][i]   = fa[fa[x][i - 1]][i - 1];
        mmin[x][i] = min(mmin[x][i - 1], mmin[fa[x][i - 1]][i - 1]);
    }
    for (int i = Tr.head[x]; ~i; i = Tr.edge[i].nxt) {
        auto &e = Tr.edge[i];
        int v   = e.v;
        if (v == _fa)
            continue;
        fa[v][0]   = x;
        mmin[v][0] = e.w;
        dfs1(v, x);
    }
}
int LCA(int x, int y) {
    if (dep[x] < dep[y]) {
        swap(x, y);
    }
    for (int i = 19; i >= 0; i--) {
        if (dep[fa[x][i]] >= dep[y]) {
            x = fa[x][i];
        }
    }
    if (x == y)
        return x;
    for (int i = 19; i >= 0; i--) {
        if (fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}
int querymin(int x, int y) {
    int t  = dep[x] - dep[y];
    ll res = (1ll << 62);
    for (int i = 0; i <= 19; ++i) {
        if (t >> i & 1) {
            res = min(res, mmin[x][i]);
            x   = fa[x][i];
        }
    }
    return res;
}
int a[N];
int st[N], top, lca[N];
bool mark[N];
void build_tr(int k) {
    sort(a + 1, a + k + 1, [&](const int &A, const int &B) -> bool {
        return id[A] < id[B];
    });
    top       = 0;
    st[++top] = 1;
    a[0]      = 1;
    for (int i = 1; i <= k; i++) {
        lca[i]         = LCA(a[i], a[i - 1]);
        vTr.head[a[i]] = vTr.head[lca[i]] = -1;
        mark[lca[i]]                      = 0;
    }
    for (int i = 1; i <= k; i++) {
        mark[a[i]] = 1;
    }
    for (int i = 1; i <= k; ++i) {
        while (top > 1 && dep[lca[i]] < dep[st[top - 1]]) {
            vTr.add(st[top - 1], st[top], querymin(st[top], st[top - 1]));
            --top;
        }
        if (lca[i] != st[top]) {
            vTr.add(lca[i], st[top], querymin(st[top], lca[i]));
            --top;
            if (lca[i] != st[top]) {
                st[++top] = lca[i];
            }
        }
        if (a[i] != st[top]) {
            st[++top] = a[i];
        };
    }
    while (top > 1) {
        vTr.add(st[top - 1], st[top], querymin(st[top], st[top - 1]));
        top--;
    }
}
ll dp[N];
void dfs2(int x) {
    dp[x] = 0;
    for (int i = vTr.head[x]; ~i; i = vTr.edge[i].nxt) {
        auto &e = vTr.edge[i];
        dfs2(e.v);
        dp[x] += mark[e.v] ? e.w : min(dp[e.v], 1ll * e.w);
    }
}
int main() {
    read(n);
    Tr.head.resize(n + 1, -1);
    for (int i = 1; i < n; i++) {
        int a, b, c;
        read(a, b, c);
        Tr.add(a, b, c);
        Tr.add(b, a, c);
    }
    dfs1(1, 0);
    read(m);
    while (m--) {
        int k;
        vTr.ecnt = 0;
        read(k);
        for (int i = 1; i <= k; i++) {
            read(a[i]);
        }
        build_tr(k);
        dfs2(1);
        // cout << "U" << endl;
        printf("%lld\n", dp[1]);
    }
}

T4 兔兔与蛋蛋的游戏

原题 NOI2011 兔兔与蛋蛋的游戏

挺妙的题

第一个性质是空白点一定没办法转回来，因为转回来意味着它移动了偶数次，而这一次的黑白手是互换的，所以不可能做到

那么空白点的移动就没有环，同时因为每次都是黑白交替的，可以理解为在一个二分图上增广的过程

二分图上博弈如果先手落入最大匹配中的点中则先手必败，因为后手仅需走最大匹配即可

那么如果一个点是所有最大匹配的必选点则必胜

所以删掉这个点如果它的匹配点还能找到别的匹配说明存在一个最大匹配不包含他

兔兔犯错意味着当前是必胜的走完蛋蛋是必胜的

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
#include <array>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int N = 45, K = 1005;
int n, m;
struct Graph {
    vector<int> edge[N * N];
    void add(int u, int v) {
        edge[u].emplace_back(v);
    }
    void add_two(int u, int v) {
        add(u, v);
        add(v, u);
    }
} G;
const array<int, 4> dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
array<char, N> s;
array<array<int, N>, N> mp;
array<bool, N * N> ban;
array<int, N * N> vis, link;
array<bool, 2 * K> win;
array<int, K> ans;
int vistim;
int sx, sy;
bool match(int x, const Graph &G) {
    if (ban[x]) {
        return false;
    }
    for (auto v : G.edge[x]) {
        if (vis[v] == vistim || ban[v]) {
            continue;
        }
        vis[v] = vistim;
        if (!link[v] || match(link[v], G)) {
            link[v] = x;
            link[x] = v;
            return true;
        }
    }
    return false;
}
int id(int x, int y) {
    return (x - 1) * m + y;
}
bool check_bound(int x, int y) {
    return (x >= 1 && x <= n && y >= 1 && y <= m);
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> (s.data() + 1);
        for (int j = 1; j <= m; j++) {
            if (s[j] == 'O') {
                mp[i][j] = 0;
            } else if (s[j] == 'X') {
                mp[i][j] = 1;
            } else {
                mp[i][j] = 1;
                sx       = i;
                sy       = j;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!mp[i][j]) {
                continue;
            }
            for (int k = 0; k < 4; k++) {
                int nx = i + dx[k], ny = j + dy[k];
                if (check_bound(nx, ny) && !mp[nx][ny]) {
                    G.add_two(id(i, j), id(nx, ny));
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (mp[i][j]) {
                ++vistim;
                match(id(i, j), G);
            }
        }
    }
    int k;
    cin >> k;
    k *= 2;
    for (int i = 1; i <= k; i++) {
        int now  = id(sx, sy);
        ban[now] = 1;
        if (link[now]) {
            int y     = link[now];
            link[now] = link[y] = 0;
            ++vistim;
            win[i] = !match(y, G);
        }
        cin >> sx >> sy;
    }
    k /= 2;
    int tot = 0;
    for (int i = 1; i <= k; ++i) {
        if (win[i * 2 - 1] && win[i * 2]) {
            ans[++tot] = i;
        }
    }
    cout << tot << endl;
    for (int i = 1; i <= tot; ++i) {
        cout << ans[i] << endl;
    }
    return 0;
}
// Asusetic eru quionours