ToB企服应用市场:ToB评测及商务社交产业平台

标题: P2825 [HEOI2016/TJOI2016] 游戏与 P10945 Place the Robots [打印本页]

作者: 李优秀 时间: 2024-8-29 14:32
标题: P2825 [HEOI2016/TJOI2016] 游戏与 P10945 Place the Robots
本文中的机器人同炸弹，主要是题目形貌不同，两道题目做法是本质相同的。
思绪：

先说一下没有墙怎么办，那么当一个位置放了机器人之后，这个机器人地点的行和列是不能继续放置的。
那么发现行和列几乎是独立的，考虑建二分图，若 \((i,j)\) 能放一个机器人，那么给 \(i \to j\) 建一条边。
那么答案就是这个二分图的最大匹配，这样每个匹配的就代表着一个机器人所放的位置。
如今再考虑有墙的情况，有墙时，机器人所放的激光无法穿透已往，则在墙另外一边依旧可能可以放置机器人。
发现墙就是把行或列分为了几个部分，每个部分互不干扰，则考虑每碰到墙，就新起一行表示当前位置到下一个墙或者这一行的末尾的放块；列同理。
直接跑匈牙利算法即可。
P2825 [HEOI2016/TJOI2016] 游戏 Code： [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

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)