一、for枚举 从中心点遍历全图 （或从中心点遍历周围八个方向）

参考题目：袭击村庄（计蒜客2020模拟赛（一）B组）

邪恶势力要进攻 AA 村了！

AA 村是一个 n*mn∗m 的矩形，每个点上是道路、房屋、田地三者其一，耐久度分别是 a,b,ca,b,c。

邪恶势力要进行 qq 次攻击，每次攻击都是使用炮弹对村庄进行轰炸。

邪恶势力有两种炮弹，分别是普通炮弹（编号为 11 ）和高级炮弹（编号为 00 ）。两种炮弹的攻击范围都是 k\times kk×k 的方形，其中方形中心是炮弹落地点。炮弹对攻击范围内每个格子造成的损害不一定一样，用一个 k\times kk×k 的矩阵描述，每个数字表示对对应格子造成的伤害。高级炮弹和普通炮弹的伤害矩阵相同。

上述矩阵描述的是直接攻击的伤害。对于高级炮弹，它的攻击会造成溅射伤害：如果这个格子被直接攻击，那么周围八个格子都会受到溅射伤害，造成的伤害是 ww 。所以一个高级炮弹可能对同一个格子进行多次伤害。溅射伤害不会继续造成溅射伤害。普通炮弹不造成溅射伤害。

不论是直接攻击的伤害还是溅射造成的伤害，都会使耐久度下降，下降量等于伤害的大小。耐久度最多降为 00，一个建筑单位受到的伤害定义为耐久度的减少量。

如果攻击范围涉及到地图边界外，那么不予计算（溅射伤害也不会计算）。

现在，给定上述的所有信息，我们想知道 AA 村被袭击之后的道路、房屋、田地的总伤害，以及全村的总伤害。

输入格式
第一行两个整数 n,mn,m，表示 A 村大小。

接下来一行三个整数 a,b,ca,b,c。

接下来一行两个整数 k,wk,w。

接下来 kk 行，每行 kk 个数，描述高级炮弹和普通炮弹对相对位置所造成的伤害。

接下来一个 n\times mn×m 的矩阵，表示 AA 村的布局。 11 表示道路， 22 表示房屋， 33 表示田地。

接下来一个数 qq，表示邪恶势力要进行 qq 轮攻击。

接下来 qq 行，每行三个数 id,x,yid,x,y，分别是炮弹的编号以及他所攻击的矩阵的中心位置的 xx 坐标、 yy 坐标，即第 xx 行 yy 列。

输出格式
第一行三个整数，分别是对道路、房屋、田地造成的总伤害

第二行一个整数，表示对全村造成的伤害。

数据范围
kk 一定是奇数。

对于 30%30% 的数据：1 \leq n,m,k,q \leq 501≤n,m,k,q≤50

