搜索Ex
哎呀好几天没写POI题解了 (＞﹏＜)
看着摇曳不定的小旗子深深惶恐
打算开始肝洛谷试炼场的提高分区了【对我就是这么菜…
- 搜索Ex
比暴搜不错得多的题
拆成两问来看 第一问只要从湖边的城市（简称湖城）开始搜索就可以了
第二问的faulse项
用dfs剩的vis统计一下沙漠边缘有哪些点（简称沙城）没被搜到的
true项 蒟蒻一开始想状压
当然 n <= 500 【黑线
后来画了个等高线地形图【划掉
发现如果每个沙城都能有水喝【即true项
每个湖城管辖的沙城都是连续的区间
现在问题就变成了 至少用多少个区间覆盖整个区间
当然这问题长得很DP 但有个贪心更优
借用一位神犇的例子
m为10
N = 7：[1,5]、[1,6]、[3,6]、[1,7]、[6,9]、[9,10]、[7,9]。
先把每个区间（都是闭区间）排序 左区间小的优先
[1,5]、[1,6]、[1,7]、[3,6]、[6,9]、[7,9]、[9,10]
我们从1开始
选择每个区间的代价都是1 选择右区间大的显然更优
所以取[1, 7]
现在左区间小区等于7的区间 在小于等于7的部分已经被覆盖 所以无效了
为使区间连续 我们找（左区间小于等于8的区间）中（右区间最大的区间）
okk
最后附一句 如果找到一个地方 （可用最大右区间）小于（上一个取的区间的左区间）
1 inline void dfs(int x, int y){ 2 node[x][y].vis = 1; 3 if(x < 1 || x > n || y < 1 || y > m) return ; 4 for(int i = 0; i <= 3; i++){ 5 int sx = x + move[i][0], sy = y + move[i][1]; 6 if(node[sx][sy].w < node[x][y].w){ 7 if(!node[sx][sy].vis){ 8 dfs(sx, sy); 9 } 10 node[x][y].l = min(node[sx][sy].l, node[x][y].l); 11 node[x][y].r = max(node[sx][sy].r, node[x][y].r); 12 } 13 } 14 }
1 for(int i = 1; i <= m; i++) 2 a[i] = (A){node[1][i].l, node[1][i].r}; 3 sort(a + 1, a + m + 1, cmp); 4 int i = 1, j = 1, ans = 0; 5 while(j <= m){ 6 int k = j; 7 while(a[i].l <= k){ 8 j = max(j, a[i].r); 9 i++; 10 } 11 j++; 12 ans++; 13 } 14 printf("1 %d", ans);