cpp常用技巧

容器的累加和

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

整数的上下限

当要求动态来的数据流中的最小/最大值时,需要预设一个天花板/地板值。如果题目没给上下限,但是给了结果的数据类型,可以如下设置:

#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了此题,但是位运算操作是自己实现的函数,本着熟悉bitset的目的,我用bitset实现了一遍。

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

贪心

国王游戏
用微扰法证明贪心算法的正确性。
微扰法:如果交换方案中任意两个元素/相邻的两个元素后,答案不会变得更好,那么可以推定目前的解已经是最优解了(这其实是反证法)。
要证明的结论:对于任意最优解,当 a_i*b_i>=a_{i+1}*b_{i+1}时,交换二者位置,并不会使得结果变差。

证明:
对于第i个大臣和第i+1个大臣(i=1, 2, ... n-1),设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}}
显然交换这两个人的话,别的所有人的金币数都是不变的。
比较两种情况下的解的大小(减号前者是不交换,后者是交换):
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均为正整数(题目数据约束),可得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})
也就是说,当 a_i*b_i>=a_{i+1}*b_{i+1}时,交换之后的最大奖励不会超过不交换的情况,即交换不会使得结果变差。由于i的任意性,可知最优解总可以通过交换相邻项的方式,使得序列按照ab的升序排列,依然是最优解。*

反过来想,将数组按照a*b从小到大排序,得到的序列便是一种最优解,然后枚举每个大臣的奖励,取最大值即可(需要高精度计算)。

#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倍,但是不需要做转换。

_builtin*函数

_builtin*函数是gcc提供的函数,并不是C++的标准,一般的g++编译器都有对应的实现,以_builtin为前缀。直接用就好。
传送门
官方文档
常用的函数:

  • __builtin_popcount(unsigned int x):x中1的个数。
  • __builtin_ctz(unsigned int x):x末尾0的个数。x=0时结果未定义。
  • __builtin_clz(unsigned int x):x前导0的个数。x=0时结果未定义。
    如果要传入long, long long型的参数,则在函数名后加 l, ll。如:
  • __builtin_popcountl (unsigned long)
  • __gcd(m, n): 最大公约数函数

快捷的取对数的方法(底为2)

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

正常的取对数的方法,请使用<cmath>中的log, log10函数.

运行时,奇怪的报错munmap_chunk(): invalid pointer

查询说的是内存分配/回收有关的函数报的错,然而我的代码里面并没有显示的使用malloc()等函数,只是在用了vector的resize()函数。当然在改成了int的数组之后就不会报错了。
启示:不是必须要使用变长数组的情况下,请开固定长度的数组,不要使用容器的resize去分配容量,有可能会导致runtime error!
附上报错以及正确的代码,以及对应的输入。题目:洛谷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

改造为静态数组后的代码

#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;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 219,635评论 6 508
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 93,628评论 3 396
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 165,971评论 0 356
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,986评论 1 295
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 68,006评论 6 394
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,784评论 1 307
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,475评论 3 420
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,364评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,860评论 1 317
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 38,008评论 3 338
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,152评论 1 351
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,829评论 5 346
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,490评论 3 331
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,035评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,156评论 1 272
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,428评论 3 373
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 45,127评论 2 356

推荐阅读更多精彩内容