ACM笔记

#include<bits/stdc++.h>

stl

1.

sort(数组首地址，数组尾地址，排序规则)

默认从小到大

左闭右开

sort(arr, arr+n, greater<int>());

或者自己写个bool函数

bool cmp(int a,int b) {     return a>b; } int n=5, arr[M]={1,5,4,2,3}; sort(arr, arr+n, cmp);

2.pair

pair<int,double> p;

pair<pair<int,double>,pair<int,double>> pp;

p.first p.second make_pair(v1,v2)

3.栈

stack<int> s;

s.push(x);

s.pop();

s.top();

s.size();

上述操作均为O(1)

4.队列

queue<int> q;

q.push(x);

q.pop();

q.front();

q.size();

5.vector

变长数组，向量

变长数组，适用于预先不知道开多大，或者想要轻快简便传参的情况。

vector<int> vc;

vc.push_back(x);

vc.size();

vc[i];

6.string

字符串，某种意义下可以认为是vector<char>。

string s1,s2;

s1=“XJTUICPC”

cin>>s2;

s1.size();

s1+=s2;

s1.find(s2);

7.map

映射,关联数组

以键值对（pair）的方式有序存储，可以使用类似数组的方式去操作。

map<int,int> mp;

mp[114514] = 5;

mp[1919810]++;

printf(“%d”,mp);

未指定的值默认0

8

位运算（与&，或|，异或^，非~，左移 << ，右移 >>

1&1=1    1&0=0    0&1=0    0&0=0

1|1=1    1|0=1    0|1=1    0|0=0

异或1⊕1=0    1⊕0=1    0⊕1=1    0⊕0=0    0⊕a=a         a⊕a=0     a⊕b=b⊕a             (a⊕b)⊕c=a⊕(b⊕c)     已知 a⊕b=c 如果我们知道a和c，求b?

 ~1=0    ~0=1

5≪2 = 20        5≫2=1

20=(10100)_2

5 =(00101)_2

1 =(00001)_2 如果右移越过最右端？如果左移越过最左端？ 过界部分就没了！ 可以用来快速乘除2的幂次。

找筷子：异或

有若干双筷子，筷子需要长度一样的才能组成一双。其中一只筷子被拿走了，给你剩下n只筷子的长度，问拿走的那只的长度。

9.给定一个大小为 n 的集合，判断该集合中存在多少个子集，满足子集中所有元素之和恰好为 0 。

枚举（二进制）

折半枚举：我们考虑将集合分成两半，大小分别为 ⌊n/2⌋ 和⌈n/2⌉，记为 A 和 B，共用一个map 

10.字典序

例如 a = “aabbc”, b = “aacbc” ，则字典序 a<b。

例如 a = [1, 2, 1], b = [1, 1, 6, 7] ，则字典序 a>b。

例如 a = [1, 1], b = [1, 1, 1] ，则字典序 a<b。

例如 a = [1, 2, 3], b = [1, 2, 3] ，则字典序 a=b。

11.模运算

%和mod不一样

(a±b)modp=(amodp±bmodp)modp

(a×b)modp=((amodp)×(bmodp))modp

a^bmodp=(amodp)^bmodp