“蔚来杯“2022牛客暑期多校训练营（加赛），签到题MHEJ

题号 标题 已通过代码 通过率 团队的状态
A Alternating 2.0 点击查看 2/27
B Bustling City 点击查看 24/246
C Cmostp 点击查看 46/296
D Directions 点击查看 2/34
E Everyone is bot 点击查看 832/3213
F Flame blast magician master qcjj 点击查看 18/26
G Good red-string 点击查看 57/1477
H Here is an Easy Problem of Zero-chan 点击查看 1010/2090
I Innocent longing 点击查看 0/11
J Jellyfish and its dream 点击查看 481/2692
K Killer Sajin’s Matrix 点击查看 82/578
L Lndjy and the mex 点击查看 27/59
M Maimai DX 2077 点击查看 1237/1492

M.Maimai DX 2077

链接：https://ac.nowcoder.com/acm/contest/38727/M
来源：牛客网

题目描述
dXqwq likes playing maimai DX UNiVERSE PLUS, since he can’t fly to Japan and SEGA completely ignores the feelings of Chinese players, he can only play maimai DX 2077.

In maimai DX 2077, you need to press the button or touch the screen when NOTE appears. There are 4 types of NOTE: TAP, HOLD, SLIDE, and BREAK. There are also 5 judgments for each NOTE: CRITICAL PERFECT, PERFECT, GREAT, GOOD, and MISS.

For each type of NOTE, you can get some standard points according to the judgment. For BREAK NOTEs, you can get some extra points according to the judgment.

Here is the table of standard points:

Here is the table of extra points:

Let A,BA,B be the standard points and extra points you will have if you get CRITICAL PERFECT on every NOTE, and A_0,B_0A
0
​
,B
0
​
be the standard points and extra points you have, the achievement score for this track is defined as \frac{A_0}{A}\cdot100%+\frac{B_0}{B}\cdot1%
A
A
0
​

​
⋅100%+
B
B
0
​

​
⋅1%.

You are given the number of NOTEs for each type and each judgment, and calculate the achievement score.
输入描述:
There are 44 lines in a test, each line denotes a type of NOTE: TAP, HOLD, SLIDE and BREAK.

The ii-th line contains 55 integers c_{i,0},c_{i,1},\cdots,c_{i,4}c
i,0
​
,c
i,1
​
,⋯,c
i,4
​
(0\leq c_{i,j}\leq 10^30≤c
i,j
​
≤10
3
), each integer denotes a type of judgment: CRITICAL PERFECT, PERFECT, GREAT, GOOD, and MISS.

It’s guaranteed that there is at least one BREAK note.
输出描述:
Print the percentage of the achievement score in a line. Your answer will be considered correct if the absolute or relative error between yours and the standard answer is no more than 10^{-6}10
−6
. Formally, let your answer be aa and the jury’s answer be bb, and then your answer is considered correct if \frac{|a - b|}{\max(1, |b|)} \leq 10^{-6}
max(1,∣b∣)
∣a−b∣
​
≤10
−6
.
示例1
输入
复制
311 131 24 1 2
48 20 4 0 0
36 0 0 1 0
35 15 1 0 0
输出
复制
99.523505378
示例2
输入
复制
224 133 15 0 0
45 14 0 0 0
57 0 2 1 0
15 16 0 0 0
输出
复制
100.051026393
示例3
输入
复制
324 210 26 2 2
13 14 1 0 0
102 0 3 3 0
9 4 0 0 0
输出
复制
99.369444233
备注:
Noticed that the rules of maimai ; DX ; 2077maimaiDX2077 are different from maimai ; DX ; 2022maimaiDX2022.

题意：

• 有个音游叫Maimai DX 2077。
  这个音游有四种音符，每种音符有五个判定。不同音符的不同判定会获得不同基础分数（表1给出）
• 绝赞（附加分）的判定单独计算分数
• 给定一次游玩每种音符每种判定的数量，问达成度。

思路：

• 将判定的表作为4 × 5 数组输入程序。
• 读入时直接计算A, A0, B, B0 即可。

