ACMLife-0_1-cpp总结

ACMLife-0_1-cpp总结

  ACM
  1 小时 读完 (大约 7907 个字) 0次访问

[TOC]

序言

因为入了ACM的原因初识cpp，而从来都很少地熟悉她，只是拿着通用的编程语言技巧去使用她，这未免过于肤浅。

想要总结出cpp一些头文件在算法竞赛上的好用以及一些被忽略的用法，故对于一些在算法竞赛不常用且不算奇技淫巧的东西会选择性忽略。

stdio.h (cstdio)

在ACM比赛中，一般使用标准输入输出，读入题目输入，将程序输出与答案进行对比，来判定程序的正确性。

cstdio(C Standard Input and Output Library)是C语言的原生库，比起C++新定义的流对象操作库iostream在效率方面自然更优，故建议是只用cstdio，不用iostream，因为前者熟练使用起来几乎可以替代后者，且在时间效率上无懈可击。

cstdio这个库较为重要的知识在于五个方面：

  1. 格式化输入输出到标准IO流
  2. 格式化输入输出到字符串
  3. 单字符输入输出
  4. 输入输出重定向
  5. 快速读入、缓冲区冲刷

格式化输入输出到标准IO流

主要关注两个函数scanf、printf。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/* 变量定义 */
int i;  double d;  char c;  int is[15];  unsigned int ui;  long long ll;

/* 读入 */
scanf("%d %lf %c %d %u %lld", &i, &d, &c, &is[1], &ui ,&ll); // 其中&aa[1]可换为`aa + 1`
scanf("%1d", &i); // 只读1位到a

/* 输出 */
printf("%d %.2f %c %s %d %u %lld", i, d, c, s+1, is[1], ui, ll);  // 注意duoble输出是%f,%.2f表示四舍五入到百分位

/* 有关进制的输入输出 */
int a, b; scanf("%o %x", &a, &b); // 表示将输入看作8进制、16进制读入，比如输入"0777 0x3FFFFFF"(可以没有前导0、0x)。输出同理。

/* 有关占位输出和标准形式输出 */
printf("%*d", 5, 10); // 5位长度输出整数10
printf("%x %#x %#X", 15, 15, 15); // 输出f 0xf 0XF
printf ("%4.2f %+.0e %E \n", 3.1416, 3.1416, 3.1416); // 输出3.14 +3e+000 3.141600E+000

/* 变量地址的输出 */
int a; printf("%p %#p", a); // 输出类似00000053 0x53

/* 关于char[]的输入输出 */
char s[105];
scanf("%s", s); // 读入一个字符串，且首指针放到s+0
scanf("%s%s%s", s+1, s+21, s+41); // 读入三个字符串，且首指针分贝放到s+1、s+21、s+41，注意本样例若前两个字符串长度超过19，就会在内存有重叠而造成使用出错

/* 读入一行的处理 */
scanf("%[^\n]%*c\n", s); // 读入一行(第一种形式)，首指针为s+0。%*c表示忽略后一个字符
scanf("%[^\n]", s);getchar(); // 读入一行(第二种形式)，首指针为s+0。getchar()表示把\n取掉

printf("%s %s", s+0, s+1); // 分别表示从第0、1位开始输出，直到遇到'\0'，所以想截断输出一个字符串还可以将字符串的某个位置置为'\0'即可输出前半部分

/* 相关于string的输入输出 */
string s;s.resize(100); // 想用scanf读string必须预先设置大小
scanf("%s", &s[0]); // 读入到string

scanf("%[^\n]%*c", &s[0]); // 读入1行到string
/* 对于string的用scanf读入一行
  直接读入由于resize，有时会出现奇怪的问题（后面会填充为空格）
  比如读入下面的格式：
1
this is a bug problem.
*/

// 建议下面这样做：
char tmp[100];
scanf("%s", tmp+1);  s=tmp+1; // 先读入到char[]再令string=char[]
printf("%s", s.c_str());      // 输出string

/* 多组输入的实现-T组数组 */
int T;scanf("%d", &T);
while(T--) { /* 代码 */ }

/* 多组输入的实现-读入到文件末尾EOF */
while(~scanf("%d%d",&n,&m)) { /* 代码 */ }

/* 在stdin中输入结束符 */
Unix terminal "End of File" (same as "exit" on many shells) —— ctrl+d
DOS "End of File" —— ctrl+z

格式化输入输出到字符串

主要关注sscanf、sprintf。和scanf、printf的使用一致，只是输入、输出的对象从标准输入输出变成了char[]。

1
2
3
4
5
char s[] = "123 52.2 adas";
int a; double b; char ss[105];
sscanf(s, "%d%lf%s", &a, &b, ss); // a=123, b=52.2, ss="adas"
a++; ss[0]='b';
sprintf(s, "%d%lf%s", a, b, ss); // s="12452.2bdas"  后面还追有 '\0' 's' '\0'

单字符输入输出

大多数情况下scanf、printf配合%c可以适应单字符输入输出的要求。但是对于优化效率，getchar()、putchar()十分有用。

1
2
char c = getchar();  // 从标准输入读入一个字符
putchar(c);          // 输出一个字符到标准输出

输入输出重定向

freopen可以将标准输入输出导向文件，在一些规定了文件输入输出的ACM题目，或者本地调试时极为有用。

1
2
freopen("in.txt", "r", stdin);  // 重定向输入流
freopen("out.txt", "w", stdout);// 重定向输出流

快速读入、缓冲区冲刷

