cpp常用技巧

容器的累加和

#include<numeric>
int sum = accumulate(ans.begin(), ans.end(), 0);

整數(shù)的上下限

當(dāng)要求動態(tài)來的數(shù)據(jù)流中的最小/最大值時，需要預(yù)設(shè)一個天花板/地板值。如果題目沒給上下限，但是給了結(jié)果的數(shù)據(jù)類型，可以如下設(shè)置：

#includ<climits>

int int_max = INT_MAX;
int int_min = INT_MIN;

long long ll_max = LLONG_MAX;
long long ll_min = LLONG_MIN;

位運算的容器

教程參考
例題：OpenJudge P2811 熄燈問題
例題講解：郭煒老師的慕課課程
郭老師用位運算AC了此題，但是位運算操作是自己實現(xiàn)的函數(shù)，本著熟悉bitset的目的，我用bitset實現(xiàn)了一遍。

#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>

using namespace std;

vector<bitset<6>> oriLight, light, result;
int n=5, m=6;
char input[6];
int in;

int main() {
    oriLight.resize(5);
    result.resize(5);
    for(int i=0; i<n; i++) {
        for(int j=m-1; j>=0; j--) {
            scanf("%d", &in);
            input[j] = in==1?'1': '0';
        }
        oriLight[i] = bitset<6>(string(input));
    }
    for(int i=0; i<(1<<m); i++) {
        light = vector<bitset<6>>(oriLight);
        bitset<6> switchs(i);
        for(int j=0; j<n; j++) {
            result[j] = switchs;
            for(int k=0; k<m; k++) {
                if(switchs[k]) {
                    if(k>0)
                        light[j].flip(k-1);
                    light[j].flip(k);
                    if(k<m-1)
                        light[j].flip(k+1);
                }
            }
            if(j<n-1)
                light[j+1] ^= switchs;
            switchs = light[j];
        }
        if(light[n-1].none()){
            for(auto res: result) {
                for(int i=0; i<m; i++) {
                    printf("%d ", res[i]?1:0);
                }
                printf("\n");
            }
            return 0;
        }
    }
    return 0;
}

貪心

國王游戲
用微擾法證明貪心算法的正確性。
微擾法：如果交換方案中任意兩個元素/相鄰的兩個元素后，答案不會變得更好，那么可以推定目前的解已經(jīng)是最優(yōu)解了（這其實是反證法）。
要證明的結(jié)論：對于任意最優(yōu)解，當(dāng) a_i*b_i>=a_{i+1}*b_{i+1}時，交換二者位置，并不會使得結(jié)果變差。

證明：
對于第i個大臣和第i+1個大臣（i=1, 2, ... n-1），設(shè)s表示第 i個大臣前面所有人的左手的乘積。如果a_i*b_i>=a_{i+1}*b_{i+1}.
不交換時的獎勵： 第i個大臣：\frac sb_i, 第i+1個大臣： \frac {s \cdot a_i} {b_{i+1}}
交換時的獎勵： 第i個大臣：\frac sb_{i+1}, 第i+1個大臣： \frac {s \cdot a_{i+1}} {b_{i}}
顯然交換這兩個人的話，別的所有人的金幣數(shù)都是不變的。
比較兩種情況下的解的大?。p號前者是不交換，后者是交換）：
max(\frac sb_i, \frac {s \cdot a_i} {b_{i+1}}) - max(\frac sb_{i+1}, \frac {s \cdot a_{i+1}} {b_{i}})
=s \cdot (max(\frac {1}{b_i}, \frac {a_i} {b_{i+1}}) - max(\frac {1}b_{i+1}, \frac {a_{i+1}} {b_{i}}))
=\frac s{b_ib_{i+1}} (max(b_{i+1}, a_ib_i) - max(b_i, a_{i+1}b_{i+1}))
由已知條件，以及a，b均為正整數(shù)（題目數(shù)據(jù)約束），可得a_{i}b_{i}>=a_{i+1}b_{i+1}>=b_{i+1}, a_{i}b_{i}>=b_{i}。故有：
max(b_{i+1}, a_ib_i) - max(b_i, a_{i+1}b_{i+1})>=0
即:
max(b_{i+1}, a_ib_i) >= max(b_i, a_{i+1}b_{i+1})
也就是說，當(dāng) a_i*b_i>=a_{i+1}*b_{i+1}時，交換之后的最大獎勵不會超過不交換的情況，即交換不會使得結(jié)果變差。由于i的任意性，可知最優(yōu)解總可以通過交換相鄰項的方式，使得序列按照ab的升序排列，依然是最優(yōu)解。*

