Shelter
0%

2022牛客多校训练营06

发表于 更新于
详细题解 我与队友一起在比赛 2022牛客多校训练营06 完成的题目

A-Array

来源: 牛客多校训练营6 算法: 构造 补完: Yes 完成时间: August 16, 2022

题解

给定\(≥2\)的正整数\(a_1\sim a_n\), 满足\(\sum_{i=1}^n\frac{1}{a_i}≤\frac12\),

构造一个循环数列, 使得其任意长度为\(a_i\)的子区间都至少包含一个\(i(1≤i≤n)\).

即要求在循环中任意两个\(i\)的距离是小于等于\(a_i\)的

转化原式子

\[ \sum_{i=1}^n\frac{1}{a_i}≤\frac12 \]

为

\[ \sum_{i=1}^n\frac{1}{a_i/2}≤1 \]

对\(a_i\)的不大于其的最大的\(2\)的幂,即

\[ a_i\to2^{\lfloor\log_2a_i\rfloor} \]

有下式总是成立

\[ \frac{a_i}{2}≤2^{\lfloor\log_2a_i\rfloor} \]

故有

\[ \sum_{i=1}^n\frac{1}{2^{\lfloor\log_2a_i\rfloor}}≤1 \]

eg.

\(a_1=3,a_2=12,a_3=24,a_4=24\)

下取整幂

\(a_1=2,a_2=8,a_3=16,a_4=16\)

即为每2步填一个1, 每8步填一个2, 每16步填一个3, 每16步填一个4

12131410121010101

在16个位置里填完所有数后仍有空位.

对想填的所有数有最大幂\(2^k\), 对填入的任意一个数有\(2^l≤2^k\), 这个数会占用\(2^{k-l}\)个位置, 填入的所有数有\(\sum 2^{k-l}\)个,

而 \(\sum 2^{k-l}=2^k\sum\frac1{2^l}\), 且上推出\(\sum_{i=1}^n\frac{1}{2^{\lfloor\log_2a_i\rfloor}}≤1\), 固有

\[ \sum 2^{k-l}≤2^k \]

那么总有空位可以填数

将数据处理为幂次, 排序后构造.

代码

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<bits/stdc++.h>

using namespace std;

const int MAXN = 100005;

int n,lim = MAXN;
int ans[MAXN];
pair<int, int> a[MAXN];