对于 100%100% 的数据：1 \leq n,m,k,q \leq 300, 1 \leq a,b,c,w \leq 10000000001≤n,m,k,q≤300,1≤a,b,c,w≤1000000000

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1010;
LL sh[N][N]; //伤害
LL maps[N][N];
LL nj[N][N];
int n, m, k;
LL a, b, c;
LL w;
bool in(int x, int y) {
    return (x >= 1 && x <= n && y >= 1 && y <= m);
}
void jssh(int x, int y) {
    for (int i = x - 1; i <= x + 1; i++) {
        for (int j = y - 1; j <= y + 1; j++) {
            if (i == x && j == y)
                continue;
            LL zero = 0;
            nj[i][j] = max(zero, nj[i][j] - w);
        }
    }
}
void gj(int x, int y, bool d) {
    for (int i = x - (k - 1) / 2; i <= x + (k - 1) / 2; i++) {

        for (int j = y - (k - 1) / 2; j <= y + (k - 1) / 2; j++) {
            if (in(i, j)) {
                LL zero = 0;
                nj[i][j] = max(zero, nj[i][j] - sh[i - (x - (k - 1) / 2) + 1][j - (y - (k - 1) / 2) + 1]);
                if (d == 0) {
                    jssh(i, j);
                }
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    cin >> a >> b >> c;
    cin >> k >> w;

    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= k; j++) {
            cin >> sh[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> maps[i][j];
            if (maps[i][j] == 1)nj[i][j] = a;
            if (maps[i][j] == 2)nj[i][j] = b;
            if (maps[i][j] == 3)nj[i][j] = c;
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int num, x, y;
        cin >> num >> x >> y;
        gj(x, y, num);
    }
    int ans1 = 0, ans2 = 0, ans3 = 0;
    LL ans = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (maps[i][j] == 1) {
                if (nj[i][j] == 0)
                    ans1++;
                ans += a - nj[i][j];
            }
            if (maps[i][j] == 2) {
                if (nj[i][j] == 0)
                    ans2++;
                ans += b - nj[i][j];
            }
            if (maps[i][j] == 3) {
                if (nj[i][j] == 0)
                    ans3++;
                ans += c - nj[i][j];
            }
        }
    }
    cout << ans1 << ' ' << ans2 << ' ' << ans3 << endl;
    cout << ans << endl;
    system("PAUSE");
    return 0;
}

二、哈希方法求任何进制字符串的值

这里的值是指转化成10进制的值

long long mi[i] //26 ^ i;

long long sum = 0;
string s;
int len = s.length();
for (int i = 0; i <= len - 1; i++) {
    sum += (s[i]-'A'） * mi[len - i - 1];
}

三、位运算枚举

for(int i=1;i<=1<<m;i++)
cout<<i<<' ';
//1~32

四、Set

当想把一些符合调节的数添加到一个集合中，添加完毕后又想判断这个集合中是否存在某个数时，可以使用set

set<int> S;
    for (int i = 1; i <= k; i++) {
        if (x >= s[i]) {
            S.insert(sg(x - s[i]));//添加到集合中
        }
    }

//for中间调节不写 则可一直按照某种方式循环下去
//循环体中需要有跳出循环的操作
    for (int i = 0;; i++) {
        if (!S.count(i)) {//查找是否存在这个数
            f[x] = i;
            return i;
        }

五、同余定理的扩展

(a^n) %b=(a%b)^n%b
根据此定理可以求
(1^2019 + 2^2019 +.....+n^2019)%mod
n^2019 %mod=(n%mod)^2019

六、set和map中值唯一问题

set中每个元素唯一，set自动去重并排序
map也是根据key值来排序的，是有序的
unordered_map是无序的
map当插入重复键值的时候会覆盖

int cnt = 0;

map<string,int> m_str2id;

for(int i=0; i<5; i++) {

    m_str2id.insert(pair<string,int>("a",cnt));

    cnt++;

}

 

for(auto it = m_str2id.begin(); it != m_str2id.end(); it++) {

    printf("%s  :  %d\n", it->first.c_str(), it->second);

}
//输出 a 0；

插入 a 1的时候由于a已经对应0了 所以自动忽略

七、！！矩阵旋转问题

预处理mpni[]和mpshun[]数组 分别代表顺时针90和逆时针90的映射
然后根据vector的映射 求出旋转后的矩阵

#include<bits/stdc++.h>
using namespace std;
int n, m;
int mp[100];
int mpshun[100], mpni[100];
vector<int> a;
void rotate() {
    vector<int> tmp;
    for (int i = 0; i < a.size(); i++) {
        tmp.push_back(mpni[a[i]]);
    }

    a = tmp;
    int  cnt = 0;
    for (int i = 0; i < 25; i++) {
        cout << tmp[i] << ' ';
        cnt++;
        if (cnt % 5 == 0) {
            cout << endl;
        }
    }

}
void rotateshun() {
    vector<int> tmp;
    for (int i = 0; i < a.size(); i++) {
        tmp.push_back(mpshun[a[i]]);
    }

    a = tmp;
    int  cnt = 0;
    for (int i = 0; i < 25; i++) {
        cout << tmp[i] << ' ';
        cnt++;
        if (cnt % 5 == 0) {
            cout << endl;
        }
    }
}
int main()
{
    n = 5, m = 5;
    int t = 0;
    //原矩阵
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < n; i++) {
            mp[t++] = i+j*n;
        }
    }
    for (int i = 0; i < 25; i++) {
        a.push_back(i);
    }
    t = 0;
    for (int j = n - 1; j >= 0; j--) {
        for (int i = 0; i < n; i++) {
            mpni[t++] = i * n + j;
        }
    }
    //for (int i = 0; i < 4; i++) {
    //  rotate();
    //  cout << endl;
    //}
    t = 0;
    for (int j = 0; j <n; j++) {
        for (int i = n-1; i >=0; i--) {
            mpshun[t++] = j+ i*n;
        }
    }
    for (int i = 0; i < 4; i++) {
    rotateshun();
    cout << endl;
}

    //int cnt = 0;
    //  for (int j = 0; j < 25; j++) {
    //      cout << mp[j] << ' ';
    //      cnt++;
    //      if (cnt % 5 == 0)
    //          cout << endl;
    //  }
    
    system("PAUSE");
}

八、二进制枚举的核心操作

例题 Acwing ： 容斥原理

1、核心操作
for(int i=1;i<1<<m;i++)
左移m位 实现枚举1~2^m

i>>j&1
判断二进制的每个位是否为1

#include<bits/stdc++.h>
using namespace std;
int n, m;
typedef long long LL;
int p[20];
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> p[i];
    }
    int res = 0;
    for (int i = 0; i < 1 << m; i++) { //2^m-1; 不能小于等于

        //t表示目前累乘的质数积 cnt表示目前这个序列代表选了的集合的个数
        //cnt用来判断最后是+还是- 奇数+ 偶数-
        int t = 1, cnt = 0;
        for (int j = 0; j < m; j++) {
            if (i >> j & 1) {
                if ((LL)t*p[j] > n) {//如果这个序列代表的质数积超过n则舍去
                    t = -1;
                    break;
                }
                else {
                    t *= p[j];
                    cnt++;
                }
            }
        }
        if (t != -1) {
            if (cnt % 2 == 0) {
                res -= n / t;
            }
            else res += n / t;
        }
    }
    cout << res << endl;;
    //  system("PAUSE");
    return 0;
}

九、四舍五入 printf

在控制print输出位数的时候，可以自动的进行四舍五入操作

double num
printf("%.1lf",num);
在输入5.74时 输出5.7
在输入5.75时，输出5.8

十、结果要求浮点型

当两个整数相乘结果要求为浮点型时，结果变量定义为浮点型，1.0*

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,k;
long long sum1, sum2;
int cnt1, cnt2;
int main()
{
    cin >> n>>k;
    for (int i = 1; i <= n; i++) {
        if (i % k == 0) {
            sum1 += i;
            cnt1++;
        }
        else {
            sum2 += i;
            cnt2++;
        }
    }
    double ans1 = 1.0*sum1 / cnt1;
    double ans2 = 1.0*sum2 / cnt2;
    printf("%.1lf %.1lf\n", ans1, ans2);
    return 0;
}