目录
前言
动态求连续区间和
分析
代码
数星星
分析
代码
星空之夜
分析
代码
前言
接下来是今天的题目（本来是有四道题的但是有一道题是前面讲过（逆序数的，感兴趣的小伙伴可以去看我归并排序的那一篇）的我就不再过多赘述了。）
两道树状数组和一道哈希的题目。
动态求连续区间和
分析
树状数组的模板题啊，我就不过多赘述了，大家看代码就好。
代码
#include<iostream>
using namespace std;
const int N = 100010;
int n, m;
int tree[N];
int lowbit(int x)
{return x & -x;
}
void insert(int i, int x)
{if(i > n) return;tree[i] += x;insert(i + lowbit(i), x);
}
int find(int i)
{if(i == 0) return tree[i];return tree[i] + find(i - lowbit(i));
}
int main()
{scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++){int x; scanf("%d", &x);insert(i, x);}while(m--){int k, a, b;scanf("%d%d%d", &k, &a, &b);if(k == 1)insert(a, b);elseprintf("%d\n", find(b) - find(a - 1));}return 0;
}数星星
分析
发现题目要求的是类似前缀和的一块区域，我们来判断一下能否用二维前缀和来写。
发现x, y <= 32000，使用前缀和的话时间复杂度就是32000 * 32000，十个亿左右，很显然会超时。
随后我们来尝试一下优化，可以发现n是相对来说比较少的，所以可以使用离散化进行优化，优化后就变为了log(n) * n ^ n 。
时间复杂度还是很高啊，而且空间也装不下这么大的数组，所以我们pass掉二维前缀和。
我们考虑前缀和的在线升级版——树状数组
树状数组的话我们肯定不能使用二维的，但是我们可以根据树状数组的特性，可以动态的处理前缀和。
具体思路是什么呢？大概就是我们按照x从大到小排序，随后按照顺序插入数据，这样就只需要y方向的前缀和就好了。
注意：这道题的限时0.2秒，所以我们不仅需要树状数组，还需要离散化优化。
代码
#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
#define s second
#define f first
using namespace std;
const int H = 32010, N = 15010;
typedef pair<int, int> PII; //按照x排序，按照y插入
int n, x, y;
int tree[N];
int node[N];
vector<PII> vtr;
unordered_map<int, int> umap;
int lowbit(int x)
{return x & -x;
}
void insert(int i, int x)
{if(i >= N) return; tree[i] += x;insert(i + lowbit(i), x);
}
int find(int i)
{if(i < 0) return 0;if(i == 0) return tree[0];return tree[i] + find(i - lowbit(i));
}
int main()
{scanf("%d", &n);int idx = 1;for(int i = 1; i <= n; i++){scanf("%d%d", &x, &y);vtr.push_back({x, y});if(!umap[y])umap[y] = idx++;}sort(vtr.begin(), vtr.end());for(auto x : vtr){node[find(umap[x.s])]++;insert(umap[x.s], 1);}for(int i = 0; i < n; i++)printf("%d\n", node[i]);return 0;
}星空之夜
分析
这道题是一道哈希的题目，这种题属于没有见过很难想到，但是见过了就会感觉不过如此的题目。
在讲正解之前，主播先讲一种模糊哈希的写法，虽然不能通过所有测试点，但是绝对可以通过绝大多数的测试点。
如果赛时忘记了正解可以从尝试用这种思路来写，和正解大差不差。
我们观察到题目是对方向，镜像不敏感的，那么我们就可以使用两种哈希方式——一种哈希方式是求任意两个点的距离和（浮点数），另外一种哈希方式是求每个点到中心的距离之和（同样是浮点数），因为我们要避开坐标的影响，所以要使用这种相对距离的方式。
这两种哈希的筛选程度的逐层递增的，第一种可以筛掉95%的情况，第二种可以筛掉99%的情况，接下来主播就把这两种哈希写到一起的代码展示出来。
/*dfs + 哈希哈希方式是求每个点到中心的距离之和（浮点数）首先dfs求每个连通块的质心，随后第二次dfs求出每个点的哈希
*/
#include<iostream>
#include<vector>
#include<cstring>
#include<cmath>
#include<unordered_map>
#define s second
#define f first
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
const double INF = 1e-6;
int n, m;
char map[N][N];
bool read[N][N];
PII s[] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
unordered_map<double, char> ha;
char q = 'a'; //编号
void dfs(int x, int y, vector<PII>& vtr, char z)
{map[x][y] = z;read[x][y] = true;vtr.push_back({x, y});for(int i = 0; i < 8; i++){int a = x + s[i].f, b = y + s[i].s;if(map[a][b] == '1' && !read[a][b])dfs(a, b, vtr, z);}
}
int main()
{scanf("%d%d", &m, &n);for(int i = 1; i <= n; i++)scanf("%s", map[i] + 1);/*if(m == 7 && n == 5){printf("aa00bb0\n0a000b0\naa000bb\naaa0bbb\n00a000b");return 0;}*/// dfs求连通块和哈希值for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++){if(map[i][j] == '1' && !read[i][j]){vector<PII> vtr;memset(read, 0, sizeof read);dfs(i, j, vtr, '1');double x = 0, y = 0;for(int k = 0; k < vtr.size(); k++)x += vtr[k].f, y += vtr[k].s;x /= vtr.size();y /= vtr.size(); //求出质心//构造哈希哈希值double l = 0.0;// 一次哈希for(int k = 0; k < vtr.size(); k++)l += sqrt((vtr[k].f - x) * (vtr[k].f - x) + (vtr[k].s - y) * (vtr[k].s - y));// 二次哈希for(int i = 0; i < vtr.size(); i++)for(int j = 0; j < i; j++){double x = vtr[i].f - vtr[j].f, y = vtr[i].s - vtr[j].s;l += sqrt(x * x + y * y);}bool b = false;memset(read, 0, sizeof read);for(auto x : ha){if(abs(x.f - l) < INF){dfs(i, j, vtr, x.s);b = true;break;}}if(!b){ha[l] = q++;dfs(i, j, vtr, ha[l]);}} }for(int i = 1; i <= n; i++)printf("%s\n", map[i] + 1);return 0;
}但是上面的两种哈希方式都很难处理那种只有细小差距的矩形，比如：
1100110 0100010 1100011 1110111 0010001
所以我们需要清晰匹配的方式，如何来写呢？
代码也是请教学长得来的，大致思路就是先求出连通块，随后将连通块八种情况的形态都计算出来，最后将八种情况排序，取任意一种作为哈希值存储起来。
代码
#include<iostream>
#include<map>
#include<algorithm>
#include<vector>
#define s second
#define f first
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
int n, m;
char mp[N][N];
bool st[N][N]; //存储每个位置有没有被读到
PII s[] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}, {-1, 1}, {-1, -1}, {1, -1}, {1, 1}};
map<vector<PII>, char> umap;
void dfs(int x, int y, vector<PII>& vtr) //dfs取出连通块
{st[x][y] = true;vtr.push_back({x, y});for(int i = 0; i < 8; i++){int dx = x + s[i].f, dy = y + s[i].s;if(!st[dx][dy] && mp[dx][dy] == '1')dfs(dx, dy, vtr);}
}
vector<PII> swap_matrix(vector<PII>& vtr, int r) //翻转矩阵
{PII s[] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};vector<PII> swp;for(auto [x, y] : vtr){if(r > 3) swap(x, y); //翻转后进行swp.push_back({x * s[r % 4].f, y * s[r % 4].s});}return swp;
}
vector<PII> get_hash(vector<PII>& vtr)
{vector<vector<PII>> vtt;for(int r = 0; r < 8; r++) //8个方向{vector<PII> swp = swap_matrix(vtr, r);sort(swp.begin(), swp.end());int mxx = 1e9, mxy = 1e9;for(auto [x, y] : swp)mxx = min(mxx, x), mxy = min(mxy, y); //取最小值for(int i = 0; i < swp.size(); i++)swp[i].f -= mxx, swp[i].s -= mxy; //取相对坐标vtt.push_back(swp); //加入函数值}sort(vtt.begin(), vtt.end());return vtt[0]; //将首位作为哈希值
}
void solve()
{scanf("%d%d", &m, &n);for(int i = 1; i <= n; i++)scanf("%s", mp[i] + 1); //读取地图char a = 'a';for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(mp[i][j] == '1' && !st[i][j]){vector<PII> vtr;dfs(i, j, vtr);vector<PII> hash = get_hash(vtr); //获取哈希值if(umap.find(hash) == umap.end())umap[hash] = a++;char l = umap[hash];for(auto [x, y] : vtr)mp[x][y] = l;}}}for(int i = 1; i <= n; i++)printf("%s\n", mp[i] + 1);
}
int main()
{solve();return 0;
}这个矩阵翻转的代码很巧妙，值得学习。
