摘要
Title: 4510. 寻宝！大冒险！
Tag: 哈希、O2优化
Memory Limit: 64 MB
Time Limit: 1000 ms

4510. 寻宝！大冒险！

题意

第26次CCF计算机软件能力认证

题目略
简短版：有一个LxL的大正方形和SxS的小正方形，大正方形中有部分打上1标记的点，SxS保证左下角一定是1，问在大正方形中能找到小正方形有多少种可能
思路

思路都是一样的，因为L太大了，不能对应到二维数组，所以还是枚举被标记的点，然后根据小正方形的各个点的偏移量和01情况，挨个进行对应即可
但此题的时限开的比较小，会出现一些问题：
- 我一开始想的是用Python的思维，用二维结构体当做key进行标记和遍历
  - 但unordered_map 没有针对pair的哈希函数，所以不能用unordered_map，得用map
  - 然而这么做，思路是对的，但是pair的存取耗时量太大，会导致TLE
- 所以可以改成将二维转成一维，进行坐标的标记
  - 具体怎么转，可以取一个比1e9大的质数作为模数，类似于，x*N+y，这样的话需要开long long，就可以再用unordered_map了
  - x和y的原值可分别用，除余和取余操作得到
- 另外，我们最后需要遍历哈希表，进行坐标读取，判断是否和小正方形的01条件对应
  - 但是如果这么写 f != st[fc(x, y)] st默认会开一个键值对，而且优先级大于你之前存的键值对，也就是说，在你auto进行遍历时，下一个会遍历这个键值对，这不是我们需要的
  - 所以应该这么写，f != (int)st.count(fc(x, y)) ，用count判断是否存在过，这样不会瞎开键值对
- 另外，开臭氧优化，会快很多!

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-01-17 11:40:21
* @FilePath: \Acwing\4510\4510.cpp
* @LastEditTime: 2023-01-17 14:30:33
*/
// #pragma GCC optimize(1)
// #pragma GCC optimize(2)    //先开优化
// #pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e9 + 7, INF = 0x3f3f3f3f;
int n, L, S;

struct sa
{
    int x, y, f;
};

unordered_map<long long, int> st;
vector<sa> rec;

signed main()
{
    auto fc = [&](int x, int y) { return 1LL * x * N + y; }; //转换函数

    scanf("%d%d%d", &n, &L, &S);
    for (int i = 1; i <= n; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        st[fc(x, y)] = 1;
    }
    for (int i = 0; i < S + 1; ++i)
    {
        for (int j = 0; j < S + 1; ++j)
        {
            int flag;
            scanf("%d", &flag);
            rec.push_back({S - i, j, flag}); // 更换坐标
        }
    }
    int ans = 0;
    for (auto &[t, _] : st)
    {
        auto xs = t / N, ys = t % N;
        int flag = 1;
        for (auto &[xp, yp, f] : rec)
        {
            int x = xs + xp;
            int y = ys + yp;
            if (x < 0 || x > L || y < 0 || y > L || f != (int)st.count(fc(x, y)))
            {
                flag = 0;
                break;
            }
        }
        ans += flag;
    }
    printf("%d", ans);
    return 0;
}

4510. 寻宝！大冒险！

题意

思路

代码