2015 Multi-University Training Contest 3 Solutions

官方题解:2015 Multi-University Training Contest 3 solutions BY ZSTU


 

 

1002 RGCDQ

HDU 5317:http://acm.hdu.edu.cn/showproblem.php?pid=5317
题意:定义 \(F(x)\) 为x的质因数个数。现有T次询问,每次询问区间 \([L,R]\) 内的 \(maxGCD(F(i),F(j))(L\leqslant i < j \leqslant R)\)
\(1\leqslant T \leqslant 10^6, 2\leqslant L < R \leqslant 10^6 \)

打表发现 \(F(x)\) 的最大值只有7,可以先预处理出所有 \(F(x)\) 的值
在算出所有 \(dp[i][j]\) ,表示前 \(i\)\(F(x)\) 中有多少个 \(j\)
区间 \([L,R]\)\(F(x)=j\) 的个数 \(cnt[j]=dp[R][j]-dp[L-1][j]\)

\(maxGCD\) 只需要找出最大的 \(p\) 满足 \(cnt[p]\geqslant 2\)
注意 \(p=3\) 时,为 \(cnt[3]+cnt[6]\geqslant 2\)
\(p=2\) 时,为 \(cnt[2]+cnt[4]+cnt[6]\geqslant 2\)

 

 


 

 

 

1004 Painter

HDU 5319:http://acm.hdu.edu.cn/showproblem.php?pid=5319
题意:在一个高度为n的画板上,可以沿斜率为-1的直线涂红色,沿斜率为1的直线涂蓝色,当一个格子被同时涂上红色和蓝色会变成绿色,每个格子只能被同种颜色涂一次,给出涂色后画板的状态,询问最少的涂色次数
\( 1\leqslant n \leqslant 50\)

模拟

分别处理红色和蓝色的涂色情况,绿色的既当做红色,也当做蓝色

注意下面这种情况:
R...
.R..
....
...R
答案是为2

 

 


 

 

 

1008 Solve this interesting problem

HDU 5323:http://acm.hdu.edu.cn/showproblem.php?pid=5323
题意:找到最小的 \(n\) 使根节点为 \([0,n]\) 的线段树存在节点 \([L,R]\)
\( 1\leqslant L\leqslant R\leqslant 10^9, \frac {L} {R-L+1}\leqslant 2015 \)

DFS
\(len=R-L+1\)
节点 \([L,R]\) 的父节点有四种情况:

\([L,R+len],[L,R+len-1],[L-len,R],[L-len-1,R]\)

通过搜索即可找出根节点

 

 


 

 

 

1011 Work

HDU 5326:http://acm.hdu.edu.cn/showproblem.php?pid=5326
题意:询问一颗节点数为n的树上子孙节点数为k的节点有多少个
\(1\leqslant n \leqslant 10^2 \)

DFS,回溯时计算子孙节点

 

 


 

 

(待续...)

Categories: ACM