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

Solved Problem ID Title Ratio (Accepted / Submitted)
1001 Pandaemonium Asphodelos: The First Circle (Savage) 14.69% (42/286)
1002 Jo loves counting 12.54% (70/558)
1003 Slipper 13.17% (548/4161)
1004 The Surveying 21.09% (93/441)
1005 3D Puzzles 5.33% (4/75)
1006 BBQ 9.82% (119/1212)
1007 Count Set 16.94% (270/1594)
1008 AC/DC 9.56% (26/272)
1009 Cube Rotate 10.47% (9/86)
1010 Bragging Dice 34.42% (789/2292)
1011 Kazuha’s String 19.69% (25/127)
1012 Buy Figurines 21.09% (669/3172)

10.Bragging Dice

1010 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 22 players in one game. Each player has nn 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\geq 1)x(x≥1) dices with y(1\leq y\leq 6)y(1≤y≤6) points in the 2 cups”.

Then Peanut has 22 choices.

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

Continue to claim, but can only claim "there are x_1x
1
​
(x_1>x)(x
1
​

x) dices with y_1(1\leq y_1\leq 6)y
1
​
(1≤y
1
​
≤6) points in the cups" or “there are x_2x
2
​
(x_2=x)(x
2
​
=x) dices with y_2y
2
​
(y_2 > y)(y
2
​
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.

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

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 55 dices and 55 dices are all with 66 points, it’s considered there are 66 dices with 66 points.

If each dice in one cup has different points, it’s considered “there are 00 dice with any points in the cup”. For example, if there are 55 dices,their points are 11 point, 22 points, 33 points, 44 points and 55 points. It’s considered “there are 00 dice with 11 point in the cup”, “there are 00 dice with 22 point in the cup”, … , “there are 00 dice with 55 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 \le T \le 30)(1≤T≤30). Description of the test cases follows.

The first line of the input contains only one integers nn (2\le n \le 2\times 10^5)(2≤n≤2×10
5
) indicating the number of dices.

The next line contains nn integers a_1, a_2, \cdots, a_na
1
​
,a
2
​
,⋯,a
n
​
. The ii-th integer a_ia
i
​
indicating the points of the ii-th dice from YahAHa.

The next line contains nn integers b_1, b_2, \cdots, b_nb
1
​
,b
2
​
,⋯,b
n
​
. The ii-th integer b_ib
i
​
indicating the points of the ii-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!

题意：

• 有2个人，每个人都有n个骰子，给出初始的点数，每个人看不到对方的数字。
• 每一回合，玩家都有两种操作。
  1、称呼：玩家都可以称“2n个骰子中有x个y点”，每一轮的称呼x2,y2至少有一个要比上一轮的称呼x1,y1要大。
  2、挑战：如果上一轮对方的称呼每答对，那么我的挑战就胜利，否则就输了。
• 两个人都是最优操作，求谁能获胜。
• 三个特殊规则：
  1、如果没人说过有x个1点，那么1可以看做任何点数。
  2、如果一个杯子里的骰子都相同，比如有5个5点，那么认为是6个6点。
  3、如果一个杯子里的头子都不同，比如5个分别是1,2,3,4,5，那么认为是0个1,2,3,4,5点。

思路：

• 一般情况下，YahAHa先手，直接说出（最大的）“x个y”，那么后手无论怎么说，因为不能比先手大嘛，所以说不了了，就只能挑战，然后挑战就会输掉。因此先手直接获胜，输出Win!。
• 但是当双方都roll出全部不同的点数时，那么先手说不了x个y（x必须大于0嘛），所以先手不管说啥都是错的，然后后手挑战就会获胜。

