前面的前面
目录
高精度
排序
进制转换
快速读写
高精度
回到目录
高精度加法
inline string add(string a, string b) {
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
if (a.size() < b.size()) swap(a, b);
int len1 = a.size(), len2 = b.size(), carry = 0;
string ans = "";
for(int i = 0; i < len1; i++) {
int res = a[i] - '0' + carry;
if (len2 > i) res += b[i] - '0';
carry = res / 10;
res %= 10;
ans += res + '0';
}if (carry > 0) ans += carry + '0';
reverse(ans.begin(), ans.end());
return ans;
}
高精度减法
inline string sub(string a, string b) {
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
string ans = "";
if ((a.size() < b.size()) || (a.size() == b.size() && a < b)) {
ans += "-"
swap(a, b);
}int len1 = a.size(), len2 = b.size(), carry = 0;
for(int i = 0; i < len1; i++) {
int res = a[i] - '0' - carry;
if (len2 > i) res -= b[i] - '0';
carry = res < 0;
res = (res + 10) % 10;
ans += res + '0';
}while (!ans.empty() && ans[ans.size() - 1] == '0') ans = ans.substr(0, ans.size() - 1);
reverse(ans.begin(), ans.end());
return ans;
}
高精度乘法
inline string mult(string a, string b) {
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int len1 = a.size(), len2 = b.size();
int len = len1 + len2;
int c[len + 10] = {};
for(int i = 0; i < len1; i++) {
for(int j = 0; j < len2; j++) {
c[i + j] += (a[i] - '0') * (b[j] - '0');
}
}for(int i = 0; i < len - 1; i++) {
c[i + 1] += c[i] / 10;
c[i] %= 10;
}while (c[len] == 0) len --;
string ans = "";
for(int i = len; i >= 0; i--) ans += c[i] + '0';
return ans;
}
高精度阶乘
inline string mult(string a, string b) {
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int len1 = a.size(), len2 = b.size();
int len = len1 + len2;
int c[len + 10] = {};
for(int i = 0; i < len1; i++) {
for(int j = 0; j < len2; j++) {
c[i + j] += (a[i] - '0') * (b[j] - '0');
}
}for(int i = 0; i < len - 1; i++) {
c[i + 1] += c[i] / 10;
c[i] %= 10;
}while (c[len] == 0) len --;
string ans = "";
for(int i = len; i >= 0; i--) ans += c[i] + '0';
return ans;
}// 阶乘的话用这个
inline string fact(int n) {
string ans = "1";
for(int i = 1; i <= n; i++) ans = mult(ans, to_string(i));
return ans;
}
高精度除法（高精度 ÷ 低精度）
inline string divid(string a, int b) {
string ans = "";
int len = a.size(), now = 0;
for(int i = 0; i < len; i++) {
now = now * 10 + a[i] - '0';
ans += now / b + '0';
now %= b;
}len = ans.size();
while (len > 1 && ans[0] == '0') {
ans = ans.substr(1, len - 1);
len --;
}return ans;
}
高精度除法（带余数计算，就是rem全局变量）
int rem = 0;
inline string divid(string a, int b) {
string ans = "";
int len = a.size(), now = 0;
for(int i = 0; i < len; i++) {
now = now * 10 + a[i] - '0';
ans += now / b + '0';
now %= b;
}len = ans.size();
while (len > 1 && ans[0] == '0') {
ans = ans.substr(1, len - 1);
len --;
}rem = now;
return ans;
}
排序
回到目录
选择排序
inline void select_sort(int a[], int n) {
for(int i = 1; i <= n; i++) {
int ith = i;
for(int j = i + 1; j <= n; j++) {
if (a[j] < a[ith]) ith = j;
}swap(a[i], a[ith]);
}
}
插入排序
inline void insert_sort(int a[], int n) {
for(int i = 2; i <= n; i++) {
int key = a[i];
int j = i - 1;
while (j >= 1 && a[j] > key) {
a[j + 1] = a[j];
j --;
}a[j + 1] = key;
}
}
冒泡排序
inline void bubble_sort(int a[], int n) {
for(int i = 1; i < n; i++) {
bool flag = true;
for(int j = 1; j <= n - i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
flag = false;
}
}if (flag) break;
}
}
计数排序
constexpr int maxn = 10000001;
int a[maxn], cnt[maxn];
inline vector<int> count_sort(int a[], int n) {
for(int i = 1; i <= n; i++) {
cnt[a[i]] ++;
}vector<int> ans;
for(int i = 0; i <= maxn; i++) {
while (cnt[i] --) ans.push_back(i);
}return ans;
}
进制转换
回到目录
十进制转n进制
十进制转二进制
inline string dec_to_bin(int n) {
string bin = "";
while (n) {
int remai = n % 2;
bin += to_string(remai);
n /= 2;
}reverse(bin.begin(), bin.end());
return bin;
}
十进制转八进制
inline string dec_to_oct(int n) {
string oct = "";
while (n) {
int remai = n % 8;
oct += to_string(remai);
n /= 8;
}reverse(oct.begin(), oct.end());
return oct;
}
十进制转十六进制
inline string dec_to_hex(int n) {
string hex = "";
const string hexmap = "0123456789ABCDEF";
while (n) {
int remai = n % 16;
hex += hexmap[remai];
n /= 16;
}reverse(hex.begin(), hex.end());
return hex;
}
十进制转n进制
inline string dec_to_base(int n, int base) {
string ans = "";
const string nummap = "0123456789ABCDEF";
while (n) {
int remai = n % base;
ans += nummap[remai];
n /= base;
}reverse(ans.begin(), ans.end());
return ans;
}
n进制转十进制
二进制转十进制
inline int bin_to_dec(int n) {
int dec = 0, base = 1;
while (n) {
int rem = n % 10;
dec += rem * base;
base *= 2;
n /= 10;
}return dec;
}
八进制转十进制
inline int oct_to_dec(int n) {
int dec = 0, base = 1;
while (n) {
int rem = n % 10;
dec += rem * base;
base *= 8;
n /= 10;
}return dec;
}
十六进制转十进制
inline int hex_to_dec(string n) {
int dec = 0, base = 1, len = n.size();
for(int i = len - 1; i >= 0; i--) {
if (isdigit(n[i]))
dec += (n[i] - '0') * base;
else if (n[i] >= 'A' && n[i] <= 'F')
dec += (n[i] - 'A' + 10) * base;
base *= 16;
}return dec;
}
n进制转十进制
inline int base_to_dec(string s, int base) {
int dec = 0, b = 1;
if (base <= 10) {
int n = stoi(s);
while (n) {
int remai = n % 10;
dec += remai * b;
b *= base;
n /= 10;
}
}else {
int len = s.size();
for(int i = len - 1; i >= 0; i--) {
if (isdigit(s[i])) dec += (s[i] - '0') * base;
else dec += (s[i] - 'A' + 10) * b;
b *= base;
}
}return dec;
}
快速读写
回到目录
数字读写
数字快读
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch >'9') {
if (ch == '-') f = -1;
ch = getchar();
}while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
数字快写
inline void write(int x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
字符串读写
字符串快读
inline string readstr() {
string s = "";
char ch;
while ((ch = getchar()) != '\\n') s += ch;
return s;
}
字符串快写
inline void writestr(string s) {
for (int i = 0; i < s.size(); i++) putchar(s[i]);
}
