前行 - AtCoder Beginner Contest 133

前40分钟码完了前五题……最后还是没做出 F 题 TAT

也是第一次接触离线算法。听说 F 题可以用 树上莫队 和 主席树 做,但是我还没写,写完了如果能够记起来就再把博客补一下吧


· A题:T or T

- 题意

$n$ 个人出去旅行,可以选择以下方式:

  1. $n$ 个人都坐火车,每人会花费 $A$ 日元;
  2. $n$ 个人全部坐出租车,总共会花费 $B$ 日元;
    求最小花费。
    ($1\leq n\leq 20,1\leq A,B\leq 50$)
【点击展开/收起样例
Input 4 2 9 4 2 7
Output 8 7

(无解析可言)

- 源代码

【点击展开/折叠代码
1
2
3
4
5
6
7
8
9
10
11
12
13
/*Lucky_Glass*/
#include<map>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
int n,a,b;
scanf("%d%d%d",&n,&a,&b);
printf("%d\n",min(b,a*n));
return 0;
}

· B题:Good Distance

- 题意

定义在 $D$ 维空间的两点 $X=(x_1,x_2,x_3,…,x_D),Y=(y_1,y_2,y_3,…,y_D)$ 的距离为 $\sqrt{(x_1-y_1)^2+(x_2-y_2)^2+…+(x_D-y_D)^2}$。
给定 $D$ ,给出 $N$ 个 $D$ 维的点,求有多少对不同的点的距离是整数。
($2\leq N\leq 10,1\leq D\leq10$,保证坐标的绝对值不超过 $20$)

【点击展开/收起样例
Input 3 2
1 2
5 5
-2 8
3 4
-3 7 8 2
-12 1 10 2
-2 8 9 3
Output 1 2

(直接模拟,无解析可言)

- 源代码

【点击展开/折叠代码
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
/*Lucky_Glass*/
#include<map>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10;
int n,d;
int pos[N+5][N+5];
int main(){
scanf("%d%d",&n,&d);
for(int i=1;i<=n;i++){
for(int j=1;j<=d;j++)
scanf("%d",&pos[i][j]);
}
int ans=0;
for(int u=1;u<=n;u++)
for(int v=u+1;v<=n;v++){
int tot=0;
for(int i=1;i<=d;i++)
tot+=(pos[u][i]-pos[v][i])*(pos[u][i]-pos[v][i]);
double _tot=sqrt(tot);
long long A=(long long)ceil(_tot),B=(long long)floor(_tot);
if(A*A==tot || B*B==tot)
ans++;
}
printf("%d\n",ans);
return 0;
}

· C题:Remainder Minimization 2019

一开始这道题吓了我一跳……

- 题意

给定 $L,R$ ,求对于 $i,j\in[L,R] 且 i\not=j$ ,$i\times j\bmod 2019$ 的最小值。

($0\leq L<R\leq2\times 10^9$)

【点击展开/收起样例
Input 2020 2040 2000 2020
Output 2 0
Explain i=2020,j=2021 i=2019,j=2020

- 解析

显然如果 $[L,R]$ 中存在 $2019$ 的倍数,那么 $i$ 取该数,$j$ 随便取,就可以使 $ij\bmod 2019=0$,这样当然是最小的。

考虑另外的情况——也就是 $[L,R]$ 中没有 $2019$ 的倍数……由于 $[L,R]$ 是一段连续的整数,如果没有 $2019$ 的倍数,那么……$[L,R]$ 中岂不是最多只有 $2018$ 个数?
(Right) 这么小的范围直接枚举就好了嘛。

- 源代码

【点击展开/折叠代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*Lucky_Glass*/
#include<map>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int main(){
ll L,R;
scanf("%lld%lld",&L,&R);
if((L-1)/2019!=R/2019){
printf("0\n");
return 0;
}
ll ans=2019;
for(ll i=L;i<=R;i++)
for(ll j=i+1;j<=R;j++)
ans=min(ans,i*j%2019);
printf("%lld\n",ans);
return 0;
}

· D题:Rain Flows into Dams

一开始没看到 $N$ 是奇数,卡了一小会

- 题意

