这场多校幸亏有数学大手子队友切了道多项式题，$rank$++

然后记录一下我赛中写的几题。

1003-Slipper

题意

给出一颗根节点为$1$的树，每条边都有$w_i$的费用。

现在给你两个整数$k,p$，代表任意$u,v$只要$|depth_u-depth_v|=k$，那么就可以花费$p$的代价从$u$走到$v$或者从$v$走到$u$。

最后给你两个整数$s,t$求从$s$走到$t$的花费的最小代价是多少

思路

我们考虑对每个深度建立一个虚点，我们设这个虚点为$d_i$，然后树上每个节点对应深度的虚点向该节点连边，

该节点向深度为$depth_i+k$以及$depth_i-k$对应的虚点连边，最后跑$s \rightarrow t$的最短路。

但是没想到这题卡$vector$，必须用链式前向星连边才行。

png1

代码

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
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e6 + 5, MOD = 99824435;

int n, k, p, s, t;
struct Edge {
    int u, v, w;
} G[1000005];
int dep[1000005];
struct Node {
    LL v, w;
    bool operator < (const Node &o) const {
        return w > o.w;
    }
};
LL dis[N];
bool vis[N];
int head1[N], ver1[N], Next[N], tot1;
void add_edge1(int u, int v) {
    ver1[++ tot1] = v;
    Next[tot1] = head1[u];
    head1[u] = tot1;
}
int head2[N * 3], ver2[N * 3], Next2[N * 3], val[N * 3], tot2;
void add_edge2(int u, int v, int w) {
    ver2[++ tot2] = v;
    val[tot2] = w;
    Next[tot2] = head2[u];
    head2[u] = tot2;
}
void dfs(int x, int p) {
    dep[x] = dep[p] + 1;
    for (int i = head1[x]; i; i = Next[i]) {
        int y = ver1[i];
        if (y ^ p) {
            dfs(y, x);
        }
    }
}
priority_queue< Node > q;
void dijkstra(int st, int ed) {
    for (int i = 0; i <= n * 2; ++ i) {
        dis[i] = 1e14;
        vis[i] = false;
    }
    while (!q.empty()) {
        q.pop();
    }
    q.push({st, dis[st] = 0});
    while (!q.empty()) {
        Node p = q.top();
        q.pop();
        if (vis[p.v]) {
            continue;
        }
        vis[p.v] = true;
        for (int i = head2[p.v]; i; i = Next[i]) {
            LL v = ver2[i], w = val[i];
            if (!vis[v] && dis[v] > dis[p.v] + w) {
                q.push({v, dis[v] = dis[p.v] + w});
            }
        }
    }
}
void solve() {
    scanf("%d", &n);
    for (int i = 0; i <= tot1; ++ i) {
        head1[i] = 0;
    }
    for (int i = 0; i <= tot2; ++ i) {
        head2[i] = 0;
    }
    tot1 = tot2 = 0;
    for (int i = 1; i < n; ++ i) {
        scanf("%d %d %d", &G[i].u, &G[i].v, &G[i].w);
        add_edge1(G[i].u, G[i].v);
        add_edge1(G[i].v, G[i].u);
    }
    dfs(1, 0);
    for (int i = 1; i < n; ++ i) {
        int u = G[i].u, v = G[i].v, w = G[i].w;
        add_edge2(u, v, w);
        add_edge2(v, u, w);
    }
    scanf("%d %d", &k, &p);
    for(int i = 1;i <= n; ++ i){
        add_edge2(dep[i] + n, i, 0);
    }
    scanf("%d %d", &s, &t);
    for (int i = 1; i <= n; ++ i) {
        int l = dep[i] - k;
        if (l >= 1){
            add_edge2(i, l + n, p);
        }
        int r = dep[i] + k;
        if (r <= n){
            add_edge2(i, r + n, p);
        }
    }
    dijkstra(s, t);
    printf("%lld\n", dis[t]);
}
signed main() {
    int t;
    scanf("%d", &t);
    while (t -- ) {
        solve();
    }
    return 0;
}

1012-Buy Figurines

题意

$n$个人，$m$条排队通道，每个人都要来商场购物，给出每个人到达时间 $s_i$ 和购物所需的时间 $t_i$。

现有如下规则：

  • 当第$i$个人到达商场时，他会选择当前排队人数最少的通道，若这样的通道不只一个，那么他会选择队伍编号最小的
  • 若当前时刻有人离开，那么他会等所有当前时刻的人离开后，再去排队

求所有人都完成购物的最少时间

思路

我们考虑维护当前时刻每个队伍的人数以及排了队的人的离开时间和他所属的排队通道的标号，当该时刻有人来购物时，我们把所有排了队的人里结束时间小于等于该时刻的人给“丢掉”，并且实时更新“丢掉”的人所属排队通道正在排队的人数。最后输出最大离开时间即可。

代码

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
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 5, MOD = 998244353, INF = 0x3f3f3f3f;

#define int LL
int n, m;
int cnt[N], ed_time[N];
void solve() {
    cin >> n >> m;
    vector< pair< LL, LL > > a;
    for (int i = 1; i <= n; ++ i) {
        int s, t;
        cin >> s >> t;
        a.push_back({s, t});
    }
    for (int i = 1; i <= m; ++ i) {
        cnt[i] = ed_time[i] = 0;
    }
    int num = 0;
    multiset< pair< int, int > > st;
    sort(a.begin(), a.end());
    multiset< pair< int, int > > que;
    multiset< pair< int, int > >::iterator it;
    for (int i = 0; i < n; ++ i) {
        int s = a[i].first, t = a[i].second;
        if (num < m) {
            ++ num;
            cnt[num] = 1;
            ed_time[num] = s + t;
            st.insert({1, num});
            que.insert({s + t, num});
        } else {
            while (!que.empty() && que.begin()->first <= s) {
                int pos = que.begin()->second;
                st.erase(st.find({cnt[pos], pos}));
                -- cnt[pos];
                st.insert({cnt[pos], pos});
                que.erase(que.begin());
            }
            int CNT = st.begin()->first, POS = st.begin()->second;
            st.erase(st.begin());
            ++ cnt[POS];
            ed_time[POS] = max(ed_time[POS], s) + t;
            st.insert({cnt[POS], POS});
            que.insert({ed_time[POS], POS});
        }
    }
    cout << *max_element(ed_time + 1, ed_time + m + 1) << '\n';
}
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int t;
    cin >> t;
    while (t -- ) {
        solve();
    }
    return 0;
}