Posts

第 14 章 重载运算与类型转换 14.1 基本概念 重载的运算符是具有特殊名字的函数。 重载运算符的参数数量与该运算符作用的运算对象数量一样多。除了重载的函数调用运算符 operator() 之外其他重载运算符不能含有默认实参。 一个重载运算符

下标池 IdPool template<typename T> struct IdPool { map<T, int> idmap; vector<T> items; void clear() { idmap.clear(); items.clear(); } int getid(const T &t) { auto it = idmap.find(t); if (it != idmap.end()) return it->second; int ans = items.size(); items.push_back(t); idmap[t] = ans; return ans; } T& operator[](int i) { return items[i]; } int size() { return items.size(); } }; IdPool<int> idp;

第 13 章 拷贝控制 拷贝控制 copy control 操作包括： 拷贝构造函数 copy constructor 拷贝赋值运算符 copy-assignment operator 移动构造函数 move constructor 移动赋值运算符 move-assignment operator 析构函数 destructor 13.1 拷贝、赋值与销毁 合成拷贝构造函数 synthesized copy constructor #include <iostream>#include <string>using namespace std; class A { public: string name; A() : name("") { cout << "default ctor" << endl; } A(string

第 12 章 动态内存 静态内存用来存储 局部 static 对象，类 static 成员，定义在任何函数之外的变量。 栈内存用来存储 定义在函数内的非 static 对象。 除了这两部分，程序还拥有一个内存池。这部分内存被称为自由空间 free store 或 堆 heap。程序用

第 11 章 关联容器 关联容器 associative-container map set multimap multiset unordered_map unordered_set unordered_multimap unordered_multiset 11.1 使用关联容器 map 通常称为关联数组 associative array。 11.2 关联容器概述 有序容器的关键字类型 需要定义 <，且该运算需要满足严格弱序 strict weak ordering。 11.2.3 pair 类型 pair 定义在

