Posts

第 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

最大公约数（GCD）与欧几里得算法 最大公约数（Greatest Common Divisor，GCD） 两个数最大公约数顾名思义，两个数的所有公约数中最大的。 若正整数 $a,b$ 的质因数分解为 $$a = \prod_{i} p_i ^ {e_{a,i}}$$ $$b = \prod_{i} p_i ^ {e_{b,i}}$$ 则其最大公

对拍程序 from os import system tc=0 while True: system("python data.py > data.in") system("std.exe < data.in > std.out") system("my.exe < data.in > my.out") # system("diff std.out my.out > diff.out"): if system("fc std.out my.out > diff.out"): print("WA") break else: tc += 1 print("AC #%d"%tc) print("-------------------- data.in --------------------") # system("cat data.in") system("type data.in") print("-------------------- std.out --------------------") system("type std.out") print("-------------------- my.out ---------------------") system("type my.out") Powershell #include <bits/stdc++.h>using namespace std; int main() { int tc=0; while(1) { system("./E_data > data.in"); system("cat data.in | ./E_std.exe > std.txt"); system("cat data.in | ./E.exe > my.txt"); if(system("diff std.txt my.txt > diff.txt")) { cout<<"WA"<<endl; break; } else

树状数组 Binary Index Tree/Fenwick Tree 1d 单点修改，区间询问 // T must + - // id 1~n template<typename T,size_t M,typename OpPlus=plus<T>,typename OpMinus=minus<T>> struct BIT { static int lowbit(int x) { return x&(-x); } constexpr static OpPlus opp{}; constexpr static OpMinus opm{}; static T tmp[M+1]; T tree[M+1]; // tree[i] -> sum of [i-lowbit(i)+1,i] int n; void init(int n_) { n=n_; for(int i=1;i<=n;i++) tree[i]=T(0); } void init(int n_,T v[]) // v[0 ~ n_-1] { n=n_; tmp[0]=T(0); for(int i=1;i<=n;i++) tmp[i]=opp(tmp[i-1],v[i]); for(int i=1;i<=n;i++) tree[i]=opm(tmp[i],tmp[i-lowbit(i)]); // for(int i=0;i<n;i++) add(i,v[i]); } void add(int p,T V) { for(;p<=n;p+=lowbit(p))

计时 Timing chrono class Timing { private: typedef chrono::time_point<std::chrono::high_resolution_clock> TP; TP current_time() { return chrono::high_resolution_clock::now(); } TP st,ed; public: void start() { st=current_time(); } void end() { ed=current_time(); } void print() { cout<<chrono::duration_cast<chrono::microseconds>(ed-st).count() <<"ms\n"; } }timing;

C++ 日常使用 template <typename A, typename B> string to_string(pair<A, B> p); template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p); template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p); string to_string(const string& s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(bool b) { return (b ? "true" : "false"); } string to_string(vector<bool> v) { string res = "{"; for (int i = 0; i < static_cast<int>(v.size()); i++) { if (i) { res += ", "; } res

C++ 日常使用 #include <bits/stdc++.h>using namespace std; int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }(); using LL = long long; using ULL = unsigned long long; using LD = long double; using PII = pair<int, int>; using VI = vector<int>; using MII = map<int, int>; template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; } template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; } template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z if(z<x) { y=x; x=z; } else if(z<y) y=z; } template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z if(x<z) { y=x;

前 总结一下 LeetCode 上比较好的题目（部分题可能并不是很好，但是实现细节复杂，面试需要特别注意也囊括进来了）。 推荐指数 $1-5$ 是按照可能已经掌握的知识层次进行排序的，竞赛选手推荐刷推荐指数 $3$ 以上的题目。推荐指数和难度

安全哈希函数 struct custom_hash { static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; 用这个函数作为 unordered_set 的第二个参数或 unordered_map 的第三个参数。

模下计算 普通 const int MO=1e9+7; inline int add(int x,int y) { x+=y; if(x>=MO) x-=MO; return x; } inline int sub(int x,int y) { x-=y; if(x<0) x+=MO; return x; } inline int mul(int x,int y) { return 1LL*x*y%MO; } inline void addv(int &x,int y) { x+=y; if(x>=MO) x-=MO; } inline void subv(int &x,int y) { x-=y; if(x<0) x+=MO; } inline void mulv(int &x,int y) { x=1LL*x*y%MO; } int qp(int x,int n) { int ans=1; while(n) { if(n&1) { mulv(ans,x); } mulv(x,x); n>>=1; } return ans; } ModInt template<int MO=1000000007> struct ModInt { int x; ModInt(int x=0):x(x){ norm();

左偏树 Leftist Tree // min leftist tree // T must define < // M: the size of the heap template<typename T,size_t M,typename Cmp=less<T>> struct Leftist { static Cmp cmp; T val[M]; int l[M],r[M],d[M]; int nn; // number of node void init() { nn=0; } // using val to build a leftist tree // return the id of the root int build(int n,T val_[]) { queue<int> qu; for(int i=1;i<=n;i++) qu.push(i); int u,v; while(qu.size()>1) { u=qu.front(); qu.pop(); v=qu.front(); qu.pop(); merge(u,v); qu.push(u); } return qu.front(); } int newtree(T v) { val[++nn]=v; r[nn]=l[nn]=d[nn]=0; return nn; } void merge(int &x,int y) // merge

克鲁斯卡尔 Kruskal template<typename T,size_t V,size_t E> struct Kruskal { typedef tuple<T,int,int> Edge; typedef pair<T,int> PTI; Edge edges[E]; int inmst[E]; int n; // number of vertex int m; // number of edge int uf[V]; int find(int x) { return x==uf[x]?x:uf[x]=find(uf[x]); } void init(int n_) { n=n_; m=0; } void addedge(int u,int v,T w) { edges[m++]={w,u,v}; } PTI solve() { int cnt=n; // number of connected component T sum=0; int u,v; T w; for(int i=0;i<n;i++) uf[i]=i; sort(edges,edges+m); for(int i=0;i<m&&cnt>1;i++) { tie(w,u,v)=edges[i]; u=find(u); v=find(v); if(u==v) continue; inmst[i]=1; sum=sum+w; cnt--; uf[u]=v; } return {sum,cnt==1}; // {totval in mst, ismst} }