cpp常用技巧

容器的累加和

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

整數(shù)的上下限

當(dāng)要求動(dòng)態(tài)來的數(shù)據(jù)流中的最小/最大值時(shí)订晌，需要預(yù)設(shè)一個(gè)天花板/地板值。如果題目沒給上下限锻煌，但是給了結(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;

位運(yùn)算的容器

教程參考
例題：OpenJudge P2811 熄燈問題
例題講解：郭煒老師的慕課課程
郭老師用位運(yùn)算AC了此題，但是位運(yùn)算操作是自己實(shí)現(xiàn)的函數(shù)购城，本著熟悉bitset的目的吕座，我用bitset實(shí)現(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;
}

貪心

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

證明：
對(duì)于第i個(gè)大臣和第i+1個(gè)大臣（i=1, 2, ... n-1），設(shè)s表示第 i個(gè)大臣前面所有人的左手的乘積箭昵。如果a_i*b_i>=a_{i+1}*b_{i+1}.
不交換時(shí)的獎(jiǎng)勵(lì)： 第i個(gè)大臣：\frac sb_i, 第i+1個(gè)大臣： \frac {s \cdot a_i} {b_{i+1}}
交換時(shí)的獎(jiǎng)勵(lì)： 第i個(gè)大臣：\frac sb_{i+1}, 第i+1個(gè)大臣： \frac {s \cdot a_{i+1}} {b_{i}}
顯然交換這兩個(gè)人的話税朴，別的所有人的金幣數(shù)都是不變的。
比較兩種情況下的解的大屑抑啤（減號(hào)前者是不交換正林，后者是交換）：
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}時(shí)杈绸，交換之后的最大獎(jiǎng)勵(lì)不會(huì)超過不交換的情況帖蔓，即交換不會(huì)使得結(jié)果變差。由于i的任意性瞳脓，可知最優(yōu)解總可以通過交換相鄰項(xiàng)的方式塑娇，使得序列按照ab的升序排列，依然是最優(yōu)解劫侧。*

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

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

高精度計(jì)算

參考：https://oi-wiki.org/math/bignum/#_9
高精度-單精度乘法审姓，高精度-單精度除法珍特。用vector<int>存儲(chǔ)，而不是string魔吐，存儲(chǔ)空間會(huì)浪費(fèi)4倍扎筒，但是不需要做轉(zhuǎn)換。

_builtin*函數(shù)

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

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

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

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

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

運(yùn)行時(shí)躲撰，奇怪的報(bào)錯(cuò)munmap_chunk(): invalid pointer

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

#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)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末坪郭，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子脉幢，更是在濱河造成了極大的恐慌截粗，老刑警劉巖，帶你破解...
    沈念sama閱讀 217,734評(píng)論 6贊 505
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件鸵隧，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡意推，警方通過查閱死者的電腦和手機(jī)豆瘫，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,931評(píng)論 3贊 394
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來菊值，“玉大人外驱，你說我怎么就攤上這事∧逯希” “怎么了昵宇？”我有些...
    開封第一講書人閱讀 164,133評(píng)論 0贊 354
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵，是天一觀的道長儿子。 經(jīng)常有香客問我瓦哎，道長，這世上最難降的妖魔是什么柔逼？ 我笑而不...
    開封第一講書人閱讀 58,532評(píng)論 1贊 293
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任蒋譬，我火速辦了婚禮，結(jié)果婚禮上愉适，老公的妹妹穿的比我還像新娘犯助。我一直安慰自己，他們只是感情好维咸，可當(dāng)我...
    茶點(diǎn)故事閱讀 67,585評(píng)論 6贊 392
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布剂买。 她就那樣靜靜地躺著，像睡著了一般癌蓖。 火紅的嫁衣襯著肌膚如雪瞬哼。 梳的紋絲不亂的頭發(fā)上，一...
    開封第一講書人閱讀 51,462評(píng)論 1贊 302
  • 城市分裂傳說
    那天费坊，我揣著相機(jī)與錄音倒槐，去河邊找鬼。 笑死附井，一個(gè)胖子當(dāng)著我的面吹牛讨越，可吹牛的內(nèi)容都是我干的两残。 我是一名探鬼主播，決...
    沈念sama閱讀 40,262評(píng)論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼把跨，長吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼人弓！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起着逐，我...
    開封第一講書人閱讀 39,153評(píng)論 0贊 276
  • 萬榮殺人案實(shí)錄
    序言：老撾萬榮一對(duì)情侶失蹤崔赌，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后耸别，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體健芭，經(jīng)...
    沈念sama閱讀 45,587評(píng)論 1贊 314
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,792評(píng)論 3贊 336
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年秀姐，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了慈迈。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 39,919評(píng)論 1贊 348
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡省有，死狀恐怖痒留，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情蠢沿，我是刑警寧澤伸头，帶...
    沈念sama閱讀 35,635評(píng)論 5贊 345
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布，位于F島的核電站舷蟀，受9級(jí)特大地震影響恤磷，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜野宜，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,237評(píng)論 3贊 329
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一碗殷、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧速缨，春花似錦锌妻、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,855評(píng)論 0贊 22
  • 一樁弒父案仿粹，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至原茅，卻和暖如春吭历，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背擂橘。 一陣腳步聲響...
    開封第一講書人閱讀 32,983評(píng)論 1贊 269
  • 情欲美人皮
    我被黑心中介騙來泰國打工晌区， 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 48,048評(píng)論 3贊 370
  • 代替公主和親
    正文 我出身青樓朗若，卻偏偏與公主長得像恼五，于是被迫代替她去往敵國和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子哭懈，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,864評(píng)論 2贊 354

推薦閱讀更多精彩內(nèi)容