2022牛客暑期多校训练营6(总结+补题)

总结

上把刚成为打的最差的一把，这把就忽然猛起来了，开局队友2速推式子，24分钟过了 $J$ ，我也一眼丁真用树剖+小操作过了 $B$ ，队友2又写了一会模拟过了 $G$ ，然后我们三个就一起讨论 $M$ ，讨论了一个多小时后将 $M$ 的所有情况大概整理出来了，队友1，2 就开始写，写好我们又互相hack了一下，一发过了 $M$ ，由于这把签得太快，我们陷入了无题可做的境地，此时看 $A$ 过的人有点多，草草读了下题后我和队友1觉得不可做，但队友2觉得他可以，遂把 $A$ 丢给队友2，我和队友1开启了挂机模式，243分钟时，队友2第二发 $AC$ 了，五题结束。（撒花）

题解

B - Eezie and Pie

题意：

给你一棵 $n-1$ 条边组成的树，你要从每个点开始做 $n$ 次操作，每次操作将当前点到根结点 $1$ 之间简单路径上与点 $i$ 距离小于等于 $d_i$ 的点的点权 +$1$ ，输入做完 n 次操作后每个点的点权是多少。

做法：

由于这里涉及到树上链的区间操作，我们很自然的能够想到树链剖分，那么我们可以考虑对于每个点找到他与根结点 $1$ 的简单路径中与该点距离为 $d_i$ (若点 $i$ 与 $1$ 的距离大于 $d_i$ ，则为 $1$ )，这里我们可以使用dfs，维护一个类似栈的数组，对于每个 i ，我们假设 i 在当前数组中的位置为 idx ，则数组中的元素 $point=a[max(0,idx-d_i)]$ 即为所求，找到这个父节点之后我们再使用树剖中链的区间修改操作即可，最后再逐个将点的值输出。复杂度为 $O(nlo{g}^{2}n)$

代码：

/*
 author:wuzx
 */

