首页 > ACM题库 > HDU-杭电 > HDU 4769-Sword-分治-[解题报告]HOJ
2015
09-17

HDU 4769-Sword-分治-[解题报告]HOJ

Sword

问题描述 :

Satoshi, who has strong obsessions with Chinese domestic RPG, will never miss the marvelous game, Gu Jian Qi Tan II, a.k.a., the Legend of Ancient Sword II, because of its gorgeous graphics, picturesque characters and lively design.

Recently, Satoshi has some troubles in the new battle mode of the game, and seeks you for help to solve the problems.

Specifically, in the new instant-action mode, Satoshi can control N roles, and his goal is to kill all M tiny monsters to declare victory. The tiny monsters are too fragile to survive from any skills of any roles. In every second, Satoshi can choose to operate one single role once, or do nothing. However, to make his series of operations magnificent, he would not use same role in any two consecutive seconds, i.e., the role used in i-th second cannot be used in the (i+1)-th second anymore.

For each role, we know the number of skills he/she owns, as well as the LPT (loop time) of each skill, which indicates that the skill could be performed in every LPT seconds starting from the beginning (e.g., if the LPT of a skill is 3, Satoshi could cast the skill at 3s, 6s, 9s, …, so on and so forth). Moreover, the information of whether a skill can reach (touch) a certain monster is also provided (i.e., whether a monster is within the attacking range of a specific skill). Your task is to help Satoshi use the minimum amount time to win the game; ties are broken by preferring fewer number of operations, which is counted by the number of seconds in which Satoshi chooses to operate a role instead of doing nothing.

Note that Satoshi could choose a certain role, and of course no roles, in a specific second. And when he operates a role in a specific second, he can cast all the available skills (subject to the the LPT constraints) if he wants. Time begins with the 1st second.

输入:

The integer R in the first line of input indicates the total number of test cases. For each test case, there are two integers N (1 <= N <= 10) and M (1 <= M <= 200) as stated above, in the first line. Then N blocks of input follow. For the i-th block, the first line contains an integer S_i (1 <= S_i <= 300) denoting the number of skills that the i-th role owns. Each of the the next S_i lines in the i-th block has M+1 integers, i.e., the LPT (1 <= LPT <= 6) of the i-th role, and M Boolean values (0/1) where the j-th Boolean value indicates if the j-th monster is within the attacking range of the i-th role.

输出:

The integer R in the first line of input indicates the total number of test cases. For each test case, there are two integers N (1 <= N <= 10) and M (1 <= M <= 200) as stated above, in the first line. Then N blocks of input follow. For the i-th block, the first line contains an integer S_i (1 <= S_i <= 300) denoting the number of skills that the i-th role owns. Each of the the next S_i lines in the i-th block has M+1 integers, i.e., the LPT (1 <= LPT <= 6) of the i-th role, and M Boolean values (0/1) where the j-th Boolean value indicates if the j-th monster is within the attacking range of the i-th role.

样例输入:

4

1 1
1
1 1

1 1
1
3 1

2 2
2
1 1 0
2 1 0
1
1 1 0

1 2
3
2 1 0
5 0 1
6 1 1

样例输出:

1 1
3 1
0
5 2

本来只想出个中等难度题, 在题意上绕一下, 没想到到了网络赛的时候竟然没有队伍ac, 

而且全场也只有2个队伍北大,华南师范尝试过提交,

就连4小时就已经10题的清华都没在最后1小时有提交(估计他们10题之后就出去玩耍了吧),

师弟直接给我个称号防ak题制造者

——————————————————————————————

题意及题意描述改了7、8遍了。。。想出道题真心不容易。。。

————————吐槽分割线—————————————————

因为最多有6s的技能cd,10个角色,可以推断最坏情况下60秒就可以覆盖所有的角色的所有技能(下面给出简单证明),

也就是说前60秒的操作如果都不能打败所有boss,说明一定是无解的了。所以我们只需解出最多前60秒的情况,

二分时间+暴力验证,验证的时候直接搜索最优解(也可以求出二分出最小时间后在求最有解),可以用Dancing Links X (当然解法也很多)

 

(t, k)行,列时间冲突的约束,以及同一角色不再相邻时间出现的约束。

T*K时间的列,同一时间只能操作同一英雄,精确覆盖(部分覆盖), Link((t,k), (t,k))不允许冲突。

英雄控制相邻时间, (T*K)  Link((t, k), (t,k+1)).   

(m1+sigma(p1…pm2))列,怪物的列重复覆盖。  

t, k  能够打的boss  遍历所有完全覆盖的重复覆盖列数的解,求得最小值即可。

 

这里可以简单证明下,要某个角色所有技能,显然要找个一个时间集合,其中要包括能整除1,2,3,4,5,6的数,那么我们就是要在1~60找到10个这样的不相交集合

其中1 2 3 是6的因子,只需考虑4, 5, 6

将6,12,18……60 分到10个集合里,除了这些数之外,还有60*(6-1)/6/5个5的整数倍数,(嗯,实际上只需要8个,),这些数考虑差大于一这个条件,分放入10个集合中,在考虑60*(6-1)/6*(5-1)/5/4这10个4的倍数,如上操作,即可。

华南师范的思路基本正确, 只是在构造冲突上好像还差了点, 很可惜, 截止到10月2日, 

这题目除了我的标程,还没有第二份ac的代码。 如果有大神看到题解, 可以帮忙ac下,证明数据和标程是正确的, thx~

参考:http://blog.csdn.net/jxy859/article/details/12242601