【蓝桥杯】逐日练习 Day18

目次
前言
动态求一连区间和
分析
代码
数星星
分析
代码
星空之夜
分析
代码

---

前言

接下来是今天的标题（原来是有四道题的但是有一道题是前面讲过（逆序数的，感爱好的小同伴可以去看我归并排序的那一篇）的我就不再过多赘述了。）
两道树状数组和一道哈希的标题。

---

动态求一连区间和

---

分析

树状数组的模板题啊，我就不外多赘述了，各人看代码就好。

---

代码

1. #include<iostream>
2. using namespace std;
3. const int N = 100010;
4. int n, m;
5. int tree[N];
6. ​
7. int lowbit(int x)
8. {
9.    return x & -x;
10. }
11. ​
12. void insert(int i, int x)
13. {
14.    if(i > n) return;
15.    tree[i] += x;
16.    insert(i + lowbit(i), x);
17. }
18. ​
19. int find(int i)
20. {
21.    if(i == 0) return tree[i];
22.    return tree[i] + find(i - lowbit(i));
23. }
24. ​
25. int main()
26. {
27.    scanf("%d%d", &n, &m);
28.    for(int i = 1; i <= n; i++)
29.    {
30.        int x; scanf("%d", &x);
31.        insert(i, x);
32.    }
33.    while(m--)
34.    {
35.        int k, a, b;
36.        scanf("%d%d%d", &k, &a, &b);
37.        if(k == 1)
38.            insert(a, b);
39.        else
40.            printf("%d\n", find(b) - find(a - 1));
41.    }
42.    
43.    return 0;
44. }

复制代码

---

数星星

---

分析

发现标题要求的是雷同前缀和的一块地区，我们来判定一下能否用二维前缀和来写。
发现x, y <= 32000，利用前缀和的话时间复杂度就是32000 * 32000，十个亿左右，很显然会超时。
随后我们来实验一下优化，可以发现n是相对来说比力少的，以是可以利用离散化举行优化，优化后就变为了log(n) * n ^ n 。
时间复杂度还是很高啊，而且空间也装不下这么大的数组，以是我们pass掉二维前缀和。
我们思量前缀和的在线升级版——树状数组
树状数组的话我们肯定不能利用二维的，但是我们可以根据树状数组的特性，可以动态的处理前缀和。
详细思路是什么呢？大概就是我们按照x从大到小排序，随后按照序次插入数据，如许就只须要y方向的前缀和就好了。
注意：这道题的限时0.2秒，以是我们不但须要树状数组，还须要离散化优化。

---

代码

1. #include<iostream>
2. #include<vector>
3. #include<unordered_map>
4. #include<algorithm>
5. #define s second
6. #define f first
7. ​
8. using namespace std;
9. const int H = 32010, N = 15010;
10. typedef pair<int, int> PII; //按照x排序，按照y插入
11. int n, x, y;
12. int tree[N];
13. int node[N];
14. vector<PII> vtr;
15. unordered_map<int, int> umap;
16. int lowbit(int x)
17. {
18.    return x & -x;
19. }
20. ​
21. void insert(int i, int x)
22. {
23.    if(i >= N) return;  
24.    tree[i] += x;
25.    insert(i + lowbit(i), x);
26. }
27. ​
28. int find(int i)
29. {
30.    if(i < 0) return 0;
31.    if(i == 0) return tree[0];
32.    return tree[i] + find(i - lowbit(i));
33. }
34. ​
35. int main()
36. {
37.    scanf("%d", &n);
38.    int idx = 1;
39.    for(int i = 1; i <= n; i++)
40.    {
41.        scanf("%d%d", &x, &y);
42.        vtr.push_back({x, y});
43.        if(!umap[y])
44.            umap[y] = idx++;
45.    }
46.    sort(vtr.begin(), vtr.end());
47.    
48.    for(auto x : vtr)
49.    {
50.        node[find(umap[x.s])]++;
51.        insert(umap[x.s], 1);
52.    }
53.    
54.    for(int i = 0; i < n; i++)
55.        printf("%d\n", node[i]);
56.    return 0;
57. }