#include
using namespace std;

double pw[5][5] = {
    {1,1,0.8,0.5,0},
    {2,2,1.6,1.0,0},
    {3,3,2.4,1.5,0},
    {5,5,2.5,2,0},
    {1,0.5,0.4,0.3,0} //附加分判定
};

int main(){
    double A0 = 0, A = 0, B0 = 0, B = 0;
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 5; j++){
            int x;  cin>>x;
            A0 += pw[i][j]*x;      //获得的分数
            A += pw[i][0]*x;       //全部perfet的分
            if(i==3){
                B0 += pw[4][j]*x;  //获得的附加分
                B += pw[4][0]*x;   //全部perfet的附加分
            }
        }
    }
    printf("%.10lf\n",A0/A*100+B0/B);
    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

H.Here is an Easy Problem of Zero-chan

链接：https://ac.nowcoder.com/acm/contest/38727/H
来源：牛客网

题目描述
Zero-chan has a rooted tree with nn nodes. The root of given tree is node 11. She defines f(x)= \prod_{i=1}^nlca(x,i)f(x)=∏
i=1
n
​
lca(x,i).

lca(u,v)lca(u,v) meas the Least Common Ancestor of node uu and node vv.

Zero-chan gives you some integers xx and asks you to calculate: the number of suffix zeros of f(x)f(x)
输入描述:
First line contains 2 integers n,qn,q (1\leq q\leq n\leq 10^5)1≤q≤n≤10
5
) - the size of given tree and the number of queries.

Each of the next n -1n−1 lines contains two integers u,vu,v (1\leq u,v\leq n, u \neq v1≤u,v≤n,u

​
=v) indicating an undirected edge between node uu and node vv. It is guaranteed that the given edges form a tree.

The following line containing qq integers describes the queries. Each of query has a integer xx (1\leq x \leq n1≤x≤n).
输出描述:
For each query, print a integer - the answer of the query.
示例1
输入
复制
5 5
2 3
5 4
2 5
1 5
1 2 3 4 5
输出
复制
0
2
1
2
0

题意：

• 有一颗n （1e5）个节点且以1 为根的有根树，第i 个点的点权为i。
• 多次查询（1e5）编号为x 的点， ${\prod }_{i=1}^{n}lca(i,x)$ 的末尾有多少个零。

思路：

• 官方：
  
  

#include
using namespace std;
typedef long long LL;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
const int maxn = 1e5+10;

int n, q;
vector<int>G[maxn];
LL siz[maxn], a2[maxn], a5[maxn];
void dfs(int x, int f){
    siz[x] = 1;
    for(int y : G[x]){
        if(y==f)continue;
        dfs(y,x);
        siz[x] += siz[y];
    }
}

LL ans[maxn];
void dfs2(int x, int f, LL t2, LL t5){
    ans[x]  = min(t2,t5);
    for(int y : G[x]){
        if(y==f)continue;
        dfs2(y,x, t2+a2[y]*siz[y]-a2[x]*siz[y], t5+a5[y]*siz[y]-a5[x]*siz[y]);
    }
}

