1，常见板子
素数
bool isPrime(int n)
{
if (n == 1)
return false;
if (n == 2 || n == 3)
return true;
if (n % 6 != 1 && n % 6 != 5)
return false;
for (int i = 5; i <= sqrt(n); i += 6)
{
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
最大公约数：辗转相除法
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
快速幂：
\[pow\_mod(x,n,mod) = \begin{cases} 1, &n=0\\ pow\_mod(x*x\%mod,n/2,mod), & \text{if }n\text{ is even} \\ pow\_mod(x*x\%mod,n/2,mod)*x\%mod, & \text{if }n\text{ is odd} \end{cases}\]ll pow_mod(ll x, ll n, ll mod) {
if (n == 0)
return 1;
ll res = pow_mod(x * x % mod, n / 2);
if (n & 1)
res = res * x % mod;
return res;
}
冒泡排序：
void bublesort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
运算符重载
struct Grade{
string name;
string id;
int score;
bool operator < (const Grade t) const{
// return score < t.score 升序
return t.score < score;//降序
}
};
KMP:字符串匹配
#include <iostream>
#include<string>
using namespace std;
void get_next(string T, int next[]){
int i=0, j=-1;
next[0] = -1;
while(i<T.length()-1){
if(j==-1 || T[i] == T[j]){
i++; j++;
next[i] = j; //当pi = pj, 'p0...pk-1pk' = 'pj-k...pj', next[j+1] = k+1, 即next[j+1] = next[j]+1
}
else
j = next[j]; //Ti != Tj, j=next[j];
}
}
int index_KMP(string S, string T, int next[]){
int i=0, j=0;
// cout << (-1<int(T.length())) << endl;
// cout << (-1<t.length())
while(i<int(S.length()) && j<int(T.length())){
if(j==-1 || S[i]==T[j]){
i++; j++; //继续比较后面的字符
}
else{
j = next[j]; //模式串向右移动
}
}
if(j>=T.length())
return i-T.length();//匹配成功
else
return 0; //匹配失败
}
int main()
{
int next[100];
string s = "babaabcaba", t = "abaabcaba";
get_next(t, next);
cout << index_KMP(s,t,next);
return 0;
}
线段树：
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
using namespace std;
struct SegTree{
int l, r, Sum, Max;
}seq[1000001];
void init(int l,int r, int i){//l表示左端点，r表示右端点， i表示序号
seq[i].l = l;
seq[i].r = r;
seq[i].Max = 0;
seq[i].Sum = 0;
if(l!=r){
int mid = (l+r)/2;
init(l,mid, i*2);
init(mid+1, r, i*2+1);
}
}
void insert(int root, int i, int val){
if(seq[root].l == seq[root].r){
seq[root].Max = val;
seq[root].Sum = val;
return;
}
int mid = (seq[root].l + seq[root].r)/2;
if(i <= mid)
insert(root*2,i, val);
else
insert(root*2+1, i, val);
seq[root].Max = max(seq[root*2].Max, seq[root*2+1].Max);
seq[root].Sum = seq[root*2].Sum + seq[root*2+1].Sum;
}
int find_max(int x, int y, int i){
if(x==seq[i].l && y==seq[i].r)
return seq[i].Max;
int mid = (seq[i].l + seq[i].r)/2;
if(x > mid)
return find_max(x,y,i*2+1);
else if(y<=mid)
return find_max(x,y,i*2);
else
return max(find_max(x,mid,i*2), find_max(mid+1,y, i*2+1));
}
int find_sum(int x, int y, int i){
if(x==seq[i].l && y==seq[i].r)
return seq[i].Sum;
int mid = (seq[i].l + seq[i].r)/2;
if(x > mid)
return find_sum(x,y,i*2+1);
else if(y<=mid)
return find_sum(x,y,i*2);
else
return find_sum(x,mid,i*2) + find_sum(mid+1,y, i*2+1);
}
int main(){
int n,m,weight, p, x, y;
scanf("%d%d", &n, &m);
init(1,n,1);
for(int l1=1; l1<=n; l1++){
scanf("%d", &weight);
insert(1,l1,weight);
}
for(int l1=1; l1<=m; l1++){
scanf("%d%d%d", &p, &x, &y);
if(p==1){
insert(1,x,y);
}
else if(p==2){
printf("%d\n", find_sum(x,y,1));
}
else{
printf("%d\n", find_max(x,y,1));
}
}
return 0;
}
并查集
PAT 1001 Battle Over Cities - Hard Version
class DisjointSet {
public:
vector<int> parent;
int count;
DisjointSet(int maxn) {
parent.resize(maxn + 1);
count = maxn;
for (int i = 0; i < maxn; i++) {
parent[i] = i;
}
};
//查找根节点
int find(int x) {
while (x != parent[x]) {
//路径压缩：隔代压缩
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
//合并
void merge(int x, int y) {
int rootx = find(x);
int rooty = find(y);
if (rootx == rooty)
return;
parent[rootx] = rooty;
count--;
};
};
cout 二进制、十进制、八进制、十六进制:
#include<iostream>
#include<bitset>
using namespace std;
int main(){
//bi -> dec
bitset<14> biNum("101001101101111");
cout << biNum.to_ullong() << endl;
//dec -> bi
cout << bitset<14>(i) << endl;
//dec -> hex
cout << hex << a << endl;
//dec -> oct
cout << oct << a << endl;
return 0;
}
二进制枚举：
//二进制枚举：超时
#include<iostream>
using namespace std;
int main()
{
int n,m;
cin >> n >> m;
int ans = 0;
for(int i=0; i<(1<<(n+m-1)); i++){//最后遇到花是确定的，前n+m-1个不确定
int tot_store = 0;
int tot_flower = 0;
int wine = 2;
for(int j=0; j<(n+m-1); j++){
if(i&(1 << j)){// i的第j位为1，设为遇到的是花
tot_flower++;
wine--;
}
else{
tot_store++;
wine *= 2;
}
}
if(tot_flower==m-1 && tot_store==n && wine==1)
ans++;
}
cout << ans % 1000000007 << endl;
return 0;
}
递归：
//递归：超时
#include<iostream>
using namespace std;
int n,m;
int ans = 0;
int cnt=0;
void solution(int flower, int store, int wine){
if(flower+store >= n+m)
return;
if(flower==m-1 && store==n && wine==1){
ans++;
return;
}
// cout << cnt++ << endl;
// if(cnt == (1<<13))
// cout << "here";
solution(flower+1, store, wine-1);
solution(flower, store+1, wine*2);
}
int main()
{
cin >> n >> m;
solution(0,0,2);
cout << ans % 1000000007 << endl;
return 0;
}
动态规划：
//DP动态规划
#include<iostream>
using namespace std;
typedef long long ll;
ll n,m;
ll dp[202][101][101];//dp[i][j][k]: 第i个位置，遇到j个花， 还剩k斗酒 的策略数
ll mod = 1e9+7;
int main()
{
cin >> n >> m;
dp[0][0][2] = 1;
for(int i=1; i<n+m; i++){
for(int j=0; j<m; j++){
for(int k=0; k<=m; k++){
if(!(k&1)){//k为偶数
dp[i][j][k] = (dp[i][j][k] + dp[i-1][j][k>>1]) % mod;
}
if(j>=1){
dp[i][j][k] = (dp[i][j][k] + dp[i-1][j-1][k+1]) % mod;
}
}
}
}
cout << dp[n+m-1][m-1][1] << endl;
return 0;
}
最长公共子序列：
int lcs(string x, string y) {
int xlen = x.length(), ylen = y.length();
x = " " + x; y=" "+y;//下标从1开始取
vector<vector<int>> dp;
dp.resize(xlen+1);
for (int i = 0; i < xlen+1; i++)
dp[i].resize(ylen+1);
for (int i = 0; i <= xlen; i++)
dp[i][0] = 0;
for (int j = 0; j <= ylen; j++)
dp[0][j] = 0;
for (int i = 1; i <= xlen; i++) {
for (int j = 1; j <= ylen; j++) {
if (x[i] == y[j]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[xlen][ylen];
}
最长公共子序列：
int lis(string s) {
vector<int> dp;
dp.resize(s.size());
dp[0] = 1;
for (int i = 1; i < s.size();i++) {
int maxl = 1;
for (int j = 0; j < i;j++) {
if (s[i] > s[j])
maxl = max(maxl, dp[j] + 1);
else
maxl = max(maxl, dp[j]);
}
dp[i] = maxl;
}
return dp[s.size() - 1];
}
回溯：
void init(int n){
col.resize(n), row.resize(n), diag.resize(n*2-1), negdiag.resize(n*2-1);
for(int i=0; i<n; i++)
row[i] = col[i] = FREE;
for(int i=0; i<n*2-1; i++)
diag[i] = negdiag[i] = FREE;
};
vector<vector<string>> ans;
void printAns(int n){
vector<string> solution;
for(int i=0; i<n; i++){
string tmp = "";
for(int j=0; j<n; j++){
if(row[i] == j){
tmp += "Q";
}
else
tmp += ".";
}
solution.push_back(tmp);
}
ans.push_back(solution);
};
void recursive(int i, int n){
if(i==n){
printAns(n);
return;
}
for(int j=0; j<n; j++){
if(col[j] == NOTFREE || diag[i+j] == NOTFREE || negdiag[i-j+n-1] == NOTFREE)
continue;
row[i] = j; col[j] = diag[i+j]=negdiag[i-j+n-1] = NOTFREE;
recursive(i+1, n);
row[i] = col[j] = diag[i+j] = negdiag[i-j+n-1] = FREE;
}
};
vector<vector<string>> solveNQueens(int n) {
init(n);
recursive(0,n);
return ans;
}
2, 图论
邻接矩阵表示法：
class MatGraph {
public:
set<int> V;//顶点表
int E[maxn][maxn];//边表
int vn, en;//当前图的顶点数和边数
MatGraph() {
for (int i = 0; i < maxn; i++) {
for (int j = 0; j < maxn; j++)
{
E[i][j] = -1;
}
}
vn = en = 0;
};
void addV(int newV) {
if (V.find(newV) == V.end()) {
V.insert(newV);
vn++;
}
};
void addE(int begin, int end, int weight) {
if (E[begin][end] == -1) {
en++;
}
E[begin][end] = E[end][begin] = weight;
};
};
邻接表法：
struct {
int tovex;//该边指向的顶点的位置
edgeNode* next;//下一条边的指针
}edgeNode;
struct {
int data;//定点信息
edgeNode* first;//指向第一条依附于该定点的边的指针
}vexNode,AdjList[maxn];
struct {
AdjList vex; //定点表（链表的头）
int vexnum, edgenum;//当前图的顶点数和边数
}AdjGraph;
最小生成树：
prime：
#include<iostream>
#include<vector>
#include<set>
using namespace std;
const int maxn = 100;
class MatGraph {
public:
set<int> V;//顶点表
int E[maxn][maxn];//边表
int vn, en;//当前图的顶点数和边数
MatGraph() {
for (int i = 0; i < maxn; i++) {
for (int j = 0; j < maxn; j++)
{
E[i][j] = -1;
}
}
vn = en = 0;
};
void addV(int newV) {
if (V.find(newV) == V.end()) {
V.insert(newV);
vn++;
}
};
void addE(int begin, int end, int weight) {
if (E[begin][end] == -1) {
en++;
}
E[begin][end] = E[end][begin] = weight;
};
};
const int max_weight = 0x3f3f3f;
void Prim(MatGraph G, MatGraph &T, int V) {//G为图，T为要返回的最小生成树，初始化为空, V为任取一个顶点
T.addV(V);
int vn = G.vn;
while(T.vn != vn){//树中不含全部顶点
int start = 0, end = 0, weight=max_weight;//权值最小的边
for (auto v_st : T.V) {
for (auto v_ed : G.V) {
if (T.V.find(v_ed) == T.V.end() && G.E[v_st][v_ed]!= -1 && G.E[v_st][v_ed] < weight) {
start = v_st, end = v_ed, weight = G.E[v_st][v_ed];
}
}
}
T.addE(start, end, weight);
T.addV(end);
}
}
struct E{
int start, end, weight;
};
int main()
{
MatGraph G;
for (int i = 1; i < 7; i++)
{
G.addV(i);
}
E e[10] = { {1,2,6},{1,4,5},{1,3,1},{2,3,5},{3,4,5},{2,5,3},{3,5,6},{3,6,4},{4,6,2},{5,6,6} };
for (int i = 0; i < 10; i++)
{
G.addE(e[i].start, e[i].end, e[i].weight);
}
MatGraph T;
Prim(G, T, 1);
for (size_t i = 1; i <= T.vn; i++)
{
for (size_t j = 1; j <= T.vn; j++)
{
if (T.E[i][j] != -1)
cout << i << " " << j << " " << T.E[i][j] << endl;
}
}
return 0;
}
Kruskal:
void kruskal(MatGraph G, MatGraph& T) {
for (auto v : G.V) {
T.addV(v);
}
DisjointSet ds(T.vn);
while (ds.count > 1) {
int vs = 0, vd = 0, weight = max_weight;
for (int i = 1; i <= T.vn; i++)
{
for (int j = 1; j <= T.vn; j++)
{
if (G.E[i][j] != -1 && ds.find(i)!= ds.find(j) && G.E[i][j] < weight) {
vs = i, vd = j, weight = G.E[i][j];
}
}
}
T.addE(vs, vd, weight);
ds.merge(vs, vd);
}
}
最短路径：
Dijkstra:
void Dijkstra(MatGraph G, int vs, int vd) {
int vn = G.vn;
vector<int> dist(vn);
vector<int> pathAhead(vn);
pathAhead[vs] = vs;
for (int i = 1; i <= G.vn; i++)
{
dist[i] = max_weight;
}
dist[vs] = 0;
set<int> V;
V.insert(vs);
int cur_short = vs;
while (V.size() != G.vn) {
for (int i = 1; i <= G.vn; i++)
{
if (G.E[cur_short][i] != -1 && dist[cur_short] + G.E[cur_short][i] < dist[i]) {
dist[i] = dist[cur_short] + G.E[cur_short][i];
pathAhead[i] = cur_short;
}
}
int weight = max_weight;
for (int i = 1; i <= G.vn; i++)
{
if (V.find(i) == V.end() && dist[i] < weight) {
weight = dist[i];
cur_short = i;
}
}
V.insert(cur_short);
}
//print inversed path from vs to vd :
cur_short = vd;
while (cur_short != vs) {
cout << cur_short << endl;
cur_short = pathAhead[cur_short];
}
cout << cur_short << endl;
}
Bellman-Ford:
const int max_weight = 0x3f3f3f3f;
void Bellman_Ford(MatGraph G, int vs) {
int vn = G.vn;
vector< vector<int> > dist(vn+1, vector<int>(vn+1, max_weight));
dist[0][vs] = 0;
for (int i = 1; i < vn; i++)
{
for (auto v : G.V){
int minDist = max_weight;
for (auto pv : G.V) {
if (G.E[pv][v] != -1 && dist[i - 1][pv] + G.E[pv][v] < minDist)
minDist = dist[i - 1][pv] + G.E[pv][v];
}
dist[i][v] = min(dist[i - 1][v], minDist);
}
}
//print all distances from vs to all vertex.
for (auto v : G.V)
cout << vs << " to " << v << ":" << dist[vn - 1][v] << endl;
}
Floyd_Warshall:
const int max_weight = 0x3f3f3f3f;
void Floyd_Warshall(MatGraph G) {
int vn = G.vn;
//初始化
vector<vector<vector<int>>> dist(vn + 1, vector<vector<int>>(vn + 1, vector<int>(vn + 1, max_weight)));
for (int i = 0; i <= vn; i++) {
for (int j = 1; j <= vn; j++)
{
for (int k = 1; k <= vn; k++) {
if (j == k)
dist[i][j][k] = 0;
else if (G.E[j][k] != -1)
dist[i][j][k] = G.E[j][k];
}
}
}
//i作为中间节点，找到dist[i-1][j][i] + dist[i-1][i][k] < dist[i][j][k]
for (int i = 1; i <= vn; i++) {
for (int j = 1; j <= vn; j++) {
for (int k = 1; k <= vn; k++) {
dist[i][j][k] = min(dist[i - 1][j][k], dist[i - 1][j][i] + dist[i - 1][i][k]);
}
}
}
for (int j = 1; j <= vn; j++) {
for (int k = 1; k <= vn; k++) {
cout << "shortest path from " << j << " to " << k << ":" << dist[vn][j][k] << endl;
}
}
}
拓扑排序：
广度优先搜索拓扑排序：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAXV 10005
vector<int> vec[MAXV];
vector<int> ans;
int v, e;
int indeg[MAXV] = {0};
bool vis[MAXV] = {false};
void bfs(int u)
{
queue<int>q;
vis[u] = true;
q.push(u);
while(!q.empty())
{
int t = q.front();
q.pop();
ans.push_back(t);
for(int x:vec[t])
{
indeg[x]--;
if(indeg[x]==0&&vis[x]==false)
{
q.push(x);
vis[x] = true;
}
}
}
}
void solve()
{
for (int i = 0; i < v; ++i)
{
if (indeg[i] == 0 && vis[i] == false)
{
bfs(i);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> v >> e;
int s, t;
for (int i = 0; i < e; ++i)
{
cin >> s >> t;
vec[s].push_back(t);
indeg[t]++;
}
solve();
for(int x:ans)
{
cout<<x<<endl;
}
}
深度优先深度搜索：
vector<int>g[N];//邻接表存储
int vis[N],topo[N],cnt;
bool dfs(int u)
{
vis[u] = -1;//-1用来表示顶点u正在访问
for(int i = 0 ; i < g[u].size() ; i ++)
{
if(vis[g[u][i]] == -1)//表示这个点进入了两次，肯定出现了环
return false;
else if(vis[g[u][i]] == 0)
{
dfs(g[u][i]);
}
}
vis[u] = 1;
topo[cnt++] = u;//放到结果数组里，输出的时候记得倒序输出，（回溯的原因）
return true;
}
bool toposort(int n)
{
memset(vis,0,sizeof(vis));
for(int i = 1 ; i <= n ; i ++)
{
if(!vis[i])
{
if(!dfs(i)) return false;//huan
}
}
return true;
}
#include<iostream>
using namespace std;
int main(){
int ans = 0;
int n,m;
cin>> n>>m;
int l = 1;
int j;
cin>>j;
int arr[10000];
for(int l1=1; l1<=j; l1++){
int tmp;
cin>>tmp;
arr[l1] = tmp;
}
int cur=1;
int next;
while(cur<j){
next = cur+1;
if(arr[next] >= arr[cur]){
int Min = min(abs(arr[cur] - l), abs(arr[next]-(l+m-1)));
ans += Min;
if(Min == abs(arr[cur]-l)){
l=arr[cur];
}
else{
l = arr[next]-m+1;
}
if(arr[next] <= l+m-1){
cur +=2;
}
else{
cur++;
}
}
else{
int Min = min(abs(arr[cur]-(l+m-1)), abs(arr[next]-l));
ans += Min;
if(Min = abs(arr[cur]-l+m-1))
l = arr[cur]+1-m;
else{
l = arr[next];
}
if(arr[next] >= l){
cur += 2;
}
else{
cur++;
}
}
}
if(arr[cur] >= l && arr[cur] <= l+m-1){
}
else{
ans += min(abs(l-arr[cur]), abs(l+m-1-arr[cur]));
}
cout << ans << endl;
}
文档信息
- 本文作者：Yang Jucai
- 本文链接：https://yangjucai.github.io//2020/09/10/ACM%E6%A8%A1%E6%9D%BF/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）