ACM板子

基础算法

快速幂

Code:

LL ksm(LL a, LL b, LL c)
{LL ans = 1;//最后答案在answhile (b > 0){if (b & 1)//b是奇数的话会出现一个a{ans = ans * a % c;}b >>= 1;a = (a * a) % c;//b变一半所以a就要平方了}return ans;
}

快速乘

一般快速乘应用于快速幂

Code:

LL ksc(LL a, LL b, LL p) {LL ans = 0;//快速成是加法while (b > 0) {if (b & 1) {ans = (ans + a) % p;}b >>= 1;a = (a + a) % p;}return ans;
}
LL ksm(LL a,LL b,LL p)//快速幂
{LL ans = 1;//快速幂的乘法while (b > 0) {if (b & 1) {ans = ksc(ans, a, p) % p;//用快速乘代替原来的乘法运算}b >>= 1;a = ksc(a, a, p) % p;}return ans;
}

欧拉筛

Code：

//切记主函数初始化init
#include 
using namespace std;
const int N = 1e4 + 5;
const int max1 = 1e4;
int b[N], prime[N];
int cnt;
void init() 
{memset(b, 1, sizeof(b));b[0] = b[1] = 0;for (int i = 2; i <= max1; i++) {if (b[i])prime[++cnt] = i;for (int j = 1; j <= cnt && prime[j] * i <= max1; j++)//质数的质数倍，保证不做重复运算{b[prime[j] * i] = 0;//标记为0，即为非质数if (i % prime[j] == 0) break;//解释为i的最小素因子是prime[j]，但我猜测此时i==prime[j]}}
}

快读

Code:

int qread() {int x = 0, y = 1;char c = getchar();while (c < '0' || c > '9') {if (c == '-')y = -1;c = getchar();}while (c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}return x * y;
}//读取操作
for (int i = 1; i <= n; i++) {arr[i] = readInt();r = max(r, arr[i]);
}

高精度

用于超出long long数的运算

加法

Code:

#include 
using namespace std;
vector x,y,z;
string a, b;
int main()
{cin >> a >> b;for (int i = a.size() - 1; i >= 0; i--) x.push_back(a[i] - '0');for (int i = b.size() - 1; i >= 0; i--) y.push_back(b[i] - '0');int t = 0;for (int i = 0; i < x.size() || i < y.size(); i++) {if (i < x.size()) t += x[i];if (i < y.size()) t += y[i];z.push_back(t % 10);t /= 10;}if(t) z.push_back(t);//加完之后数位多了的情况for (int i = z.size() - 1; i >= 0; i--) {//最高位在最后if (i != z.size()) cout << z[i];else cout << z[i] << endl;}
}

减法

Code:

#include 
using namespace std;
vector x,y,z;
string a, b;
bool pd()//判断x，y两个数据大小
{if (x.size() != y.size()) return x.size() > y.size();for (int i = x.size() - 1; i >= 0; i--) {if (x[i] != y[i]) return x[i] > y[i];}return 1;
}
int main()
{cin >> a >> b;for (int i = a.size() - 1; i >= 0; i--) x.push_back(a[i] - '0');for (int i = b.size() - 1; i >= 0; i--) y.push_back(b[i] - '0');int t = 0;int tmp = 0;if (pd()) {for (int i = 0; i < x.size(); i++) {t = x[i] - t;if (i < y.size()) t -= y[i];z.push_back((t + 10) % 10);if (t < 0) t = 1;else t = 0;}}else {tmp = 1;//标记负号for (int i = 0; i < y.size(); i++) {t = y[i] - t;if (i < x.size()) t -= x[i];z.push_back((t + 10) % 10);if (t < 0) t = 1;else t = 0;}}while (z.size() > 1 && z.back() == 0) z.pop_back();//减法出现0，去除多余的0if (tmp) cout << "-";for (int i = z.size() - 1; i >= 0; i--) {//也是末尾是最高位if (i != z.size()) cout << z[i];else cout << z[i] << endl;}return 0;
}

乘法

一个大数乘一个小数

Code:

#include 
using namespace std;
vector x, y, z;
string a, b;
int c;
int main()
{cin >> a >> c;for (int i = a.size() - 1; i >= 0; i--) x.push_back(a[i] - '0');int t = 0;for (int i = 0; i < x.size(); i++) {t += x[i] * c;z.push_back(t % 10);t /= 10;}while (t) {z.push_back(t % 10);t /= 10;}while (z.size() > 1 && z.back() == 0) z.pop_back();//乘0的情况for (int i = z.size() - 1; i >= 0; i--) {if (i != z.size()) cout << z[i];else cout << z[i] << endl;}return 0;
}

除法

Code:

//如果只有除法最好使用正序插入，但由于进行四则运算要与其它运算保持一致所以这里使用逆序
#include 
using namespace std;
vector x, y, z;
string a, b;
int c;
int main()
{cin >> a >> c;for (int i = a.size() - 1; i >= 0; i--) x.push_back(a[i] - '0');int t = 0;for (int i = x.size() - 1; i >= 0; i--) {t = t * 10 + x[i];z.push_back(t / c);t %= c;}reverse(z.begin(), z.end());while (z.size() > 1 && z.back() == 0) z.pop_back();for (int i = z.size() - 1; i >= 0; i--) {if (i != 0) cout << z[i];else cout << z[i] << endl;}cout << t << endl;//t作余数return 0;
}

矩阵乘法

多个矩阵相乘，其核心为尽可能用少的时间复杂度，可以考虑先算后面再进行前面的运算顺序

且其一般构造结构体进行存取，Code:

ypedef long long LL;
typedef struct {LL m[MAX][MAX];
}Mit;

矩阵快速幂/乘

Code:

Mit Mul(Mit a, Mit b)//快速乘
{Mit c;for (int i = 0; i < MAX; i++)for (int j = 0; j < MAX; j++) {c.m[i][j] = 0;for (int k = 0; k < MAX; k++) {a.m[i][k] = (a.m[i][k] % Mod + Mod) % Mod;b.m[k][j] = (b.m[k][j] % Mod + Mod) % Mod;c.m[i][j] += (a.m[i][k] * b.m[k][j]) % Mod;}c.m[i][j] = (c.m[i][j] % Mod + Mod) % Mod;}return c;
}
Mit qpow(Mit P, Mit I, int n)//快速幂
{Mit m = P, b = I;while (n >= 1) {if (n & 1) {b = Mul(b, m);}n = n >> 1;m = Mul(m, m);}return b;
}

二分

整数

Code:

bool check(int k)
{}
int main()
{int l = 0, r = 1e9;while (l < r) {int mid = l + r >> 1;if (check(mid)) {l = mid + 1;}else {r = mid;}}cout << r << endl;return 0;
}

浮点数

Code:

double x;
bool check(double k)
{return (k * k * k) < x;//k即为二分结果，要求三次方根，即为k的三次方
}
int main()
{l = -10000;r = 10000;while (r - l > 1e-8)//这里1e-8为精度，一般比要求多2{double mid = (l + r) / 2;if (check(mid)) l = mid;else r = mid;}printf("%.6lf\n", l);
}

双指针

Code:

for (int i = 0, j = 0; i < n; i ++ ){while (j < i && check(i, j)) j ++ ;//check表示题目的判断条件，没必要一定写函数，一般都是一个for里面套一个while，for里面接具体逻辑}

数据结构

树状数组

一般用来解决对数组的某一段区间进行询问和/差，以及对某个或者某段区间的修改

Code：

#include 
using namespace std;
const int N = 5e5 + 5;
int n, m;
int a[N], c[N];
void add(int x, int v)//建立数组
{for (; x <= n; x += x & -x) c[x] += v;//本代码以对区间加和为例，如果修改是减法则需要重新写一个建立函数
}
int sum(int x)//对区间查询操作，求1-x的和
{int ans = 0;for (; x; x -= x & -x) ans += c[x];return ans;
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i];add(i, a[i]);}
}

如果是对区间的修改可以变成差分数组，但不建议，建议使用线段树

线段树

线段树同树状数组一样可以实现对区间的操作，但与树状数组不同的是，线段是更加全面，它可以实现对某些不可逆操作的实现，例如最大值，最小值

Code：（对于线段树更多使用long long）

#include 
using namespace std;
const int N = 1e5 + 5;
typedef long long LL;
LL a[N], tr[N << 2];
LL tag[N << 2];//懒标记
int n, m;
void push_up(int id)//父节点更新函数
{tr[id] = tr[id << 1] + tr[id << 1 | 1];
}
void push_down(int id, int l, int r)//懒标记下传操作
{if (tag[id]) {//这里tag[id]为0，但在一些体中可能为0，所以需要改变判断条件int mid = l + r >> 1;tag[id << 1] += tag[id];tag[id << 1 | 1] += tag[id];tr[id << 1] += tag[id] * (mid - l + 1);tr[id << 1 | 1] += tag[id] * (r - mid);tag[id] = 0;}
}
void bui(int id, int l, int r)//建树
{if (l == r) {tr[id] = a[l];return;}int mid = l + r >> 1;bui(id * 2, l, mid);bui(id * 2 + 1, mid + 1, r);push_up(id);
}
void qjxg(int id, int l, int r, int x, int y, LL v)//区间修改x，y为待修改区间
{if (x <= l && y >= r) {tag[id] += v;tr[id] += v * (r - l + 1);return;}push_down(id, l, r);//没返回下移int mid = l + r >> 1;if (x <= mid) qjxg(id << 1, l, mid, x, y, v);if (y > mid) qjxg(id << 1 | 1, mid + 1, r, x, y, v);push_up(id);
}
LL find(int id, int l, int r, int x, int y)//区间查询
{if (x <= l && y >= r) return tr[id];push_down(id, l, r);int mid = r + l >> 1;LL ans = 0;if (x <= mid) ans += find(id << 1, l, mid, x, y);if (y > mid) ans += find(id * 2 + 1, mid + 1, r, x, y);return ans;
}
void dxg(int id, int l, int r, int x, int v)//单点修改，对于区间l到r，把下标为x的更新为v
{if (l == r) {if (tr[id] < v) tr[id] = v;return;}int mid = r + l >> 1;if (x <= mid) dxg(id * 2, l, mid, x, v);else dxg(id * 2 + 1, mid + 1, r, x, v);tr[id] = max(tr[id * 2], tr[id * 2 + 1]);//这里单点修改实现最大值
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i];}bui(1, 1, n);while (m--) {int p;cin >> p;if (p == 1) {int x, y, k;cin >> x >> y >> k;qjxg(1, 1, n, x, y, k);对于区间x，y将其内数组加k}else if (p == 2) {int x, y;cin >> x >> y;cout << find(1, 1, n, x, y) << "\n";}}return 0;
}

