Asusetic
0%

2021.07.02模拟赛

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

这里不知道写啥

2021.07.02 模拟赛

T1 走夜路

首先肯定是在价格低的地方多充，价格高的少充

那么用ST表二分找到下一个小于它的电站，这一站充到能走过去就行

如果没有比他小的了就充满然后走，无解很好判 O(nlog⁡n)O(n \log n)

可以用单调栈去维护这个下一个小于他的电站，就是 O(n)O(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
#include <cstdio>
#include <iostream>
using namespace std;
using ll    = long long;
const int N = 500005;
ll d[N], p[N];
namespace ST {
int lg2[N];
ll st[N][20];
void init(int n) {
    lg2[1] = 0, lg2[2] = 1;
    for (int i = 3; i <= n; ++i) {
        lg2[i] = lg2[i >> 1] + 1;
    }
    for (int i = 1; i <= n; ++i) {
        st[i][0] = p[i];
    }
    for (int i = 1; i < 20; ++i) {
        int lim = n - (1 << i) + 1;
        for (int j = 1; j <= lim; ++j)
            st[j][i] = min(st[j][i - 1], st[j + (1 << i - 1)][i - 1]);
    }
}

ll query(int l, int r) {
    int i = lg2[r - l + 1];
    return min(st[l][i], st[r - (1 << i) + 1][i]);
}
} // namespace ST

ll n, t;
int main() {
    cin >> n >> t;
    for (int i = 1; i <= n; ++i) {
        cin >> d[i] >> p[i - 1];
        d[i] += d[i - 1];
    }
    ST::init(n);
    ll pos = 0, now = 0, ans = 0;
    while (pos < n) {
        if (now < 0) {
            cout << -1 << endl;
            return 0;
        }
        ll l = pos + 1, r = n, res = -1;
        while (l <= r) {
            ll mid = (l + r) / 2;
            if (ST::query(pos + 1, mid) <= p[pos]) {
                r   = mid - 1;
                res = mid;
            } else {
                l = mid + 1;
            }
        }
        if (d[res] - d[pos] > t) {
            ans += (t - now) * p[pos];
            now = t - (d[pos + 1] - d[pos]);
            pos++;
        } else {
            ll tmp = 0;
            if (now > d[res] - d[pos])
                tmp = now - d[res] + d[pos];
            ans += (d[res] - d[pos] - min(now, d[res] - d[pos])) * p[pos];
            now = tmp;
            pos = res;
        }
    }
    cout << ans << endl;
    return 0;
}

###　T2 t2

数位DP

注意前导 00

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
#include <cstring>
#include <iostream>
using namespace std;
using ll = long long;
ll l, r;
ll dp[20][12];
int dig[20];
int X, Y;
ll dfs(int x, int pre, int lim, bool zero) {
    // printf("%d %d %d\n", x, pre, lim);
    if (x < 0) {
        return 1;
    }
    if (!lim && ~dp[x][pre]) {
        return dp[x][pre];
    }
    int up = lim ? dig[x] : 9;
    ll res = 0;
    for (int i = 0; i <= up; i++) {
        if (pre == X && i == Y) {
            continue;
        }
        res += dfs(x - 1, (zero & (i == 0)) ? 11 : i, lim && (i == up),
                   zero & (i == 0));
    }
    if (!lim) {
        dp[x][pre] = res;
    }
    return res;
}
ll solve(ll x) {
    int len = 0;
    memset(dp, -1, sizeof(dp));
    while (x) {
        dig[len++] = x % 10;
        x /= 10;
    }
    return dfs(len - 1, 11, 1, 1);
}
int main() {
    cin >> l >> r >> X >> Y;
    cout << solve(r) - solve(l - 1);
}

T3 奇怪的集训队

先钦定 kk 种元素，有 (nk)\binom{n}{k} 种选择

要求剩下的 n−kn-k 元素的集合个交集为空

考虑 恰好 和 至少 的二项式反演

就能得到答案为 ∑(−1)i(n−ki)(22n−k−i−1)\sum(-1)^i\binom{n-k}{i}(2^{2^{n-k-i}}-1)

T4 最短路

首先这两个点肯定在 S,TS,T 的同一条最短路上

然后考虑 S,TS,T 之间所有最短路构成的最短路图，是个DAG，然后拓扑+bitset跑每个点能到达的点即可

O(nlog⁡n+m+nmw)O(n\log n+m+\frac{nm}{w})

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
#include <algorithm>
#include <array>
#include <bitset>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll     = long long;
const int N  = 3e4 + 5;
const ll INF = (1ll < 48);
array<bool, N> mark, vis;
array<int, N> in, siz;
bitset<N> nya[N];
vector<int> pre[N];
int n, m;
struct Graph {
    struct Node {
        int v, w;
    };
    vector<Node> edge[N];
    void add(int u, int v, int w) {
        edge[u].emplace_back(Node{v, w});
    }
} G, G0;
struct Node {
    int v;
    ll dis;
    const bool operator<(const Node &B) const {
        return dis > B.dis;
    }
};
vector<ll> ShortestPath(const int S, const Graph &G) {
    vector<ll> dis;
    dis.resize(n + 1);
    dis.assign(n + 1, -1);
    priority_queue<Node> q;
    dis[S] = 0;
    q.push(Node{S, dis[S]});
    while (!q.empty()) {
        int now = q.top().v;
        q.pop();
        for (auto e : G.edge[now]) {
            int v = e.v;
            if (dis[v] == -1 || dis[v] > dis[now] + e.w) {
                dis[v] = dis[now] + e.w;
                pre[v].clear();
                pre[v].push_back(now);
                q.push(Node{v, dis[v]});
            } else if (dis[v] == dis[now] + e.w) {
                pre[v].push_back(now);
            }
        }
    }
    return dis;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G.add(u, v, w);
        G.add(v, u, w);
    }
    ShortestPath(1, G);
    queue<int> q;
    q.push(n);
    in.fill(-1);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        if (~in[x]) {
            continue;
        }
        in[x]++;
        for (auto v : pre[x]) {
            G0.add(v, x, 1);
            ++in[x];
            q.push(v);
        }
    }
    vector<int> topo;
    q.push(1);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        topo.push_back(x);
        for (auto e : G0.edge[x]) {
            --in[e.v];
            if (!in[e.v]) {
                q.push(e.v);
            }
        }
    }
    reverse(topo.begin(), topo.end());
    ll ans = 0;
    for (auto x : topo) {
        // cout << x << endl;
        nya[x][x] = 1;
        for (auto e : G0.edge[x]) {
            nya[x] |= nya[e.v];
        }
        ans += nya[x].count() - 1;
    }
    cout << ans << endl;
}