常用C++函数
1.isdigit()函数判断字符是否为0-9的数字
2.isalpha()函数判断当前字符是否为英文字母如果为大写字母eg:’A’返回1, 小写’a’就返回2
3.ceil()上取整函数
4.floor()下取整函数
5.stoi函数传入一个数字字符的字符串,返回其对应的10进制整数,如果传入的字符串非法则会报错
6.reverse,字符串翻转函数,调用规则:reverse(str.begin(), str.end()), str为string类型,可以实现对字符串的翻转。
算法板子:
并查集
Code
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
int p[N];
int cnt[N];
int n, m;
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
void merge(int x, int y)
{
p[find(x)] = p[find(y)];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
for(int i = 1; i <= n; i ++) p[i] = i;
for(int i = 1; i <= m; i ++)
{
int u, v;
cin >> u >> v;
merge(u, v);
}
for(int i = 1; i <= n; i ++)
{
cnt[find(i)] ++;
}
vector<int> res;
for(int i = 1; i <= n; i ++)
if(cnt[i]) res.push_back(cnt[i]);
sort(res.begin(), res.end());
for(auto t : res) cout << t << " ";
return 0;
}
朴素版本dijkstra算法
Code
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e3 + 10;
struct edge{
int to, w;
};
int n, m;
int d[N];
bool vis[N]; //表示当前点是否已经为最短距离
vector<edge> g[N];
void dijkstra(int st)
{
d[st] = 0;
for(int i = 1; i <= n - 1; ++ i) //迭代n-1次
{
int t = 1;
for(int j = 1; j <= n; ++ j) //每次选择当前距离源点最近的点
if(vis[t] || (!vis[j] && d[t] > d[j])) t = j;
vis[t] = true;
for(auto &p : g[t])
{
if(!vis[p.to] && d[t] + p.w < d[p.to]) d[p.to] = d[t] + p.w;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
memset(d, 0x3f, sizeof d);
for(int i = 1; i <= m; ++ i)
{
int u, v, w;
cin >> u >> v >> w;
if(u != v) g[u].push_back({v, w});
}
dijkstra(1);
cout << d[n];
return 0;
}
堆优化版本dijkstra()
Code
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
struct edge{
int to, w;
bool operator < (const edge &a)const{ //堆的运算符重载是和正常的运算符重载是相反的
return w > a.w;
}
};
int n, m;
int d[N];
bool vis[N]; //表示当前点是否已经为最短距离
vector<edge> g[N];
void dijkstra(int st)
{
d[st] = 0;
priority_queue<edge> pq;
pq.push({st, d[st]});
while(pq.size())
{
auto t = pq.top();
pq.pop();
int x = t.to;
if(vis[x]) continue; //第一次从队列出来就已经是最小值了,防止重复更新
vis[x] = true; //取出的x点已经得到了最短距离
for(auto &p : g[x])
{
if(!vis[p.to] && d[x] + p.w < d[p.to]) //如果vis[to]成立表示当前点已经是最短距离,无需更新
{
d[p.to] = d[x] + p.w;
pq.push({p.to, d[p.to]});
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
memset(d, 0x3f, sizeof d);
for(int i = 1; i <= m; ++ i)
{
int u, v, w;
cin >> u >> v >> w;
if(u != v) g[u].push_back({v, w});
}
dijkstra(1);
if(d[n] >= 0x3f3f3f3f) cout << -1;
else cout << d[n];
return 0;
}
多源最短路 Floyd算法
Code
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 310;
int n, m, q;
int d[N][N];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m >> q;
memset(d, 0x3f, sizeof d);
for(int i = 1; i <= m; ++ i)
{
int u, v, w;
cin >> u >> v >> w;
d[u][v] = min(d[u][v], w);
}
for(int i = 1; i <= n; ++ i) d[i][i] = 0;
for(int k = 1; k <= n; ++ k)
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= n; ++ j)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
while(q --)
{
int a, b;
cin >> a >> b;
cout << (d[a][b] >= 0x3f3f3f3f ? -1 : d[a][b]) << endl;
}
return 0;
}
堆优化版prim
Code
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n, m;
struct edge{
LL x, w;
bool operator < (const edge &v)const{
return w > v.w;
}
};
bool st[N];
vector<edge> g[N];
LL d[N];
LL ans;
void prim()
{
priority_queue<edge> pq;
d[1] = 0;
pq.push({1, 0});
while(pq.size()) //用堆来维护距离最小生成树距离最近的点
{
auto t = pq.top();
pq.pop();
LL x = t.x;
if(st[x]) continue; //如果当前点已经在生成树中就跳过
st[x] = true; //将当前点加入生成树中
ans += d[x];
d[x] = 0; //加入最小生成树之后,当前点距离最小生成树的距离为0
for(auto &p : g[x]) //用当前点来更新其他点到最小生成树的距离
{
if(!st[p.x] && d[p.x] > p.w)
{
d[p.x] = p.w;
pq.push({p.x, p.w});
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
for(int i = 1; i <= m; i ++)
{
int u, v, w;
cin >> u >> v >> w;
if(u != v)
{
g[u].push_back({v, w});
g[v].push_back({u, w});
}
}
memset(d, 0x3f, sizeof d);
prim();
bool flag = true;
for(int i = 1; i <= n; i ++) if(!st[i]) flag = false;
if(flag) cout << ans;
else cout << -1;
return 0;
}
kruskal算法
Code:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n, m;
int p[N];
struct edge{
int u, v, w;
bool operator < (const edge &m)const{
return w < m.w;
}
};
vector<edge> g;
int cnt;
int find(int x)
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
for(int i = 1; i <= m; i ++)
{
int u, v, w;
cin >> u >> v >> w;
g.push_back({u, v, w});
}
for(int i = 1; i <= n; i ++) p[i] = i;
sort(g.begin(), g.end());
LL ans = 0;
for(int i = 0; i < g.size(); i ++)
{
int fa = find(g[i].u);
int fb = find(g[i].v);
if(fa != fb)
{
++ cnt;
ans += g[i].w;
p[fa] = fb;
}
}
if(cnt != n - 1) ans = -1;
cout << ans;
return 0;
}
求一个数的因子与质因子
求因子
Code:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
LL n;
vector<LL> v;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
for(int i = 1; i <= n / i; i ++)
{
if(n % i) continue;
v.push_back(i);
if(i != n / i) v.push_back(n / i);
}
sort(v.begin(), v.end());
for(auto &x : v) cout << x << " ";
return 0;
}
质因子:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
LL n;
vector<LL> v;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
for(int i = 2; i <= n / i; i ++)
{
if(n % i) continue;
v.push_back(i);
while(n % i == 0) n /= i;
}
if(n > 1) v.push_back(n);
sort(v.begin(), v.end());
for(auto &x : v) cout << x << " ";
return 0;
}
埃氏筛法
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e6 + 10;
int n;
vector<int> prime;
bool st[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
st[0] = st[1] = true;
for(int i = 1; i <= n; i ++)
if(!st[i])
{
prime.push_back(i);
for(int j = 2 * i; j <= n; j += i)
st[j] = true;
}
for(auto &x : prime) cout << x << ' ';
return 0;
}
最小公倍数gcd和最大公约数lcm
Code
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e6 + 10;
LL gcd(LL x, LL y)
{
if(!y) return x;
else return gcd(y, x % y);
}
LL lcm(LL x, LL y)
{
return x / gcd(x, y) * y;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
while(T --)
{
LL a, b;
cin >> a >> b;
cout << gcd(a, b) << " " << lcm(a, b) << endl;
}
return 0;
}
快速幂
Code
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e6 + 10;
LL qmi(LL a, LL b, LL mod)
{
LL res = 1;
while(b)
{
if(b & 1)
{
res = res * a % mod;
}
b >>= 1;
a = a * a % mod;
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
while(T --)
{
LL a, b, mod;
cin >> a >> b >> mod;
cout << qmi(a, b, mod) << endl;
}
return 0;
}
乘法逆元
Code
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e6 + 10, MOD = 998244353;
//乘法逆元,在mod某个数p的意义下,除以这个数等于乘以这个数的逆元
//费马小定理:a在mod数p下的逆元就是a的p-2次方
LL qmi(LL a, LL b, LL mod)
{
LL res = 1;
while(b)
{
if(b & 1)
{
res = res * a % mod;
}
b >>= 1;
a = a * a % mod;
}
return res;
}
LL inv(LL t, LL MOD) //求逆元函数
{
return qmi(t, MOD - 2, MOD);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
while(T --)
{
LL a, b, c, q;
cin >> a >> b >> c >> q;
while(q --)
{
LL x;
cin >> x;
cout << (a * x % MOD + b) % MOD * inv(c * x % MOD, MOD) % MOD << endl;
}
}
return 0;
}