前面的前面
目录
高精度
排序
进制转换
快速读写
开外
高精度
回到目录
高精度加法
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;
}
高精度乘法
看这里
高精度除法（高精度 ÷ 低精度），返回值为string
inline string divid(string a, int b) {
if (b == 0) return "0";
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;
}
高精度取模
string mod(string num, int b) {
if (b == 0) return "0";
long long res = 0;
for (char c : num) {
int x = c - '0';
res = (res * 10 + x) % b;
}return to_string(res);
}
排序
回到目录
选择排序
inline void SelectSort(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 InsertSort(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 BubbleSort(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> CountSort(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 & 1;
bin += to_string(remai);
n >>= 1;
}reverse(bin.begin(), bin.end());
return bin;
}
十进制转八进制
inline string dec_to_oct(int n) {
string oct = "";
while (n) {
int remai = n & 7;
oct += to_string(remai);
n >>= 3;
}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 & 15;
hex += hexmap[remai];
n >>= 4;
}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;
}
快速读写
回到目录
```cpp
namespace FastIO {
const int BUF_SIZE = 1 << 20;
char inbuf[BUF_SIZE], outbuf[BUF_SIZE];
char *pin = inbuf, *pend = inbuf, *pout = outbuf;
inline char getc() {
if (pin == pend) {
pend = inbuf + fread(inbuf, 1, BUF_SIZE, stdin);
pin = inbuf;
}
return pin == pend ? EOF : *pin++;
}inline void putc(char c) {
if (pout == outbuf + BUF_SIZE) {
fwrite(outbuf, 1, BUF_SIZE, stdout);
pout = outbuf;
}*pout++ = c;
}int readi() {
int x = 0, f = 1;
char ch = getc();
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getc();
}while (isdigit(ch)) {
x = x * 10 + (ch - '0');
ch = getc();
}return x * f;
}string reads() {
string s;
char ch = getc();
while (isspace(ch)) ch = getc();
while (!isspace(ch) && ch != EOF) {
s.push_back(ch);
ch = getc();
}return s;
}void writei(int x) {
if (x < 0) {
putc('-');
x = -x;
}if (x > 9) writei(x / 10);
putc(x % 10 + '0');
}void writes(const string& s) {
for (char c : s) putc(c);
}struct AutoFlush {
~AutoFlush() {
fwrite(outbuf, 1, pout - outbuf, stdout);
}
}auto_flush;
}
自带输入，输出函数，用`fread`和`fwrite`优化，完美利用缓存，让输入更快速，更便捷
# 开外
[回到目录](https://kedaoi.cn/blog/6978/664c9552c48ae7291ac12ced#目录)
## 字符串比较
```cpp
inline bool compare(string a, string b) {
if (a.size() > b.size()) return true;
else if (a.size() < b.size()) return false;
else {
int len = a.size();
for(int i = 0; i < len; i++) {
if (a[i] > b[i]) return true;
else if (a[i] < b[i]) return false;
}
}return true;
}
括号匹配
inline string check(string s) {
stack<char> st;
int size = s.size();
for(int i = 0; i < size; i++) {
if (s[i] == '(' || s[i] == '['') { // 根据情况添加
st.push(s[i]);
}else if (s[i] == ')') {
if (st.size() && st.top() == '(') {
st.pop();
}else {
return "no";
}
}else if (s[i] == ']') {
if (st.size() && st.top() == '[') {
st.pop();
}else {
return "no";
}
}
}if (st.empty()) return "yes";
else return "no";
}
