2015 Multi-University Training Contest 4 Solutions

官方题解:2015 Multi-University Training Contest 4 solutions BY 学军中学


 

 

1001 Olympiad

HDU 5327:http://acm.hdu.edu.cn/showproblem.php?pid=5327
题意:每次询问 \([a,b](a\leqslant b)\) 中有多少个 beautiful number, beautiful number指每位数字不同
\(1\leqslant T\leqslant 1000,1\leqslant a\leqslant b\leqslant 10^5\)

因为范围比较小,可以直接暴力预处理出[1,n]内beautiful number的数量。
[a,b]=[1,a]-[1,b-1]

 

 


 

 

 

1002 Problem Killer

HDU 5328:http://acm.hdu.edu.cn/showproblem.php?pid=5328
题意:求出最长的等差数列和等比数列,答案取两者长度大的
\(1\leqslant n\leqslant 10^6\)

随便YY一发就能过。

 

 


 

 

 

1007 Virtual Participation

HDU 5334:http://acm.hdu.edu.cn/showproblem.php?pid=5334
题意:知道一个序列的不同的连续字串个数K,求构造满足K的任意一个序列
\(1\leqslant K\leqslant 10^9\) ,序列长度 \(1\leqslant K\leqslant 10^5\)

因为序列长度 \(n\) 的最大范围小于 \(K\) ,所以不能用全填 \(1\) 的方法

如果序列为这种形式: \(1,\cdots ,1,2\cdots,2,3,\cdots,3,\cdots,t\)
\(n\) 为序列长度, \(L_i\) 为数 \(i\) 出现的次数,那么序列的不同的连续字串个数

\[K=\frac{n^2+n-\sum_{i=1}^{t}L_i(L_i-1)}{2}\]

可以列出下面的方程

\[\left\{\begin{matrix}\sum_{i=1}^{t}L_i(L_i-1)=n^2+n-2k\\ \sum_{i=1}^{t}L_i=n\end{matrix}\right.\]

\(\sum_{i=1}^{t}L_i(L_i-1)=d\) ,那么可以用二分找出最大的 \(p\) 使 \(p(p-1)\leqslant d\) ,然后 \(L_1\) 可以取 \(p\)
此时另 \(d=d-p(p-1)\) ,又可以用上面的方法求出所有 \(L_i\) 。因为 \(d\) 一定为偶数,所以最后一定能让 \(d=0\)
因为 \(d=n^2+n-2k\) ,所以需要用二分找到最小的 \(n\) 满足 \(n^2+n-2k\geqslant 0\)
如果最后满足 \(\sum_{i=1}^{t}L_i=n \) ,那么便是一个解。
通过打表发现不满足的只有 \(k=4\)\(k=16\) 时,对于这两组直接全输出1就行

 

 


 

 

 

1010 XYZ and Drops

HDU 5336:http://acm.hdu.edu.cn/showproblem.php?pid=5336
题意:在一个c*r的格子里,有一些水滴。一个大小大于4的水滴会向4个方向(上下左右)分裂成4个小水滴。小水滴会一直沿分裂方向运动,直到遇到水滴,使水滴大小加1,小水滴消失。现在给出一些水滴的坐标和大小。并在0s时在(x,y)处有一个水滴分裂。问Ts时所有水滴的状态
\( 1\leqslant r \leqslant100, 1\leqslant c\leqslant 100, 1\leqslant n\leqslant 100, 1\leqslant T\leqslant 10000 \)

因为数据范围较小,可以直接模拟整个过程。

有三点需要注意:
1、无论分裂前的水滴大小是多少,分裂后小水滴的大小始终是为1的。
2、0s时注意判断是否有水滴大小大于4,这些水滴在0s分裂。
3、水滴分裂后及时清除水滴的标记,此时水滴已经不存在

 

 


 

 

(待续...)

Categories: ACM