Slipper

Problem Description

Gi is a naughty child. He often does some strange things. Therefore, his father decides to play a game with him.

Gi’s father is a senior magician, he teleports Gi and Gi’s Slipper into a labyrinth. To simplify this problem, we regard the labyrinth as a tree with n nodes, rooted at node 1. Gi is initially at node s, and his slipper is at node t. In the tree, going through any edge between two nodes costs w unit of power.

Gi is also a little magician! He can use his magic to teleport to any other node, if the depth difference between these two nodes equals to k. That is, if two nodes u,v satisfying that |depu−depv|=k, then Gi can teleport from u to v or from v to u. But each time when he uses magic he needs to consume p unit of power. Note that he can use his magic any times.

Gi want to take his slipper with minimum unit of power.

Input

Each test contains multiple test cases. The first line contains the number of test cases (1≤T≤5). Description of the test cases follows.

The first line contains an integer n — The number of nodes in the tree. 2≤n≤106.

The following n−1 lines contains 3 integers u,v,w that means there is an edge between nodes u and v. Going through this edge costs w unit of power. 1≤u,v≤n,1≤w≤106.

The next line will contain two separated integers k,p. 1≤k≤maxu⊆V(depu),0≤p≤106.

The last line contains two positive integers s,t, denoting the positions of Gi and slipper. 1≤s≤n,1≤t≤n. It is guaranteed the s≠t.

Output

For each test case:

Print an integer in a line — the minimum unit of power Gi needs.

Sample Input

1
6
6 1 2
3 5 2
2 4 6
5 2 2
5 6 20
3 8
6 5

Sample Output

12

Hint

Example1: Gi can go from node 6 to node 1 using 2 units of power. Then he teleports from node 1 to node 2 using 8 units of power. Finally, he goes from node 2 to node 5 using 2 units of power. Total cost=2+8+2=12

Source

2022“杭电杯”中国大学生算法设计超级联赛（5）

给你一个树，，已知起点终点，设当前深度为x同时可以花费p点到达x+k或者x-k的节点，求起点到终点的最短距离

不妨设当前深度为d，那么我们新增两个点，in点指向当前深度的所有点,out点由当前深度的所有点指向，同时out点以p的花费指向d-k和d+k的in点
然后跑dijkstra即可

/****************

 *@description:for the Escape Project

 *@author: Nebula_xuan

 * @Date: 2022-08-03 10:10:50

 *************************************************************************/

  

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

  

using namespace std;

#define xx first

#define yy second

#define rep(i, h, t) for (int i = h; i <= t; i++)

#define dep(i, t, h) for (int i = t; i >= h; i--)

#define endl char(10)

//记得%d应该写成%lld

  

typedef pair<long long, int> PII;

const int N = 4e6 + 10;

int e[N * 2], ne[N * 2], w[N * 2], idx, h[N], dep[N];

int k, p, s, t;

int n;

vector<int> v[N];

long long dist[N];

bool vis[N];

void add(int a, int b, int c)

{

    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;

}

void dfs(int u, int fa)

{

    dep[u] = dep[fa] + 1;

    v[dep[u]].push_back(u);

    for (int i = h[u]; ~i; i = ne[i])

    {

        int j = e[i];

        if (j == fa)

            continue;

        dfs(j, u);

    }

}

void dijkstra()

{

    priority_queue<PII, vector<PII>, greater<PII>> heap;

    memset(dist, 0x3f, sizeof dist);

    memset(vis, 0, sizeof vis);

    dist[s] = 0;

    heap.push({dist[s], s});

    while (heap.size())

    {

        auto t = heap.top();

        heap.pop();

        int dis = t.xx;

        int ver = t.yy;

        if (vis[ver])

            continue;

        vis[ver] = true;

        for (int i = h[ver]; ~i; i = ne[i])

        {

            int j = e[i];

            if (dist[j] > dist[ver] + w[i])

            {

                dist[j] = dist[ver] + w[i];

                heap.push({dist[j], j});

            }

        }

    }

}

signed main()

{

    ios::sync_with_stdio(false);

    int tt;

    cin >> tt;

    while (tt--)

    {

        idx = 0;

        memset(h, -1, sizeof h);

  

        cin >> n;

        for (int i = 1; i <= n; i++)

            v[i].clear();

        for (int i = 1; i < n; i++)

        {

            int a, b, c;

            cin >> a >> b >> c;

            add(a, b, c);

            add(b, a, c);

        }

        cin >> k >> p >> s >> t;

        dfs(1, 0);

        for (int i = 1; i <= n; i++)

        {

            for (auto it : v[i])

            {

                add(it, i + 2 * n, 0);

                add(i + n, it, 0);

            }

            if (i - k > 0)

                add(2 * n + i, i - k + n, p);

            if (i + k <= n)

                add(2 * n + i, i + k + n, p);

        }

        dijkstra();

        cout << dist[t] << endl;

    }

}
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
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225

