C++ 代码模板
前言
今天突然高产了
听说好多人的微软E5开发者计划都被停了，趁着有时间赶紧保存了一下重要数据，翻出来了好几年前写的各种模板，虽然已经好久没打算法了，不舍得丢这些代码，在这里分享一下
模板
快读写
模板
template <typename T>
inline T read()
{
register char __ch = getchar();
register T __x = 0, __cf = 1;
while (__ch < '0' || __ch > '9')
{
if (__ch == '-') __cf = -1;
__ch = getchar();
}
while (__ch >= '0' && __ch <= '9')
{
__x = (__x << 3) + (__x << 1) + (__ch ^ 48);
__ch = getchar();
}
return __x * __cf;
}
template <typename T>
inline void write(T __x)
{
if (__x < 0) {putchar('-'); __x = -__x;}
if (__x > 9) write(__x / 10);
putchar(__x % 10 + '0');
}优化 getchar
忘记从哪里抄的了
char __In[1 << 20], *__ss=__In, *__tt=__In;
#define getchar() (__tt == __ss && (__tt = (__ss = __In) + fread(__In, 1, 1 << 20, stdin), __ss == __tt) ? EOF : *__ss++)优化 cin cout
忘记从哪里抄的了
namespace Fastio
{
struct Reader
{
template <typename T> Reader& operator >> (T &x)
{
x = 0;
short f = 1;
char c = getchar();
while (c < '0' || c > '9') { if (c == '-') f *= -1; c = getchar(); }
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
x *= f;
return *this;
}
Reader& operator >> (double &x)
{
x = 0;
double t = 0;
short f = 1, s = 0;
char c = getchar();
while ((c < '0' || c > '9') && c != '.') { if (c == '-') f *= -1; c = getchar(); }
while (c >= '0' && c <= '9' && c != '.') x = x * 10 + (c ^ 48), c = getchar();
if (c == '.') c = getchar();
else { x *= f; return *this; }
while (c >= '0' && c <= '9') t = t * 10 + (c ^ 48), s++, c = getchar();
while (s--) t /= 10.0;
x = (x + t) * f;
return *this;
}
Reader& operator >> (long double &x)
{
x = 0;
long double t = 0;
short f = 1, s = 0;
char c = getchar();
while ((c < '0' || c > '9') && c != '.') { if (c == '-') f *= -1; c = getchar(); }
while (c >= '0' && c <= '9' && c != '.') x = x * 10 + (c ^ 48), c = getchar();
if (c == '.') c = getchar();
else { x *= f; return *this; }
while (c >= '0' && c <= '9') t = t * 10 + (c ^ 48), s++, c = getchar();
while (s--) t /= 10.0;
x = (x + t) * f;
return *this;
}
Reader& operator >> (__float128 &x)
{
x = 0;
__float128 t = 0;
short f = 1, s = 0;
char c = getchar();
while ((c < '0' || c > '9') && c != '.') { if (c == '-') f *= -1; c = getchar(); }
while (c >= '0' && c <= '9' && c != '.') x = x * 10 + (c ^ 48), c = getchar();
if (c == '.') c = getchar();
else { x *= f; return *this; }
while (c >= '0' && c <= '9') t = t * 10 + (c ^ 48), s++, c = getchar();
while (s--) t /= 10.0;
x = (x + t) * f;
return *this;
}
Reader& operator >> (char &c)
{
c = getchar();
while (c == ' ' || c == '\n' || c == '\r') c = getchar();
return *this;
}
Reader& operator >> (char *str)
{
int len = 0;
char c = getchar();
while (c == ' ' || c == '\n' || c == '\r') c = getchar();
while (c != ' ' && c != '\n' && c != '\r') str[len++] = c, c = getchar();
str[len] = '\0';
return *this;
}
Reader& operator >> (string &str)
{
str.clear();
char c = getchar();
while (c == ' ' || c == '\n' || c == '\r') c = getchar();
while (c != ' ' && c != '\n' && c != '\r') str.push_back(c), c = getchar();
return *this;
}
Reader() {}
} cin;
const char endl = '\n';
struct Writer
{
const int Setprecision = 6;
typedef int mxdouble;
template <typename T> Writer& operator << (T x)
{
if (x == 0) { putchar('0'); return *this; }
if (x < 0) putchar('-'), x = -x;
static short sta[40];
short top = 0;
while (x > 0) sta[++top] = x % 10, x /= 10;
while (top > 0) putchar(sta[top] + '0'), top--;
return *this;
}
Writer& operator << (double x)
{
if (x < 0) putchar('-'), x = -x;
mxdouble _ = x;
x -= (double)_;
static short sta[40];
short top = 0;
while (_ > 0) sta[++top] = _ % 10, _ /= 10;
if (top == 0) putchar('0');
while (top > 0) putchar(sta[top] + '0'), top--;
putchar('.');
for (int i = 0; i < Setprecision; i++) x *= 10;
_ = x;
while (_ > 0) sta[++top] = _ % 10, _ /= 10;
for (int i = 0; i < Setprecision - top; i++) putchar('0');
while (top > 0) putchar(sta[top] + '0'), top--;
return *this;
}
Writer& operator << (long double x)
{
if (x < 0) putchar('-'), x = -x;
mxdouble _ = x;
x -= (long double)_;
static short sta[40];
short top = 0;
while (_ > 0) sta[++top] = _ % 10, _ /= 10;
if (top == 0) putchar('0');
while (top > 0) putchar(sta[top] + '0'), top--;
putchar('.');
for (int i = 0; i < Setprecision; i++) x *= 10;
_ = x;
while (_ > 0) sta[++top] = _ % 10, _ /= 10;
for (int i = 0; i < Setprecision - top; i++) putchar('0');
while (top > 0) putchar(sta[top] + '0'), top--;
return *this;
}
Writer& operator << (__float128 x)
{
if (x < 0) putchar('-'), x = -x;
mxdouble _ = x;
x -= (__float128)_;
static short sta[40];
short top = 0;
while (_ > 0) sta[++top] = _ % 10, _ /= 10;
if (top == 0) putchar('0');
while (top > 0) putchar(sta[top] + '0'), top--;
putchar('.');
for (int i = 0; i < Setprecision; i++) x *= 10;
_ = x;
while (_ > 0) sta[++top] = _ % 10, _ /= 10;
for (int i = 0; i < Setprecision - top; i++) putchar('0');
while (top > 0) putchar(sta[top] + '0'), top--;
return *this;
}
Writer& operator << (char c) { putchar(c); return *this; }
Writer& operator << (char *str)
{
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer& operator << (const char *str)
{
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer& operator << (string str)
{
int st = 0, ed = str.size();
while (st < ed) putchar(str[st++]);
return *this;
}
Writer() {}
} cout;
}
using namespace Fastio;
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl归并排序
const int NR = 5e5 + 10;
int a[NR], b[NR];
void merge_sort(int l, int r)
{
if (l == r) return;
int mid = (l + r) >> 1, i = l, j = mid + 1, cnt = l;
merge_sort(l, mid), merge_sort(mid + 1, r);
while (i <= mid && j <= r) b[cnt++] = (a[i] < a[j]) ? (a[i++]) : (a[j++]);
while (i <= mid) b[cnt++] = a[i++];
while (j <= r) b[cnt++] = a[j++];
for (int i = l; i <= r; i++) a[i] = b[i];
}链式前向星
// head[x] 以x为起点的最后一条边的编号
// to[i] 第i条边的终点
// next[i] 第i条边的前一条相同起点的边
// cnt 标记边的数量
void add(int x, int y, int z)
{
cnt++;
to[cnt] = y;
w[cnt] = z;
next[cnt] = head[x];
head[x] = cnt;
}
void dfs(int x, int fa)
{
for (int i = head[x]; i; i = next[i])
if (to[i] != fa) dfs(to[i], x);
}欧拉序
// 欧拉序 : (2n - 1个边)
// 对这棵树进行先序遍历 记录遍历所经过的点
// 进入每个点x时 存入它的编号
// 枚举它的所有子树
// 遍历完一棵子树 回到x时 存入x的编号
// 直到递归结束
int compare(int x, int y)
{
return ((dep[x] < dep[y]) ? (x) : (y));
}
// len表示欧拉序的长度
for (int j = 1; (1 << j) <= len; j++)
for (int i = 1; i + (1 << j) - 1 <= len; i++)
p[i][j] = compare(p[i][j - 1], p[i + (1 << j - 1)][j - 1]);
// id[x]表示 x 点第一次在欧拉序中出现的下标
int lca(int x, int y)
{
if (id[x] > id[y]) swap(x, y);
return query(id[x], id[y]);
}树上差分
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int NR = 5e4 + 10;
const int MR = 20;
int n, k;
int cnt, len;
int dep[NR], head[NR], f[NR][MR + 5];
int v[NR], s[NR];
struct edge
{
int to, next, w;
}e[NR << 1];
void add(int x, int y)
{
e[++cnt] = (edge){y, head[x]};
head[x] = cnt;
}
void dfs(int x, int fa)
{
dep[x] = dep[fa] + 1;
f[x][0] = fa;
for (int i = 1; (1 << i) <= dep[x]; i++)
f[x][i] = f[f[x][i - 1]][i - 1];
for (int i = head[x]; i; i = e[i].next)
{
if (e[i].to == fa) continue;
dfs(e[i].to, x);
}
}
int lca(int x, int y)
{
if (dep[x] < dep[y]) swap(x, y);
for (int i = MR; i >= 0; i--)
if (dep[x] - dep[y] >= (1 << i)) x = f[x][i];
if (x == y) return x;
for (int i = MR; i >= 0; i--)
if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
return f[x][0];
}
int dist(int a, int b)
{
return dep[a] + dep[b] - 2 * dep[lca(a, b)];
}
int jump(int x, int k)
{
for (int i = MR; i >= 0; i--)
if (k >= (1 << i)) x = f[x][i], k -= (1 << i);
return x;
}
void op(int x, int y)
{
int z = lca(x, y);
v[x]++;
v[y]++;
v[z]--;
v[f[z][0]]--;
}
void cal(int x, int fa)
{
s[x] = v[x];
for (int i = head[x]; i; i = e[i].next)
{
if (e[i].to == fa) continue;
cal(e[i].to, x);
s[x] += s[e[i].to];
}
}
int main()
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= n - 1; i++)
{
int x, y;
scanf("%d%d", &x, &y);
add(x, y);
add(y, x);
}
dfs(1, 0);
for (int i = 1; i <= k; i++)
{
int s, t;
scanf("%d%d", &s, &t);
op(s, t);
}
cal(1, 0);
int ans = -1e9;
for (int i = 1; i <= n; i++)
ans = max(ans, s[i]);
printf("%d\n", ans);
return 0;
}lca
ST 表
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int NR = 1e5 + 10;
int n, m, s;
int cnt, len;
int dep[NR], id[NR], head[NR], p[2 * NR][21];
struct edge
{
int to, next, w;
}e[2 * NR];
void add(int x, int y)
{
e[++cnt] = (edge){y, head[x]};
head[x] = cnt;
}
int compare(int x, int y)
{
return dep[x] < dep[y] ? x : y;
}
int query(int l, int r)
{
int z = log2(r - l + 1);
return compare(p[l][z], p[r - (1 << z) + 1][z]);
}
int lca(int x, int y)
{
return query(min(id[x], id[y]), max(id[x], id[y]));
}
void dfs(int x, int fa)
{
p[++len][0] = x;
id[x] = len;
dep[x] = dep[fa] + 1;
for (int i = head[x]; i; i = e[i].next)
{
if (e[i].to == fa) continue;
dfs(e[i]. to, x);
p[++len][0] = x;
}
}
void rmq()
{
for (int j = 1; (1 << j) <= len; j++)
for (int i = 1; i + (1 << j) - 1 <= len; i++)
p[i][j] = compare(p[i][j - 1], p[i + (1 << j - 1)][j - 1]);
}
int dist(int a, int b)
{
return dep[a] + dep[b] - 2 * dep[lca(a, b)];
}
bool on_string(int a, int b, int c)
{
return dist(a, c) + dist(b, c) == dist(a, b);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n - 1; i++)
{
int x, y;
scanf("%d%d", &x, &y);
add(x, y);
add(y, x);
}
dfs(1, 0);
rmq();
for (int i = 1; i <= m; i++)
{
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", lca(a, b));
}
return 0;
}倍增
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int NR = 1e5 + 10;
const int MR = 20;
int n, m, s;
int cnt, len;
int dep[NR], head[NR], f[NR][MR + 5];
struct edge
{
int to, next, w;
}e[NR << 1];
void add(int x, int y)
{
e[++cnt] = (edge){y, head[x]};
head[x] = cnt;
}
void dfs(int x, int fa)
{
dep[x] = dep[fa] + 1;
f[x][0] = fa;
for (int i = 1; (1 << i) <= dep[x]; i++)
f[x][i] = f[f[x][i - 1]][i - 1];
for (int i = head[x]; i; i = e[i].next)
{
if (e[i].to == fa) continue;
dfs(e[i].to, x);
}
}
int lca(int x, int y)
{
if (dep[x] < dep[y]) swap(x, y);
for (int i = MR; i >= 0; i--)
if (dep[x] - dep[y] >= (1 << i)) x = f[x][i];
if (x == y) return x;
for (int i = MR; i >= 0; i--)
if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
return f[x][0];
}
int dist(int a, int b)
{
return dep[a] + dep[b] - 2 * dep[lca(a, b)];
}
int jump(int x, int k)
{
for (int i = MR; i >= 0; i--)
if (k >= (1 << i)) x = f[x][i], k -= (1 << i);
return x;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n - 1; i++)
{
int x, y;
scanf("%d%d", &x, &y);
add(x, y);
add(y, x);
}
dfs(1, 0);
for (int i = 1; i <= m; i++)
{
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", lca(a, b));
}
return 0;
}
If you enjoyed this, leave a comment~