int main(){
    IOS;
    cin>>n>>q;
    for(int i = 2; i <= n; i++){
        int u, v;  cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i = 1; i <= n; i++){
        int t = i;
        while(t%2==0){ t/=2; a2[i]++; }
        while(t%5==0){ t/=5; a5[i]++; }
    }
    dfs(1,-1);
    dfs2(1,-1, 0, 0);
    for(int i = 1; i <= q; i++){
        int x;  cin>>x;
        cout<<ans[x]<<"\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

E.Everyone is bot

链接：https://ac.nowcoder.com/acm/contest/38727/E
来源：牛客网

题目描述
Have you ever used the chat application QQ? Well, in a chat group of QQ, administrators have permission to muzzle a user for some days.

There is a famous activity called ‘‘Fudu’’, which means repeating the sentence from the last guy sent.

As we all known, the penultimate person who do ‘‘Fudu’’ will be muzzled.

But Administrator Mieputrygub Bot thinks it’s too boring, so he decided to muzzle the last pp-th person who do ‘‘Fudu’’.

Now, there are nn persons in a chat group who want to do ‘‘Fudu’’. If few people participate in ‘‘Fudu’’, it will be boring, so the number of participants nn will be greater than or equal to pp. If everyone does ‘‘Fudu’’, it is certain that existing a man who is the last pp-th.

However, the way they do ‘‘Fudu’’ is unusual, there will be several rounds. In each round, nn persons perform the following actions in sequence.

• If he did ‘‘Fudu’’ in the any previous rounds, he can’t do ‘‘Fudu’’ in this round. It means each person can do ‘‘Fudu’’ only once.

• Otherwise, he can choose whether to do ‘‘Fudu’’.

If there is a round nobody do ‘‘Fudu’’, the process of doing ‘‘Fudu’’ will end.

For the person ii, if he is the jj-th person to do ‘‘Fudu’’, he can get a_{i,j}a
i,j
​
bottles of Ice Black Tea.

However, if he was the last pp-th person to do ‘‘Fudu’’, he will be muzzled, not get any Ice Black Tea. He also need to give Mieputrygub Bot 154154 bottles of Ice Black Tea.It means he get -154−154 bottles of Ice Black Tea.

If the last pp-th person does not exist, nobody will be muzzled.

Everyone wants to maximize the amount of Ice Black Tea they can get, you need to find out how much Ice Black Rea that each person can get finally.
输入描述:
The first line contains two postive integers n,pn,p (1 \le p \le n \le 10^{3}1≤p≤n≤10
3
).

Next nn lines, ii-th line contains nn postive integers a_{i,1},a_{i,2},\dots,a_{i,n}a
i,1
​
,a
i,2
​
,…,a
i,n
​
(1 \le a_{i,j}\le 10^{9}1≤a
i,j
​
≤10
9
).

For j\neq kj

​
=k, a_{i,j}\neq a_{i,k}a
i,j
​


​
=a
i,k
​
.
输出描述:
Output one line with nn integers, ii-th integers means the number of Ice Black Tea ii-th person will get.
示例1
输入
复制
3 2
1 14 5
141 9 1
9 8 10
输出
复制
1 0 0
说明
The first person in the first round will do “Fudu” and get 11 bottle of Ice Black Tea.
And the remaining two are holding each other back.(If someone first do “Fudu” in this round , then another one can do “Fudu” in the next round to let first one be the last 22-th person who do “Fudu”)
示例2
输入
复制
5 3
1000 4 3 2 1
4 1000 3 2 1
4 3 1000 2 1
4 3 2 1000 1
4 3 2 1 1000
输出
复制
1000 1000 0 0 0

题意：

• 有n 个人打算在群里复读。一次复读的过程如下：
  每一轮，n 个人按照编号从小到大依次执行以下操作。
  如果这个人在前几轮已经进行过复读，他不会再次复读。否则他可以选择是否进行复读。
  如果某一轮没有人进行复读，那么复读的过程结束。
• 对于第i 个人，如果他是所有人中第j 个进行复读的，他会获得ai,j 瓶冰红茶。
  但是如果他是所有进行了复读的人当中倒数第p 个进行复读的人，那么他不会获得任何冰红茶，并且需要交给咩噗特雷格博bot 154 瓶冰红茶（即获得−154 杯冰红茶）
• 每个人都想最大化自己获得的冰红茶数量，求所有人一共会拿到多少冰红茶。

思路：

• 首先，如果当前已经有n − p 个人复读了，那么后面不会有任何人复读。
  因为一旦有人复读，剩下的人必然都会参与复读，那么这个人就会被禁言。所以他不会这么做。因此n - p后面值一定都是0。
• 同样的，如果有n − 2p 个人复读了，那么后面不会有任何人复读，因为一旦他复读了，接下来一定有p − 1 个人加入复读，，而这时候是n − p 个人复读的状态，剩下p 个人一定不会复读，那么他就被禁言了。
• 同样可以推出，如果当前复读人数是n − kp 那么后面不会有人复读。
  所以结论：参与复读人数是n mod p。
• 对于参与复读的人，按照顺序参与即可（因为游戏只能玩一轮，前面的人第一轮不复读后面就被抢走机会了，所以肯定会直接复读当前能复读的值，尽可能拿到冰红茶，因此游戏只有一轮，第二轮就结束了）。

#include
using namespace std;
const int maxn = 1010;
int a[maxn][maxn];
int main(){
    int n, p;  cin>>n>>p;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin>>a[i][j];
    for(int i = 1; i <= n; i++){
        if(i<=n%p)cout<<a[i][i]<<" ";
        else cout<<0<<" ";
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

J.Jellyfish and its dream

链接：https://ac.nowcoder.com/acm/contest/38727/J
来源：牛客网

题目描述
Jellyfish can only long drift throughout their lives as if they have no thoughts of their own. But you know, how we know that jellyfish really have no dreams, right? — S4M, Jellyfish
You are given a 00-indexed array aa of length nn where a_i\in{0,1,2}a
i
​
∈{0,1,2}.

You can perform the operation below:
Choose an index ii such that (a_i+1)\bmod 3=a_{(i+1)\bmod n}(a
i
​
+1)mod3=a
(i+1)modn
​
, then let a_i \gets (a_i+1)\bmod 3a
i
​
←(a
i
​
+1)mod3.

Jellyfish’s dream is to make all elements equal. Check if its dream could be achieved after performing some (possibly zero) operations.
输入描述:
Each test contains multiple test cases. The first line contains the number of test cases TT (1\leq T\leq 10^51≤T≤10
5
). Description of the test cases follows.

The first line contains a single integer nn (2 \leq n \leq 10^62≤n≤10
6
).

The second line contains nn integers a_0,a_1,\ldots,a_{n-1}a
0
​
,a
1
​
,…,a
n−1
​
(0 \leq a_i <30≤a
i
​
❤️).

It is guaranteed that the sum of nn over all test cases does not exceed 10^610
6
.
输出描述:
For each test case, output one line. If all element can be equal after some (possibly zero) operations, print “Yes”, otherwise print “No”.

You can print letters in any case (upper or lower).
示例1
输入
复制
5
2
1 0
3
0 2 1
4
0 1 2 2
5
0 2 1 0 1
6
2 0 2 1 0 1
输出
复制
Yes
No
Yes
No
Yes

题意：

• 给一个序列（n<1e6），值域为0 ∼ 2。
  如果(ai + 1) mod 3 = a[i+1] mod n，就可以将ai 赋值为(ai + 1) mod 3
• 相当于如果a[i+1]比a[i]大1（取模后0比2大1），就可以让a[i]=a[i+1]， 且序列末位循环，a[n]的后一个是a[1]。
• 问有限次操作后是否能使所有元素均相等。

思路：

• 对于去重后的数组，如果a[i]可以+1变成a[i+1]，那么就能形成一个联通块。最终所有相连的块里的元素一定可以相等并变成这个块最右边的元素，且最左边元素的操作次数为块的大小-1。
• 同时对于原本不在块内的与最左边元素相邻的元素，在块中元素像最右边元素迭代的过程中，若次数>3，那么一定会出现一个刚好比左边元素>1的值，此时左边的元素跟块联通到了一起，一起做迭代，依次类推（相邻元素也是，如果存在会被纳入联通块中）。
• 最后整个数组能够联通成为一整个联通块，当且仅当满足a[i]+1=a[i+1]的个数比不满足该条件的个数要多（不在块内的与块内的元素一一抵消），此时输出Yes，否则No即可。

#include
using namespace std;
const int maxn = 2e6+10;
int a[maxn];
int main(){
    ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
    int T;  cin>>T;
    while(T--){
        int n;  cin>>n;
        for(int i = 0; i < n; i++) cin>>a[i];
        int x=0,y=0;
        for(int i = 0; i < n; i++){
            if(a[i]!=a[(i+1)%n]){
                if((a[i]+1)%3==a[(i+1)%n]) x++;
                else y++;
            }
        }
        if(x>=y)cout<<"Yes\n";
        else cout<<"No\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