AtCoder ABC209题解
AtCoder Beginner Contest 209题解
传送门： AtCoder Beginner Contest 209
A. Counting
题意：输出[a,b][a,b][a,b]之间有多少个数。
思路：签到题，注意可能a>ba>ba>b。
12345678#include <bits/stdc++.h>using namespace std;int main() { int a, b; cin >> a >> b; cout << max(0, b - a + 1) << endl; return 0;}
B. Can you buy them all?
题意：有NNN件商品，偶数天的商品会便宜111元，给了XXX元，求能不能把NNN件商品买完。
思路：签到题，直接模拟。
12345678910111213141516#include <bits/stdc++.h>using namespace std;int main() { ...
CFRound 731(Div. 3)题解
Codeforces Round #731 (Div. 3)题解
传送门：Codeforces Round #731 (Div. 3) - Codeforces
A. Shortest Path with Obstacle
题意：给了三个点的坐标A,B,FA, B, FA,B,F，求AAA到BBB不经过FFF的最短距离。
思路：很容易发现，只有当A,BA, BA,B在同一行或同一列，且FFF在两点之间才会有影响。
123456789101112131415161718#include <bits/stdc++.h>using namespace std;int main() { int T; cin >> T; while (T--) { int xa, ya, xb, yb, xf, yf; cin >> xa >> ya >> xb >> yb >> xf >> yf; if (xa == xb && ...
ACM模板大数
大数模板
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137#include <bits/stdc++.h>using namespace std;struct BigInteger { typedef unsigned long long LL; static const int BASE = 100000000; static const int WIDTH = 8; vector<int> s ...
ACM模板计算几何
二维几何
基本运算
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950const double eps = 1e-12;const double PI = acos(-1);// 判断正负int sgn(double x) { return fabs(x) < eps ? 0 : (x < 0 ? -1 : 1); }// 弧度转角度double R_to_D(double rad) { return 180 / PI * rad; }// 角度转弧度double D_to_R(double D) { return PI / 180 * D; }struct Point { double x, y; Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}};typedef Point Vec ...
ACM模板树上问题
树上差分
12345678910//树上边差分d[u] += x;d[v] += x;d[LCA(u, v)] -= 2 * x;//树上点差分d[u] += x;d[v] += x;d[LCA(u, v)] -= x;d[fa[LCA(u, v)]] -= x;
RMQ+LCA
预处理：O(VlogV)O(VlogV)O(VlogV)，查询：O(1)O(1)O(1)。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include <bits/stdc++.h>using namespace std;const int MAX = 5e5 + 50;struct Edge { int v, next;}edges[MAX << 1];int head[MAX], k, n, m, root;int deep[MAX], first[MAX], oula[MA ...
ACM模板数据结构
并查集
12345678910111213141516171819202122232425262728293031struct UF { vector<int> fa, sz; int n, comp_cnt; UF(int _n): n(_n), comp_cnt(_n), fa(_n), sz(_n, 1) { iota(fa.begin(), fa.end(), 0); } int find(int x) { return fa[x] == x ? x : (fa[x] = find(fa[x])); } bool merge(int x, int y) { x = find(x); y = find(y); if (x == y) { return false; } if (sz[x] < sz[y]) { swap(x, y); } fa[y] = x; sz[x] ...
ACM模板图论
Tarjan时间复杂度：O(V+E)O(V+E)O(V+E)
要注意原图不连通以及重边的情况
Tarjan求割点
123456789101112131415161718192021int dfn[MAX], low[MAX], idx;bool is[MAX];vector<int> edges[MAX];void tarjan(int u, int root) { dfn[u] = low[u] = ++idx; int child = 0; for (auto& v: edges[u]) { if (dfn[v] == 0) { child++; tarjan(v, root); low[u] = min(low[u], low[v]); //两种情况1.根节点且孩子>=2; // 2.非根节点且有一个孩子能回溯的最早的low不超过自己dfn的值. if (u == root && child >= 2) is[u] = ...
ACM模板数论
快速乘 && 快速幂
12345678910111213ll mul(ll a, ll b, ll P) { return (a * b - (ll)((long double) a * b / P) * P + P) % P;}ll ksm(ll a, ll b, ll P) { ll res = 1; while (b) { if (b & 1) res = res * a % P; a = a * a % P; b >>= 1; } return res % P;}
康托展开+康托逆展开
12345678910111213141516171819202122232425262728int fac[MAX], a[MAX], b[MAX], n;bool vis[MAX];int contor() { int rank = 0; for (int i = 1; i <= n; i++) { int cnt = 0; f ...
ACM模板杂项
快读
1234567891011121314151617181920212223242526272829303132333435363738394041424344namespace fastIO { #define BUF_SIZE 100000 //fread -> read bool IOerror = 0; inline char nc() { static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE; if (p1 == pend) { p1 = buf; pend = buf + fread(buf, 1, BUF_SIZE, stdin); if (pend == p1) { IOerror = 1; return -1; } } return *p1++; } inline bool blank(char c ...
ACM模板字符串类
字符串哈希
12345678910111213141516struct StrHash { char s[MAX]; int len; ull h[MAX], p[MAX], B; char& operator [] (const int& pos) { return s[pos]; } void init() { len = strlen(s + 1); B = 786433; p[0] = 1; for (int i = 1; i <= len; i++) { h[i] = h[i - 1] * B + s[i] - 'a'; p[i] = p[i - 1] * B; } } ull calc(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; }};
KMP
时间复杂度：O(n+m)O(n+m)O(n+m)
123456 ...
