#include <bits/stdc++.h>
using namespace std;
bool memory_space_start;
// 模板函数 快读
// 1.确保需要读入/输出的是整型(int, long long, __int128)；
// 2.如果数据范围小则最好不要使用快读快写，如果数据范围大则一定要使用快读快写。
template <typename T>
inline T read() {
T 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;
}
// 模板函数 快写
// 1.确保需要读入/输出的是整型(int, long long, __int128)；
// 2.如果数据范围小则最好不要使用快读快写，如果数据范围大则一定要使用快读快写。
template <typename T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
// 已过期的函数
void out_of_date_func() {
// gets()
// strlwr()
// strupr()
// atoi()
// itoa()
}
// 判断 闰年
bool leapyear(int year) {
if (year % 400 == 0 || year % 4 == 0 && year % 100 != 0) {
return true;
} else {
return false;
}
}
// 成绩等级
char grade(int score) {
char grade;
if (score >= 90) {
grade = 'A';
} else if (score >= 80) {
grade = 'B';
} else if (score >= 70) {
grade = 'C';
} else if (score >= 60) {
grade = 'D';
} else {
grade = 'E';
}
return grade;
}
// 判断 素数
bool prime(int n) {
bool isPrime = true;
if (n <= 1) {
isPrime = false;
} else {
int nn = sqrt(n);
for (int i = 2; i <= nn; i++) {
if (n % i == 0) {
isPrime = false;
break;
}
}
}
return isPrime;
}
// 埃氏筛法求区间素数
void prime_zone(int n) {
bool arr[10000 + 1];
memset(arr, true, sizeof(arr));
int nn = sqrt(n);
for (int i = 2; i <= nn; i++) {
if (!arr[i]) {
for (int j = 2; i * j <= n; j++) {
arr[i * j] = false;
}
}
}
for (int i = 2; i <= n; i++) {
if (arr[i]) {
cout << i << " ";
}
}
cout << endl;
}
// 辗转相除法求最大公约数
int gcd (int a, int b) {
if (a < b) {
swap(a, b);
}
int c = a % b;
while (c != 0) {
a = b;
b = c;
c = a % b;
}
return b;
}
// 求最小公倍数
int lcm(int a, int b) {
int ans = 0;
if (a > b) {
swap(a, b);
}
for (int i = 1; i <= a; i++) {
if (b * i % a == 0) {
ans = b * i;
break;
}
}
return ans;
}
// 判断回文数
bool hw_number(int n) {
int nn = n, reverse = 0, num;
do {
num = nn % 10;
reverse = reverse * 10 + num;
nn = nn / 10;
} while (nn > 0);
return (n == reverse);
}
// 判断回文串
bool hw_string(char arr[]) {
bool flag = true;
int len = strlen(arr);
for (int i = 0; i < len / 2; ++i) {
if (arr[i] != arr[len - 1 - i]) {
flag = false;
break;
}
}
return flag;
}
// 分解质因数
void prime_factor(int n) {
cout << n << "=";
for (int i = 2; i <= n / i; i++) { // 注意遍历范围是 2 ~ sqrt(n)
while (n % i == 0 && n != i) { // 最后一个不输出 n / i != 1
cout << i << "*";
n /= i;
}
}
cout << n << endl; // 补充输出剩余部分
}
// 约瑟夫环
void joseph_circle(int n, int m) {
int cnt = 0, check = 0, remain; // 计数器，检查器，剩余人数
bool arr[1000 + 1]; // 用布尔型数组模拟人的编号，标记是否出局
memset(arr, true, sizeof(arr)); // 数组元素 设置为 true;
remain = n; // 初始剩余人数为 总人数
while (remain > 0) { // 循环条件为 剩余人数不为零
cnt++; // 计数器始终进行
if (arr[cnt]) { // 判断当前计数器所在数组元素是否已出局
check++; // 若未出局，则检查器加一
}
if (check == m) { // 当检查器数到报数数时
arr[cnt] = false; // 设置当前编号(数组元素)出局
cout << cnt << " "; // 输出当前数组元素的索引
check = 0; // 检查器置零
remain--; // 剩余人数减一
}
if (cnt == n) { // 当计数器运行到末尾时
cnt = 0; // 计数器置零，实现转圈效果
}
}
cout << endl;
}
// 同余方程
// (a + b) mod c = (a mod c + b mod c) mod c
// (a * b) mod c = ((a mod c) * (b mod c)) mod c
// (a * a) mod c = ((a mod c) * (a mod c)) mod c
// 同余方程求阶乘之和
long long fac_sum(int n) {
long long sum = 0, num = 1; // 阶乘和 、阶乘值
for (int i = 1; i <= n; i++) { // 优化算法（一重循环）
num = num * i % 1000000; // 阶乘不重置 1，继续累乘
sum = (sum + num) % 1000000; // 累加阶乘和 取模
}
return sum;
}
// 进制转换
void number_system_func() {
/*
// itoa 和 atoi 是 非标准 库函数，比赛中不可使用！！！
// 整数 转 字符数组 (int 范围 有效)
int n = 1234;
itoa(n, arr, 10); // 转换为 十进制 数字 字符数组
cout << arr << endl;
itoa(n, arr, 2); // 转换为 二进制 数字 字符数组
cout << arr << endl;
itoa(n, arr, 8); // 转换为 八进制 数字 字符数组
cout << arr << endl;
itoa(n, arr, 16); // 转换为 十六进制 数字 字符数组
cout << arr << endl;
// 字符数组 转 整数 (int 范围 有效)
strcpy(arr, "5678");
cout << atoi(arr) << endl;
cout << atoi(arr) + atoi(arr) << endl;
// 字符数组 转 浮点数 (float 范围 有效)
strcpy(arr, "123.45");
cout << atof(arr) << endl;
cout << atof(arr) + atof(arr) << endl;
*/
// 以下 数值转换 的方法可以正常使用
// 用 二进制、八进制、十六进制 给变量赋值
int num = 0b10100; // 二进制 赋值
cout << num << endl;
num = 024; // 八进制 赋值
cout << num << endl;
num = 0x14; // 十六进制 赋值
cout << num << endl;
int n = 20;
char arr[1000 + 1];
memset(arr, 0, sizeof(arr));
string str;
// 整数 转换 二进制 字符串 （方法一）
int nn = n, i = 0;
while (nn > 0) {
arr[i++] = nn % 2 + '0';
nn = nn / 2;
}
reverse(arr, arr + strlen(arr));
cout << arr << endl;
// 整数 转换 二进制 字符串 （方法二）
str = bitset<sizeof(n) * 8>(n).to_string();
cout << str << endl;
// 整数 转换 八进制 字符串
sprintf(arr, "%o", n);
cout << arr << endl;
// 整数 转换 十六进制 字符串
sprintf(arr, "%x", n);
cout << arr << endl;
// 整数 或 浮点数 转换成 字符串
int n5 = 1234567890;
str = to_string(n5);
cout << str << endl;
long long ll5 = 123456789012345678;
str = to_string(ll5);
cout << str << endl;
double f5 = 1234567890.12345;
str = to_string(f5);
cout << str << endl;
// 从 字符串 转换成 整型和浮点型 （包括 十进制，八进制，十六进制）
str = "123456789";
cout << stoi(str) << endl;
cout << stoi(str, 0, 10) << endl; // 十进制 字符 转换 十进制 整数
str = "10";
cout << stoi(str, 0, 8) << endl; // 八进制 字符 转换 十进制 整数
str = "10";
cout << stoi(str, 0, 16) << endl; // 十六进制 字符 转换 十进制 整数
str = "123456789012345678";
cout << stoll(str) << endl;
cout << stoll(str, 0, 10) << endl;
str = "1234567890.12345";
cout << fixed << setprecision(10) << stod(str) << endl;
str = "1234567890.123456789";
cout << fixed << setprecision(10) << stold(str) << endl;
cout << fixed << setprecision(0) << endl;
}
// 数学 常用函数
void math_func() {
int n = -3;
cout << abs(n) << endl; // 整数取绝对值
double f = -3.3;
cout << fabs(f) << endl; // 浮点数取绝对值
double f1 = 1.23;
cout << ceil(f1) << endl; // 向上取整
double f2 = 1.98;
cout << floor(f2) << endl; // 向下取整
double f3 = 1.45;
cout << round(f3) << endl; // 四舍五入
int n1 = 2, m1 = 4;
cout << pow(n1, m1) << endl; // 乘方
int n2 = 16, m2 = 2;
cout << pow(n2, 1.0 / m2) << endl; // 开方
cout << sqrt(n2) << endl; // 平方根
cout << cbrt(n2) << endl; // 立方根
int x1 = 10, y1 = 3;
cout << max(x1, y1) << endl; // 最大值 (泛型)
cout << min(x1, y1) << endl; // 最小值 (泛型)
div_t result = div(x1, y1); // 整数除法运算 (10 / 3)
cout << result.quot << endl; // 返回 商 (3)
cout << result.rem << endl; // 返回 余数 (1)
double f4 = 1.2345;
cout << fixed << setprecision(2) << f4 << endl; // 保留小数位数
}
// 字符 常用函数
void char_func() {
char c1, c2;
// 普通 输入输出
cin >> c1;
cout << c1 << endl;
// 函数 输入输出
c2 = getchar();
putchar(c2);
putchar('\n');
// 判断 c 是否是数字字符，返回 0 或 1 代表 false 或 true
cout << isdigit(c1) << endl;
// 判断 c 是否是一个字母，返回 0 或 1 代表 false 或 true
cout << isalpha(c2) << endl;
// 判断 c 是否是一个数字或字母，返回 0 或 1 代表 false 或 true
cout << isalnum(c2) << endl;
// 判断 c 是否是一个小写字母，返回 0 或 1 代表 false 或 true
cout << islower(c2) << endl;
// 判断 c 是否是一个大写字母，返回 0 或 1 代表 false 或 true
cout << isupper(c2) << endl;
// 如果 c 是一个大写字母，则返回其 小写字母 ASCII 码值
cout << char(tolower(c2)) << endl;
// 如果 c 是一个小写字母，则返回其 大写字母 ASCII 码值
cout << char(toupper(c2)) << endl;
}
// 字符数组 常用函数
// 参考资料：https://www.runoob.com/cprogramming/c-strings.html
// 参考资料：https://www.runoob.com/cprogramming/c-standard-library-string-h.html
void char_array_func() {
// 普通读取 (不包括 行末换行符)
char arr1[1000 + 1];
memset(arr1, 0, sizeof(arr1));
cin >> arr1;
cout << arr1 << endl;
// 读取 行末换行符 (ASCII 10)
int c = getchar();
cout << c << endl;
// 整行读取 (包括 行末换行符)
char arr2[1000 + 1];
memset(arr2, 0, sizeof(arr2));
cin.getline(arr2, sizeof(arr2));
cout << arr2 << endl;
// 连续读取
char arr3[1000 + 1];
memset(arr3, 0, sizeof(arr3));
int cnt = 0;
while (cin >> arr3) {
cout << arr3 << endl;
if (++cnt >= 3) {
break;
}
}
// 返回字符数组有效长度 (非空字符 '\0')
cout << strlen(arr2) << endl;
// 比较字符数组
cout << strcmp(arr1, arr3) << endl;
// 连接两个字符数组
strcat(arr1, arr3);
cout << arr1 << endl;
// 复制字符数组
strcpy(arr1, arr3);
cout << arr1 << endl;
strcpy(arr1, "aBcD");
cout << arr1 << endl;
// gets(), strupr() 和 strlwr() 在比赛中已不可用
/*
// 转换字符数组为大写
cout << strupr(arr1) << endl;
// 转换字符数组为小写
cout << strlwr(arr1) << endl;
*/
// 在参数 str 所指向的字符串中搜索第一次出现字符 c（一个无符号字符）的位置。
// strchr(str, c)
strcpy(arr1, "aBcDeF");
char c1 = 'e';
char * ptr1 = strchr(arr1, c1);
cout << ptr1 << endl;
// 在字符串 str1 中查找第一次出现字符串 str2（不包含空结束字符）的位置。
// strstr(str1, str2)
strcpy(arr2, "DeF");
char * ptr2 = strstr(arr1, arr2);
cout << ptr2 << endl;
// 分解字符串 str 为一组字符串，delim 为分隔符。
// strtok(str, delim)
strcpy(arr1, "abc,def,ghi");
strcpy(arr2, ",");
char * arrarr[100 + 1][1000 + 1];
memset(arrarr, 0, sizeof(arrarr));
char * ptr3 = strtok(arr1, arr2);
while (ptr3 != NULL) {
cout << ptr3 << endl;
ptr3 = strtok(NULL, arr2);
}
}
// 字符串类 常用函数
// 官方资料：https://zh.cppreference.com/w/cpp/string/basic_string
void string_func() {
string str1, str2, str3;
int pos, len; // 位置，长度
// 普通读取
cin >> str1;
cout << str1 << endl;
// 读取 行末换行符 (ASCII 10)
int c = getchar();
cout << c << endl;
// 整行读取
getline(cin, str2);
cout << str2 << endl;
// 连续读取
int cnt = 0;
while (cin >> str3) {
cout << str3 << endl;
if (++cnt >= 3) {
break;
}
}
// 字符数组 转换 字符串
char arr[100 + 1] = "abcXYZabc";
string str(arr);
cout << str << endl;
// 字符串 转换 字符数组
str = "abcdef";
strcpy(arr, str.c_str());
cout << arr << endl;
// 判断 字符串 是否为空
cout << str2.empty() << endl;
// 返回 字符串 有效长度 (非空字符 '\0')
cout << str2.size() << endl;
cout << str2.length() << endl;
cout << strlen(str2.c_str()) << endl;
// 比较 字符串
cout << (str1 == str3) << endl;
cout << str1.compare(str3) << endl;
// 连接 两个 字符串
cout << str1 + " " + str3 << endl;
str1.append(str3);
cout << str1 << endl;
// 复制 字符串
str1 = str3;
cout << str1 << endl;
// 插入 符串 insert
str1 = "abcdef";
str2 = "xyz";
pos = 3;
str1.insert(pos, str2);
cout << str1 << endl;
// 查找 字符串 find, rfind,
// find_first_of, find_first_not_of, find_last_of, find_last_not_of
str1 = "AAAxyzBBBxyzCCC";
str2 = "xyz";
pos = str1.find(str2); // 从左向右查找
cout << pos << endl;
pos = str1.rfind(str2); // 从右向左查找
cout << pos << endl;
str1 = "AAA";
str2 = "xyz";
if (str1.find(str2) == string::npos) {
cout << "Not Found" << endl;
}
// 替换 字符串 replace
str1 = "AAABBBCCC";
str2 = "xyz";
pos = 3;
len = 3;
cout << str1.replace(pos, len, str2) << endl;
// 截取 字符串 substr
str1 = "AAAxyzBBB";
pos = 3;
len = 3;
cout << str1.substr(pos, len) << endl;
// 删除 字符串 erase
str1 = "AAAxyzBBB";
pos = 3;
len = 3;
cout << str1.erase(pos, len) << endl;
// 清除 字符串 clear
str1 = "AAAxyzBBB";
str1.clear();
cout << str1 << endl;
// to_string 换整数或浮点值 为 字符串
long long n1 = 1.2e18;
cout << to_string(n1) << endl;
double f1 = 123.456789;
cout << to_string(f1) << endl;
// 字符串 转 整数 (int 范围 有效)
str1 = "1200";
cout << stoi(str1) << endl;
cout << stoi(str1) + stoi(str1) << endl;
// 字符串 转 浮点数 (float 范围 有效)
str1 = "123.45";
cout << stof(str1) << endl;
cout << stof(str1) + stof(str1) << endl;
}
// 正则表达式 常用函数
// 参考资料：https://zh.cppreference.com/w/cpp/regex
// 参考资料：http://112.253.31.18:8372/dt/srv003/blog/3/2022-10-19/refer03.html
// 符号 意义
// ^ 匹配行的开头
// $ 匹配行的结尾
// . 匹配任意单个字符
// […] 匹配[]中的任意一个字符
// (…) 设定分组
// \ 转义字符
// \d 匹配数字[0-9]
// \D \d 的 取反
// \w 匹配字母[a-z]，数字，下划线
// \W \w 的 取反
// \s 匹配空格
// \S \s 的 取反
// + 前面的元素重复1次或多次
// * 前面的元素重复任意次
// ? 前面的元素重复0次或1次
// {n} 前面的元素重复n次
// {n,} 前面的元素重复至少n次
// {n,m} 前面的元素重复至少n次，至多m次
// | 逻辑或
void regex_func() {
// regex_match (C++11) 尝试匹配一个正则表达式到整个字符序列 (函数模板)
regex r1("(\\w+\\s\\d+)");
string s1 = "abc 123";
if (regex_match(s1, r1)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
// regex_search (C++11) 尝试匹配一个正则表达式到字符序列的任何部分 (函数模板)
regex r2("(\\d+)");
string s2 = "abc 123 ABC";
if (regex_search(s2, r2)) {
cout << "Found" << endl;
} else {
cout << "Not Found" << endl;
}
// regex_replace (C++11) 以格式化的替换文本来替换正则表达式匹配的出现位置 (函数模板)
regex r3("(\\d+)");
string s3 = "abc 123 ABC";
string result = regex_replace(s3, r3, "KKK");
cout << result << endl;
}
// STL 容器库 ：https://zh.cppreference.com/w/cpp/container
// 顺序容器
// array 固定长度的连续数组
// 官方资料：https://zh.cppreference.com/w/cpp/container/array
void array_func() {
array<int, 5> arr1 = {1, 3, 2, 5, 4};
sort(arr1.begin(), arr1.end()); // 数组 排序
for (auto i : arr1) {
cout << i << ' ';
}
cout << endl;
array<int, 5> arr2 = arr1; // 数组 复制
reverse(arr2.begin(), arr2.end()); // 数组 反转
for (auto i : arr2) {
cout << i << ' ';
}
cout << endl;
cout << arr1.empty() << endl; // 判断 数组 是否 为空
cout << arr1.size() << endl; // 返回 数组 的 长度
cout << arr1[3] << endl; // 获得 数组 指定 位置 的元素
cout << arr1.at(3) << endl; // 获得 数组 指定 位置 的元素
cout << get<3>(arr1) << endl; // 获得 数组 指定 位置 的元素
}
// vector 变化长度的连续数组
// 官方资料：https://zh.cppreference.com/w/cpp/container/vector
void vector_func() {
vector<int> vec1;
vec1.push_back(20); // 添加元素到向量的末尾
vec1.push_back(50);
vec1.push_back(10);
vec1.push_back(60);
vec1.push_back(40);
vec1.push_back(30);
sort(vec1.begin(), vec1.end()); // 向量 排序
vec1.pop_back(); // 移除向量末尾的元素
for (auto i : vec1) {
cout << i << ' ';
}
cout << endl;
cout << vec1.empty() << endl; // 判断 向量 是否为空
cout << vec1.size() << endl; // 返回 向量 的长度
cout << vec1.front() << endl; // 获得 向量 头部位置的元素
cout << vec1.back() << endl; // 获得 向量 尾部位置的元素
cout << vec1[3] << endl; // 获得 向量 指定位置的元素
cout << vec1.at(3) << endl; // 获得 向量 指定位置的元素
vector<int> vec2 = vec1; // 向量 复制
reverse(vec2.begin(), vec2.end()); // 向量 反转
for (auto i : vec2) {
cout << i << ' ';
}
cout << endl;
// 插入多个元素到指定位置 (注意要用迭代器)
vec2.insert(vec2.begin() + 3, {70, 80, 90});
for (auto i : vec2) {
cout << i << ' ';
}
cout << endl;
// 删除指定起始和终止位置的元素 (注意右端是开区间)
vec2.erase(vec2.begin() + 3, vec2.begin() + 5 + 1);
for (auto i : vec2) {
cout << i << ' ';
}
cout << endl;
vec2.clear(); // 清空向量
}
// deque 双端队列
// 官方资料：https://zh.cppreference.com/w/cpp/container/deque
void deque_func() {
deque<int> dq1 = {3, 2, 1, 5, 4};
dq1.push_front(7); // 添加 元素 至 双端队列 的 开头
dq1.push_back(6); // 添加 元素 至 双端队列 的 末尾
sort(dq1.begin(), dq1.end()); // 双端队列 排序
dq1.pop_front(); // 移除 双端队列 开头的元素
dq1.pop_back(); // 移除 双端队列 末尾的元素
for (auto i : dq1) {
cout << i << ' ';
}
cout << endl;
cout << dq1.empty() << endl; // 判断 双端队列 是否为空
cout << dq1.size() << endl; // 返回 双端队列 的长度
cout << dq1.front() << endl; // 获得 双端队列 头部位置的元素
cout << dq1.back() << endl; // 获得 双端队列 尾部位置的元素
cout << dq1[3] << endl; // 获得 双端队列 指定位置的元素
cout << dq1.at(3) << endl; // 获得 双端队列 指定位置的元素
deque<int> dq2 = dq1; // 双端队列 复制
reverse(dq2.begin(), dq2.end()); // 双端队列 反转
for (auto i : dq2) {
cout << i << ' ';
}
cout << endl;
// 插入多个元素到指定位置 (注意要用迭代器)
dq2.insert(dq2.begin() + 3, {70, 80, 90});
for (auto i : dq2) {
cout << i << ' ';
}
cout << endl;
// 删除指定起始和终止位置的元素 (注意右端是开区间)
dq2.erase(dq2.begin() + 3, dq2.begin() + 5 + 1);
for (auto i : dq2) {
cout << i << ' ';
}
cout << endl;
dq2.clear(); // 清空 双端队列
}
// forward_list 单链表：https://zh.cppreference.com/w/cpp/container/forward_list
// list 双链表：https://zh.cppreference.com/w/cpp/container/forward_list
// 容器适配器
// stack 栈
// 官方资料：https://zh.cppreference.com/w/cpp/container/stack
void stack_func() {
stack<int> sta1;
sta1.push(10); // 压入 栈顶
sta1.push(20);
sta1.push(30);
cout << sta1.top() << endl; // 返回 栈顶
sta1.pop(); // 弹出 栈顶
cout << sta1.top() << endl;
cout << sta1.empty() << endl; // 判断 栈 是否为空
cout << sta1.size() << endl; // 返回 栈 的长度
stack<int> sta2 = sta1; // 栈 复制
cout << sta2.top() << endl;
}
// queue 队列
// 官方资料：https://zh.cppreference.com/w/cpp/container/queue
void queue_func() {
queue<int> que1;
que1.push(10); // 压入 队尾
que1.push(20);
que1.push(30);
cout << que1.front() << endl; // 返回 队头
cout << que1.back() << endl; // 返回 队尾
que1.pop(); // 弹出 队头 (10)
cout << que1.front() << endl;
cout << que1.back() << endl;
cout << que1.empty() << endl; // 判断 队列 是否为空
cout << que1.size() << endl; // 返回 队列 的长度
queue<int> que2 = que1; // 队列 复制
cout << que2.front() << endl;
cout << que2.back() << endl;
}
// priority_queue 优先队列
// 官方资料：https://zh.cppreference.com/w/cpp/container/priority_queue
void priority_queue_func() {
priority_queue<int> pq1; // 默认 大根堆 (最大值在队顶)
pq1.push(10); // 压入 优先队尾
pq1.push(30);
pq1.push(20);
cout << pq1.top() << endl; // 返回 优先队顶
pq1.pop(); // 弹出 优先队顶 (30)
cout << pq1.top() << endl;
cout << pq1.empty() << endl; // 判断 优先队列 是否为空
cout << pq1.size() << endl; // 返回 优先队列 的长度
priority_queue<int, vector<int>, greater<int> > pq2; // 小根堆 优先队列 (最小值在队顶)
pq2.push(10); // 压入 优先队尾
pq2.push(30);
pq2.push(20);
cout << pq2.top() << endl; // 返回 优先队头
// 转移 数组元素 到 优先队列
int arr[10 + 1] = {1, 3, 5, 4, 2} ;
priority_queue<int> pq3;
for (auto i : arr) {
pq3.push(i);
}
cout << pq3.top() << endl;
}
// 关联容器
// set 唯一集合 (元素不重复，自动升序排列)
// 官方资料：https://zh.cppreference.com/w/cpp/container/set
// 参考资料：https://blog.csdn.net/weixin_52115456/article/details/124210086
void set_func() {
set<int> st1;
st1.insert(1); // 添加 集合 元素
st1.insert(3);
st1.insert(2);
st1.insert(5);
st1.insert(4);
st1.insert(5); // 重复的元素，自动合并
// 遍历 集合 ，注意 集合 会将元素自动排序 (升序)
for (auto i : st1) {
cout << i << ' ';
}
cout << endl;
cout << st1.empty() << endl; // 判断 集合 是否为空
cout << st1.size() << endl; // 返回 集合 元素个数
cout << st1.count(3) << endl; // 判断 集合 中 是否含有 指定元素
st1.erase(3); // 删除 集合 中 指定元素
cout << st1.count(3) << endl; // (0)
set<int>::iterator it; // 创建 集合 迭代器
it = st1.find(4); // 查找 集合 (返回迭代器)
cout << *it << endl;
// lower_bound() 返回指向大于（或等于）某值的第一个元素的迭代器
it = st1.lower_bound(4);
cout << *it << endl; // (4)
// upper_bound() 返回大于某个值元素的迭代器
it = st1.upper_bound(4);
cout << *it << endl; // (5)
set<int> st2 = st1; // 复制 集合
for (auto it = st2.begin(); it != st2.end(); it++) {
cout << *it << ' '; // 使用 迭代器 遍历
}
cout << endl;
st2.clear(); // 清空 集合
}
// pair 对组
// 官方资料：https://zh.cppreference.com/w/cpp/utility/pair
// 参考资料：https://blog.csdn.net/sevenjoin/article/details/81937695
void pair_func() {
// 赋值方式一
pair<string, string> pi1("James", "Bond");
pair<string, int> pi2("Alan", 18);
pair<string, int> pi3(pi2);
pair<string, int> pi4 = pi3;
pair<string, vector<int> > pi5;
cout << pi2.first << " " << pi2.second << endl;
// 赋值方式二
pi2.first = "Pony";
pi2.second = 28;
cout << pi2.first << " " << pi2.second << endl;
// 赋值方式三
pi2 = make_pair("Tony", 38);
cout << pi2.first << " " << pi2.second << endl;
// 通过 tie 函数 获取 pair 元素值
string name;
int age;
tie(name, age) = pi4;
cout << name << " " << age << endl;
}
// map 唯一映射 (元素不重复，自动升序排列)
// 官方资料：https://zh.cppreference.com/w/cpp/container/map
void map_func() {
map<string, int> mp1;
mp1["Alan"] = 18;
mp1["Pony"] = 28;
pair<string, int> pi("Tony", 38);
mp1.insert(pi);
mp1["Mike"] = 48;
mp1["John"] = 58;
mp1["Alan"] = 18;
// 遍历 映射 ，遍历元素类型 为 pair 对组，
// 注意 映射 会将 元素 按照 Key 的字典序自动排序 (升序)
for (auto pi : mp1) {
cout << pi.first << ' ' << pi.second << endl;
}
cout << mp1.empty() << endl; // 判断 映射 是否为空
cout << mp1.size() << endl; // 返回 映射 元素个数
cout << mp1.count("Pony") << endl; // 判断 映射 中 是否含有 指定元素
mp1.erase("Pony"); // 删除 映射 中 指定键值元素
cout << mp1.count("Pony") << endl; // (0)
map<string, int>::iterator it; // 创建 映射 迭代器
it = mp1.find("Tony"); // 查找 映射 (返回迭代器)
cout << it->first << " " << it->second << endl;
for (auto it = mp1.begin(); it != mp1.end(); it++) {
cout << it->first << " " << it->second << endl; // 使用 迭代器 遍历
}
cout << mp1.size() << endl; // 返回 映射 元素个数
// lower_bound() 返回指向首个不小于给定键的元素的迭代器
it = mp1.lower_bound("John");
cout << it->first << " " << it->second << endl; // (John)
// upper_bound() 返回指向首个大于给定键的元素的迭代器
it = mp1.upper_bound("John");
cout << it->first << " " << it->second << endl; // (Mike)
mp1.clear(); // 清空 映射
}
// multiset 多重集合 (元素可重复，自动升序排列)：https://zh.cppreference.com/w/cpp/container/multiset
// multimap 多重映射 (元素可重复，自动升序排列)：https://zh.cppreference.com/w/cpp/container/multimap
// 无序关联容器
// unordered_set 无序唯一集合：https://zh.cppreference.com/w/cpp/container/unordered_set
// unordered_map 无序唯一映射：https://zh.cppreference.com/w/cpp/container/unordered_map
// unordered_multiset 无序多重集合：https://zh.cppreference.com/w/cpp/container/unordered_multiset
// unordered_multimap 无序多重映射：https://zh.cppreference.com/w/cpp/container/unordered_multimap
int arr[1000000 + 1];
bool memory_space_end;
int main() {
auto start = chrono::steady_clock::now();
freopen("template.in", "r", stdin);
freopen("template.out", "w", stdout);
cout << "Memory Cost: " << abs(&memory_space_start - &memory_space_end) / 1024. / 1024. << "MB" << endl;
// 测试 模板函数 __int128 类型 （-3.4e38 ~ 3.4e38）
__int128 a2= read<__int128>();
__int128 b2 = read<__int128>();
write<__int128>(a2 + b2);
cout << endl;
// 测试 模板函数 long long 类型 （-9.2e18 ~ 9.2e18）
long long a3 = read<long long>();
long long b3 = read<long long>();
write<long long>(a3 + b3);
cout << endl;
// 测试 模板函数 int 类型 （-2.1e9 ~ 2.1e9）
int a4 = read<int>();
int b4 = read<int>();
write<int>(a4 + b4);
cout << endl;
// 已过期的函数
out_of_date_func();
// 判断 闰年
int year = 1900;
cout << leapyear(year) << endl;
// 成绩等级
int score = 79;
cout << grade(score) << endl;
// 判断 素数
int n1 = 13;
cout << prime(n1) << endl;
// 求 区间素数(埃氏筛法)
int n2 = 100;
prime_zone(n2);
// 求 最大公约数(辗转相除法)
int a5 = 1500, b5 = 1200;
cout << gcd(a5, b5) << endl;
// 求 最小公倍数
int a6 = 15, b6 = 12;
cout << lcm(a6, b6) << endl;
// 判断 回文数
int n3 = 12321;
cout << hw_number(n3) << endl;
// 判断 回文串
char arr[100 + 1] = "abccba";
cout << hw_string(arr) << endl;
// 分解 质因数
int n4 = 60;
prime_factor(n4);
// 约瑟夫环
int n5 = 41, m5 = 3;
joseph_circle(n5, m5);
// 求 阶乘之和
int n6 = 10;
cout << fac_sum(n6) << endl;
// 进制转换
cout << "--- number_system_func() ---" << endl;
number_system_func();
// 数学 常用函数
cout << "--- math_func() ---" << endl;
math_func();
// 字符 常用函数
cout << "--- char_func() ---" << endl;
char_func();
// 字符数组 常用函数
cout << "--- char_array_func() ---" << endl;
char_array_func();
// 字符串类 常用函数
cout << "--- string_func() ---" << endl;
string_func();
// 正则表达式 常用函数
cout << "--- regex_func() ---" << endl;
regex_func();
// array 固定长度的连续数组 (定长数组)
cout << "--- array_func ---" << endl;
array_func();
// vector 变化长度的连续数组 (变长数组)
cout << "--- vector_func ---" << endl;
vector_func();
// deque 双端队列
cout << "--- deque_func ---" << endl;
deque_func();
// stack 栈
cout << "--- stack_func ---" << endl;
stack_func();
// queue 队列
cout << "--- queue_func ---" << endl;
queue_func();
// priority_queue 优先队列
cout << "--- priority_queue_func ---" << endl;
priority_queue_func();
// set 唯一集合
cout << "--- set_func ---" << endl;
set_func();
// pair 对组
cout << "--- pair_func ---" << endl;
pair_func();
// map 唯一映射
cout << "--- map_func ---" << endl;
map_func();
// 时间估算程序
long long sum = 0;
for (int i = 1; i <= 400000000; ++i) {
sum += i;
}
auto end = chrono::steady_clock::now();
chrono::duration<double> elapsed_seconds = chrono::duration<double>(end - start);
cout << "Elapsed Time: " << elapsed_seconds.count() << "s\n";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
//判断质数
bool prime(int n){
if (n < 2) return false;
for (int i = 2; i < sqrt(n); i++){
if (n % i == 0) return false;
}
return true;
}
//最大公因数 （辗转相除法）
int gcd(int n, int m){
if (m < n) {
swap(n, m); //交换函数
}
int k = m % n;
while (k > 0) {
m = n;
n = k;
k = m % n;
}
return n;
}
// 求最小公倍数
int lcm(int a, int b) {
int ans = 0;
if (a > b) {
swap(a, b);
}
for (int i = 1; i <= a; i++) {
if (b * i % a == 0) {
ans = b * i;
break;
}
}
return ans;
}
int main(){
//判断质数
int n1;
cin >> n1;
prime(n1) ? cout << "ture" : cout << "false";
/*
三目运算符
格式为：表达式1 ? 表达式2 : 表达式3
具体效果为：如果 表达式1 成立，则执行 表达式2 ，否则执行 表达式3
*/
//最大公因数
int n2, m2;
cin >> n2 >> m2;
cout << gcd(n2, m2);
//最小公倍数
int n3, m3;
cin >> n3 >> m3;
cout << lcm(n3, m3);
return 0;
}
彭思哲 (pengsizhe) LV 6 @ 2023-8-21 11:31:20