一、for枚舉 從中心點(diǎn)遍歷全圖 （或從中心點(diǎn)遍歷周圍八個(gè)方向）

參考題目：襲擊村莊（計(jì)蒜客2020模擬賽（一）B組）

邪惡勢(shì)力要進(jìn)攻 AA 村了！

AA 村是一個(gè) n*mn?m 的矩形，每個(gè)點(diǎn)上是道路、房屋、田地三者其一，耐久度分別是 a,b,ca,b,c。

邪惡勢(shì)力要進(jìn)行 qq 次攻擊，每次攻擊都是使用炮彈對(duì)村莊進(jìn)行轟炸。

邪惡勢(shì)力有兩種炮彈，分別是普通炮彈（編號(hào)為 11 ）和高級(jí)炮彈（編號(hào)為 00 ）。兩種炮彈的攻擊范圍都是 k\times kk×k 的方形，其中方形中心是炮彈落地點(diǎn)。炮彈對(duì)攻擊范圍內(nèi)每個(gè)格子造成的損害不一定一樣，用一個(gè) k\times kk×k 的矩陣描述，每個(gè)數(shù)字表示對(duì)對(duì)應(yīng)格子造成的傷害。高級(jí)炮彈和普通炮彈的傷害矩陣相同。

上述矩陣描述的是直接攻擊的傷害。對(duì)于高級(jí)炮彈，它的攻擊會(huì)造成濺射傷害：如果這個(gè)格子被直接攻擊，那么周圍八個(gè)格子都會(huì)受到濺射傷害，造成的傷害是 ww 。所以一個(gè)高級(jí)炮彈可能對(duì)同一個(gè)格子進(jìn)行多次傷害。濺射傷害不會(huì)繼續(xù)造成濺射傷害。普通炮彈不造成濺射傷害。

不論是直接攻擊的傷害還是濺射造成的傷害，都會(huì)使耐久度下降，下降量等于傷害的大小。耐久度最多降為 00，一個(gè)建筑單位受到的傷害定義為耐久度的減少量。

如果攻擊范圍涉及到地圖邊界外，那么不予計(jì)算（濺射傷害也不會(huì)計(jì)算）。

現(xiàn)在，給定上述的所有信息，我們想知道 AA 村被襲擊之后的道路、房屋、田地的總傷害，以及全村的總傷害。

輸入格式
第一行兩個(gè)整數(shù) n,mn,m，表示 A 村大小。

接下來一行三個(gè)整數(shù) a,b,ca,b,c。

接下來一行兩個(gè)整數(shù) k,wk,w。

接下來 kk 行，每行 kk 個(gè)數(shù)，描述高級(jí)炮彈和普通炮彈對(duì)相對(duì)位置所造成的傷害。

接下來一個(gè) n\times mn×m 的矩陣，表示 AA 村的布局。 11 表示道路， 22 表示房屋， 33 表示田地。

接下來一個(gè)數(shù) qq，表示邪惡勢(shì)力要進(jìn)行 qq 輪攻擊。

接下來 qq 行，每行三個(gè)數(shù) id,x,yid,x,y，分別是炮彈的編號(hào)以及他所攻擊的矩陣的中心位置的 xx 坐標(biāo)、 yy 坐標(biāo)，即第 xx 行 yy 列。

輸出格式
第一行三個(gè)整數(shù)，分別是對(duì)道路、房屋、田地造成的總傷害

第二行一個(gè)整數(shù)，表示對(duì)全村造成的傷害。

數(shù)據(jù)范圍
kk 一定是奇數(shù)。

對(duì)于 30%30% 的數(shù)據(jù)：1 \leq n,m,k,q \leq 501≤n,m,k,q≤50

對(duì)于 100%100% 的數(shù)據(jù)：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;
}

二、哈希方法求任何進(jìn)制字符串的值

這里的值是指轉(zhuǎn)化成10進(jìn)制的值

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];
}

三、位運(yùn)算枚舉

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

四、Set

當(dāng)想把一些符合調(diào)節(jié)的數(shù)添加到一個(gè)集合中，添加完畢后又想判斷這個(gè)集合中是否存在某個(gè)數(shù)時(shí)，可以使用set

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

//for中間調(diào)節(jié)不寫 則可一直按照某種方式循環(huán)下去
//循環(huán)體中需要有跳出循環(huán)的操作
    for (int i = 0;; i++) {
        if (!S.count(i)) {//查找是否存在這個(gè)數(shù)
            f[x] = i;
            return i;
        }

五、同余定理的擴(kuò)展

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

六、set和map中值唯一問題

set中每個(gè)元素唯一，set自動(dòng)去重并排序
map也是根據(jù)key值來排序的，是有序的
unordered_map是無(wú)序的
map當(dāng)插入重復(fù)鍵值的時(shí)候會(huì)覆蓋

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的時(shí)候由于a已經(jīng)對(duì)應(yīng)0了 所以自動(dòng)忽略

七、??！矩陣旋轉(zhuǎn)問題

預(yù)處理mpni[]和mpshun[]數(shù)組 分別代表順時(shí)針90和逆時(shí)針90的映射
然后根據(jù)vector的映射 求出旋轉(zhuǎn)后的矩陣

#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");
}

八、二進(jìn)制枚舉的核心操作

例題 Acwing ： 容斥原理

1、核心操作
for(int i=1;i<1<<m;i++)
左移m位 實(shí)現(xiàn)枚舉1~2^m

i>>j&1
判斷二進(jìn)制的每個(gè)位是否為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表示目前累乘的質(zhì)數(shù)積 cnt表示目前這個(gè)序列代表選了的集合的個(gè)數(shù)
        //cnt用來判斷最后是+還是- 奇數(shù)+ 偶數(shù)-
        int t = 1, cnt = 0;
        for (int j = 0; j < m; j++) {
            if (i >> j & 1) {
                if ((LL)t*p[j] > n) {//如果這個(gè)序列代表的質(zhì)數(shù)積超過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輸出位數(shù)的時(shí)候，可以自動(dòng)的進(jìn)行四舍五入操作

double num
printf("%.1lf",num);
在輸入5.74時(shí) 輸出5.7
在輸入5.75時(shí)，輸出5.8

十、結(jié)果要求浮點(diǎn)型

當(dāng)兩個(gè)整數(shù)相乘結(jié)果要求為浮點(diǎn)型時(shí)，結(jié)果變量定義為浮點(diǎn)型，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;
}