JLOI2008四题题解

就模拟就行。题面让你干什么你就干什么

T2 CODES

btw,小吐槽一句,把这题放T2真的不是恶意劝退么QAQ

T3 将军

考虑二分图匹配。非常迷的一点是Dinic跑不过但是匈牙利可以。

首先因为斜行不好做,所以处理的时候把棋盘转45°。

然后我们对于每个单位,在原有的攻击范围内添加上一个Bishop的攻击范围,这样可以使得每个单位都不被它攻击。

然后判定哪些格子不会被攻击到,可以二分图匹配了。

建二分图的时候把坐标转换为转45°之后的图再建图。行列匹配。

代码写的很好懂,可以看一下。

(日狗的是,Dinic理论上复杂度比Hungary更优,然而这个题Dinic是跑满的会T,Hungary可以轻松过。)

T4 可怜的骑士

没数据,不想写。也没OJ上有这题

这是为了害人么。。。

题目难度 T2>T3>T5>T1

有毒吧

ACAM 字符集的所有走法。入门题吧。

 

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据