对于一些大量数据读入的ACM题目，格式化的输入，在底层对于识别格式串时已浪费不少时间。快速读入是一种声明了众多针对不同数据类型的读入函数，且预先将所有bytes当作char类型读到数组作为缓冲区，随后再从缓冲区中模拟读入的一种优化读入效率操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
char s[]="-123456"; // 模拟的缓冲区
void read(int &x)
{
    x=0; 
    bool sign=0;  int i=0;
    if(s[i] == '-') sign=1, i++; 
    for(; s[i]!='\0'; i++) x = x*10 + (s[i]-'0');
    if(sign) x=-x;
}


namespace fastIO {
    #define BUF_SIZE 100000        // 预定义缓冲区大小
    #define LL long long
    //fread->read
    bool IOerror=0;
    inline char nc(){
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if (p1==pend){
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if (pend==p1){IOerror=1;return -1;}
        }
        return *p1++;
    }
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    inline void read(int &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    inline void read(LL &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    inline void read(double &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (ch=='.'){
            double tmp=1; ch=nc();
            for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
        }
        if (sign)x=-x;
    }
    inline void read(char *s){
        char ch=nc();
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
        *s=0;
    }
    inline void read(char &c){
        for (c=nc();blank(c);c=nc());
        if (IOerror){c=-1;return;}
    }
    #undef LL
    #undef BUF_SIZE
}using namespace fastIO;
// 本地测试时，只能用freopen才可进行测试，读入改为read(n)，n为变量

缓冲区冲刷，fflush(stdout);，可以将输出缓冲区中的内容当即输出，在一些交互题上是必须要使用的。

ctype.h (cctype)

ctpye.h是对一些常用字符的判断、转换做了封装的一个C语言原生库。尽管大多可以用一行加减操作替代，但利用好，可以缩减代码长度，减少出错率，优化可读性，有学习的必要性。

例如，判断一个char字符我们可以这样写：if(c >= 'a' && c <= 'z')，但在ctpye.h封装的函数中，一句if(islower(c)更为简洁。更为深刻的例子当然有，比如判断一个字母或数字可以用if(isalnum(c))。

主要的函数有：

  • islower(c)，判小写字母。等效c>=’a’ && c<=’z’
  • isupper(c)，判大写字母。等效c>=’A’ && c<=’Z’
  • isalpha(c)，判字母。等效(c>=’a’ && c<=’z’ || c>=’A’ && c<=’Z’)
  • isdigit(c)，判数字
  • isblank(c)，判空白符
  • isspace(c)，判空格
  • tolower(c)，转为小写。等效c>=’A’&&c<=’Z’ ? c+’a’-‘A’ : c;
  • toupper(c)，转为大写

math.h (cmath)

数学库。常用的函数都有，比如cos、sin、tan、acos、asin、atan、exp、log、pow、sqrt。

pi的定义const double pi = acos(-1.0);

比较好用的向上取整ceil(1.2)，向下取整floor(1.2)，整数取绝对值abs(-232)，浮点数取绝对值fabs(-232.2323)。

fabs还可用于浮点数判等：

1
2
3
4
5
6
printf(0.1+0.1+0.1==0.3?"yes":"no");       // 输出no

// 判等 —— 允许误差内
const double eps = 1e-8;
double a, b;
if(fabs(a-b) < eps) printf("equals");

stdlib.h (cstdlib)

这个库定义了一些通用函数。而我们主要用到的是字符串转变量、转换进制输出到字符串、随机数生成。

字符串转变量

1
2
3
4
int i = atoi("12123");
long long l = atoll("321321321321321323");
double d = atof("-21.2323");  
char s[] = "12 2.33"; double d = atof(s+2); // s+2或s+3都行

转换进制输出到字符串

1
2
3
4
char s[100];
itoa(23, s, 2); // 23转换为2进制输出到字符串s
itoa(23, s, 3); // 23转换为3进制输出到字符串s
itoa(23, s, 8); // 23转换为8进制输出到字符串s

随机数生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* C语言的伪随机数 */
srand (time(NULL)); // 初始化随机数种子(生成器)，time函数在time.h库
int i = rand() % 10 + 1; // 随机生成一个位于[1, 10]的数
#define randInt(x,y) rand()%y+x // 定义一个随机数宏

/* mt19937随机数 */
mt19937 rnd(time(0));
printf("%lld\n", rnd());
// mt19937随机数-随机分布生成
auto dice_rand = bind(uniform_int_distribution<int>(1, 6), mt19937(time(0)));
auto real_rand = bind(uniform_real_distribution<double>(0,1),mt19937(time(0))); // [0,1)
auto real_rand1 = bind(uniform_real_distribution<double>(0,nextafter(1,DBL_MAX)),mt19937(time(0))); // [0,1]
cout << dice_rand() << endl;
cout << real_rand() << endl;
// 利用mt19937打乱序列
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
shuffle(s+1, s+1+n, rng);

string.h (cstring)

string.h定义了一些对于字符串、数组的常用操作。比较常用的有：获取字符串长度、字符串拷贝、字符串比较、字符串追加、字符串分割、内存拷贝、内存比较等。

字符串操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
char s[] = " 12354aaasd"
/* 获取字符串长度 */
int len = strlen(s+1);

/* 获取字符串中第一个'a'的下标 */
int stIndx = strchr(s+1, 'a')-s;

/* 字符串比较 */
int cmp = strcmp(s, "123"); // 相等返回0，<0则表示串1字典序小于串2

/* 字符串追加 */
strcat(s, "233333"); // 往字符串末'\0'位置追加内容，注意不能超长度

/* 字符串split，将一个字符串按某字符分割放入vector(regex有更简洁强大的写法) */
vector<string> v;
char str[] = "sda/das//d/sad/sa/d/dsad/";
char *p=strtok(str,"/");
while(p)
{
    v.push_back(p);
    p=strtok(null,"/");
}

内存操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* 内存拷贝 */
char a[20], b[20];
memcpy(a+2, b+1, sizeof(char)*10); // 将b+1后10个内存拷贝到a+2后
struct p {int a;double b;char c;} p1, p2;
memcpy(p1, p2, sizeof(p)); // 拷贝结构体

/* 数组初始化 */
int a[10];
memset(a, -1, sizeof(a)); // 初始化数组为-1
memset(a, 0, sizeof(a)); // 初始化数组为0
memset(a, 0x3fffffff, sizeof(int)*10); // 初始化数组为极大值
// 注意，除了-1、0、极大值外，不要穿其他值，因为传入int，填充内存时当作unsigned char进行填充

/* 内存比较 */
int a[3]={1,2,3}, b[3]={1,2,4};
memcmp(a, b, sizeof(int)*3); // 比较，会返回-1、0、1的一个

/* 获取素组中第一个1的下标 */
int a[10]={6,3,2,6,8,1,1,3,7,5};
int stIndx = (int*)memchr(a, 1, sizeof(int)*10) - a; // 其中数组长度10可用或者sizeof(a)/sizeof(a[0])替代

time.h (ctime)

time.h定义了获取、操作日期和时间的函数。常用用途有：获取当前cpu时间测评程序的运行时间、获取系统时间、巧妙利用库中函数处理时间戳。

测评程序运行时间

1
2
3
4
// 在算法末尾加上
#ifdef LOCAL
	printf("Time Cost: %.4f\n", clock()*1.0/CLOCKS_PER_SEC);
#endif

获得系统时间

1
2
time_t t; time(&t); // 或 time_t = time(NULL)
printf("%d %s", t, ctime(&t)); // 输出自1970年1月1日以来经过的秒数和“d m y h:m:s Y”格式的字符串

时间戳转格式化时间串

1
2
3
4
5
time_t t = time(0);
struct tm *p = gmtime(&t);
char s[100];
strftime(s, sizeof(s), "%Y-%m-%d %H:%M:%S", p); // string format time
printf("%d: %s\n", t, s); // 1498124250: 2017-06-22 09:37:30

格式化时间串转时间戳

1
2
3
4
5
6
7
8
9
char s[] = "2019-04-01 12:32:11";
struct tm t = {0};
t.tm_year = atoi(s) - 1900;       // 注意1900
t.tm_mon = atoi(s+5) - 1;         // 注意1
t.tm_mday = atoi(s+8);
t.tm_hour = atoi(s+11);
t.tm_min = atoi(s+14);
t.tm_sec = atoi(s+17);
printf("%d", mktime(&t));

获得某年某月是星期几

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* C++库 */
int year=2019, month=4, day=1;
time_t t = time(0);
struct tm *p;
p = gmtime(&t);
p->tm_year = year - 1900;
p->tm_mon = month - 1;
p->tm_mday = day;
mktime(p);  // 规整tm结构体的变量，更新p->tm_wday
printf("That day is a %d\n", p->tm_wday); // 0是星期天1是星期一

/* 蔡勒公式 */
int Day(int y, int m, int d) 
{ // 1~7分别表示星期一到星期日
    if (m == 1 || m == 2) {m += 12;--y;}
    return (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7 + 1;
}

array

array是c++11中定义的容器类。用法大多与原生数组所重，更方便的用法在不定长数组vector中也得以体现，所以array相对有用的东西较少，学习必要性较小。

1
2
3
/* 获得数组长度 */
int a[] = {1,2,3,4,4};
int len = sizeof(a) / sizeof(a[0]) = end(a) - begin(a);

vector

vector是不定长数组容器。其数组长度的扩增策略是每次乘2，所以倘若数组长度下界较为确定的话，声明vector时传入初始大小是比较明智的。

对于容器类，较为关注的是它的声明、赋值、遍历、清空操作及相应复杂度了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* 声明 */
vector<int> v(10);    // 初始大小为10
vector<int> v(10, 0); // 初始大小为10，每个值都是0
vector<vector<int> > G(n+1,vector<int>(m+1));  // 二维动态数组声明
/* 赋值 */
v.push_back(20); // 末尾放入一个元素20
v[0] = 12; // 首元素改为12
v.insert(v.begin()+1, 1);  // 第2个位置插入1
v.emplace(v.begin()+1, 1); // 第2个位置插入1，不复制构造而直接插入，优化
/* 遍历 */
for(int i=0, n=v.size();i<n;i++) printf("%d\n", v[i]); // 原生
for(vector<int>::iterator it=v.begin();it!=v.end();++it) printf("%d\n", *it); // 迭代器
for(int i : v) printf("%d", i); // for range
for(auto i : v) printf("%d", i); // for range
for(auto &i : v) i++; // 每个数自增1
/* 清空 */
v.clear(); // 整个清空
v.pop_back(); // 删除最后元素 
v.erase(v.begin()); // 删除首个元素
v.erase(v.begin(), v.begin()+3); // 删除前3个元素

list

list是链表容器。将数组换作链表使用，更在意的是其增删操作的时间复杂度和存储的空间复杂度。在链表容器中，除了对基本函数了解外，理应对迭代器有较好的理解和应用。若对时空复杂度有更高要求，单向链表forward_list也许更适合，但由于操作的相似性，就不提及了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/* 声明 */
list<int> l1;
list<int> l2(l1.begin(), l1.end()-1); // 拷贝其他链表的一部分，复杂度是O(n)

/* 赋值 */
l1.push_back(1);  // 在链表尾加一个元素
l1.push_front(1); // 在链表头加一个元素

/* 遍历 */
l1.front(); // 首元素
l1.back();  // 尾元素
for(list<int>::iterator it = l1.begin(); it != l1.end(); it++) printf("%d\n", *it);
for(list<int>::reverse_iterator it = l1.rbegin(); it != l1.rend(); it++) printf("%d\n", *it);
for(auto &i : l) printf("%d ", i);

/* 迭代器删减 */
list<int>::iterator it = l1.begin();
it++; // 迭代器移动
l1.insert(it, 1);  // 在迭代器后加一个元素
it = l1.erase(it); // 删除迭代器当前元素，必须重新赋值迭代器否则失效，赋值后迭代器等于被删元素下一个

/* 清空 */
l1.pop_front(); // 删除首元素
l1.pop_back();  // 删除尾元素
l1.clear();     // 清空链表

/* 排序，复杂度nlogn */
bool cmp(const int &o1, const int &o2) {return o1 > o2;}
l1.sort(cmp); // 空参数为递减

/* 链表反向 */
l1.reverse();

/* 链表拼接 */
l1.splice(l1.end(), l2); // 之后l2被清空 
l1.splice(l1.end(), l2, l2.begin(), l2.end());
l1.merge(l2)；           // 有序链表的归并

/* 删除链表中全部某值元素 */
l1.remove(89);                                                            // 第一种
bool cmp(const int &o) {return o==89;}                 l1.remove_if(cmp); // 第二种

/* 去重 */
l1.sort(); l1.unique();

map

map是关联容器，提供键-值对的映射方法，底层是红黑树。在map头文件中提供了map和multimap两种，其中multimap提供了单键多值映射。一般使用map，主要使用在离散化数据、判重。unordered_map是无序map，无法简单获得升序键-值，但在时间复杂度上有些许优化，用法类似，不提及了。

单键单值映射

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* 声明 */
map<int, bool> mp;

/* 赋值 */
mp[13] = true;

/* 查key是否有对应value */
if(mp[13]) printf("visited"); // 这里可以直接如此，而如果 value 类型非 bool 时需换成以下这种
if(mp.find(13) != mp.end()) printf("visited");

/* 遍历 */
for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++)
    printf("%d %d\n", it->first, it->second); // 输出是升序的
for(map<int,int>::reverse_iterator it=mp.rbegin();it!=mp.rend();it++)
    printf("%d %d\n", it->first, it->second); // 输出是降序的

/* 遍历 c++11 特性 */
for(auto &entry : mp) printf("%d %d\n", entry.first, entry.second); // for range

/* 清空 */
mp.erase(13); // 以键为关键字删除某该键-值对，复杂度是 log
mp.clear();

/* 常量map声明，而不是声明一个空的map随后在main中赋值 */
const map<char, char> mp({
    {'R', 'P'},
    {'P', 'S'},
    {'S', 'R'}
});

单键多值映射

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 声明 */
multimap<int, int> mp;

/* 赋值 */
mp.insert({1, 3});
mp.insert(make_pair(1, 3));

/* 遍历，全部遍历和map一样，主要关注单值遍历 */
for(multimap<int,int>::iterator it=mp.find(1); it->first==1; it++)
    printf("%d %d\n", it->first, it->second); // 所有键为1的键-值对

auto it = mp.lower_bound(1);  // 遍历所有键为1的键-值对
for(int i=0;i<mp.count(1);i++,it++) printf("%d %d\n", it->first, it->second);

/* 清空 */
mp.erase(1); // 删除所有键为1的键值对
mp.clear();

离散化数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 利用map离散化 */
map<int,int> mp; int indx=0;
// 输入数组a
sort(a,a+n);
for(int i=0;i<n;i++)
{
  if(mp.find(a[i]==mp.end())) mp[a[i]] = ++indx;    
  a[i] = mp[a[i]];
}

/* 利用unique、upper_bound离散化 */
vector<int> V;
// 输入V;
sort(V.begin(). V.end());
V.erase(unique(V.begin(), V.end()), V.end());
int getid(int x) {return upper_bound(V.begin().V.end(),x)-V.begin()+1;}

unordered_map

底层是基于开链法的哈希表

主要关注一下结构体的 hash 重写和 equals 重写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct Node {
    Node() {}
    Node(int _x, int _y):x(_x), y(_y) {}
    int x, y;
    bool operator == (const Node &t) const {
        return  x==t.x && y==t.y;
    }
};
struct NodeHash {
    std::size_t operator () (const Node &t) const {
        return  t.x * 100 + t.y;
    }
};
unordered_set <Node, NodeHash> h_set;
unordered_map <Node, string, NodeHash> h_map;

/* 结合 Lambda 的写法 */
unordered_set <Node, NodeHash> h_set;

set

set集合。底层是红黑树。在set头文件中提供了set和multiset两种，其中multiset允许元素重复。在ACM中用到set，主要用来维护不重复数组。对于集合本身的性质应用——求交并差集，在algorithm库里，是利用vector实现的。当然，如果是在线维护不重复数组，并且要求交并差的话，set是不错的选择。

注意一下，set删除数值是log级别的时间复杂度，删除指针所指的节点则是摊销常数。

非重复集合

可重复集合用法大都与非重复集合相同，且使用频率不大，可以忽略。故只涉及非重复集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 声明 */
set<int> s;

/* 赋值 */
s.insert(1);
s.insert(2);

/* 遍历 */
if(s.find(1) != s.end()) printf("The element is in set");
for(set<int>::iterator it=s.begin();it!=s.end();it++) printf("%d", *it); // 全部遍历
for(auto &x : s) printf("%d\n", x); 
int sz = s.size(); // 大小

/* 清空 */
s.erase(val); // 删除复杂度是logn
s.clear();

/* 二分 */
set<int>::iterator it = s.lower_bound(val); // 查找第一个大于等于 val 的元素，返回指针
if (it != set.end())    // 存在该元素
    printf("%d\n", *it);

集合交并差

1
2
3
4
5
6
#include <algorithm>
set<int> A, B, ans;
set_intersection(A.begin(), A.end(), B.begin(), B.end(), inserter(ans, ans.begin())) // 交
set_union(A.begin(), A.end(), B.begin(), B.end(), inserter(ans, ans.begin())) // 并
set_difference(A.begin(), A.end(), B.begin(), B.end(), inserter(ans, ans.begin())) // A-B
set_difference(B.begin(), B.end(), A.begin(), A.end(), inserter(ans, ans.begin())) // B-A

stack

stack，栈，先进后出的数据结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 声明 */
stack<int> s;
stack<int, vector<int> > s; // 指定底层容器的栈
stack<int, list<int> > s;   // 指定底层容器的栈

/* 赋值 */
s.push(1); // 将1压栈

/* 访问 */
s.top();   // 访问栈顶

/* 清空 */
s.pop();                             // 弹出栈顶
while(!s.empty()) s.pop();           // 清空栈
for(int i=s.size(); i; i--) s.pop(); // 清空栈

queue

queue，队列，先进先出的数据结构。queue中提供了队列queue、优先队列priority_queue，还有一种双端队列在另外一个头文件deque。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* 声明 */
queue<int> q;
priority_queue<int> pq;                             // 优先队列，大根堆
priority_queue<int, vector<int>, less<int> > pq;    // 大根堆, 结构体重载<方法
priority_queue<int, vector<int>, greater<int> > pq; // 小根堆, 结构体重载>方法


// 大根堆 O(n) 线性构造
int a[] = {1,3,4,6,78,9}
priority_queue<int> pq(a, a+6);                     

/* 赋值 */
q.push(1); // 将1入队
pq.push(1);

/* 队列访问 */
q.front(); // 访问队首
q.back();  // 访问队尾

/* 优先队列访问 */
pq.top();  // 访问堆顶

/* 清空，二者是相同的 */
q.pop();                           // 队首出队
pq.pop();                          // 弹出堆顶
while(!q.empty()) q.pop();         // 清空队列
for(int i=q.size();i;i--) q.pop(); // 清空队列

deque

双端队列。用法大多与list类似，不赘述。

algorithm

算法库，主要关注：二分、排序、去重、全排列等。

二分

1
2
3
4
5
vector v = {10,10,10,20,20,20,30,30};
int indx = lower_bound (v.begin(), v.end(), 20)-v.begin(); // 返回第一个大于等于20的数的下标  即3
int indx = upper_bound (v.begin(), v.end(), 20)-v.begin(); // 返回第一个大于20的数的下标  即6

if(binary_search(v.begin(), v.end, 20)) printf("existed"); // 在有序序列中找某个数，第4个参数可传cmp函数。

排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int a[] = {5,3,1,4};
vector<int> b = {5,3,1,4};
sort(a, a+4);                 // 左闭右开区间 升序排序
sort(b.begin()+1, b.end());   // 只排序第2个元素及其后面的元素，升序排序
sort(a, a+4, greater<int>()); // 降序排序

struct P { int a,b,c; }Ps[10];
bool cmp(const P &p1, const P &p2) { return a!=p.a ? a<p.a : (b!=p.b ? b<p.b : c<p.c); }
sort(Ps, Ps+10, cmp); // 传参比较方法，三关键字升序排序


struct P {
    int a,b,c;
    bool operator<(const P &p) const {// 第1关键字升序，第2关键字降序，第3关键字升序的多关键字排序
        if(a != p.a) return a < p.a;
        if(b != p.b) return b > p.b;
        return c < p.c;
    }
}Ps[10];
sort(Ps, Ps+10);      // 重载比较方法，第1关键字升序，第2关键字降序，第3关键字升序的多关键字排序

// Lambda 支持的结构体多关键字排序
struct P { int a,b,c; }Ps[10];
sort(Ps, Ps+10, [](P &p1, P &p2)->bool{
    if(p1.a != p2.a) return p1.a < p2.a;
    if(p1.b != p2.b) return p1.b > p2.b;
    return p1.c < p2.c;
});

去重

1
2
3
4
5
6
7
8
vector<int> a = {5,3,54,2,1,34,1,1,1,4};
sort(a.begin(), a.end());                        // 去重前先排序
a.resize(unique(a.begin(),a.end()) - a.begin());// 去重，本质是将重复元素移到末尾，返回尾指针

int a[] = {1,2,3,1};
int n = sizeof(a)/sizeof(a[0]);
n = unique(a, a+n) - a;    // 如果下标从1开始则还要改成unique(a+1, a+n+1)-a-1，同时注意a[0]对a[1]的影响
// unqiue 第3个参数可以传入自定义cmp函数来判断"重复"

全排列

1
2
3
4
5
6
7
int a[] = {3,2,1};
sort(a, a+3);       // 全排列的输出顺序是字典序的，若不先排序，则只会输出该状态以及之后的排列
do{
    for(auto x:a) printf("%d ", x);
    printf("\n");
}while(next_permutation(a, a+3));       // 输出123全排列
prev_permutation(a, a+3);               // 向前一个排列

旋转

1
2
vector<int> a = {1,2,3,4,5,6,7};
rotate(a.begin(), a.begin()+4, a.end());  // 将a.begin()到a.end()之间，以a.begin()+4为界的左右部分调换，得到{4,5,6,7,1,2,3}，复杂度是线性的，不如了解一下更玄的memcpy?

打乱

1
2
3
vector<int> a = {5,3,54,2,1,34,1,1,1,4};
random_shuffle(a.begin(), a.end());      // 听说在排序前打乱一下会有玄学效用！
sort(a.begin(), a.end());

数组判断

1
2
3
4
5
6
bool IsOdd(int i) {return i%2;}
vector<int> a = {1,3,5,7};
if(all_of(a.begin(), a.end(), IsOdd)) printf("All odd!");     // 全是奇数
if(any_of(a.begin(), a.end(), IsOdd)) printf("odd existes!"); // 存在奇数
if(none_of(a.begin(), a.end(), IsOdd)) printf("no odd");      // 不存在奇数
int odd = count_if(a.begin(), a.end());                       // 奇数数目

数组取最值

1
2
3
4
5
// max_element、min_element 返回的是地址
int a[10]; for(int i=0;i<10;i++) a[i] = i;
cout << "minElementIndex: " << min_element(a, a+10)-a << endl; // vector的话 min_element(a.begin(), a.end())-a.begin();
cout << *min_element(a, a+10) << endl;
cout << *max_element(a, a+10) << endl;

functional

functional库，主要关注几个普适的比较函数，在需要传入普通数据类型的比较函数时就不要自己重写cmp了。

1
2
3
4
int a[5] = {5,2,1,4,3};
sort(a, a+5, greater<int>()); // 降序
sort(a, a+5, less<int>());    // 升序
priority_queue<int, vector<int>, greater<int> > Q; // 大根堆

Lambda

Lambda不是cpp中某个库，而是C++11新支持的一个特性，Lambda是基于数学中的λ演算得名的，在C++11里表现为匿名函数的支持，可以替代掉一些一次性的谓词函数，起到简化逻辑、增加可读性的作用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 传统的排序 */
bool cmp(int a, int b) {return a<b;}
int a[] = {1,5,3,2};
sort(a, a+4, cmp);

/* 引入Lambda，写匿名函数 */
sort(a, a+4, [](int a,int b)->bool{return a<b;} );

/* 匿名函数 */
auto func = [](int x){ printf("%d\n", x); };   // 这甚至是一个void函数
func(123);                                     // 输出 123

/* 带返回值的匿名函数 */
auto IsOdd = [](int x)->bool{return x%2;};
printf(IsOdd(1) ? "YES" : "NO");

// 多的不深入探究了

string

字符串，主要关注各种操作函数：读入、转换、取长度、取下标字符、截取字符串、查找串、拼接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 读入 */
getline(I流， string对象, 分割char);   // 这个一个结合cpp流特性的方法，即从Input流中读入一个string，以分割字符为界。

/* 数字转字符串 */
strings s = to_string(2323.232);

/* 取长度 */
int sz = s.size();

/* 取下标字符 */
char c = s[2];

/* 截取字符串 */
string ss = s.substr(2, 3);  // 从第2个字符开始截取长度为3的串

/* 查找串 */
size_t found = s.find("23", 0); // 从位置0开始找到第1个串"23"，找到返回下标，否则found=string::npos
size_t found = s.rfind("23", s.size()-1); // 从右侧开始找到第1个串"23"，至多找到至pos

/* 拼接 */
s += "aaaa";

sstream

sstream是cpp中流的一种，在输入输出章节中，我们大多用scanf、printf替代了cin、cout的作用。但是将流用好，可以起到巧妙处理字符串的功效。其中有学习必要性的是stringstream、istringstream。

主要关注：类型转换、分割处理

类型转换

1
2
3
4
5
6
7
stringstream ss;
ss << "1234"; // 将字符串"1234"插入流中
int a;
ss >> a;      // 从流中导出数据到int
ss.clear();   // 重复使用是有必要的，因为stringstream声明很慢。重复使用要注意清空流
ss << true;
ss >> a;

分割处理

1
2
3
4
5
6
7
8
// 和java的Scanner一样好用
istringstream iss("I want to do what I want");
string s;
while(getline(iss, s, ' ')) printf("%s\n", s.c_str()); // 忽略空格得到单词

istringstream iss("I want to do\nwhat I want");
string s;
while(getline(iss, s, '\n')) printf("%s\n", s.c_str()); // 忽略换行得到断句

regex

正则表达式，C++11支持。有关正则语法单独讲，这里只讲cpp的正则用法。

正则表达式主要关注：匹配、替换、提取、切割。

匹配

1
2
3
regex re("^abcd(.*)dddd", regex::icase); // 第二个参数是忽略大小写
printf(regex_match("abcdasdjufhuiadddd", re) ? "yes": "no");    // yes
printf(regex_match("233abcdasdjufhuiadddd", re) ? "yes": "no"); // no

替换

1
2
3
string s = "<div class=233> <div class=2333>";  // 现在需要将<>里的div换成html
s = regex_replace(s, regex("<div (.*?)>"), "<html $1>");
printf("%s\n", s.c_str()); // 输出<html class=233> <html class=2333>

提取

1
2
3
4
string s = "<html>  <divdaf ssd> <asdsad>";
regex re("<(.*?)>");
for(sregex_iterator p(s.cbegin(), s.cend(), re), q; p != q; ++p)
    printf("匹配串:%s 匹配部分:%s\n", p->str().c_str(), p->format("$1").c_str());

切割

1
2
3
4
5
6
7
8
/* 切割单词后放入一个vector */
string s = "who lives in a pineapple under the sea?";
regex re(" ");
vector<string> ans{
    sregex_token_iterator(s.begin(), s.end(), re, -1),
    sregex_token_iterator()
};
for(auto &x : ans) printf("%s\n", x.c_str());

bitset

bitset，仿真的bool数组、01序列，但bool变量是1byte长度，而bitset每个0、1是1bit，具有极优的空间复杂度。除此之外，还有位设置、位翻转等遍历操作。

需要注意，bitset是cpp特有的库，对printf的输出以及直接判某位为1不太友好，对cout情有独钟，调试输出的时候需稍加码量，或换用cout。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/* 声明 */
bitset<16> a;           // 空，全零 0000000000000000
bitset<16> b(0x3fff);   // 整数参数 0011111111111111
bitset<16> c("00101");  // 字符串   0000000000000101

/* 赋值 */
a[0] = 1;    // 低位第0位设为1
a.set(0, 1); // 低位第0位设为1
a.set(0);    // 低位第0位设为1
a.set(0, 0); // 低位第0位设为0
a.set();     // 设为全1
a.reset();   // 设为全0，该函数同样有两个参数，参数1为pos，参数2位value(为空时是0)
a.flip(1);   // 翻转第1位
a.flip();    // 翻转整个01串
a<<=1;       // a左移1位

/* 遍历 */
cout << a << endl;                     // cout输出整个01串
printf("%s\n", a.to_string().c_str()); // printf输出整个01串，较为麻烦一些
cout << a[0] << endl;                  // cout输出低位第0位
printf("%d\n", a[0]==1);               // printf输出低位第0位

/* 判位、换型 */
a.test(0);                          // 判断第0位是否为1
a.any();                            // 判断是否至少1位为1
s.none();                           // 判断是否全0
int one = a.count;                  // 获得1的个数
string s = a.to_string();           // 转换为字符串
unsigned long = a.to_ulong();       // 转换为无符号整形
unsigned long long = a.to_ullong(); // 转换为无符号整形

/* 枚举子集技巧 */
for(int s = (1<<n)-1; s; s = (s-1)&((1<<n)-1))

tuple

tuple元组，是多个可异类型数据组成的数据组。utility中的pair是二元组，是tuple的特例。tuple在数组类型较为单一时，比起单独设置struct有更棒的可读性和简洁性。

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 声明 */
tuple<int, double, long long> t;
tuple<int, int, int, int> t(1, 2, 3, 4);
tuple<string, int> t = make_tuple("haha", 2333);

/* 赋值 */
get<2>(t) = 2333333333333; // 对第2个（也就是第3）元素赋值

/* 访问 */
int a = get<0>(t);                            // 取第0部分到a
int a;double b;long long c; 
tie(a, b, c) = t;                             // 分别取0、1、2部分到a、b、c
int sz = tuple_size<decltype(t)>;             // 获得元组长度

gcc的__builtin_函数

GCC提供了一系列的builtin函数，可以实现一些简单快捷的功能来方便程序编写，另外，很多builtin函数可用来优化编译结果。这些函数以“__builtin_”作为函数名前缀，大都与位有关。

  • __builtin_popcount(x)：x中1的个数。
  • __builtin_popcountll(x)：x中1的个数，x是long long。
  • __builtin_ctz(x)：x末尾0的个数 。x=0时结果未定义。
  • __builtin_clz(x)：x前导0的个数。x=0时结果未定义。
  • __builtin_parity(x)：x中1的奇偶性。奇1偶0。
  • __builtin_ffs(x)：返回x右起第一个’1’的位置
  • __gcd(a, b)：返回a和b的最大公约数

调用 Linux 分解质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
string exec(const char *cmd) {
    array<char, 128> buffer;
    string result;
    unique_ptr<FILE, decltype(&pclose)> pipe(popen(cmd, "r"), pclose);
    if (!pipe)throw std::runtime_error("popen() failed!");
    while (fgets(buffer.data(), buffer.size(), pipe.get()) != nullptr)
        result += buffer.data();
    return result;
}
ll T, n;
string s, t;
int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> T;
    while (T—) {
        cin >> n;
        t = exec(("factor " + to_string(n)).c_str());
        istringstream sin(t);
        while (sin >> s);
        if (stoll(s) == n)s = "Prime";
        cout << s << endl;
    }
}

define、typedef

define、typedef，宏定义，是C++两种适合用于简化代码重复的手段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/* 定义max */
#define max(a,b) ((a>b)?a:b)
/* 定义PI */
#define PI acos(-1.0)   
/* 重定义，便于pair使用 */
#define PT pair<int, int>
#define x first
#define y second             
/* 重定义long long */
typedef long long LL;
/* 文件输入输出 */
#define FILE(x) freopen(x".in","r+",stdin);freopen(x".out","w+",stdout) // 重定义输入输出

/* 调试神器(通用,不带颜色) */
#ifdef LOCAL
    void dbg() { cout << "\n"; }
    template<typename T, typename... A>
    void dbg(T a, A... x) { cout << a << ' '; dbg(x...); }
    #define logs(x...) cout << #x << " -> "; dbg(x);
#else
    #define logs(...)
#endif

/* 调试神器(linux,带颜色) */
#ifdef LOCAL
    void dbg() { cout << "\033[39;0m\n"; }
    template<typename T, typename... A>
    void dbg(T a, A... x) { cout << a << ' '; dbg(x...); }
    #define logs(x...) cout << "---------------- \033[32;1m" << #x << " -> "; dbg(x);
#else
    #define logs(...)
#endif

/* 调试神器(Windows,带颜色) */
namespace tttt {
    #define rep(i,s,t) for(int i=s;i<=t;i++)
    #define rrep(i,s,t) for(int i=s;i>=t;i--)
    #ifdef LOCAL
        #include <windows.h>
        #include <iostream>
        class WinCMD {public:static HANDLE WinCMDHandle;static HANDLE WinCMDInit(){WinCMDHandle=GetStdHandle(STD_OUTPUT_HANDLE);setColor(0x02);std::cout<<"\t\t\t\t\tWelcome to TTTT\'s WinCMD v0.3\n\n\n\n\n\n";setColor(0x07);return WinCMDHandle;}static void setColor(int x){SetConsoleTextAttribute(WinCMDHandle,x);}static void setGrey(){setColor(0x08);}static void setGreen(){setColor(0x0A);}static void setWhite(){setColor(0x07);}};HANDLE WinCMD::WinCMDHandle=WinCMD::WinCMDInit();
        #define o(x) std::cout<<x;
        #define O(x) WinCMD::setGrey();o(""#x);WinCMD::setWhite();o("[");WinCMD::setGreen();o(x);WinCMD::setWhite();o("] ");
        #define arg_cnt_1(...) arg_cnt_2(__VA_ARGS__)
        #define arg_cnt_2(_1,_2,_3,_4,_5,_6,N,...) N
        #define arg_cnt(...) arg_cnt_1(__VA_ARGS__,6,5,4,3,2,1,0)
        #define log1(a,...) o("log1: ");O(a);o("\n");
        #define log2(a,b,...) o("log2: ");;O(a);O(b);o("\n");
        #define log3(a,b,c,...) o("log3: ");O(a);O(b);O(c);o("\n");
        #define log4(a,b,c,d,...) o("log4: ");O(a);O(b);O(c);O(d);o("\n");
        #define log5(a,b,c,d,e,...) o("log5: ");O(a);O(b);O(c);O(d);O(e);o("\n");
        #define log6(a,b,c,d,e,f,...) o("log6: ");O(a);O(b);O(c);O(d);O(e);O(f);o("\n");
        #define loga(a,s,t) {o("\t\t\t\t"#a": ");for(int i=s;i<=t;i++){WinCMD::setGrey();o(i);WinCMD::setWhite();o("[");WinCMD::setGreen();o(a[i]);WinCMD::setWhite();o("] ");}o("\n");}
        #define logs(...) {o("\t\t\t\t");switch(arg_cnt(__VA_ARGS__)){case 1:log1(__VA_ARGS__);break;case 2:log2(__VA_ARGS__,2);break;case 3:log3(__VA_ARGS__,2,3);break;case 4:log4(__VA_ARGS__,2,3,3);break;case 5:log5(__VA_ARGS__,2,3,3,3);break;case 6:log6(__VA_ARGS__,2,3,3,3,3);break;};}
    #else
        #define logs(...)
        #define loga(a,s,t)
    #endif
}using namespace tttt;


#define arg_cnt(...) std::tuple_size<decltype(std::make_tuple(__VA_ARGS__))>::value; // 计算不定参数宏的参数数目
#define arg_cnt(...) (sizeof((int[]){0, ##__VA_ARGS__})/sizeof(int)-1); // 另一种解决但只能在参数为int情况

Code::Blocks使用

ACM竞赛中，一般使用CB作为IDE，调配CB变得好用首当其冲。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
1.【控制台界面更改】：
  Settings->Environments->
  把"xterm -T $TITLE -e"改成“gnome-terminal -t $TITLE -x“
  然后就可以欢快地"Shift+Ctrl+C/V"复制粘贴了！

2.【代码提示功能优化】：
Setings->Editor->Code pompletion->
(1).Delay for auto-kick-in when typing [.::->] 改为200ms
(2).将Keyword sets to additionally include中1到9都勾上
(3).将Automatically launch when typed # letter中的4改成2，这样打两个字母就会有提示了。

3.【增加#define LOCAL】
Setings->Compiler->Global compiler settings->第二个内窗口有一个选项卡#defines->新起一行加上LOCAL这5个字母

4.【快捷键更改】
Settings->editor->Keyboard shortcuts
(1).变量重命名：Edit->Rename symbols    Ctrl+R
(2).运行键：Build->run                 F10
(3).另存为：File->Save file as...      Ctrl+Shift+S

5.【模板文件】
Settings->editor->Abbreviations
(1).在keywords栏点击"add"，起一个名字，然后把代码放到黑区
(2).在代码中加一个|表示光标起始
(3).回到编辑器，输入刚才模板命名，再按Ctrl+J。

OJ手动加栈

第一行加上#pragma comment(linker, "/STACK:1024000000,1024000000")，提交选c++编译器可以加栈内存。

  ACM, Language, cpp

喜欢这篇文章？投喂一下吧！ヾ(●´∀｀●)

ACMLife-0_2-Java总结
ACMLife-0_0-领航帖

评论

  关注我
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×