2015 Multi-University Training Contest 2 Solutions

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


 

 

1002 Buildings

HDU 5301:http://acm.hdu.edu.cn/showproblem.php?pid=5301
题意:有一个n*m的大矩阵,其中有一个1*1的坏格,求用若干个小矩阵去覆盖大矩阵,坏格不能被覆盖。问小矩阵中面积最大的面积最小是多少。给出n,m以及坏格的位置x,y

 

如果没有坏格,那么答案应该是 \(ans'=(min(m,n)+1)/2\)

有了坏格就要考虑坏格周围的4个格子是否能被覆盖到

交换 \(n,m\) 使 \(n\leqslant m\) ,并把坏格装换到矩阵左上角

那么需要被覆盖的就是坏格下方的那个格子,只要它能被覆盖,那么其他4个格子也一定能被覆盖。

同时要注意 \(ans\) 的长度不会超过 \((m+1)/2\) 。那么 \(ans=min((m+1)/2,max(ans',min(n-x,y)))\)

特殊情况:当大矩阵为正方形,且坏格位于方形中心时, \(ans=ans'-1\)

 

 


 

 

1004 Delicious Apples

HDU 5303:http://acm.hdu.edu.cn/showproblem.php?pid=5303

题意:在一个长为L的环形路上有n个苹果数,坐标为0的位置为起点。分别给出了苹果树距离起点的长度 \(x_i\) (顺时针)和苹果数量 \(a_i\) ,现在有一个最多能装 \(k\) 个苹果的篮子,从起点出发,往返摘取苹果,问最短的行走距离。

\(1\leqslant n ,k\leqslant 10^5,1\leqslant L\leqslant 10^9\)

 

如果将环路从 \(\frac{L}{2}\) 处断开,那么便可以左右分别贪心求出最小的 \(ans\)

但因为是环形,就要考虑一种特殊情况,可能需要绕整个环一周。因为左右两边贪心完后可能剩下小于 \(k\) 个的苹果(如果剩下大于 \(k\) 个,那么大于那部分走半边就可以摘取),对于这种情况特殊处理,然后取最小值。

PS:注意用__int64

 

 


 

 

1006 Friends

HDU 5305:http://acm.hdu.edu.cn/showproblem.php?pid=5305

题意:n个人m对朋友,对于每对朋友可以选择成为线上朋友或者线下朋友,但要求每人的线上朋友数等于线下朋友数,问有多少种选择方法

\(1\leqslant n\leqslant 8\)

 

当n=8时, \(\frac{8\times7}{2}=28\) 条边,如果直接暴力枚举的话需要枚举 \(2^{28}\approx10^8\) 次,明显会TLE

考虑剪枝,如果枚举的时候考虑当前边的两点,不让点的某一种朋友数超过点度数的 \(\frac{1}{2}\) ,便会节省掉很大一部分时间。

 

 


 

 

1007 Gorgeous Sequence

HDU 5306:http://acm.hdu.edu.cn/showproblem.php?pid=5306
题意:一个长度为n的序列a,定义三种操作:

0 x y t: 对于 \(x\leqslant i \leqslant y\) ,令 \(a_i=min(a_i,t)\)

1 x y: 输出区间 \([x,y]\) 内的最大值

2 x y: 输出区间 \([x,y]\) 内的数的和

 

线段树区间合并

用一个cover数组去记录lazy标记影响了多少个数

用平时的输入外挂还过不了。。贴一个标程的输入外挂

 

 

AC代码

 

 


 

 

1009 I Wanna Become A 24-Point Master

HDU 5308:http://acm.hdu.edu.cn/showproblem.php?pid=5308
题意:给n个整数n,用“+”,“-”,“*”,“/”,括号凑24点。

\(1\leqslant n\leqslant 10^5\)

 

对于 \(n<15\) 时可以打表:

\(n\leqslant 3,\) 无解

\(n=4,4*4+4+4=24\)

\(n=5,(5-\frac{\frac{5}{5}}{5})\times 5=24\)

\(n=6,6+6+6+6=24\)

\(n=7,\frac{7\times7-\frac{7}{7}}{7+7}\times7=24\)

\(n=8,8+8+8=24\)

\(n=9,9+9+9-\frac{9}{9}-\frac{9}{9}-\frac{9}{9}=24\)

\(n=10,10+10+\frac{10+10}{10}+\frac{10+10}{10}=24\)

\(n=11,11+11+\frac{11+11}{11}=24\)

\(n=12,12+12=24\)

\(n=13,13+13-\frac{13+13}{13}=24\)

\(n=14,14+14-\frac{14+14}{14}-\frac{14+14}{14}=24\)

对于 \(n\geqslant 15\)

\(\frac{n+n}{n}*\frac{n+n}{n}*\frac{n+n}{n}*\frac{n+n+n}{n}=24\)

对于多余的n可以用两个n相减得0,在把多余的n乘掉。

 

 


 

(待续。。。)

Categories: ACM