ST表

用处与线段树相差不大，且在对区间查询操作上st表甚至要快于线段树，但是st表不支持修改操作

Code:

const int N = 1e6 + 5;
int a[N], f[N][30];
int n, m;
void init()//初始化
{for (int i = 1; i <= n; i++) {f[i][0] = a[i];}for (int j = 1; (1 << j) <= n; j++) {for (int i = 1; i + (1 << (j - 1)) <= n; i++) {f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);}}
}
int rmq(int l, int r)//询问区间
{int k = log2(r - l + 1);return max(f[l][k], f[r - (1 << k) + 1][k]);
}

字典树

指的是某个字符串集合对应的有根树。树的每条边上恰好对应一个字符，每个顶点代表从根到该结点的路径所对应的字符串(将所有经过的边上的字符按顺序连接起来)。时间复杂度有数据大小决定

Code:
 

const int N = 3e6 + 5;
int trie[N][62], id, ed[N], cnt[N];//trie的大小一般是N和字符数量决定，全是大写字母或者全是小写字母一般开26，都有开52，板子开62因为有数字
int n, q;
int get(char ch)//不止一种字符的取值函数，可以根据需要修改
{if (ch >= 'a' && ch <= 'z') return ch - 'a';else if (ch >= 'A' && ch <= 'Z') return ch - 'A' + 26;else return ch - '0' + 52;
}
void insert(string s)//插入
{int p = 0;//切记从0for (char ch : s) {int c = get(ch);if (!trie[p][c])  trie[p][c] = ++id;p = trie[p][c];//如果p不是0，这里数据可能会出现错误，因为id是从0开始自加cnt[p]++;//用于统计前缀}//ed[p] = 1;//ed用于判断是否有这个字符串，cnt和ed一般指用一个
}
int find(string s)//找字符串
{int p = 0;for (char ch : s) {int c = get(ch);if (!trie[p][c]) return 0;p = trie[p][c];}return cnt[p];//需要判断有无只需改成ed[p]，必须修改因为cnt会统计前缀，例如有cat，查询ca也会返回1
}
/*这里是多次询问需要做的初始化，最好用这段不然可能会TLE
for (int i = 0; i <= id; i++) {for (int j = 0; j < 62; j++) {trie[i][j] = 0;}}for (int i = 0; i <= id; i++) {cnt[i] = 0;}
*/
int main()
{string x;for (int i = 1; i <= n; i++) {cin >> x;insert(x);}while (q--) {cin >> x;cout << find(x) << endl;}}
}

