ACM notes

#include<bits/stdc++.h>

stl

1.

sort( Array first address , Array tail address , Sort rule )

Default from small to large

Left closed right away

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

Or write it yourself bool function

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

stack<int> s;

s.push(x);

s.pop();

s.top();

s.size();

The above operations are O(1)

4. queue

queue<int> q;

q.push(x);

q.pop();

q.front();

q.size();

5.vector

Variable length array , vector

Variable length array , It is suitable for those who don't know how much to open in advance , Or if you want to transfer parameters quickly and easily .

vector<int> vc;

vc.push_back(x);

vc.size();

vc[i];

6.string

character string , In a sense, it can be regarded as vector<char>.

string s1,s2;

s1=“XJTUICPC”

cin>>s2;

s1.size();

s1+=s2;

s1.find(s2);

7.map

mapping , Associative array

Pair with key value （pair） Orderly storage , You can operate in an array like manner .

map<int,int> mp;

mp[114514] = 5;

mp[1919810]++;

printf(“%d”,mp);

Unspecified values default to 0

8

An operation （ And &, or |, Exclusive or ^, Not ~, Move left << , Move right >>

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

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

Exclusive or 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)     It is known that a⊕b=c If we knew a and c, seek b?

 ~1=0    ~0=1

5≪2 = 20        5≫2=1

20=(10100)_2

5 =(00101)_2

1 =(00001)_2 If you move right past the rightmost end ？ If you move left past the leftmost end ？ The crossing part is gone ！ It can be used to multiply and divide quickly 2 The power of .

Looking for chopsticks ： Exclusive or

There are several pairs of chopsticks , Chopsticks need the same length to form a pair . One of the chopsticks was taken away , Here you are n The length of chopsticks , Ask the length of the one you took away .

9. Given a size of n Set , Determine how many subsets exist in the set , The sum of all elements in the subset is exactly 0 .

enumeration （ Binary system ）

Half enumeration ： We consider splitting the set into two halves , The sizes are ⌊n/2⌋ and ⌈n/2⌉, Write it down as A and B, Share one map 

10. Dictionary order

for example a = “aabbc”, b = “aacbc” , Then the dictionary order a<b.

for example a = [1, 2, 1], b = [1, 1, 6, 7] , Then the dictionary order a>b.

for example a = [1, 1], b = [1, 1, 1] , Then the dictionary order a<b.

for example a = [1, 2, 3], b = [1, 2, 3] , Then the dictionary order a=b.

11. Modular arithmetic

% and mod Dissimilarity

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

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

a^bmodp=(amodp)^bmodp