社区讨论

萌新想了一下午也不知道这题建图的正确性证明

P3227[HNOI2013] 切糕参与者 6已保存回复 12

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
12 条
当前快照
1 份
快照标识符
@locdapne
此快照首次捕获于
2023/10/30 11:55
2 年前
此快照最后确认于
2023/11/04 23:37
2 年前
查看原帖
这道题将每个 (x,y)(x,y) 连成串联的 RR 条边,并且对于相邻格子进行了差分限制。
显然,一组合法的 f(x,y)f(x,y) 对应了一组合法的割,但是如何证明任意一组割都对应了至少一个合法的 f(x,y)f(x,y),或者说不小于一组合法的 f(x,y)f(x,y)?为何不存在一条串联链上割掉了两条边的“作弊”情况?
萌新想了一下午也没想出来,hack 了一下午也没 hack 出来,所以发帖求教。

回复

12 条回复,欢迎继续交流。

正在加载回复...