Bragging Dice

Problem Description

In the mysterious accient East, there is an ancient dice game - “bragging”. Now YahAHa and Peanut is playing bragging.

The rules of the game are as follows:

There are 2 players in one game. Each player has n dices in the cup. Both players roll the dice once.

Players play in turns. YahAHa start. In the first turn, YahAHa can claim “there are x(x≥1) dices with y(1≤y≤6) points in the 2 cups”.

Then Peanut has 2 choices.

1. Challenge YahAHa. If anyone challenges, the game is over . Each player opens its cup. If indeed there are x dices with y points in the cups, YahAHa wins, otherwise Peanut wins.

2. Continue to claim, but can only claim “there are x1 (x1>x) dices with y1(1≤y1≤6) points in the cups” or “there are x2 (x2=x) dices with y2 (y2>y) points in the cups”.

After Peanut claimed, YahAHa continued to choose whether to challenge or claim. Both players take turns until someone challenges, then the game is over.

To make the game more interesting, here are some special rules.

1. If no one has claimed that “there are x dices with 1 point in the cups”, the dice with 1 point can be regarded as any points of dice.

2. If all dices in one cup has the same points, it’s considered there is an extra dice with the same points. For example, if there are 5 dices and 5 dices are all with 6 points, it’s considered there are 6 dices with 6 points.

3. If each dice in one cup has different points, it’s considered “there are 0 dice with any points in the cup”. For example, if there are 5 dices,their points are 1 point, 2 points, 3 points, 4 points and 5 points. It’s considered “there are 0 dice with 1 point in the cup”, “there are 0 dice with 2 point in the cup”, … , “there are 0 dice with 5 point in the cup”.

If there is conflict in these three rules, please consider the third special rule first.

YahAHa and Peanut don’t like stupid game of chance, so they want to play this game while knowing the points of every dices in the 2 cups.

Given you the points of all dices they roll. YahAHa wants to find out who will win the game if both of them play the game optimally.

Input

Each test contains multiple test cases. The first line contains the number of test cases (1≤T≤30). Description of the test cases follows.

The first line of the input contains only one integers n (2≤n≤2×105) indicating the number of dices.

The next line contains n integers a1,a2,⋯,an. The i-th integer ai indicating the points of the i-th dice from YahAHa.

The next line contains n integers b1,b2,⋯,bn. The i-th integer bi indicating the points of the i-th dice from Peanut.

Output

For each test case:

If YahAHa wins, print “Win!” in one line; If Peanut wins, print “Just a game of chance.” in one line.

Sample Input

1
5
4 6 4 1 2
3 6 6 2 3

Sample Output

Win!

Source

2022“杭电杯”中国大学生算法设计超级联赛（5）

阅读理解题。。。读懂就能写
因为大家都知道所有的牌
所以YahAHa只要报最大的就必胜，
只有一种情况就是都是0的情况下他报不出数所以就会输
按照规则找一下这种情况即可

AC代码

#include 
#include 
#include 
#include 
#include 
#include 
#define N 550000
using namespace std;
int vis[7], vis1[7];
signed main()
{
    int t, n;
    scanf("%d", &t);
    while (t--)
    {
        for (int i = 1; i <= 6; i++)
            vis[i] = 0, vis1[i] = 0;
        scanf("%d", &n);
        int x;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &x);
            vis[x]++;
        }
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &x);
            vis1[x]++;
        }
        bool flag1 = false;
        bool flag2 = false;
        for (int i = 1; i <= 6; i++)
        {
            if (vis[i] > 1)
                flag1 = true;
            if (vis1[i] > 1)
                flag2 = true;
        }

        if (flag1 || flag2)
            printf("Win!\n");
        else
            printf("Just a game of chance.\n");
    }
    return 0;
}
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

Buy Figurines

Problem Description

During the “Hues of the Violet Garden” event, As the professional Lady Guuji hired, Sayu is assigned to buy one of the figurines, that is “Status of Her Excellency, the Almighty Narukami Ogosho, God of Thunder”.

There are n people numbered from 1 to n who intent to buy a figurine and the store has m windows with m queues identified from 1 to m. The i-th person has an arrival time ai and a spent time si to buy a figurine(It guaranteed that everyone’s arrival time ai is different). When a person arrives at the store, he will choose the queue with the least number of people to queue. If there are multiple queues with the least number of people, he will choose the queue with the smallest identifier. It should be noted that if someone leaves the queue at the same time, the person will choose the queue after everyone leaves the team.