#include
#define ll long long
#define endl "\n"
#define P pair<int,int>
#define f first
#define s second
using namespace std;
const int inf = 0x3f3f3f3f;
int t;
int n,m,k;
const int maxn = 2000010;
int w[maxn];
struct slpf{
    const int nn;
    struct node{
        int l,r,tag;
        int val;
    };
    vector<node> tr;
    vector<int> fa,dep,son,siz,top,dfn;
    vector<vector<int>> g;
    vector<int> num1;
    int tim;
    slpf(int n1):nn(n1),tr((n1+10)*4),fa(n1+1),dep(n1+1),son(n1+1,0),siz(n1+1),top(n1+1),dfn(n1+1),g(n1+1),tim(0){}
    void add(int uu,int vv)
    {
        g[uu].push_back(vv);
        g[vv].push_back(uu);
    }
    void dfs1(int now,int fr)
    {
        fa[now]=fr;
        dep[now]=dep[fr]+1;
        siz[now]=1;
        int max_size=-1;
        for(int x:g[now])
        {
            if(x==fr)
                continue;
            dfs1(x,now);
            siz[now]+=siz[x];
            if(siz[x]>max_size)
            {
                max_size=siz[x];
                son[now]=x;
            }
        }
    }
    void dfs2(int now,int tp)
    {
        dfn[now]=++tim;
        top[now]=tp;
        if(!son[now])
            return;
        dfs2(son[now],tp);
        for(int x:g[now])
        {
            if(x==fa[now]||x==son[now])
                continue;
            dfs2(x,x);
        }
    }
    void build(int root,int l,int r)//根节点为1，范围从1-n
    {
        tr[root].l=l;
        tr[root].r=r;
        tr[root].tag=0;//add的初始值为0
        if(l==r)
        {
            tr[root].val=0;//初始值
            return;
        }
        int mid=(l+r)/2;
        build(root*2,l,mid);
        build(root*2+1,mid+1,r);
        tr[root].val=tr[root*2].val+tr[root*2+1].val;
    }
    void spread(int p)
    {
        if(tr[p].tag!=0)
        {
            tr[p*2].val+=tr[p].tag*(tr[p*2].r-tr[p*2].l+1);
            tr[p*2+1].val+=tr[p].tag*(tr[p*2+1].r-tr[p*2+1].l+1);
            tr[p*2].tag+=tr[p].tag;
            tr[p*2+1].tag+=tr[p].tag;
            tr[p].tag=0;
        }
    }
    void update(int root,int l,int r,int x)
    {
        if(l<=tr[root].l&&r>=tr[root].r)
        {
            tr[root].val+=x*(tr[root].r-tr[root].l+1);
            tr[root].tag+=x;
            return;
        }
        spread(root);
        int mid=(tr[root].l+tr[root].r)>>1;
        if(l<=mid)
            update(root*2,l,r,x);
        if(r>mid)
            update(root*2+1,l,r,x);
        tr[root].val=tr[root*2].val+tr[root*2+1].val;
    }
    int getsum(int root,int l,int r)
    {
        if(l<=tr[root].l&&r>=tr[root].r)
            return tr[root].val;
        spread(root);
        int mid=(tr[root].l+tr[root].r)>>1;
        int ans=0;
        if(l<=mid)
            ans=(ans+getsum(root*2,l,r));
        if(r>mid)
            ans=(ans+getsum(root*2+1,l,r));
        return ans;
    }
    void update_son(int x,int z)//x为根结点的子树所有节点值+z
    {
        update(1,dfn[x],dfn[x]+siz[x]-1,z);
    }
    int query_son(int x)//x为根结点的子树所有节点值之和
    {
        return getsum(1,dfn[x],dfn[x]+siz[x]-1);
    }
    void update_chain(int x,int y,int z)
    {
        while(top[x]!=top[y])
        {
            if(dep[top[x]]<dep[top[y]])
                swap(x,y);
            update(1,dfn[top[x]],dfn[x],z);
            x=fa[top[x]];
        }
        if(dep[x]>dep[y])
            swap(x,y);
        update(1,dfn[x],dfn[y],z);
    }
    int query_chain(int x,int y)
    {
        int res=0;
        while(top[x]!=top[y])
        {
            if(dep[top[x]]<dep[top[y]])
                swap(x,y);
            res+=getsum(1,dfn[top[x]],dfn[x]);
            x=fa[top[x]];
        }
        if(dep[x]>dep[y])
            swap(x,y);
        res+=getsum(1,dfn[x],dfn[y]);
        return res;
    }
    void dfs3(int now,int fa)//dfs，On找出所有点距离di的父节点
    {
        num1.push_back(now);
        int sz=num1.size();
      	//找到后直接使用树剖的区间修改将链中的点+1
        if(sz<=w[now])
            update_chain(now,num1[0],1);
        else
            update_chain(now,num1[sz-1-w[now]],1);
        for(int x:g[now])
        {
            if(x==fa)
                continue;
            dfs3(x,now);
        }
        num1.pop_back();
    }
    void make_tree(int root)
    {
      	//长链剖分+建树
        dfs1(root,root);
        dfs2(root,root);
        build(1,1,nn);
      	//dfs求父节点并区间修改
        dfs3(root,root);
      	//输出答案
        for(int i=1;i<=n;i++)
            cout<<query_chain(i,i)<<" ";
    }
};
signed main()
{   
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    int u,v;
    slpf tr(n);
    for(int i=1;i<n;i++)
    {
        cin>>u>>v;
        tr.add(u,v);
    }
    for(int i=1;i<=n;i++)
        cin>>w[i];
    tr.make_tree(1);
    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
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

G - Icon Design

小模拟题，直接手动把五个形状画好就行。代码略。

J - Number Game

题意：

给你三个数 $ABC$ ,你可以做以下任意操作任意次，问是否能将 $C$ 变成 $x$

操作一：将 $B$ 变成 $A-B$

操作二：将 $C$ 变成 $B-C$

做法：

我们手推一下可以看出，$B$ 只能变成 $A-B$ 或 $B$ 这两种情况，而 $C$ 也只能变成 $B-C$ 和 $C$ ，因此要想让每次操作过后的数都不同，必须将两种操作交替进行，若操作 $1$ 和操作 $2$ 使用的次数相同，则 C 能变成的集合为 $S=\left {x|x=C+K\times(A-2\times B) \right } $ ，若操作 $1$和操作 $2$ 的次数不相同，则 $C$ 能变成的集合为 $S=\left {x|x=B-C+K\times(A-2\times B) \right } $ ，注意：当 $A=2\times B$ 时，直接判断 $C$ 和 $B-C$ 即可。

代码：

/*
 author:wuzx
 */

#include
#define ll long long
#define int long long
#define endl "\n"
#define P pair<int,int>
#define f first
#define s second
using namespace std;
const int inf = 0x3f3f3f3f;
int t;
int n,m,k;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        int a,b,c,x;
        cin>>a>>b>>c>>x;   
        if(a==2*b)
        {
            if(c==x||x==b-c)
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
        else if((x-c)%(a-2*b)==0)
            cout<<"Yes"<<endl;
        else if((x-b+c)%(a-2*b)==0)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    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