昨天比赛的 T3，题解思路比较新颖，小记一下。
题意
网格图上，人物要从 \((0,0)\) 走到 \((n,m)\)。
给出两个长度分别为 \(n,m\) 的序列 \(a,b\)，若 \(a_i+b_j>0\)，则 \((i,j)\) 不可进入。
问人物能否走到 \((n,m)\)。注意 \(a_0=b_0=0\)。
\(n,m \le 10^6,|a_i|,|b_i| \le 10^9\)。
题解
如果只是一般的网格图，复杂度最小是 \(O(nm)\)。此题构造网格的特点在于：任意两行或两列的状态一定有包含关系。
不难发现答案为是的一个必要条件：行的最小值所在的列全为 \(1\)，列也同理。因为状态存在包含关系，而这两条行列的状态是最大的。
我们称这两条行列为“红线”。然后可以分解为两部分：\((0,0)\) 到红线，\((n,m)\) 到红线。以前者为例。
此时复杂度仍然是 \(O(nm)\) 的。继续利用包含关系的性质。考虑如下图：
实际上，圈出的线段可以删去。因为其左右均不连通，作用仅是通过绿色的边沟通左下与右上。但根据竖边的包含关系，不会存在这两条绿边，其中一条会是黄边。那么仅用红色长横边和黄色竖边即可代替原来的三条边。
以此类推，所有不和坐标轴连通的边均可删去。那么只剩下 \(O(n)\) 条边，答案也容易判断了。
原文地址：http://www.cnblogs.com/FishJokes/p/16885351.html
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，请务用于商业用途!
3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！
8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载
声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性