Sayu has been here since last night so she could buy a figurine. But after waiting and waiting, her eyes started to feel real droopy and… overslept. If Sayu doesn’t buy one of these figurines, the Tenryou Commission tengu will lock her up for life! The store will close after these n people buy figurines, that means she must wake up before the last one leaves. Now Lady Guuji wants to know the latest time Sayu wakes up.

For example, there are two people in the same line, a1=1,s1=2,a2=2,s2=2. When the first person arrives, there is no one in the line, so the start time and end time of purchasing the figurine are 1 and 3. When the second person arrives, the first person is still in line, so the start time and end time of purchasing the figurine are 3 and 5. And if the end time of the last person is x, the answer is x.

Input

The first line contains one integer T (1≤T≤10) .

The first line of each test case contains two positive integers n and m (1≤n≤2×105,1≤m≤2×105) — the number of people and the number of queues.

Then, n lines follow, each consisting of two integers ai and si (1≤ai,si≤109) — the arrival time and spent time of i-th person.

It guaranteed that the sum of n does not exceed 2×106, and the sum of m does not exceed 2×106.

Output

For each test case:

print a line containing a single integer — the latest time Sayu wakes up, that means the end time of the last person.

Sample Input

1
5 3
2 4
1 3
5 1
3 4
4 2

Sample Output

7

Source

2022“杭电杯”中国大学生算法设计超级联赛（5）

有n个人买东西，已知到达时间和花费时间，每个人会优先选择排队人数最少的，其次是编号较小的
问最后一个人离开的时间是多少

用线段树维护当前人数最小的队列和位置
用vector以到达时间为第一关键字，所需时间为第二关键词排序，优先队列中存储每个人的离开时间每次插入前先把离开时间小于到达时间的人从队列中清除，并更新到线段树上

tags线段树，优先队列

AC代码

/****************

 *@description:for the Escape Project

 *@author: Nebula_xuan

 * @Date: 2022-08-03 09:17:07

 *************************************************************************/

  

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

  

using namespace std;

#define xx first

#define yy second

#define rep(i, h, t) for (int i = h; i <= t; i++)

#define dep(i, t, h) for (int i = t; i >= h; i--)

#define endl char(10)

#define int long long

//记得%d应该写成%lld

  

typedef pair<int, int> PII;

const int N = 2e6 + 10;

int n, m;

int time[N];

struct node

{

    int l, r;

    int pos, num;

} tr[N << 2];

void pushup(int u)

{

    tr[u].num = min(tr[u << 1].num, tr[u << 1 | 1].num);

    if (tr[u << 1].num <= tr[u<<1|1].num)

        tr[u].pos = tr[u << 1].pos;

    else

        tr[u].pos = tr[u << 1 | 1].pos;

}

void build(int u, int l, int r)

{

    tr[u] = {l, r, l, 0};

    if (l == r)

        return;

    int mid = l + r >> 1;

    build(u << 1, l, mid);

    build(u << 1 | 1, mid + 1, r);

    pushup(u);

}

void modify(int u, int x, int v)

{

    if (tr[u].l == tr[u].r && tr[u].l == x)

    {

        tr[u].num += v;

    }

    else

    {

        int mid = tr[u].l + tr[u].r >> 1;

        if (x <= mid)

            modify(u << 1, x, v);

        if (x > mid)

            modify(u << 1 | 1, x, v);

        pushup(u);

    }

}

  

signed main()

{

    ios::sync_with_stdio(false);

    int t;

    cin >> t;

    vector<PII> v;

    while (t--)

    {

        v.clear();

        cin >> n >> m;

        for (int i = 1; i <= n; i++)

        {

            int a, b;

            cin >> a >> b;

            v.push_back({a, b});

        }

        sort(v.begin(), v.end());

        for (int i = 1; i <= m; i++)

            time[i] = 0;

        int ans = 0;

        priority_queue<PII, vector<PII>, greater<PII>> heap;

        build(1, 1, m);

        for (int i = 0; i < n; i++)

        {

            while (heap.size() && heap.top().xx <= v[i].xx)

            {

                modify(1, heap.top().second, -1);

                heap.pop();

            }

            int pos = tr[1].pos;

            modify(1, pos, 1);

            time[pos] = max(v[i].xx, time[pos]) + v[i].yy;

            heap.push({time[pos], pos});

            ans = max(ans, time[pos]);

        }

        cout << ans << endl;

    }

}
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
204
205
206
207
208
209
210
211
212
213