复制代码

---

星空之夜

---

分析

这道题是一道哈希的标题，这种题属于没有见过很难想到，但是见过了就会感觉不外云云的标题。
在讲正解之前，主播先讲一种含糊哈希的写法，固然不能通过全部测试点，但是绝对可以通过绝大多数的测试点。
如果赛时忘记了正解可以从实验用这种思路来写，和正解大差不差。
我们观察到标题是对方向，镜像不敏感的，那么我们就可以利用两种哈希方式——一种哈希方式是求任意两个点的间隔和（浮点数），别的一种哈希方式是求每个点到中央的间隔之和（同样是浮点数），因为我们要避开坐标的影响，以是要利用这种相对间隔的方式。
这两种哈希的筛选程度的逐层递增的，第一种可以筛掉95%的情况，第二种可以筛掉99%的情况，接下来主播就把这两种哈希写到一起的代码展示出来。

1. /*
2.    dfs + 哈希
3.    哈希方式是求每个点到中心的距离之和（浮点数）
4.    首先dfs求每个连通块的质心，随后第二次dfs求出每个点的哈希
5. */
6. #include<iostream>
7. #include<vector>
8. #include<cstring>
9. #include<cmath>
10. #include<unordered_map>
11. #define s second
12. #define f first
13. using namespace std;
14. typedef pair<int, int> PII;
15. const int N = 110;
16. const double INF = 1e-6;
17. int n, m;
18. char map[N][N];
19. bool read[N][N];
20. PII s[] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
21. unordered_map<double, char> ha;
22. char q = 'a'; //编号
23. ​
24. void dfs(int x, int y, vector<PII>& vtr, char z)
25. {
26.    map[x][y] = z;
27.    read[x][y] = true;
28.    vtr.push_back({x, y});
29.    for(int i = 0; i < 8; i++)
30.    {
31.        int a = x + s[i].f, b = y + s[i].s;
32.        if(map[a][b] == '1' && !read[a][b])
33.            dfs(a, b, vtr, z);
34.    }
35. }
36. ​
37. int main()
38. {
39.    scanf("%d%d", &m, &n);
40.    for(int i = 1; i <= n; i++)
41.        scanf("%s", map[i] + 1);
42.    /*if(m == 7 && n == 5)
43.    {
44.        printf("aa00bb0\n0a000b0\naa000bb\naaa0bbb\n00a000b");
45.        return 0;
46.    }*/
47.    // dfs求连通块和哈希值
48.    for(int i = 1; i <= n; i++)
49.        for(int j = 1; j <= m; j++)
50.        {
51.            if(map[i][j] == '1' && !read[i][j])
52.            {
53.                vector<PII> vtr;
54.                memset(read, 0, sizeof read);
55.                dfs(i, j, vtr, '1');
56.                double x = 0, y = 0;
57.                for(int k = 0; k < vtr.size(); k++)
58.                    x += vtr[k].f, y += vtr[k].s;
59.                x /= vtr.size();
60.                y /= vtr.size(); //求出质心
61.                //构造哈希哈希值
62.                double l = 0.0;
63.                // 一次哈希
64.                for(int k = 0; k < vtr.size(); k++)
65.                    l += sqrt((vtr[k].f - x) * (vtr[k].f - x) + (vtr[k].s - y) * (vtr[k].s - y));
66.                // 二次哈希
67.                for(int i = 0; i < vtr.size(); i++)
68.                    for(int j = 0; j < i; j++)
69.                    {
70.                        double x = vtr[i].f  - vtr[j].f, y = vtr[i].s - vtr[j].s;
71.                        l += sqrt(x * x + y * y);
72.                    }
73.                bool b = false;
74.                memset(read, 0, sizeof read);
75.                for(auto x : ha)
76.                {
77.                    if(abs(x.f - l) < INF)
78.                    {
79.                        dfs(i, j, vtr, x.s);
80.                        b = true;
81.                        break;
82.                    }
83.                }
84.                if(!b)
85.                {
86.                    ha[l] = q++;
87.                    dfs(i, j, vtr, ha[l]);
88.                }
89.            }            
90.        }
91.    for(int i = 1; i <= n; i++)
92.        printf("%s\n", map[i] + 1);
93.    return 0;
94. }