并查集

并查集一般用于计算联通块或者快速查询两个点是否是联通的

Code:

int pre[N];//记录上级
int rak[N];//记录有多少上级
int n, m;
void init()//初始化
{for (int i = 1; i <= n; i++) {pre[i] = i;rak[i] = 1;}
}
int find(int x)//判断x的最上级，最后判断两个点时只需判断两个点的祖宗是否一样即可
{if (pre[x] == x) return x;return pre[x] = find(pre[x]);
}
bool join(int x, int y)//连接两个点以及路径压缩
{x = find(x);y = find(y);if (x == y) return false;if (rak[x] < rak[y]) { pre[x] = y; rak[y] += rak[x]; }else {if (rak[x] == rak[y]) rak[x]++;else rak[x] += rak[y];pre[y] = x;}return true;
}

单调队列

哈希

模拟散列表

数据值过大但数据小，采用映射的方法

Code:

const int N = 2e5 + 5;//N要和MOD取值接近
const int MOD = 2e5 + 3;//取模一般用数据范围二倍且大于它的最小素数
const int null = 0x3f3f3f3f;
int h[N];
int n;
int find(int x)//查询x的下标是否有，有返回，没有返回可以用的空下标
{int t = (x % MOD + MOD) % MOD;//防止负数while (h[t] != null && h[t] != x) {t++;if (t == N) t = 0;//到尾了，从头再来}return t;
}
int main()
{memset(h, 0x3f, sizeof(h));char ch;int x;cin >> ch >> x;int tmp = find(x);//得下标if (ch == 'I') {h[tmp] = x;}else {if (h[tmp] == null) cout << "No" << endl;else cout << "Yes" << endl;}
}
}

