NOI2016 D1T2题解
HJWJBSR
posted @ 2016年7月30日 23:47
in 题解
, 1456 阅读
考场上面写的东西。因为我不会求割点，然后可能常数比较大。
就是离散化之后把所有的轮廓线都拿出来，然后轮廓线就是很多环，给环上每个线段定个向，方向指向没有格子的那一边。
比如一行一列有个格子，它下方是一个轮廓线的一部分，那么这个这部分的方向就是往下的。
做这个的办法就是画个图出来发现可以每次找到一个没有提过的线段然后逆时针找下一个线段是哪一个。这东西需要用map存。
判掉无解的情况：最多只有两个空格子
判掉不用的情况：轮廓线顶部的线条是往下的环个数就是连通块个数。
判掉只用一个格子的情况：枚举黑格子，然后在它旁边8个格子试着放一个黑格子，然后用之前的方法去判断能不能把一个环切成两部分。
最后那个情况我在考场上面处理的比较naive，所以跪了。而且我一直以为是对的，到后面才拍出来。
现在想想如果考场上面能够一次想清楚不浪费时间的话说不定还是刚的出来的。
这方法止增笑耳。
评论 (0)