复制代码

但是上面的两种哈希方式都很难处理那种只有微小差距的矩形，比如：
  

1. 1100110
2. 0100010
3. 1100011
4. 1110111
5. 0010001

复制代码

以是我们须要清晰匹配的方式，怎样来写呢？
代码也是请讲授长得来的，大抵思路就是先求出连通块，随后将连通块八种情况的形态都盘算出来，末了将八种情况排序，取任意一种作为哈希值存储起来。

---

代码

1. #include<iostream>
2. #include<map>
3. #include<algorithm>
4. #include<vector>
5. #define s second
6. #define f first
7. using namespace std;
8. const int N = 110;
9. typedef pair<int, int> PII;
10. int n, m;
11. char mp[N][N];
12. bool st[N][N]; //存储每个位置有没有被读到
13. PII s[] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}, {-1, 1}, {-1, -1}, {1, -1}, {1, 1}};
14. map<vector<PII>, char> umap;
15. ​
16. void dfs(int x, int y, vector<PII>& vtr) //dfs取出连通块
17. {
18.    st[x][y] = true;
19.    vtr.push_back({x, y});
20.    for(int i = 0; i < 8; i++)
21.    {
22.        int dx = x + s[i].f, dy = y + s[i].s;
23.        if(!st[dx][dy] && mp[dx][dy] == '1')
24.            dfs(dx, dy, vtr);
25.    }
26. }
27. ​
28. vector<PII> swap_matrix(vector<PII>& vtr, int r) //翻转矩阵
29. {
30.    PII s[] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
31.    vector<PII> swp;
32.    for(auto [x, y] : vtr)
33.    {
34.        if(r > 3) swap(x, y); //翻转后进行
35.        swp.push_back({x * s[r % 4].f, y * s[r % 4].s});
36.    }
37.    return swp;
38. }
39. ​
40. vector<PII> get_hash(vector<PII>& vtr)
41. {
42.    vector<vector<PII>> vtt;
43.    for(int r = 0; r < 8; r++) //8个方向
44.    {
45.        vector<PII> swp = swap_matrix(vtr, r);
46.        sort(swp.begin(), swp.end());
47.        int mxx = 1e9, mxy = 1e9;
48.        for(auto [x, y] : swp)
49.            mxx = min(mxx, x), mxy = min(mxy, y); //取最小值
50.        for(int i = 0; i < swp.size(); i++)
51.            swp[i].f -= mxx, swp[i].s -= mxy; //取相对坐标
52.        vtt.push_back(swp); //加入函数值
53.    }
54.    sort(vtt.begin(), vtt.end());
55.    return vtt[0]; //将首位作为哈希值
56. }
57. ​
58. void solve()
59. {
60.    scanf("%d%d", &m, &n);
61.    for(int i = 1; i <= n; i++)
62.        scanf("%s", mp[i] + 1); //读取地图
63.    char a = 'a';
64.    for(int i = 1; i <= n; i++)
65.    {
66.        for(int j = 1; j <= m; j++)
67.        {
68.            if(mp[i][j] == '1' && !st[i][j])
69.            {
70.                vector<PII> vtr;
71.                dfs(i, j, vtr);
72.                vector<PII> hash = get_hash(vtr); //获取哈希值
73.                if(umap.find(hash) == umap.end())
74.                    umap[hash] = a++;
75.                char l = umap[hash];
76.                for(auto [x, y] : vtr)
77.                    mp[x][y] = l;
78.            }
79.        }
80.    }
81.    for(int i = 1; i <= n; i++)
82.        printf("%s\n", mp[i] + 1);
83. }
84. int main()
85. {
86.    solve();
87.    return 0;
88. }

复制代码

这个矩阵翻转的代码很奥妙，值得学习。