c++算法模板
前言
OI的一大特色就在于学习各种算法，但是很多算法都结构复杂而拥有固定模板，很少有随机应变的情况，即使你把算法的意思搞清楚了，敲起代码也会很烦，那么本篇blog就给大家整理了很多这种算法
声明：仅作者个人想法，不喜勿喷
正文
以下代码整理了作者目前所知的算法模板，想要使用可以直接复制，但是 不可以复制整篇代码给其他人展示已达到任何目的 ，如果想要这么做请 获得作者同意 ，作者uid已在blog副标题展示
建议加上磁带妈的所有头文件，不然可能会造成因为头文件不全而造成的意外情况
// 作者@sean_coder，uid = 557975
// 未经允许，严禁转载
# include <iostream>
# include <string>
# include <algorithm>
# include <stack>
using namespace std;
// 判断质数
bool isPrime(int x) {
if (x == 1) {
return false;
}
for (int i = 2; i * i <= x; ++i) {
if (x % i == 0) {
return false;
}
}
return true;
}
// 筛法判断质数
void setisPrime(bool flag[], int len) {
int i, j;
for (i = 0; i <= len; ++i) {
flag[i] = true;
}
flag[0] = flag[1] = false;
for (i = 2; i <= len; ++i) {
if (flag[i]) {
for (j = 2 * i; j <= len; j += i) {
flag[j] = false;
}
}
}
}
// 约数个数
int facCnt(int x) {
int cnt = 0;
for (int i = 1; i * i <= x; ++i) {
if (x % i == 0) {
cnt += 2;
}
if (i * i == x) {
--cnt;
}
}
return cnt;
}
// 约数之和
int facSum(int x) {
int sum = 0;
for (int i = 1; i * i <= x; ++i) {
if (x % i == 0) {
sum += i;
sum += x / i;
}
if (i * i == x) {
sum -= x / i;
}
}
return sum;
}
// 最大公约数
int gcd(int x, int y) {
while (y != 0) {
int temp = y;
y = x % y;
x = temp;
}
return x;
}
// 最小公倍数(需要最大公倍数函数)
int sml(int x, int y) {
return x * y / gcd(x, y);
}
// 其他进制转十进制(36进制以内)
int m2D(int m, string s) {
int ans = 0;
for (int i = 0; i <= s.size() - 1; i++) {
if (s[i] >= '0' && s[i] <= '9') {
ans = ans * m + s[i] - '0';
}
else {
ans = ans * m + s[i] - 'A' + 10;
}
}
return ans;
}
// 十进制转其他进制(36进制以内)
string D2m(int n, int m) {
string digit = "0123456789ABCDEF";
string ans = "";
while (n > 0) {
ans = digit[n % m] + ans;
n /= m;
}
return ans;
}
// 进制之间互相转换(36进制以内)
string m2m(int m1, int m2, string x) {
int num = m2D(m1, x);
string ans = D2m(num, m2);
return ans;
}
// 把字符串s存储的整数按照大整数的格式存入数组a中
void s2BIG(string s, int a[]) {
int la = s.length();
for (int i = 1; i <= la; i++) {
a[i] = s[la - i] - '0';
}
a[0] = la;
}
// 将n化为大整数形式保存在数组a中
void i2BIG(int n, int a[]) {
int cur = 0;
while (n > 0) {
++cur;
a[cur] = n % 10;
n /= 10;
}
a[0] = cur;
}
// 将x+y的结果存入数组z中
void addBIG(int x[], int y[], int z[]) {
z[0] = max(x[0], y[0]);
for (int i = 1; i <= z[0]; ++i) {
z[i] = x[i] + y[i];
}
for (int i = 1; i <= z[0]; ++i) {
z[i + 1] += z[i] / 10;
z[i] %= 10;
if (z[z[0] + 1] > 0) {
++z[0];
}
}
}
// 将x*y的结果存入数组z中(大数乘整数)
void mulBIG(int x[], long long y, int z[]) {
z[0] = x[0];
for (int i = 1; i <= z[0]; i++) { // 每位求积
z[i] = x[i] * y;
}
for (int i = 1; i <= z[0]; i++) // 进位处理
{
z[i + 1] += z[i] / 10;
z[i] %= 10;
if (z[z[0] + 1] > 0) {
++z[0];
}
}
}
// 比较x和y，若x代表的大整数较小返回true，否则返回false
bool cmpBIG(int x[], int y[]) {
int lx = x[0], ly = y[0];
if (lx != ly) {
return lx < ly;
}
for (int i = lx; i >= 1; --i) {
if (x[i] != y[i]) {
return x[i] < y[i];
}
}
return false;
}
// 用一行输出a记录的大整数（包括换行符）
void printBIG(int a[]) {
int la = a[0];
for (int i = la; i >= 1; i--) {
cout << a[i];
}
cout << endl;
}
// 将字符串大写小写标准化,字符排序标准化
string standard(string s)
{
for (int i = 0; i <= s.size() - 1; ++i) {
if (s[i] >= 'A' && s[i] <= 'Z') {
s[i] = s[i] - 'A' + 'a';
}
}
sort(s.begin(), s.end());
return s;
}
// 整数除以整数得到x位小数
void mulfan(int a, int b, int x)
{
cout << a / b << '.';
int yu = a % b;
for (int i = 1; i <= x; ++i) {
yu *= 10;
cout << yu / b;
yu %= b;
}
cout << endl;
}
// 判断闰年
bool isLeap(int y) {
if ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0) {
return true;
}
return false;
}
// 快速排序
void quicksort(int a[], int l, int r) {
int x = a[(l + r) / 2];
int i = l, j = r;
if (i >= j)return;
while (i <= j) {
while (a[i] <= x)i++;
while (a[j] >= x)j--;
if (i <= j)swap(a[i], a[j]);
}
quicksort(a, l, j);
quicksort(a, i, r);
}
// 归并排序
void megersort(int a[], int b[], int l, int r) {
if (l >= r)return;
int i, j, k, mid = (l + r) / 2;
megersort(a, b, l, mid);
megersort(a, b, mid + 1, r);
i = l, j = mid + 1, k = l - 1;
while (i <= mid && j <= r) {
k++;//位置右挪一个
if (a[i] < a[j])b[k] = a[i++];
else b[k] = a[j++];
}
while (i <= mid)b[++k] = a[i++];
while (j <= r)b[++k] = a[j++];
for (int q = l; q <= r; q++)a[q] = b[q];
}
// 求x的数字和
int cal(int x)
{
int sum = 0;
while (x > 0) {
sum += x % 10;
x /= 10;
}
return sum;
}
// 判断回文数
bool isPal(int x) {
int w = x;
int rev = 0;
while (x != 0) {
int a = x % 10;
rev = rev * 10 + a;
x /= 10;
}
if (rev == w) {
return true;
}
return false;
}
// 倒序数
int Pal(int x) {
int r = 0;
while (x >= 0) {
r = r * 10 + x % 10;
x /= 10;
}
return r;
}
// 运算符号排序
int pri(char c) {
if (c == '+' || c == '-') {
return 1;
}
else if (c == '*' || c == '/') {
return 2;
}
else if (c == '^') {
return 3;
}
else if (c == '(' || c == ')') {
return 4;
}
else if (c == '[' || c == ']') {
return 4;
}
else if (c == '{' || c == '}') {
return 4;
}
return 0;
}
// 中缀表达式转后缀表达式
string tra(string in) {
stack<string> stn;
stack<char> stc;
stc.push('(');
for (int i = 0; i < (int)in.size(); ++i) {
if (in[i] >= '0' && in[i] <= '9') {
string s("");
s += in[i];
stn.push(s);
}
else {
if (in[i] == '(') {
stc.push(in[i]);
}
else if (in[i] == ')') {
while (stc.top() != '(') {
string b = stn.top();
stn.pop();
string a = stn.top();
stn.pop();
char c = stc.top();
stc.pop();
string s = a + b + c;
stn.push(s);
}
stc.pop();
}
else {
while (pri(in[i]) <= pri(stc.top()) && !(in[i] == '^' && stc.top() == '^')) {
string b = stn.top();
stn.pop();
string a = stn.top();
stn.pop();
char c = stc.top();
stc.pop();
string s = a + b + c;
stn.push(s);
}
stc.push(in[i]);
}
}
}
if (!stc.empty()) {
while (stc.top() != '(') {
string b = stn.top();
stn.pop();
string a = stn.top();
stn.pop();
char c = stc.top();
stc.pop();
string s = a + b + c;
stn.push(s);
}
stc.pop();
}
return stn.top();
}
// 输出栈（需要一个函数外部的需要输出的栈）
stack<int> st;
void printst() {
stack<int> p1;
stack<int> p2;
while (!st.empty()) {
p1.push(st.top());
p2.push(st.top());
st.pop();
}
while (!p1.empty()) {
cout << p1.top() << ' ';
p1.pop();
}
while (!p2.empty()) {
st.push(p2.top());
p2.pop();
}
}
// 拆分字符串中的单词（需要一个数组存储）
string a[10005];
void split(string stc) {
int pos = 0;
for (int i = 0; i < stc.size(); ++i) {
bool isbreak = false;
for (int j = i; j < stc.size(); ++j) {
if (stc[j] != ' ') {
i = j;
break;
}
if (j == stc.size() - 1) {
isbreak = true;
}
}
if (isbreak) {
break;
}
int nextspc = -1;
for (int j = i; j < stc.size(); ++j) {
if (stc[j] == ' ') {
a[++pos] = stc.substr(i, j - i);
for (int k = j; k < stc.size(); ++k) {
if (stc[k] != ' ') {
nextspc = k - 1;
//cout << " >j:" << j << " k:" << k << endl;
break;
}
}
break;
}
if (j == stc.size() - 1) {
a[++pos] = stc.substr(i, j - i + 1);
break;
}
}
if (nextspc == -1) {
break;
}
i = nextspc;
}
return;
}
int main() {
return 0;
}后记
另外，如果遇到有代码做得不对，请私信作者或者在本篇blog下评论 ，感谢反馈！！！
感谢大家支持，如果作者学习到了新的算法，也会更新！
如果您有较好的算法模板，欢迎在本blog下 或 私信 发我！