一 基础算法上1.模拟1.1多项式输出#include iostream #include cmath using namespace std; int main() { int n; cin n; // 循环次数从最高次n遍历到0次 for(int i n; i 0; i--) { int a; cin a; if(a 0) continue; // 处理系数为 0 的情况 // 1. 符号 if(a 0) cout -; else { if(i ! n) cout ; } // 2. 数字 a abs(a); if(a ! 1 || (a 1 i 0)) //末项1*x^01 cout a; // 3. 次数 if(i 0) continue; else if(i 1) cout x; else cout x^ i; } return 0; }1.2蛇形方阵因为这个题目它是从左上角开始的 所以需要在左上角为0,0#include iostream #include cstdio using namespace std; const int N 15; // 定义 右下左上 四个方向 int dx[] {0, 1, 0, -1}; int dy[] {1, 0, -1, 0}; int arr[N][N]; int main() { int n; cin n; // 模拟填数过程 int x 1, y 1; // 初始位置 int cnt 1; // 当前位置要填的数 int pos 0; // 当前的方向 while(cnt n * n) { arr[x][y] cnt; // 计算下一个位置 int a x dx[pos], b y dy[pos]; // 判断是否越界或者已经填过数字 if(a 1 || a n || b 1 || b n || arr[a][b]) { // 换方向 pos (pos 1) % 4; //进行循环 当pos为3的时候会0 a x dx[pos], b y dy[pos]; } x a, y b; cnt; } // 打印矩阵 for(int i 1; i n; i) { for(int j 1; j n; j) { printf(%3d, arr[i][j]); } puts(); } return 0; }1.3字符串的展开#include iostream #include algorithm #include string using namespace std; int p1, p2, p3, n; string s; string ret; // 判断是否是数字字符 bool isdig(char ch) { return ch 0 ch 9; } // 判断是否是小写字母 bool islet(char ch) { return ch a ch z; } // 把 [left, right] 之间的字符展开 // left, right 这两个字符是不做处理 void add(char left, char right) { string t; // 遍历中间的字符 for(char ch left 1; ch right; ch) //left和right不做展示 { char tmp ch; // 处理 p1 if(p1 2 islet(tmp)) tmp - 32; // 小写变大写 else if(p1 3) tmp *; // 变成星号 // 处理 p2 for(int i 0; i p2; i) { t tmp; } } // 处理 p3 if(p3 2) reverse(t.begin(), t.end()); ret t; } int main() { cin p1 p2 p3 s; n s.size(); for(int i 0; i n; i) { char ch s[i]; if(s[i] ! - || i 0 || i n - 1)//减号在开头或者末尾 ret ch; else { char left s[i - 1], right s[i 1]; // 判断是否展开 if( (isdig(left) isdig(right) right left) || (islet(left) islet(right) right left) ) { // 展开 add(left, right); } else { ret ch; } } } cout ret endl; return 0; }2. 高精度2.1 高精度加法因为计算的时候是先进行计算个位 所以需要进行逆序 逆序的话就先从个位进行的加法#include iostream #include string #include algorithm using namespace std; const int N 1e6 10; int a[N], b[N], c[N]; int la, lb, lc; // 高精度加法模板 - c a b; void add(int c[], int a[], int b[]) { for(int i 0; i lc; i) { c[i] a[i] b[i]; // 对应位相加 c[i 1] c[i] / 10; // 进位 c[i] % 10; // 本位留余数 } if(c[lc]) lc; // 最高位还有进位长度1 } int main() { string x, y; cin x y; // 1.拆分每一位逆序存入数组低位存在下标0 la x.size(); lb y.size(); lc max(la, lb); for(int i 0; i la; i) a[la - 1 - i] x[i] - 0; for(int i 0; i lb; i) b[lb - 1 - i] y[i] - 0; // 2.模拟加法 add(c, a, b); // 倒序输出 for(int i lc - 1; i 0; i--) cout c[i]; return 0; }2.2高精度减法字符串比的是第一个数字 19#include iostream #include string #include algorithm using namespace std; const int N 1e6 10; int a[N], b[N], c[N]; int la, lb, lc; // 比较大小如果x y 返回true bool cmp(string x, string y) { // 先比较长度 if(x.size() ! y.size()) return x.size() y.size(); // 再按照字典序的方式比较 return x y; } // 高精度减法模板 - c a - b保证 a b void sub(int c[], int a[], int b[]) { for(int i 0; i lc; i) { c[i] a[i] - b[i]; // 对应位相减然后处理借位 if(c[i] 0) { c[i 1] - 1; // 借位 c[i] 10; } } // 处理前导零 while(lc 1 c[lc - 1] 0) lc--; } int main() { string x, y; cin x y; // 比较大小如果xy交换输出负号 让大数减去小数 if(cmp(x, y)) { swap(x, y); cout -; } // 1. 拆分每一位然后逆序放在数组中 la x.size(); lb y.size(); lc max(la, lb); for(int i 0; i la; i) a[la - i - 1] x[i] - 0; for(int i 0; i lb; i) b[lb - i - 1] y[i] - 0; // 2. 模拟减法的过程 sub(c, a, b); // c a - b // 输出结果 for(int i lc - 1; i 0; i--) cout c[i]; return 0; }swap是交换函数作用把两个变量的值互相交换。2.3高精度乘法#include iostream #include string using namespace std; const int N 1e6 10; int a[N], b[N], c[N]; int la, lb, lc; // 高精度乘法模版c a * b void mul(int c[], int a[], int b[]) { // 无进位相乘累加 for(int i 0; i la; i) { for(int j 0; j lb; j) { c[i j] a[i] * b[j]; } } // 统一处理进位 for(int i 0; i lc; i) { c[i 1] c[i] / 10; c[i] % 10; } // 去除前导零 while(lc 1 c[lc - 1] 0) lc--; } int main() { string x, y; cin x y; la x.size(); lb y.size(); lc la lb; // 逆序存入数组低位存在下标0 for(int i 0; i la; i) a[la - 1 - i] x[i] - 0; for(int i 0; i lb; i) b[lb - 1 - i] y[i] - 0; mul(c, a, b); // 逆序输出 for(int i lc - 1; i 0; i--) cout c[i]; return 0; }2.4高精度除以低精度#include iostream #include string using namespace std; const int N 1e6 10; typedef long long LL; int a[N], b, c[N]; int la, lc; LL div(int c[], int a[], int b) { LL t 0; for(int i la - 1; i 0; i--) //除法是从最高位进行的 { t t * 10 a[i]; c[i] t / b; t % b; } while(lc 1 c[lc - 1] 0) lc--; return t; // 返回余数 } int main() { string x; cin x b; la x.size(); for(int i 0; i la; i) a[la - 1 - i] x[i] - 0; lc la; LL rem div(c, a, b); // 输出商 for(int i lc - 1; i 0; i--) cout c[i]; cout endl 余数 rem endl; return 0; }3.枚举3.1 普通枚举3.1.1 铺地毯通过从后往前进行枚举 这样只要在范围内 那么这个肯定是最后的#include iostream using namespace std; const int N 1e4 10; int n; int a[N], b[N], g[N], k[N]; int x, y; int find() { // 从后往前枚举地毯 for(int i n; i 1; i--) { // 判断点(x,y)是否在第i块地毯上 // 地毯左下角(a[i],b[i])长宽g[i],k[i] if(a[i] x x a[i] g[i] b[i] y y b[i] k[i]) { return i; } } return -1; } int main() { cin n; for(int i 1; i n; i) { cin a[i] b[i] g[i] k[i]; } cin x y; cout find() endl; return 0; }3.1.2 回文日期在策略1里面需要遍历20000101到20240101 数据非常的庞大 这时候需要枚举240000遍而策略2里面只需要遍历2000到2024 然后判断回文的月日合不合法推广到完整 4 位年份范围10009999一共 8999个数策略三进行遍历所有的月和日的组合 这样遍历12乘以31为372#include iostream using namespace std; int x, y; // 闰年每月天数2月29天 int day[] {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; //当二月为u29天的时候 它的回文数必定是闰年92200229 int main() { cin x y; int ret 0; // 枚举月 i日 j for (int i 1; i 12; i) { for (int j 1; j day[i]; j) { // 构造前面4位日月翻转 日j月i → 月日颠倒作为年份 int k j % 10 * 1000 j / 10 * 100 i % 10 * 10 i / 10; // 完整8位数k(4位年份) i(2位月) j(2位日) int num k * 10000 i * 100 j; if (x num num y) ret; } } cout ret endl; return 0; }3.1.3 扫雷下标从1开始 防止下标越位#include iostream using namespace std; const int N 1e4 10; int n; int a[N], b[N]; // a[1]不放地雷a[1]0 int check1() { a[1] 0; for(int i 2; i n 1; i) { a[i] b[i - 1] - a[i - 1] - a[i - 2]; if(a[i] 0 || a[i] 1) return 0; } // 边界条件a[n1]必须等于0才合法 if(a[n 1] 0) return 1; else return 0; } // a[1]放地雷a[1]1 int check2() { a[1] 1; for(int i 2; i n 1; i) { a[i] b[i - 1] - a[i - 1] - a[i - 2]; if(a[i] 0 || a[i] 1) return 0; } if(a[n 1] 0) return 1; else return 0; } int main() { cin n; for(int i 1; i n; i) cin b[i]; int ret 0; ret check1(); ret check2(); cout ret endl; return 0; }3.2二进制枚举3.2.1子集#include vector using namespace std; class Solution { public: vectorvectorint subsets(vectorint nums) { vectorvectorint ret; int n nums.size(); // st 代表状态从 0 ~ (1n)-1 for(int st 0; st (1 n); st) //向左移动 { vectorint tmp; for(int i 0; i n; i) { // 判断 st 的第 i 位是否为 1 if((st i) 1) { tmp.push_back(nums[i]); } } ret.push_back(tmp); } return ret; } };时间复杂度3.2.2 费解的开关进行一行的一行点亮 如果第一行没有点亮 那么第二行必须把第一行点亮 要不然后续就点不亮了可以使用一个数进行存储 比如第一行10111 这个二进制的数为29 所以29对应亮灭亮亮亮1^10 0^11 0^00 1^01当前行为10010 的时候 下一行按的就是10010当按位的时候是做高位需要按的时候10000 在左移100000的过程当中会把改变好的a[i]01111从5个位变成6个位101111 而最高位多了个1 这个时候就变成了6位 所以需要使用15为32 然后为100000 100000-1为011111所以就是101111011111为001111 最高位多余的干扰 1 被直接清除只留下有效低 5 位。读取一行字符串输入00111#include iostream #include cstring #include algorithm using namespace std; const int N 5; int a[N]; // 原始灯状态每行用一个整数二进制存储 int t[N]; // 临时副本模拟操作 // 统计x二进制里面1的个数统计按下开关数量 int calc(int x) { int cnt 0; while(x) { cnt; x x - 1; // 消除最低位的1 } return cnt; } int main() { int T; cin T; while(T--) { //多组数据要清空之前的数据 memset(a, 0, sizeof a); // 读入5*5网格 for(int i 0; i N; i) { for(int j 0; j N; j) { char ch; cin ch; // 存相反0代表灯初始需要点亮需要关掉标记为1 if(ch 0) a[i] | 1 j; //a[i] a[i] | (1 j); } } int ret 0x3f3f3f3f; // 枚举【第一行所有按压方案】 st: 0 ~ 2^5 - 1 for(int st 0; st (1 N); st) { memcpy(t, a, sizeof a); int push st; // 当前行按压状态 int cnt 0; // 按压总次数 for(int i 0; i N; i) { cnt calc(push); // 按压push影响本行自身、左、右 t[i] ^ push ^ (push 1) ^ (push 1); 因为^1会把0变成1 把1变成0 又因为需要把左边和右边的进行变化 所以需要进行换位置 就是左移和右移 把当前位置的左边和右边进行变化 t[i] (1 N) - 1; // 屏蔽超出5列的高位防止越界影响 // 当前行按压会改变下一行同列灯 t[i 1] ^ push; // 关键下一行必须按 t[i]才能把本行灯全部熄灭 push t[i]; } // 全部操作完成后最后一行必须全部熄灭(t[4]0)才算合法方案 if(t[N - 1] 0) ret min(ret, cnt); } // 题目规定超过6步输出-1 if(ret 6) cout -1 endl; else cout ret endl; } return 0; }时间复杂度3.2.3Even Parity比如第一行为010的时候 为了满足第一行的上下左右为偶数 所以下一行为101 之后进行依次类推010101因为题目里面指出来在这个数字的上下左右1的个数为偶数 所以0的个数也为偶数根据一个异或的特性 在异或里面两个数一行的时候结果为0 x ^ x 0 并且异或有交换律 所以在一个式子里面 1^0^1^00 而10^1^0#include iostream #include cstring #include algorithm using namespace std; const int N 20; int n; int a[N]; // 用二进制存储状态 int t[N]; // 备份 // 判断 x-y 是否合法 // 返回 -1表示不合法 // 其余的数表示合法并且表示 0-1 的次数 int calc(int x, int y) { int sum 0; for(int i 0; i n; i) { if(((x i) 1) 0 ((y i) 1) 1) sum; if(((x i) 1) 1 ((y i) 1) 0) return -1; } return sum; } int solve() { int ret 0x3f3f3f3f; // 记录最小的改变次数 初始化为无穷大用来求最小值 // 枚举第一行的最终状态 for(int st 0; st (1 n); st) { memcpy(t, a, sizeof a); int change st; int cnt 0; // 统计 0-1 的次数 bool flag 1; for(int i 1; i n; i) { // 先判断 change 是否合法 int c calc(t[i], change); if(c -1) { flag 0; break; } cnt c; // 累加次数 // 当前行的最终状态 t[i] change; // 计算下一行的最终状态 change t[i - 1] ^ (t[i] 1) ^ (t[i] 1); change (1 n) - 1; } if(flag) ret min(ret, cnt); } if(ret 0x3f3f3f3f) return -1; else return ret; } int main() { int T; cin T; for(int k 1; k T; k) { // 多组测试数据记得清空 memset(a, 0, sizeof a); cin n; for(int i 1; i n; i) // 避免越界访问 防止到[-1] { for(int j 0; j n; j) { int x; cin x; if(x) a[i] | 1 j; } } printf(Case %d: %d\n, k, solve()); } return 0; }数组a[i]里面存的就是普通十进制整数只是程序在运算的时候把这个整数当成一串二进制比特来操作移位、按位与、按位或时间复杂度4.前缀和4.1⼀维前缀和#include iostream using namespace std; typedef long long LL; const int N 1e5 10; int n, q; LL a[N]; LL f[N]; // 前缀和数组 int main() { cin n q; for(int i 1; i n; i) cin a[i]; // 处理前缀和数组 for(int i 1; i n; i) { f[i] f[i - 1] a[i]; } // 处理 q 次询问 while(q--) { int l, r; cin l r; cout f[r] - f[l - 1] endl; } return 0; }4.2最大子段和#include iostream using namespace std; typedef long long LL; const int N 2e5 10; int n; LL f[N]; // 前缀和数组 int main() { cin n; for(int i 1; i n; i) { LL x; cin x; f[i] f[i - 1] x; } LL ret -1e20; //有的数是小于0的 LL prevmin 0; for(int i 1; i n; i) { ret max(ret, f[i] - prevmin); //获取最大的字段和 prevmin min(prevmin, f[i]); //获取前i数的最小和 //如果数据是-1 -2 -3 代码进行颠倒后pre-1 ret0 就不对了 //通过找前i的最小值 让i的数进行减去min(pre) 因为题目要求是非空的 所以pre的范围i要小于求的ret的i 所以pre需要放在ret的后面 这样计算的时候pre里面的i永远小于ret的i //然后就获得了最新的子段 cout ret endl; return 0; }premin得到的是前i个数的最小值4.3二维前缀和#include iostream using namespace std; typedef long long LL; const int N 1010; int n, m, q; LL f[N][N]; int main() { cin n m q; // 预处理二维前缀和矩阵 for(int i 1; i n; i) { for(int j 1; j m; j) { LL x; cin x; f[i][j] f[i - 1][j] f[i][j - 1] - f[i - 1][j - 1] x; } } // 处理 q 次查询 while(q--) { int x1, y1, x2, y2; cin x1 y1 x2 y2; cout f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] f[x1 - 1][y1 - 1] endl; } return 0; }4.4激光炸弹这样的可以 这样的不可以#include iostream #include algorithm using namespace std; const int N 5010; int n, m; int a[N][N]; int f[N][N]; // 前缀和矩阵 int main() { cin n m; while(n--) { int x, y, v; cin x y v; x, y; // 下标从 1 开始计数 a[x][y] v; // 同一个位置有可能有多个目标 } n 5001; // 预处理前缀和矩阵 for(int i 1; i n; i) { for(int j 1; j n; j) { f[i][j] f[i - 1][j] f[i][j - 1] - f[i - 1][j - 1] a[i][j]; } } int ret 0; m min(m, n); // 如果 m 很大相当于就是把整个区域全部摧毁 // 枚举所有边长为 m 的正方形 for(int x2 m; x2 n; x2) { for(int y2 m; y2 n; y2) { int x1 x2 - m 1, y1 y2 - m 1; ret max(ret, f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] f[x1 - 1][y1 - 1]); } } cout ret endl; return 0; }【ACM 模式与核心代码模式】