反過來想，將數(shù)組按照a*b從小到大排序，得到的序列便是一種最優(yōu)解，然后枚舉每個大臣的獎勵，取最大值即可（需要高精度計算）。

#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int n;
vector<pair<int, int>> p;

vector<int> mul(vector<int> a, int b) {
    vector<int> res;
    int c = 0;
    for(int i=0; i<a.size()||c; i++) {
        if(i<a.size())
            c += a[i] * b;
        res.push_back(c%10);
        c = c / 10;
    }
    return res;
}

vector<int> divd(vector<int> a, int b) {
    vector<int> res;
    int c = 0;
    for(int i=a.size()-1; i>=0; i--) {
        c = c*10 + a[i];
        int d = c / b;
        if(d || !res.empty())
            res.push_back(d);
        c %= b;
    }
    reverse(res.begin(), res.end());
    if(res.empty())
        res.push_back(0);
    return res;
}

vector<int> maxVectorInt(vector<int> a, vector<int> b) {
    if(a.size() != b.size())
        return a.size()>b.size()? a: b;
    for(int i=a.size()-1; i>=0; i--) {
        if(a[i]!=b[i])
            return a[i]>b[i]?a: b;
    }
    return a;
}

int main() {
    cin>>n;
    p.resize(n+1);
    cin>>p[0].first>>p[0].second;
    int a, b;
    for(int i=1; i<=n; i++) {
        cin>>a>>b;
        p[i] = make_pair(a*b, b);
    }
    sort(p.begin()+1, p.end());
    vector<int> res(1, 0);
    vector<int> prod(1, 1);
    prod = mul(prod, p[0].first);
    for(int i=1; i<=n; i++) {
        res = maxVectorInt(res, divd(prod, p[i].second));
        prod = mul(prod, p[i].first / p[i].second);
    }
    for(int i=res.size()-1; i>=0; i--) {
        printf("%d", res[i]);
    }
    cout<<endl;
    return 0;
}

高精度計算

參考：https://oi-wiki.org/math/bignum/#_9
高精度-單精度乘法，高精度-單精度除法。用vector<int>存儲，而不是string，存儲空間會浪費4倍，但是不需要做轉(zhuǎn)換。

_builtin*函數(shù)

_builtin*函數(shù)是gcc提供的函數(shù)，并不是C++的標(biāo)準(zhǔn)，一般的g++編譯器都有對應(yīng)的實現(xiàn)，以_builtin為前綴。直接用就好。
傳送門
官方文檔
常用的函數(shù)：

  • __builtin_popcount(unsigned int x)：x中1的個數(shù)。
  • __builtin_ctz(unsigned int x)：x末尾0的個數(shù)。x=0時結(jié)果未定義。
  • __builtin_clz(unsigned int x)：x前導(dǎo)0的個數(shù)。x=0時結(jié)果未定義。
    如果要傳入long， long long型的參數(shù)，則在函數(shù)名后加 l， ll。如:
  • __builtin_popcountl (unsigned long)
  • __gcd(m, n): 最大公約數(shù)函數(shù)

快捷的取對數(shù)的方法(底為2)

int n;
int logn = 31 - __builtin_clz(n);

正常的取對數(shù)的方法，請使用<cmath>中的log, log10函數(shù).

運行時，奇怪的報錯munmap_chunk(): invalid pointer

查詢說的是內(nèi)存分配/回收有關(guān)的函數(shù)報的錯，然而我的代碼里面并沒有顯示的使用malloc()等函數(shù)，只是在用了vector的resize()函數(shù)。當(dāng)然在改成了int的數(shù)組之后就不會報錯了。
啟示：不是必須要使用變長數(shù)組的情況下，請開固定長度的數(shù)組，不要使用容器的resize去分配容量，有可能會導(dǎo)致runtime error！
附上報錯以及正確的代碼，以及對應(yīng)的輸入。題目：洛谷P1816 忠誠
報錯的代碼：

