CSP202206_2
目录题目
思路
暴力
首先 L 为 1e9 的数量级，直接开二维存地图显然不可行，因此考虑只记录有树的点。
进一步对于藏宝图，s 只有 50，因此直接存储即可。
针对所有地图中为 1 的点，直接枚举其作为左下角点，遍历藏宝图，如果超出地图范围或者地图与藏宝图不一致，直接结束对藏宝图的遍历，枚举下一个可能的左下角点。
时间复杂度\(O(n^2s^2)\)，70pts............ ？AC了？
应该是数据比较水，循环过程中 break 较多，明显的优化了时间。
如果想卡，应该可以卡TLE的吧？
评测时间78ms
优化方法
在对暴力解法的分析中，我们可以想到最容易也最适合优化的，显然是在遍历藏宝图后，在原地图进行匹配判断的过程。
注意到题目中说明地图中同一点不会多次出现，我们显然可以考虑直接用 pair 存点，用 set 存储地图。而在 set 中调用 count 查询一个点是否存在，时间复杂度为\(O(logn)\)，显然要比\(O(n)\)的遍历要优。
在用 set 写的时候还意识到好像判断是否超出地图范围可以直接在最外层循环判断，应该能更快一点。
结果憨憨的超出范围 continue 前忘了 it++，反而交了个 0pts。
评测时间0ms
Code
-
暴力(100pts)
#include<bits/stdc++.h> using namespace std; inline int read() { int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } return x * f; } struct NODE { int x, y; } node[1010]; int n, l, s; int ans; int mp[61][61]; int main() { n = read(), l = read(), s = read(); for(int i = 1; i <= n; i++) { node[i].x = read(); node[i].y = read(); } for(int i = s; i >= 0; i--) { for(int j = 0; j <= s; j++) { mp[i][j] = read(); } } for(int k = 1; k <= n; k++) { int x = node[k].x; int y = node[k].y; bool flag = true; for(int i = 0; i <= s; i++) { for(int j = 0; j <= s; j++) { if(x + i > l || y + j > l) { flag = false; break; } if(!mp[i][j]) { for(int kk = 1; kk <= n; kk++) { if(node[kk].x == x + i && node[kk].y == y + j) { flag = false; break; } } } else { for(int kk = 1; kk <= n; kk++) { if(node[kk].x == x + i && node[kk].y == y + j) { break; } if(kk == n) { flag = false; } } } } if(!flag) { break; } } if(flag) ans++; } cout << ans; return 0; } -
set(100pts)
#include<bits/stdc++.h> using namespace std; inline int read() { int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } return x * f; } set< pair<int, int> > st; int n, l, s; int ans; int mp[61][61]; int main() { n = read(), l = read(), s = read(); for(int i = 1; i <= n; i++) { int x = read(), y = read(); st.insert(make_pair(x, y)); } for(int i = s; i >= 0; i--) { for(int j = 0; j <= s; j++) { mp[i][j] = read(); } } set < pair<int, int> > :: iterator it = st.begin(); while(it != st.end()) { int x = it->first; int y = it->second; bool flag = true; if(x + s > l || y + s > l) { it++; continue; } for(int i = 0; i <= s; i++) { for(int j = 0; j <= s; j++) { if(!mp[i][j]) { if(st.count(make_pair(x + i, y + j))) { flag = false; break; } } else { if(!st.count(make_pair(x + i, y + j))) { flag = false; break; } } } if(! flag) break; } if(flag) ans++; it++; } cout << ans; return 0; }