有 $N$ 座山围成环(第1座山的旁边是第N座和第2座),第 $i$ 座山和第 $(i+1)$ 座山之间是河流 $i$ (第 $N$ 座和第 $1$ 座之间是河流 $N$)。
如果第 $i$ 座山降了 $D_i$ 升雨,则它相邻的两条河流会分别涨水 $\frac {D_i}2$ 升。
现在给出第 $i$ 条河流涨了多少水,求出每座山各下了多少雨。
保证N是奇数,$3\leq N<10^5$,河流的涨水量不超过 $10^9$)

【点击展开/收起样例
Input 3
2 2 4
Output 4 0 4

- 解析

设第 $i$ 座山下了 $x_i$ 的雨,第 $j$ 条河流涨了 $y_j$ 的水。于是我们可以列方程——

接下来就是消元了——由 $(1)-(2)+(3)-…-(N-1)+(N)$ 可得:

解出 $x_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
/*Lucky_Glass*/
#include<map>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5;
int n;
ll cur;
ll t[N+5],x[N+5];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&t[i]),
cur+=(i%2? 1:-1)*2ll*t[i];
x[1]=cur/2;
for(int i=1;i<n;i++)
x[i+1]=2*t[i]-x[i];
for(int i=1;i<=n;i++)
printf("%lld%c",x[i],i==n? '\n':' ');
return 0;
}

· E题:Virus Tree 2

- 题意

给出一个 $N$ 个节点的树以及 $K$ 种不同的颜色,你需要给树的每个节点上色,使得任何距离小于等于 $2$ 的两不同点的颜色不同。求方案数模 $(10^9+7)$。
($1\leq N,K\leq 10^5$)

【点击展开/收起样例
Input 4 3
1 2
2 3
3 4
5 4
1 2
1 3
1 4
4 5
Output 6 48

- 解析

考虑树上的一部分:

img1

可以想到 V1,V2,…,Vt 总共可以取 $K-2$ 种颜色(也就是不能和 U,P 重复)。如果我们把给 V1,V2,…,Vt 涂色分步骤——也就是先涂 V1,再涂 V2,…,最后涂 Vt;

那么可以想到,V1 可以涂 $(K-2)$ 种颜色(不能和 P,U 相同);V2 可以涂 $(K-3)$ 种颜色 (不能和 P,U,V1)相同;…;Vt 可以涂 $(K-t-1)$ 种颜色。

但是根节点比较特殊,如果 U 是根节点,就不存在 P。特判即可。根据乘法原理乘起来即可

- 源代码

【点击展开/折叠代码
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
/*Lucky_Glass*/
#include<map>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5;
const ll MOD=ll(1e9)+7;
int n;
ll ans,col;
vector<int> lnk[N+5];
void DFS(int u,int pre,int dep){
int cnt=0;
for(int it=0;it<lnk[u].size();it++){
int v=lnk[u][it];
if(v==pre) continue;
if(dep==1) ans=ans*max(0ll,col-1-cnt)%MOD;
if(dep>=2) ans=ans*max(0ll,col-2-cnt)%MOD;
DFS(v,u,dep+1);
cnt++;
}
}
int main(){
scanf("%d%lld",&n,&col);
for(int i=1;i<n;i++){
int u,v;scanf("%d%d",&u,&v);
lnk[u].push_back(v);
lnk[v].push_back(u);
}
ans=col%MOD;
DFS(1,0,1);
printf("%lld\n",ans);
return 0;
}

· F题:Colorful Tree

- 题意

给出一个有 $N$ 个节点的树,树的第 $i$ 条边有颜色 $c_i$ 和长度 $d_i$。
现给出 $Q$ 个询问,每个询问给出 $x,y,u,v$ :即如果将树上所有颜色为 $x$ 的边的长度改为 $y$ ,求 $u$ 到 $v$ 的简单路径的长度。
($2\leq N\leq 10^5,1\leq Q\leq 10^5,1\leq c_i<N,1\leq d_i\leq 10^4,1\leq y\leq 10^4$)

【点击展开/收起样例
Input 5 3
1 2 1 10
1 3 2 20
2 4 4 30
5 2 1 40
1 100 1 4
1 100 1 5
3 1000 3 4
Output 130
200
60