#include
using namespace std;
const int maxn = 2e5+10;
int main(){
    ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);//TLE
    int T;  cin>>T;
    while(T--){
        int n;  cin>>n;
        int a[10] = {0}, b[10] = {0}, x;
        for(int i = 1; i <= n; i++)cin>>x, a[x]++;
        for(int i = 1; i <= n; i++)cin>>x, b[x]++;
        int ok = 0;
        for(int i = 1; i <= 6; i++){
            if(a[i]>1 || b[i]>1)ok = 1;
        }
        if(ok)cout<<"Win!\n";
        else cout<<"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

12.Buy Figurines

1012 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 nn people numbered from 11 to nn who intent to buy a figurine and the store has mm windows with mm queues identified from 11 to mm. The ii-th person has an arrival time a_ia
i
​
and a spent time s_is
i
​
to buy a figurine(It guaranteed that everyone’s arrival time a_ia
i
​
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 nn 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, a_1=1, s_1=2, a_2=2, s_2=2a
1
​
=1,s
1
​
=2,a
2
​
=2,s
2
​
=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 11 and 33. When the second person arrives, the first person is still in line, so the start time and end time of purchasing the figurine are 33 and 55. And if the end time of the last person is xx, the answer is xx.

Input
The first line contains one integer TT (1 \le T \le 10)(1≤T≤10) .

The first line of each test case contains two positive integers nn and mm (1\le n \le 2 \times 10^5,1\le m \le 2 \times 10^5)(1≤n≤2×10
5
,1≤m≤2×10
5
) — the number of people and the number of queues.

Then, nn lines follow, each consisting of two integers a_ia
i
​
and s_is
i
​
(1\le a_i,s_i \le 10^9)(1≤a
i
​
,s
i
​
≤10
9
) — the arrival time and spent time of ii-th person.

It guaranteed that the sum of nn does not exceed 2 \times 10^62×10
6
, and the sum of mm does not exceed 2 \times 10^62×10
6
.

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

题意

• 有n（2e5）个人，m（2e5）个队列。每个人有一个到达时间和办事情需要的时间。每个人到达后会优先选择人最少的队列进去，如果有多个人数一样，那就选编号最小的进去（无缝衔接）。
• 求最后一个人办完事情离开的时间是什么时候。题目保证每个人的到达时间都是不同的。

思路：

• 到达的顺序和办事时间给了，选队伍的规则也给了，所以就是个模拟题，唯一要注意的就是数据范围2e5稍微有点大，需要一些数据结构优化一下。
• 注意到每个人的到达时间是不一样的，考虑当第i个人在ai时刻到达时，我们需要找到人数最少并且编号最短的队伍，可以用开两个set维护空队伍的id，非空队伍的（长度，id），logn自动排序后找到的就是当前需要入队的队伍id。
• 然后我们再开一个deque数组，维护第i个队伍中每个人的结束时间，最后n个人都到达完了之后，所有剩余非空队伍的最后一个人的结束时间的最大值就是要求的答案。
• 对于第i个人到达时，我们要保证当前的se,se2都是合法的，即对于时刻ai，要知道前面有哪些队伍是空的，哪些是非空，长度是多少的。我们再开一个小根堆维护当前每个队伍的结束时间，即可logn的得到最早结束的队伍，去更新set。而不用去遍历所有的队伍，找到当前时间哪个队伍需要pop_front()。

#include
using namespace std;
typedef long long LL;
const int maxn = 2e5+10;
struct node{ LL x, s;}a[maxn];
bool cmp(node x, node y){ return x.x<y.x; }
deque<LL>q[maxn]; //队伍i中每个人的结束时间
int main(){
    ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
    int T;  cin>>T;
    while(T--){
        // 输入
        int n, m;  cin>>n>>m;
        for(int i = 1; i <= n; i++)cin>>a[i].x>>a[i].s;
        sort(a+1,a+n+1,cmp);

        // 空队伍(下标), 非空队伍（长度,下标）, 小根堆（结束时间, 下标）
        set<int>se;  set<pair<int,int> >se2;
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> >p;
        for(int i = 1; i <= m; i++)se.insert(i), q[i].clear();

        // 依次入队
        for(int i = 1; i <= n; i++){
            //找到最早结束的队, 不断出队 (保证当前有空队伍)
            while(p.size() && p.top().first <= a[i].x){
                int id = p.top().second;  p.pop();
                se2.erase(make_pair(q[id].size(),id));
                q[id].pop_front();
                if(q[id].empty())se.insert(id);
                else {
                    se2.insert({q[id].size(), id});
                    p.push({q[id].front(), id});
                } 
            }
            
            //空队伍>最短的队伍>下标小的队伍
            if(se.size() > 0){
                int id = *se.begin();  se.erase(id);
                q[id].push_back(a[i].x+a[i].s);
                se2.insert({1,id});
                p.push({a[i].x+a[i].s, id});
            }else{
                int id=se2.begin()->second, len=se2.begin()->first; se2.erase(se2.begin());
                q[id].push_back(max(q[id].back(), a[i].x)+a[i].s);
                se2.insert({len+1,id});
            }
        }
        LL ans = 0;
        for(auto x : se2)ans = max(ans, q[x.second].back());
        cout<<ans<<"\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
47
48
49
50
51
52
53
54
55

3.Slipper

Slipper
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 524288/262144 K (Java/Others)
Total Submission(s): 717 Accepted Submission(s): 160

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）

题意：

• 给出一个有n（1e6）个点的树，然后n-1条边都有一个代价（1e6），现在有一个魔法，可以从任意一点u快速到达dep[u]+k或dep[u]-k这两层的任意一个点，代价为p。
• 求从起点到终点的最小代价。

思路：

• 考虑无脑暴力，不难想到建树直接跑（堆优化）Dijkstra板子，转移的时候除了原来树上的边，还可以转移到所有dep[u]+k或dep[u]-k这两层的每个点，路径为p。
• 考虑优化，Dij的复杂度为(n+m)logn优化不了了，考虑在建图上优化，都是规律性的+k层-k层，没必要n^2条边全部连出来，可以新建超级节点表示第i层。
  然后每个点u往自己所在的层dep[u]连一条代价为0的边，再从第dep[u]+k和dep[u]-k层往这个点连一条代价为p的边，那么只用了最多n个点和3n条边就能实现当前点->当前层->±k层->跳转层点。
• 注意这里连的是有向边，不要把自己连到第k层，再从第k层连到自己，那么就会走过去走回来死循环，只要自己走到当前层，再通过层走过去，那么第k层走不到当前层，只能往第k层的点走，就不会挂了。
• 最后赛后他们群里说是有原题，Nya图最短路，HDU4725 , kuangbin专题， acwings4254。

//链式前向星, AC
#include
using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;
const int maxn = 2e6+10;//+n层

//Graph
int n, m = 0;
int head[maxn];
struct Edge{ int to, next, w; }edge[maxn*3]; 
void add_edge(int u, int v, int w){
    edge[m].to = v;
    edge[m].next = head[u];
    edge[m].w = w;
    head[u] = m++;
}
int depp[maxn], mxdep = 0;
void dfs(int u, int fa, int d){
    mxdep =  max(mxdep, d);
    depp[u] = d;
    for(int j = head[u]; j != -1; j = edge[j].next){
        if(edge[j].to == fa)continue;
        dfs(edge[j].to, u, d+1);
    }
}

//Dijkstra
int k, p;
int st, ed;
LL dist[maxn];
bool vis[maxn];
void dijkstra(int st,  LL dis[]){
    for(int i = 0; i <= 2*n+10; i++) dis[i]=1e18, vis[i] = 0;
    priority_queue< P,vector<P>, greater<P> >que;
    dis[st] = 0;
    que.push({dis[st],st});
    while(!que.empty()){
        P now=que.top(); que.pop();
        int u=now.second;
        if(vis[u]) continue;
        vis[u]=1;
        for(int j = head[u]; j != -1; j = edge[j].next){
            int v=edge[j].to;
            if(vis[v]) continue;
            int cost=edge[j].w;
            if(dis[v]>dis[u]+cost){
                dis[v]=dis[u]+cost;
                que.push({dis[v],v});
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
    int T;  cin>>T;
    while(T--){
        cin>>n;    
        mxdep = 0, m = 0;   //TLE
        for(int i = 0; i <= 2*n+5; i++) head[i] = -1;
        for(int i = 1; i < n; i++){
            int u, v, w;  cin>>u>>v>>w;
            add_edge(u,v,w);
            add_edge(v,u,w);
        }
        //预处理+建图
        dfs(1,0, 1);
        cin>>k>>p;  cin>>st>>ed;
        for(int i = 1; i <= n; i++){
            add_edge(i, depp[i] + n + 1, 0);
            if(depp[i]+k<=mxdep){
                // add_edge(i, depp[i]+n+1+k, p); //WA
                add_edge(depp[i]+n+1+k, i, p);
            }
            if(depp[i]-k>0){
                // add_edge(i, depp[i]+n+1-k, p);
                add_edge(depp[i]+n+1-k, i, p);
            }
        }
        dijkstra(st, dist);
        cout<<dist[ed]<<"\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
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

//vector, RE
#include
using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;
const int maxn = 6e6+10;//+n层

//Graph
int n, m = 0;
struct node{int to, w;};
vector<node>G[maxn];
int depp[maxn], mxdep = 0;
void dfs(int u, int fa, int d){
    mxdep =  max(mxdep, d);
    depp[u] = d;
    for(auto v : G[u]){
        if(v.to==fa)continue;
        dfs(v.to, u, d+1);
    }
}

//Dijkstra
int k, p;
int st, ed;
LL dist[maxn];
bool vis[maxn];
void dijkstra(int st,  LL dis[]){
    for(int i = 0; i <= 3*n+10; i++) dis[i]=1e18, vis[i] = 0;
    priority_queue< P,vector<P>, greater<P> >que;
    dis[st] = 0;
    que.push({dis[st],st});
    while(!que.empty()){
        P now=que.top(); que.pop();
        int u=now.second;
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i].to;
            int cost=G[u][i].w;
            if(dis[v]>dis[u]+cost){
                dis[v]=dis[u]+cost;
                que.push({dis[v],v});
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
    int T;  cin>>T;
    while(T--){
        cin>>n;    
        mxdep = 0, m = 0;   //TLE
        for(int i = 1; i < n; i++){
            int u, v, w;  cin>>u>>v>>w;
            G[u].push_back({v,w});
            G[v].push_back({u,w});
        }
        //预处理+建图
        dfs(1, 0, 1);
        cin>>k>>p;  cin>>st>>ed;
        for(int i = 1; i <= n; i++){
            G[i].push_back({depp[i]+n+1,0});
            if(depp[i]+k<=mxdep){
                G[depp[i]+n+1+k].push_back({i,p});
            }
            if(depp[i]-k>0){
                G[depp[i]+n+1-k].push_back({i,p});
            }
        }
        dijkstra(st, dist);
        cout<<dist[ed]<<"\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
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