void solve() {
    cin>>n;
    for (int i = 1; i <= n; i++) {
        cin>>a[i].first;
        int t = log2(a[i].first);
        a[i].first  = (1<<t);
        a[i].second = i;
    }
    sort(a+1, a+1+n);
    int k = 1;
    for (int i = 1; i <= n; i++) {
        while (ans[k])k++;
        for (int j = k; j <= lim; j+=a[i].first) {
            ans[j] = a[i].second;
        }
    }
    printf("%d\n",k);
    for (int i = 1; ans[i]; i++) {
        printf("%d ",ans[i]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    // cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}

B-Eezie and Pie

来源: 牛客多校训练营6 算法: DFS, 树上差分 补完: Yes 完成时间: August 12, 2022

题解

有一颗\(n\)个点的树, 结点\(i\)上的食物可以送到从\(i\)走到\(1\)的简单路径上且距离不超过\(d_i\)的结点, 问每个结点都能被送到多少食物.

本题固定了食物只能向根节点方向送, 故考虑树上差分, 只需要在每个点上\(+1\), 并在每个点的第\(d_i\)个祖先上\(-1\)即可.

如何找到第\(d_i\)个祖先呢, 在DFS过程中程序会从上往下遍历, 只要在访问到每个节点的时候记录下来, 得到的就是一条从根结点出发的链, 在路径上即可访问到祖先.当没有那么多祖先时, 就不操作.

代码

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
#include<bits/stdc++.h>

using namespace std;

const int MAXN = 2000005;

vector<int> e[MAXN];
vector<int> d(MAXN);
vector<int> s(MAXN);
vector<int> path;

void dfs(int u,int f){
    path.push_back(u);
    s[u]++;
    s[path[max(-1,(int)(path.size()-2-d[u]))]]--;
    for (auto v: e[u]) {
        if(v==f)continue;
        dfs(v,u);
        s[u] += s[v];
    }
    path.pop_back();
}
void solve() {
    int n;
    cin>>n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    d.push_back(0);
    for (int i = 1; i <= n; i++) {
        cin>>d[i];
    }
    dfs(1,0);
    for (int i = 1; i <= n; i++) {
        cout<<s[i]<<" ";
    }
}

int main() {
    int T = 1;
    // cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}

G-Icon Design

来源: 牛客多校训练营6 算法: 构造, 语法 题目链接: https://ac.nowcoder.com/acm/contest/33191/G 补完: Yes 完成时间: August 6, 2022

题解

画字符画图像,一看\(n≤5\),打表!

代码

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;

string ans[5] = {
{"\
********************************\n\
*..............................*\n\
*..@...@..@@@@@..@......@@@@@..*\n\
*..@@..@..@......@......@......*\n\
*..@.@.@..@@@@@..@......@@@@@..*\n\
*..@..@@..@......@..........@..*\n\
*..@...@..@......@@@@@..@@@@@..*\n\
*..............................*\n\
********************************"},
{"\
*********************************************\n\
*...........................................*\n\
*...........................................*\n\
*...@.....@...@@@@@@@...@.........@@@@@@@...*\n\
*...@@....@...@.........@.........@.........*\n\
*...@.@...@...@.........@.........@.........*\n\
*...@..@..@...@@@@@@@...@.........@@@@@@@...*\n\
*...@...@.@...@.........@...............@...*\n\
*...@....@@...@.........@...............@...*\n\
*...@.....@...@.........@@@@@@@...@@@@@@@...*\n\
*...........................................*\n\
*...........................................*\n\
*********************************************"},
{"\
**********************************************************\n\
*........................................................*\n\
*........................................................*\n\
*........................................................*\n\
*....@.......@....@@@@@@@@@....@............@@@@@@@@@....*\n\
*....@@......@....@............@............@............*\n\
*....@.@.....@....@............@............@............*\n\
*....@..@....@....@............@............@............*\n\
*....@...@...@....@@@@@@@@@....@............@@@@@@@@@....*\n\
*....@....@..@....@............@....................@....*\n\
*....@.....@.@....@............@....................@....*\n\
*....@......@@....@............@....................@....*\n\
*....@.......@....@............@@@@@@@@@....@@@@@@@@@....*\n\
*........................................................*\n\
*........................................................*\n\
*........................................................*\n\
**********************************************************"},
{"\
***********************************************************************\n\
*.....................................................................*\n\
*.....................................................................*\n\
*.....................................................................*\n\
*.....................................................................*\n\
*.....@.........@.....@@@@@@@@@@@.....@...............@@@@@@@@@@@.....*\n\
*.....@@........@.....@...............@...............@...............*\n\
*.....@.@.......@.....@...............@...............@...............*\n\
*.....@..@......@.....@...............@...............@...............*\n\
*.....@...@.....@.....@...............@...............@...............*\n\
*.....@....@....@.....@@@@@@@@@@@.....@...............@@@@@@@@@@@.....*\n\
*.....@.....@...@.....@...............@.........................@.....*\n\
*.....@......@..@.....@...............@.........................@.....*\n\
*.....@.......@.@.....@...............@.........................@.....*\n\
*.....@........@@.....@...............@.........................@.....*\n\
*.....@.........@.....@...............@@@@@@@@@@@.....@@@@@@@@@@@.....*\n\
*.....................................................................*\n\
*.....................................................................*\n\
*.....................................................................*\n\
*.....................................................................*\n\
***********************************************************************"},
{"\
************************************************************************************\n\
*..................................................................................*\n\
*..................................................................................*\n\
*..................................................................................*\n\
*..................................................................................*\n\
*..................................................................................*\n\
*......@...........@......@@@@@@@@@@@@@......@..................@@@@@@@@@@@@@......*\n\
*......@@..........@......@..................@..................@..................*\n\
*......@.@.........@......@..................@..................@..................*\n\
*......@..@........@......@..................@..................@..................*\n\
*......@...@.......@......@..................@..................@..................*\n\
*......@....@......@......@..................@..................@..................*\n\
*......@.....@.....@......@@@@@@@@@@@@@......@..................@@@@@@@@@@@@@......*\n\
*......@......@....@......@..................@..............................@......*\n\
*......@.......@...@......@..................@..............................@......*\n\
*......@........@..@......@..................@..............................@......*\n\
*......@.........@.@......@..................@..............................@......*\n\
*......@..........@@......@..................@..............................@......*\n\
*......@...........@......@..................@@@@@@@@@@@@@......@@@@@@@@@@@@@......*\n\
*..................................................................................*\n\
*..................................................................................*\n\
*..................................................................................*\n\
*..................................................................................*\n\
*..................................................................................*\n\
************************************************************************************"},
    };

void solve() {
    int n;
    cin>>n;
    cout<<ans[n-1];
}

int main() {
    int T = 1;
    // cin>>T;
    while(T--)solve();
    return 0;
}

J-Number Game

来源: 牛客多校训练营6 算法: 数论 题目链接: https://ac.nowcoder.com/acm/contest/33191/J 补完: Yes 完成时间: August 6, 2022

题解

给数字\(A,B,C,x\), 和操作\(B = A-B,C = B-C\),判断能否让\(C==x\)

画图找可能产生的\(C\)值

Geogebra

动画3.gif

\[ C_0=~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~C_0\\ C_1=B_0-C_0= ~~~~~~~~~~~~~~~B_0-C_0\\ C_2=B_1-C_0= ~~~~~A-~~B_0-C_0\\ C_3=B_1-C_1= ~~~~~A-2B_0+C_0\\ C_4=B_0-C_2= -~~A+2B_0+C_0\\ C_5=B_0-C_3= -~~A+3B_0-C_0\\ C_6=B_1-C_4= ~~~2A-3B_0-C_0\\ C_7=B_1-C_5= ~~~2A-4B_0+C_0\\ C_8=B_0-C_6= -2A+4B_0+C_0\\ C_9=B_0-C_7= -2A+5B_0-C_0\\\dots \]

观察化简可得\(x\)通项公式

\[ n(A-2B)+C~~~~~~~~=x\\ n(A-2B)-C+B=x \]

若存在\(n\)使得等式满足即可

\[ n=\frac{x-C~~~~~~~~}{A-2B}\\ n=\frac{x+C-B}{A-2B} \]

注意特判\(A-2B==0\)情况,

公式上此时无法进行除法操作,

物理上此时有\(B_0==B_1\)无法产生新类型的\(C\), 仅存在\(C_0\)和\(C_1\).

代码

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
#include<bits/stdc++.h>
using namespace std;
void solve() {
    int A,B,C,x;
    cin>>A>>B>>C>>x;
    if(A==2*B){
        if(x==C || x==B-C) 
            printf("Yes\n");
        else 
            printf("No\n");
    }
    else {
        if((x-C)%(A-2*B)==0 || (x-B+C)%(A-2*B)==0) 
            printf("Yes\n");
        else 
            printf("No\n");
    }
}

int main() {
    int T = 1;
    cin>>T;
    while(T--)solve();
    return 0;
}