P2825 [HEOI2016/TJOI2016] 游戏 与 P10945 Place the Robots
本文中的机器人同炸弹，主要是题目描述不同，两道题目做法是本质相同的。思路：
先说一下没有墙怎么办，那么当一个位置放了机器人之后，这个机器人所在的行和列是不能继续放置的。
那么发现行和列几乎是独立的，考虑建二分图，若 \((i,j)\) 能放一个机器人，那么给 \(i \to j\) 建一条边。
那么答案就是这个二分图的最大匹配，这样每个匹配的就代表着一个机器人所放的位置。
现在再考虑有墙的情况，有墙时，机器人所放的激光无法穿透过去，则在墙另外一边依旧可能可以放置机器人。
发现墙就是把行或列分为了几个部分，每个部分互不干扰，则考虑每遇到墙，就新起一行表示当前位置到下一个墙或者这一行的末尾的放块；列同理。
直接跑匈牙利算法即可。
P2825 游戏 Code： #include#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);#define For(i,l,r) for(int i=l;i=l;i--)using namespace std;typedef double db;typedef unsigned long long ull;typedef long long ll;const ll N=2505;inline ll read(){ ll x=0,f=1; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c 新版吗？好像是停更了吧。 鼓励转贴优秀软件安全工具和文档！ yyds。多谢分享 用心讨论，共获提升！ 过来提前占个楼 新版吗？好像是停更了吧。 新版吗？好像是停更了吧。 谢谢楼主提供！ 感谢分享 懂技术并乐意极积无私分享的人越来越少。珍惜 收藏一下 不知道什么时候能用到 分享、互助 让互联网精神温暖你我 热心回复！ 收藏一下 不知道什么时候能用到 很好很强大我过来先占个楼 待编辑
页:
[1]