Title typedef long long LL; typedef vector<int> VI; typedef vector<VI> VVI; const LL INF=0x3f3f3f3f3f3f3f3f; inline LL sqr(LL x){ return x*x; } inline LL dis(const VI &a,const VI &b) { return sqr(a[0]-b[0])+sqr(a[1]-b[1]); } bool cmp(const VI &a, const VI &b) { return a[1]<b[1]; } VVI tmp; LL help(VVI &ps,int l,int r) { int n=r-l+1; if(n<=3) { LL ans=INF; for(int i=l;i<=r;i++) { for(int j=i+1;j<=r;j++) ans=min(ans,dis(ps[i],ps[j])); } sort(ps.begin()+l, ps.begin()+r+1, cmp); return ans; } int m=(l+r)>>1; int mp=ps[m][0]; LL ans=min(help(ps,l,m),help(ps,m+1,r)); int i=l,j=m+1,p=l; while(i<=m || j<=r) { if(i>m || j<=r&&cmp(ps[j],ps[i])) { tmp[p++]=ps[j++]; } else { tmp[p++]=ps[i++]; } } copy(tmp.begin()+l, tmp.begin()+r+1,ps.begin()+l); p=0; for(int i=l;i<=r;i++) { if(sqr(ps[i][0]-mp)

第 10 章 泛型算法 泛型算法 generic algorithm 10.1 概述 大多数算法定义在头文件 algorithm 中。另外在 numeric 种定义了一组数值泛型算法。 一般来说这些算法并不直接操作容器，二十遍历由两个迭代器指定的一个元素范围来进行操作。 10.2 初识泛型算法 10.2.1 只读算

第 9 章 顺序容器 sequential container 9.1 顺序容器概述 vector deque list forward_list array string 9.2 容器库概览 类型别名 意义 iterator 迭代器类型 const_iterator 不能修改元素的迭代器类型 size_type 容器类型最大可能的大小 difference_type 两个迭代器间的距离 value_type 元素类型 reference 元素的左值类型与 value_type& 相同 const_reference 元素的 const 左值类

第 8 章 IO 库 8.1 IO 类 头文件 类型 作用 iostream istream, wistream 从流读 ostream, wostream 向流写 iostream,wiostream 读写流 fstream ifstream, wifstream 从文件读 ofstream, wofstream 向文件写 fstream, wfstream 读写文件 sstream istringstream, wistringstream 从 string 读 ostringstream, wostringstream 向 string 写 stringstream, wstringstream 读写 string ifstream 和 istringstream 继承自 istream ofstream 和 ostringstream 继承自 ostream IO 对象没有拷贝和赋值操作。 8.1.2 条件状态 IO 类定

第 7 章 类 类的基本思想是数据抽象 data abstraction 和封装 encapsulation。 数据抽象是一种依赖于接口 interface 和实现 implementation 分离的编程/设计技术。 7.1 定义抽象数据类型 引入 this this 是一个常量指针。 成员函数通过隐式参数 this 来访问调用它

第 6 章 函数 6.1 函数基础 我们可以通过调用运算符 call operator 来执行函数。 形参 parameter 实参 argument 主调函数 calling function 被调函数 called function 空形参列表可以是空的括号，或是 void void f1() {} void f2(void) {} 6.1.1 局部对象 C++ 中名字有作用域，对象有声明周期 lifetime。 名

第 5 章 语句 一个表达式末尾加上分号就变成了表达式语句 expression statement。 空语句 null statement。 复合语句 compound statement 也称块 block 是用花括号括起来的语句和声明序列。在程序某个位置如果语法上需要一个语句，逻辑上需

第 4 章 表达式 表达式 expression 由一个或多个运算对象 operand 组成，对表达式求值将得到一个结果。字面值和变量是最简单的表达式，运算符 operator 将一个或多个对象组合起来可以生成复杂的表达式。 4.1 基础 4.1.1 基本概念 对于复杂的表达式，需要了

第 3 章 字符串、向量和数组 3.1 命名空间的 using 声明 using 声明 using declaration using namesapce::name; 头文件不应包含 using 声明。因为头文件会被包含到其他文件中去，使用 using 声明则可能带来名字冲突。 3.2 标准库类型 string 3.2.1 定义和初始化 string 对象 #include <iostream>#include <cassert>#include <iterator>#include <string>#include <cctype> int main() { { // string::string()

第 2 章 变量和基本类型 2.1 基本内置类型 基本内置类型分为算数类型 arithmetic type 和空类型 void 2.1.1 算数类型 整型 integral type 和浮点型 注意 C++ 只规定了每种算数类型的最小尺寸，所以不同机器上可能会有差异。 类型 含义 最小尺寸 bool 未定义 char 8 位 wchar_t 宽字

随机数 Random #include <bits/stdc++.h>using namespace std; typedef long long LL; struct FastIO { FastIO() { ios::sync_with_stdio(false); cin.tie(nullptr); } }fastio; mt19937 rnd(chrono::system_clock::now().time_since_epoch().count()); mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count()); // [0,r) int rndi(int r) { return rnd()%r; } // [l,r] r-l+1<=INT_MAX int rndi(int l,int r) { return rnd()%(r-l+1)+l; } LL rndll(LL l,LL r) { return rnd_64()%(r-l+1)+l; } char rndc() { return rndi(-128,127); } char rndc(const string &s) { return s[rndi(s.length())]; } char rnd_lower() { return rndi(26)+'a'; } char rnd_upper() { return rndi(26)+'A'; } char rnd_digit() { return rndi(10)+'0'; } char rnd_alpha() { int r=rndi(52); return r<26?(r+'a'):(r-26+'A'); } char rnd_alphadigit() { int r=rndi(62); if(r<10) return

离散化 Discretization template<typename T, int IdFrom=0, typename OpLs=less<T>, typename OpEq=equal_to<T>> struct Dctz { static OpLs ls; static OpEq eq; vector<T> x; void clear() { x.clear(); } void add(T v) { x.push_back(v); } void init() { sort(x.begin(),x.end(),ls); x.erase(unique(x.begin(),x.end(),eq),x.end()); } int size() { return x.size(); } int id(const T &v) { return lower_bound(x.begin(),x.end(),v,ls)-x.begin()+IdFrom; } T& operator[](int id) { return x[id-IdFrom]; }; }; Dctz<> dc;

约翰逊 Johnson 算法 全源最短路 对于最短路问题，我们的常用算法是 Dijkstra 算法或 Bellman-Ford 算法。但这两个算法经常解决的是单源最短路问题。 对于多源（全源）最短路问题，我们有一个基于动态规划的优秀算法，Floyd-Warshall

扩展欧几里得算法（ExGCD） // ax+by=gcd(a,b)=g // check a>0 b>0 // if a != b, |x|<b, |y|<a template<typename T> void exgcd(T a,T b,T &g,T &x,T &y) { if(!b) { g=a; x=1; y=0; } else { exgcd(b,a%b,g,y,x); y-=a/b*x; } } 求逆元 template<typename T> void exgcd(T a,T b,T &g,T &x,T &y) { if(!b) { g=a; x=1; y=0; } else { exgcd(b,a%b,g,y,x); y-=a/b*x; } } template<typename T> T inv(T a,T m) { T g,x,y; exgcd(a,m,g,x,y); if(g!=1) return -1; // no inverse element if(x<0) x+=m; return x; } 不定方

扩展欧几里得算法 有时我们需要求解类似于 $ax+by=m$ 的不定方程（丢番图方程），扩展欧几里得算法就是求解这样方程的利器。 除此以外我们可以通过简单地变形处理模逆元和线性同余方程。 裴蜀定理/贝祖定理（Bezout&rs