- 解析

= 求解答案

令树的根是 rt ,记 uv 的LCA为 lca ,那么我们可以计算出路径 (u,v)=(u,rt)+(v,rt)-2*(lca,rt),也就是说任意两点的路径信息都可以用点到根节点的路径的信息。

那么我们需要储存路径的什么信息?对于每个询问,我们需要知道路径(u,v)上颜色为 $x$ 的边的总长度collen数量colcnt,以及路径 (u,v) 在未修改时的长度totlen——那么我们可以计算出修改后路径 (u,v)=totlen-collen+colcnt*y(也就是在原路径中删除颜色为 $x$ 的边,再把原来 colcnt 条颜色为 $x$ 的边的长度都改为 $y$ 加入路径中)。

但是颜色、询问和节点数都是 $10^5$ ,如果每个点都储存一个从它到根节点的路径的信息,是显然存不下的……

于是……

= 离线处理

由于 LCA 是 $O(\log n)$ (甚至离线还可以 $O(n)$,但是我不想写),我们想到可以先用 $O(Q\log n)$ 的时间复杂度把 $u,v,lca$ 都打一个标记。即对于第 i 个查询,在查询的 u,v 处分别打一个第 i 查询的标记 1,表示查询 i 的答案的一部分是需要加上路径 (u,rt),(v,rt) 的信息;在 lca 处打第 i 查询的标记2,表示查询 i 的答案的另一部分是减去两倍路径 (lca,rt) 的信息。

于是这样就实现了离线处理——

有什么作用呢?最显著的影响就是极大节省了内存:我们只需要在 DFS 时维护当前节点到 rt 的路径的信息就可以了。

em……详见代码……

- 源代码

【点击展开/折叠代码
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
/*Lucky_Glass*/
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5;
struct EDGE{int u,v,col,len;}edg[N+5];
struct QUERY{int col,id,mdy,tag;};
vector<int> lnk[N+5];
vector<QUERY> qry[N+5];
int fa[N+5][20],dep[N+5],ans[N+5];
int n,m;
void Process(int u,int pre){
fa[u][0]=pre;dep[u]=dep[pre]+1;
for(int i=1;i<20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=0;i<lnk[u].size();i++){
int v=edg[lnk[u][i]].u==u? edg[lnk[u][i]].v:edg[lnk[u][i]].u;
if(v==pre) continue;
Process(v,u);
}
}
int totfar,colcnt[N+5],collen[N+5];
void DFS(int u,int pre){
for(auto it : qry[u])
ans[it.id]+=it.tag*(totfar-collen[it.col]+colcnt[it.col]*it.mdy);
for(int i=0;i<lnk[u].size();i++){
int v=edg[lnk[u][i]].u==u? edg[lnk[u][i]].v:edg[lnk[u][i]].u;
if(v==pre) continue;
totfar+=edg[lnk[u][i]].len;
colcnt[edg[lnk[u][i]].col]++;
collen[edg[lnk[u][i]].col]+=edg[lnk[u][i]].len;
DFS(v,u);
totfar-=edg[lnk[u][i]].len;
colcnt[edg[lnk[u][i]].col]--;
collen[edg[lnk[u][i]].col]-=edg[lnk[u][i]].len;
}
}
int LCA(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
for(int i=19;i>=0;i--)
if(dep[fa[u][i]]>=dep[v])
u=fa[u][i];
if(u==v) return u;
for(int i=19;i>=0;i--)
if(fa[u][i]!=fa[v][i])
u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++){
int u,v,col,len;scanf("%d%d%d%d",&u,&v,&col,&len);
edg[i]=(EDGE){u,v,col,len};
lnk[u].push_back(i);lnk[v].push_back(i);
}
Process(1,0);
for(int i=1;i<=m;i++){
int u,v,col,len;
scanf("%d%d%d%d",&col,&len,&u,&v);
int lca=LCA(u,v);
qry[u].push_back((QUERY){col,i,len,1});
qry[v].push_back((QUERY){col,i,len,1});
qry[lca].push_back((QUERY){col,i,len,-2});
}
DFS(1,0);
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ,欢迎提问~

0%