#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
int m,n;
vector<int> data;
vector<pair<int, int>> query;
vector<vector<int>> f;

int main() {
    cin>>m>>n;
    data.resize(m+1, 1e9);
    query.resize(n);
    int logn = 31 - __builtin_clz(m);
    f.resize(m+1, vector<int>(logn, 1e9));
    for(int i=1; i<=m; i++) {
        scanf("%d", &data[i]);
    }
    for(int i=0; i<n; i++) {
        scanf("%d%d", &query[i].first, &query[i].second);
    }
    for(int i=1; i<=m; i++) {
        f[i][0] = data[i];
    }
    for(int j=1; j<=logn; j++) {
        for(int i=1; i+(1<<j)-1 <= m; i++) {
            f[i][j] = min(f[i][j-1], f[i+(1<<(j-1))][j-1]);
        }
    }
    for(int i=0; i<query.size(); i++) {
        int x=query[i].first, y=query[i].second;
        int lognq = 31 - __builtin_clz(y-x+1);
        printf("%d ", min(f[x][lognq], f[y-(1<<lognq) + 1][lognq]));
    }
    return 0;
}

輸入：

100 100
30634 1463 36025 59785 78967 24115 17462 51412 96756 21058 11876 12331 94933 92818 36571 65550 2114 8570 26348 68050 75991 88502 19870 10545 12502 70972 33774 71152 31874 12967 57160 51952 15822 903 97000 76124 26208 48469 83598 92584 83826 28413 78236 19851 39962 16623 98727 99073 16637 80691 12727 40313 11164 63852 26221 53537 88627 62334 88333 93666 10078 21668 60272 23080 90178 44161 21422 97010 52537 45772 92507 50695 80023 24695 70562 22104 11889 6073 93754 24079 78884 22188 5693 41387 16664 89866 47387 65085 53731 50691 68642 35716 55682 15745 61519 90912 55787 22967 6406 28409
80 93
52 77
79 93
2 4
1 73
6 45
62 85
14 54
17 54
41 71
34 39
40 45
57 79
52 71
12 63
40 43
30 82
30 63
61 69
32 45
20 21
56 59
17 91
45 55
19 31
19 97
30 81
14 99
1 10
39 64
22 73
43 89
29 34
50 58
53 59
93 98
60 95
32 41
5 11
4 79
68 91
64 97
79 91
49 84
2 43
42 67
6 65
49 76
24 44
39 69
3 36
79 98
53 92
8 40
26 58
65 81
29 31
82 98
10 28
27 80
11 16
26 77
29 95
7 24
29 85
69 82
53 67
98 99
44 48
30 93
49 68
27 53
1 9
13 92
65 76
8 85
34 93
30 46
15 54
14 85
53 88
44 48
29 83
2 18
16 99
7 53
45 74
55 93
33 56
28 53
28 45
46 98
2 14
1 69
16 82
9 10
16 26
64 96
1 86
89 91

改造為靜態(tài)數(shù)組后的代碼

#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
int m,n;
int data[100005], f[100005][32];
int query[100005][2];

int main() {
    cin>>m>>n;
    int logn = 31 - __builtin_clz(m);
    for(int i=1; i<=m; i++) {
        scanf("%d", &data[i]);
    }
    for(int i=0; i<n; i++) {
        scanf("%d%d", &query[i][0], &query[i][1]);
    }
    for(int i=1; i<=m; i++) {
        f[i][0] = data[i];
    }
    for(int j=1; j<=logn; j++) {
        for(int i=1; i+(1<<j)-1 <= m; i++) {
            f[i][j] = min(f[i][j-1], f[i+(1<<(j-1))][j-1]);
        }
    }
    for(int i=0; i<n; i++) {
        int x=query[i][0], y=query[i][1];
        int lognq = 31 - __builtin_clz(y-x+1);
        printf("%d ", min(f[x][lognq], f[y-(1<<lognq) + 1][lognq]));
    }
    return 0;
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容