字符串

typedef unsigned long long ULL;//代替取模过程
const int P = 131;//P一般取131或者13331，MOD取2的64次方
const int N = 1e5 + 5;
int n, m;
ULL p[N], h[N];
string x;
void init()//hash预处理
{p[0] = 1;h[0] = 0;for (int i = 1; i <= 1e5; i++) {p[i] = p[i - 1] * P;//h[i] = h[i - 1] * P + x[i - 1];//在main内实现特殊情况在这里使用}
}
ULL get(int x, int y)//返回区间x,y的哈希值
{return h[y] - h[x - 1] * p[y - x + 1];
}

KMP

Code:

const int N = 1e6 + 5;
char p[N], s[N];
int ne[N];
int n, m;//p长度为n，s长度为m
int main()
{cin >> n >> p + 1 >> m >> s + 1;for (int i = 2, j = 0; i <= n; i++) {//得到ne数组，从2开始因为1前面只有0了while (j && p[i] != p[j + 1]) j = ne[j];if (p[i] == p[j + 1]) j++;ne[i] = j;}for (int i = 1, j = 0; i <= m; i++) {while (j && s[i] != p[j + 1]) j = ne[j];if (s[i] == p[j + 1]) j++;if (j == n) {//找到字串j = ne[j];}}return 0;
}

贪心

图论

BFS

Code:

int mn[][2] = { 0,1,1,0,0,-1,-1,0 };//方向函数
struct sa {int x, y;
};
queuesva;
char a[25][25];
int bfs(int l, int r, int m, int n)//起点l，r，终点m，n
{sva.push({ l,r });struct sa tmp;int ans = 1;while (sva.size()) {tmp = sva.front();sva.pop();for (int i = 0; i < 4; i++) {int tmpx = mn[i][0] + tmp.x;int tmpy = mn[i][1] + tmp.y;if (tmpx > 0 && tmpy > 0 && tmpx <= m && tmpy <= n && a[tmpx][tmpy] == '.') {//判断条件：不出边界且符合题意sva.push({ tmpx,tmpy });ans++;}}}return ans;
}

DFS

LCA

树的直径

最短路

数学

区间筛

约数

将一个数质因子分解为pow(p1,a1)*pow(p2,a2)*...*pow(pk,ak)

约数个数

约数的个数为(a1+1)*(a2+1)*..*(ak+1)

Code:

#include 
typedef long long LL;
unordered_mapsva;//内部自带哈希，但其头文件不在万能头文件中
const int MOD = 1e9 + 7;
int main()
{int n;cin >> n;while (n--) {int a;cin >> a;for (int i = 2; i <= a / i; i++) {//质因子分解过程while (a % i == 0) {a /= i;sva[i]++;}}if (a > 1) sva[a]++;}LL res = 1;for (auto tmp : sva) {res = (res * (tmp.second + 1)) % MOD;}cout << res << endl;return 0;
}

区间计数

欧拉函数计算

GCD和EXGCD

Code:

int gcd(int a, int b)
{if (b == 0) return a;else return(gcd(b, a % b));
}
void exgcd(int a, int b, int& x, int& y)//求方程ax+by=gcd(a,b)的解
{if (!b) {x = 1, y = 0;return ;}int d = exgcd(b, a % b, y, x);y -= a / b * x;return d;
}

线性同余方程

一般使用扩展欧几里得算法，对于ax+by=d有解，d当且仅当是gcd(a,b)的倍数

Code:

//求解ax同余与b（mod m）
int exgcd(int a, int b, int& x, int& y)
{if (!b) {x = 1, y = 0;return a;}int d = exgcd(b, a % b, y, x);y -= a / b * x;return d;
}
int main()
{int a, b, m;int x, y;cin >> a >> b >> m;int d = exgcd(a, m, x, y);if (b % d != 0) cout << "impossible" << endl;else {cout << b / d * x % m << endl;//x的值，证明没看懂}
} 

逆元

博弈论

sg函数

组合数

数据a，b均小于2000

Code:

const int MOD = 1e9 + 7;
const int N = 2e3 + 5;
int c[N][N];
void init()
{for (int i = 0; i < N; i++) {for (int j = 0; j <= i; j++) {if (!j) c[i][j] = 1;else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;}}
}
int main()
{int a,b;cin >> a >> b;cout << c[a][b] << endl;return 0;
}

 数据在1e5以内

Code:

typedef long long LL;
const int MOD = 1e9 + 7;
const int N = 1e4 + 5;
LL f[N], inf[N];
LL qmi(LL a, LL b, LL m)
{LL ans = 1;while (b >= 1) {if (b & 1)  ans = (ans * a) % m;b = b >> 1;a = (a * a) % m;}return ans;
}
int main()
{f[0] = inf[0] = 1;for (int i = 1; i <= N; i++) {f[i] = f[i - 1] * i % MOD;inf[i] = inf[i - 1] * qmi(i, MOD - 2, MOD) % MOD;}int a, b;cin >> a >> b;cout << f[a] * inf[b] % MOD * inf[a - b] % MOD << endl;return 0;
}

 数据达到1e18

Code:

typedef long long LL;
LL m;
LL qmi(LL a, LL b)
{LL ans = 1;while (b >= 1) {if (b & 1)  ans = (ans * a) % m;b = b >> 1;a = (a * a) % m;}return ans;
}
LL C(LL a, LL b)
{if (b > a) return 0;LL ans = 1;for (int i = 1, j = a; i <= b; i++, j--) {ans = ans * j % m;ans = ans * qmi(i, m - 2) % m;}return ans;
}
LL lucas(LL a, LL b)
{if (a < m && b < m) return C(a, b);return C(a % m, b % m) * lucas(a / m, b / m) % m;
}
int main()
{LL a, b;cin >> a >> b >> m;cout << lucas(a, b) << endl;return 0;
}

动态规划

背包

01背包

Code:

for (int i = 1; i <= n; i++) {for (int j = m; j >= v[i]; j--) {//从m开始保证不会在遍历时对本层已遍历数据再次利用，导致同一个数据多次使用dp[j] = max(dp[j], dp[j - v[i]] + w[i]);}}cout << dp[m] << endl;/*至于答案为社么在dp[m]上，由于一共就m个数据每回合都会调用这些数据中的某些并取最大值，同时对于第一层调用dp数组为全局变量数组中都会赋值为0，在第一次调用时不会产生其他数据出现，所以dp[m]也是答案所在*/

完全背包

Code:

 for(int i=1;i<=n;i++){for(int j=v[i];j<=m;j++){//和01背包唯一的不同点dp[j]=max(dp[j],dp[j-v[i]]+w[i]);}}cout<

int dp[N];
int v[N], w[N], s[N];
int n, m;
int a[N], b[N];
int cnt;
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> v[i] >> w[i] >> s[i];}for (int i = 1; i <= n; i++) {for (int j = 1; j <= s[i]; j *= 2) {//按照二进制拆分如果最后数据不是二进制则出循环，单独写入//原理：例如‘6’差分为1，2，3，当取1时就是只拿一个的情况，想要拿4个即是拿一个1，再拿一个3，所以可以把所有情况都枚举一遍s[i] -= j;cnt++;a[cnt] = v[i] * j;b[cnt] = w[i] * j;}if (s[i] > 0) {cnt++;a[cnt] = v[i] * s[i];b[cnt] = w[i] * s[i];}}for (int i = 1; i <= cnt; i++) {//这就转化为01背包了for (int j = m; j >= a[i]; j--) {dp[j] = max(dp[j], dp[j - a[i]] + b[i]);}}cout << dp[m] << endl;return 0;
}

//多重背包上的全部拆分为01思想
int dp[N];
int v[N], w[N], s[N];
int n, m;
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> s[i];for (int j = 1; j <= s[i]; j++) {cin >> v[j] >> w[j];}for (int j = m; j >= 0; j--) {for (int k = 1; k <= s[i]; k++) {if (j >= v[k]) {dp[j] = max(dp[j], dp[j - v[k]] + w[k]);}}}}cout << dp[m] << endl;return 0;
}

#include 
using namespace std;
const int N = 1e4 + 5;
const int M = 1e6 + 5;
int n, m, cnt;
int dp[N];
int v[N], w[N], s[N];
int a[M], b[M], c[M];
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> v[i] >> w[i] >> s[i];}for (int i = 1; i <= n; i++) {if (s[i] < 0) {//本身就是01背包，直接存起来cnt++;a[cnt] = v[i];b[cnt] = w[i];c[cnt] = 1;}else if (s[i] == 0) {//原来是完全背包，也是直接存起来cnt++;a[cnt] = v[i];b[cnt] = w[i];c[cnt] = 0;}else {//原来是多重背包，二进制优化，变成01背包后再存起来for (int j = 1; j <= s[i]; j *= 2) {s[i] -= j;cnt++;a[cnt] = v[i] * j;b[cnt] = w[i] * j;c[cnt] = 1;}if (s[i] > 0) {cnt++;a[cnt] = v[i] * s[i];b[cnt] = w[i] * s[i];c[cnt] = 1;}}}for (int i = 1; i <= cnt; i++) {if (c[i] == 1) {//01背包for (int j = m; j >= a[i]; j--) {dp[j] = max(dp[j], dp[j - a[i]] + b[i]);}}else if (c[i] == 0) {//完全背包for (int j = a[i]; j <= m; j++) {dp[j] = max(dp[j], dp[j - a[i]] + b[i]);}}}cout << dp[m] << endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！