NOIP复赛笔记
这是一个普通的备赛笔记
一些基本函数和C++中STL库的用法
多记住一点，万一复赛用上了呢！另一个笔记
Heads
#include <bits/stdc++.h>
using namespace std;Class & Struct
基本结构
class Node
{
private:
......
public:
......
};
struct Node
{
......
};构造函数
Node(int a, int b, int c) : x(a), y(b), z(c)
{
Volume = x * y * z;
}重载运算符
Node operator+(const Node &b)
{
Node n(this->x + b.x, this->y + b.y, this->z + b.z);
return n;
}STL
Containers 容器
Member 成员列表
container.begin();//头元素迭代器
container.end();//尾元素迭代器
container.rbegin();//反向头元素迭代器
container.rend();//反向尾元素迭代器
container.size();//大小
container.empty();//是否为空
container.max_size();//最大大小Sequence containers 序列容器
Constructor 构造函数
Container
std::container<type> first; // 空type队列
std::container<type> second (num,val); // num个值为val的type
std::container<type> third (second.begin(),second.end()); // 通过第二个新建
std::container<type> fourth (third); // 第三个的副本String
std::string s0 ("Initial string");
// constructors used in the same order as described above:
std::string s1;
std::string s2 (s0);
std::string s3 (s0, 8, 3);
std::string s4 ("A character sequence");
std::string s5 ("Another character sequence", 12);
std::string s6a (10, 'x');
std::string s6b (10, 42); // 42 is the ASCII code for '*'
std::string s7 (s0.begin(), s0.begin()+7);s1:
s2: Initial string
s3: str
s4: A character sequence
s5: Another char
s6a: xxxxxxxxxx
s6b: **********
s7: Initial
Member 成员列表
container.front();//第一个元素引用
container.back();//最后一个元素引用
container.at(n);//返回第n个元素引用
container[n];//返回第n个元素引用
container.assign(first,last);//分配数组到容器
container.assign(n,val);//填充分配n个val
container.insert(position,val);//插入元素val到position位置
container.insert(position,n,val);//从position位置填充n个val
container.insert(position,first,last);//将一段区域[first,last)插入position位置
container.erase(position);//移除元素
container.erase(first,last);//移除区间[first,last)
container.push_back(val);//末尾添加元素
container.pop_back(val);//末尾删除元素
container.clear();//清空容器
container.swap(container);//交换容器[动态数组] <vector> vector
template < class T, class Alloc = allocator<T> > class vector;特有函数
vector.reserve();//反转数组[列表] <list> list
template < class T, class Alloc = allocator<T> > class list;特有函数
无 list[]; list.at()
list.reverse();//反序
list.push_front();//首添加元素
list.pop_front();//首删除元素
list.unique();//删除重复值
list.unique(cmp);//删除cmp返回true的重复值
list.sort();//排序
list.sort(cmp);//以cmp返回值排序
list.merge(list);//合并列表
list.merge(list,cmp);//通过cmp排序合并
list.remove(val);//删除val
list.remove_if(pred);//删除pred返回true的值[双端数组] <deque> deque
template < class T, class Alloc = allocator<T> > class deque;特有函数
deque.push_front();//首添加元素
deque.pop_front();//首删除元素[字符串] <string> string
typedef basic_string<char> string;特有函数
//std::string::npos <=> 空串
sring.reserve();//反转
string.length();//长度
string[n];//访问
string.at();//访问
string += string;//拼接
string = string + string;//拼接
string.append(string);//拼接
string.push_back(char);//添加字符
string.substr(pos,len);//从pos开始分离长度为len的子字符串
string.find(str);//查找str位置
string.find(char);//查找char位置
string.find(str,pos);//从pos开始查找str
//查找 第一个(最后一个) 匹配(不匹配) str中任何字符的值,类似于find可以从pos开始
string.find_first_of(str);
string.find_last_of(str);
string.find_first_not_of(str);
string.find_last_not_of(str);append 的用法
std::string str;
std::string str2="Writing ";
std::string str3="print 10 and then 5 more";
// used in the same order as described above:
str.append(str2); // "Writing "
str.append(str3,6,3); // "10 "
str.append("dots are cool",5); // "dots "
str.append("here: "); // "here: "
str.append(10u,'.'); // ".........."
str.append(str3.begin()+8,str3.end()); // " and then 5 more"
str.append<int>(5,0x2E); // "....."Writing 10 dots here: … and then 5 more…
replace 的用法
std::string base="this is a test string.";
std::string str2="n example";
std::string str3="sample phrase";
std::string str4="useful.";
// replace signatures used in the same order as described above:
// Using positions: 0123456789*123456789*12345
std::string str=base; // "this is a test string."
str.replace(9,5,str2); // "this is an example string." (1)
str.replace(19,6,str3,7,6); // "this is an example phrase." (2)
str.replace(8,10,"just a"); // "this is just a phrase." (3)
str.replace(8,6,"a shorty",7); // "this is a short phrase." (4)
str.replace(22,1,3,'!'); // "this is a short phrase!!!" (5)
// Using iterators: 0123456789*123456789*
str.replace(str.begin(),str.end()-3,str3); // "sample phrase!!!" (1)
str.replace(str.begin(),str.begin()+6,"replace"); // "replace phrase!!!" (3)
str.replace(str.begin()+8,str.begin()+14,"is coolness",7); // "replace is cool!!!" (4)
str.replace(str.begin()+12,str.end()-4,4,'o'); // "replace is cooool!!!" (5)
str.replace(str.begin()+11,str.end(),str4.begin(),str4.end());// "replace is useful." (6)replace is useful.
find_first_not_of 等函数的用法
std::string str ("look for non-alphabetic characters...");
std::size_t found = str.find_first_not_of("abcdefghijklmnopqrstuvwxyz ");
if (found!=std::string::npos)
{
std::cout << "The first non-alphabetic character is " << str[found];
std::cout << " at position " << found << '\n';
}The first non-alphabetic character is - at position 12
Container adaptors 容器适配器
Constructor 构造函数
int myints[]= {10,60,50,20};
std::container<int> first;
std::container<int> second (myints,myints+4);
std::container<int, std::vector<int> > third (myints,myints+4);
//优先队列:
std::priority_queue<int, std::vector<int>, std::greater<int> > priority_queue (myints,myints+4);Member 成员列表
container.push();//添加元素
container.pop();//删除元素[队列] <queue> FIFO queue
template <class T, class Container = deque<T> > class queue;特有函数
queue.front();//第一个元素引用
queue.back();//最后一个元素引用[堆栈] <stack> LIFO stack
template <class T, class Container = deque<T> > class stack;特有函数
stack.top();//访问下一个元素[优先] <queue> priority_queue
template <class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class priority_queue;特有函数
priority_queue.top();//访问顶元素Associative containers 关联容器
Constructor 构造函数
set/multiset
std::set<int> first; // empty set of ints
int myints[]= {10,20,30,40,50};
std::set<int> second (myints,myints+5); // range
std::set<int> third (second); // a copy of second
std::set<int> fourth (second.begin(), second.end()); // iterator ctor.map/multimap
std::map<char,int> first;
first.insert(std::pair<char,int>('a',10));
first.insert(std::pair<char,int>('b',15));
first.insert(std::pair<char,int>('b',20));
first.insert(std::pair<char,int>('c',25));
std::map<char,int> second (first.begin(),first.end());
std::map<char,int> third (second);Member 成员列表
container.insert(position,val);//插入元素val到position位置
container.insert(position,n,val);//从position位置填充n个val
container.insert(position,first,last);//将一段区域[first,last)插入position位置
container.erase(position);//移除元素
container.erase(first,last);//移除区间[first,last)
container.push_back(val);//末尾添加元素
container.pop_back(val);//末尾删除元素
container.clear();//清空容器
container.swap(container);//交换容器
container.count(val);//元素个数(map为key值)，返回值仅有0,1
container.find(val);//查找元素迭代器upper_bound & lower_bound 的使用
除非set,map包含一个等价于val的元素：在这种情况下，lower_bound返回指向该元素的迭代器，而upper_bound返回指向下一个元素的迭代器。
std::set<int> myset;
std::set<int>::iterator itlow,itup;
for (int i=1; i<10; i++) myset.insert(i*10); // 10 20 30 40 50 60 70 80 90
itlow=myset.lower_bound (30); // ^
itup=myset.upper_bound (60); // ^
myset.erase(itlow,itup); // 10 20 70 80 90[集合] <set> set
template < class T, // set::key_type/value_type
class Compare = less<T>, // set::key_compare/value_compare
class Alloc = allocator<T> // set::allocator_type
> class set;[多键集合] <set> multiset
template < class T, // multiset::key_type/value_type
class Compare = less<T>, // multiset::key_compare/value_compare
class Alloc = allocator<T> > // multiset::allocator_type
> class multiset;[映射] <map> map
template < class Key, // map::key_type
class T, // map::mapped_type
class Compare = less<Key>, // map::key_compare
class Alloc = allocator<pair<const Key,T> > // map::allocator_type
> class map;特有函数
map[key] = val;[多键映射] <map> multimap
template < class Key, // multimap::key_type
class T, // multimap::mapped_type
class Compare = less<Key>, // multimap::key_compare
class Alloc = allocator<pair<const Key,T> > // multimap::allocator_type
> class multimap;特殊用法例子
std::multimap<char,int> mymm;
mymm.insert(std::pair<char,int>('a',10));
mymm.insert(std::pair<char,int>('b',20));
mymm.insert(std::pair<char,int>('b',30));
mymm.insert(std::pair<char,int>('b',40));
mymm.insert(std::pair<char,int>('c',50));
mymm.insert(std::pair<char,int>('c',60));
mymm.insert(std::pair<char,int>('d',60));
std::cout << "mymm contains:\n";
for (char ch='a'; ch<='d'; ch++)
{
std::pair <std::multimap<char,int>::iterator, std::multimap<char,int>::iterator> ret;
ret = mymm.equal_range(ch);
std::cout << ch << " =>";
for (std::multimap<char,int>::iterator it=ret.first; it!=ret.second; ++it)
std::cout << ' ' << it->second;
std::cout << '\n';
}Functions 函数
[填充] <algorithm> fill
定义
template <class ForwardIterator, class T>
void fill (ForwardIterator first, ForwardIterator last, const T& val);使用
vector<int> nums(8, 0);
std::fill(nums.begin(), nums.begin() + 4, 5); // nums: 5 5 5 5 0 0 0 0
std::fill(nums.begin() + 3, nums.end() - 2, 8); // nums: 5 5 5 8 8 8 0 0[查找] <algorithm> find
定义
template <class InputIterator，class T>
InputIterator find(InputIterator first，InputIterator last，const T＆val);使用
find (myints, myints+4, 30);
find (myvector.begin(), myvector.end(), 30);[排序] <algorithm> sort
定义
template <class RandomAccessIterator>
void sort (RandomAccessIterator first, RandomAccessIterator last);使用
std::sort (myvector.begin()+4, myvector.end(), myfunction);[大小] <algorithm> max & min
定义
template <class T> const T& max (const T& a, const T& b);
template <class T> const T& min (const T& a, const T& b);使用
maxn = INT_MIN,minn = INT_MAX;
maxn = max(maxn , num[i]);
minn = min(minn , num[i]);[变换] <algorithm> transform
定义
template <class InputIterator, class OutputIterator, class UnaryOperation>
OutputIterator transform (InputIterator first1, InputIterator last1,
OutputIterator result, UnaryOperation op);使用
transform(str.begin(),str.end(),str.begin(),::tolower);
transform(str.begin(),str.end(),str.begin(),::toupper);[反转] <algorithm> reverse
定义
template <class BidirectionalIterator>
void reverse (BidirectionalIterator first, BidirectionalIterator last);使用
std::reverse(myvector.begin(),myvector.end());[字符] <cstdlib> String conversion
//string -> int
int atoi (const char * str);
//string -> long
long int atol ( const char * str );
//string -> long long
long long int atoll ( const char * str );//C++11
//string -> double
double atof (const char* str);[数学] <cmath> Numerics library
double cos (double x);
double acos (double x);
double sin (double x);
double asin (double x);
double tan (double x);
double atan (double x);
double exp (double x); //e^x
double log (double x); //ln x
double log10 (double x); //lg x
double modf(double x，double * intpart);
// 分离整数和小数
// fractpart = modf (param , &intpart);
double pow (double base, double exponent); // x^y
double sqrt (double x);// x^1/2
double ceil (double x);//上取整
double floor (double x);//下取整
double abs (double x);//|x|
double fmod (double numer, double denom);
// 返回小数取模结果 如: fmod(5.3,2) = 1.300000[字符] <cctype> Character handling functions
//在transform中使用::tolower
int tolower (int c);
int toupper (int c);Others
[数据对] <utility> pair
template <class T1, class T2> struct pair;Constructor 构造函数
std::pair <std::string,double> product1;
std::pair <std::string,double> product2 ("tomatoes",2.30);
std::pair <std::string,double> product3 (product2);
product1 = std::make_pair(std::string("lightbulbs"),0.99);Member 成员列表
pair.first;
pair.second;
pair.swap();//交换成员零碎知识点
- cin读取加速
std::ios::sync_with_stdio(false);- foreach的写法 (c++11)
for (auto num : nums)
cout << num << "\t";- cmp的写法
bool cmp(Class a,Class b) { return a.x < b.x;}
// C++11后用lambda表达式很轻松
[](Class a,Class b) -> bool{ return a.x < b.x; };- 中文输出乱码解决
system("chcp 65001");本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 GZTime's Blog！
wechat- alipay
相关推荐
2018-09-16
First-blog
First Blog Formats Testing Testing testing Hyperlink 行内形式: Github 自动链接: Github http://github.com/GZTimeHacker List first item second item third item Table 表头1 表头2 表头3 表头4 默认左对齐 左对齐 居中对其 右对齐 默认左对齐 左对齐 居中对其 右对齐 默认左对齐 左对齐 居中对其 右对齐 Code #include<iostream> using namespace std; int...
2018-09-16
线段树
线段树的作用 线段树是一种二叉搜索树,它能以较低时间复杂度O(logN)得解决大规模求和、gcd等 空间复杂度为2N，但实际应用时还需4N的空间 查询和单点更改的代码实现 class NumArray { public: int *tree; int size; NumArray(vector<int> nums) { size = nums.size(); //size储存原始数据的数量 tree = new int[size * 4]; if...
2018-09-18
二叉树的遍历
二叉树 二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。 二叉树的定义和结构 struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL)...
评论