- 冯之几 的博客
代码模板【自存】
-
Edge of Destiny (冯之几)
LV 10
@
2026-7-18 22:37:12
自存，无不良用途，请赵老师明辨是非！——冯之几，2026-07-18, 22:35
语法阶段：
//判断回文数
bool isHWS(int num) {
// 方法1
// int temp=num,ans=0;
// while (temp!=0) {
// ans=ans*10+temp%10;
// temp/=10;
// }
// if (ans==num)
// return true;
// else
// return false;
//方法2
string a = to_string(num);
string b = a;
reverse(a.begin(), a.end());
return a == b;
}
// 试除法判断质数
int isPrime(int n) {
if (n < 2) return 0;//质数必须是大于1的整数
for (int i = 2; i <= n / i ; i++) { // 试除范围 [2,sqrt(n)] （靴子定理）
if (n % i == 0) //找到因子 不是质数
return 0;
}
return 1; // 循环过程中没找到因子 是质数
}
// 辗转相除法 gcd greatest common divisor 2最大公约数（a大b小）
// gcd(a, b) == gcd(b, a%b)
int gcd(int a, int b){
return b == 0? a : gcd(b, a % b);
}
// 分解质因数
/*
代码作用： 对一个数字进行质因数分解 从小到大输出所有因子
例如 输入20
输出 2 2 5
*/
void divide(int n) {
// 从2开始，试除每个数
for (int i = 2; i <= n / i; i++) { // 枚举 2 ~ sqrt(n)
// 如果n能被i整除，说明i是一个质因数
while (n % i == 0) {
cout << i << " ";
n /= i; // 用i整除n，继续分解
}
}
if (n != 1) // 大于 sqrt(n) 的因子最多有一个 单独 处理
cout << n;
}
// 埃氏筛法 O（n * loglog n） C * N
const int N = 1e7 + 10;
int prime[N], cnt, n, a;
bool st[N]={1,1};//标记有没有被筛掉
//埃式筛法-O(nloglogn) 只筛质数的倍数
void get_primes(int n) {
for(int i = 2; i <= n; i++) { // n / lnn * n^0.5
if(st[i]==0){ //i是质数
for(int j = i; j <= n / i; j ++) // 筛掉i的倍数 倍数大于等于 i
st[i * j] = true;//筛掉 i*j 标记下
}
}
}
//线性筛法 -O(n), n = 1e7的时候基本就比埃式筛法快一倍了
//算法核心：数字仅会被其最小质因子筛去 56
const int N = 1e7 + 10;
int prime[N], cnt;
bool st[N];//st[i]=0 没被筛掉 st[i]=1被筛掉
void get_prime(int x) {
for (int i = 2; i <= x; i++) {
if (st[i] == 0) prime[cnt++] = i; //prime[]存储1-i范围的质数
for (int j = 0; prime[j] * i <= x; j++) {
//对于任意一个合数x，假设pj为x最小质因子，当i<x/pj时，一定会被筛掉
st[prime[j]*i] = true;
if (i % prime[j] == 0)
break; //保证pj是最小质因子核心
}
}
}
算法入门：
//冒泡排序 o(n^2) 稳定
/*
排序思路
1. 比较相邻的元素。如果顺序不对，就交换。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样就完成了一轮冒泡排序，
3. 进行 i 轮冒泡排序后 可以确定后i个元素位置是正确的。 所以我们需要进行n-1轮冒泡排序。
4. 如果一趟排序没产生交换 说明排好了 结束排序
*/
#include<iostream>
using namespace std;
void BubbleSort(int a[], int n) {
int swapped;//1 标记：一趟排序有没有产生交换
for (int i = 0; i < n - 1; i++) {
swapped = 0; //2 每趟排序开始前都假设 没产生交换
for (int j = 0; j < n - 1 - i; j++) { //排序区间可以越来越短
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
swapped = 1; //3 产生交换 标记值改成1
}
}
if (swapped == 0) { //4 如果一趟排序没产生交换 说明排好了 结束排序
break;
}
}
}
//插入排序 o(n^2) 稳定
/*
插入排序 o(n2)
1.从第二个数字开始 把每个插入到前面合适的位置
插入过程：
1.用temp存储待排数字
2.循环 前面比temp大的都往后拉
3.temp插入到j位置
*/
int insertSort( int a[], int size) {
for (int i = 1; i < size ; i++) {
int temp = a[i], j = i; //存储待排数字的值和下标
while (j > 0 && a[j - 1] > temp ) { //前面比temp大的都往后拉
a[j] = a[j - 1]; // 赋值（向后拉）
j--;
}
a[j] = temp; //插入
}
}
// 选择排序 o（n^2） 不稳定
/*
不稳定性证明
例如：
5* 2 3 5 1
1 2 3 5 5*
排序思想：
1. 从数组的第一个位置开始，将其视为已排序区间的唯一元素。
2. 遍历未排序区间，找到最小（或最大）的元素。
3. 将找到的最小（或最大）元素与未排序区间的第一个元素进行交换。
4. 将交换后的元素作为已排序区间的最后一个元素。
5. 重复步骤2至4，直到所有元素都被排序。
每次选出 索引：i-n 范围内最小的数字 把它放到第i个位置
*/
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;//假设最小的数字索引就是i
for (int j = i + 1; j < n; j++) { //找最小的数字的位置
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr[i], arr[minIndex]);
}
}
// 快速排序
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],n;
void QuickSort(int s[],int l,int r)
{
if(l<r)//区间内数字个数 > 1
{
swap(s[l],s[(l+r)/2]);//优化 防止顺序数字超时
int i=l,j=r,x=s[l];//x为基准
while(i<j)//左右指针不相遇
{
while(i<j&&s[j]>x)//从右往左扫描 位置不对的元素
j--;
if(i<j)//异常元素抛到左边 左指针右移
swap(s[i++],s[j]);
while(i<j&&s[i]<x)
i++;
if(i<j)
swap(s[j--],s[i]);
}
QuickSort(s,l,i-1);
QuickSort(s,i+1,r);
}
}
int main()
{
cin >> n;
for(int i = 0;i < n; i++)
{
cin >> a[i];
}
QuickSort(a,0,n-1);
for (int i = 0;i < n;i++)
{
cout<<a[i]<<" ";
}
return 0;
}
//计数排序 （每个数字都有专属的桶） o(n+M) 简易版 不要求稳定性时用
/*
解决 数字分布范围不大的（三千万以内） 的 非负整数排序问题 去重很方便 空间换时间
数字分布范围为 0-n时：有n+1个桶
*/
#include<iostream>
using namespace std;
const int M=100000;//M代表数字最大值
int main(){
int a[M+10]={0};
int n,k;
cin>>n;//输入n个数字
for(int i=0;i<n;i++)
{
cin>>k;
a[k]++;//给k号桶投一票
}
for(int i=0;i<=M;i++)//遍历所有的桶
{
int k=0;
while(k<a[i])//完整排序结果
{
cout<<i<<" ";
k++;
}
// if(a[i]!=0)//去重排序结果
// {
// cout<<i<<" ";
// }
}
return 0;
}
//计数排序 稳定性
const int N = 100010;
const int W = 100010;
int n, w, a[N], cnt[W], b[N];
void counting_sort() {
memset(cnt, 0, sizeof(cnt));
for (int i = 1; i <= n; ++i) ++cnt[a[i]];
for (int i = 1; i <= w; ++i) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; --i) b[cnt[a[i]]--] = a[i];
}
// 二分
//二分查找 查找的数字唯一 或 不存在
int binarySearch(int a[],int l,int r,int x){
while(l<=r){ // 注意等号
int mid=(l+r)/2;//取中间数字的下标
if(a[mid]==x){
return mid;
}else if(a[mid]<x){
l=mid+1;
}else{
r=mid-1;
}
}
return -1;
}
int bs_l(int a[],int l,int r,int n)//左边界二分 返回的是第一个等于 或 第一个大于目标数字的下标
{
while(l<r)
{
int mid=(l+r)/2; //l=2 r=3 希望mid向下取整 不用+1
if(a[mid]>=n)
r=mid;
else
l=mid+1;
}
return l;
}
int bs_r(int a[],int l,int r,int n)//右边界二分 返回的是最后一个等于 或 最后一个小于 目标数字的下标
{
while(l<r)
{
int mid=(l+r+1)/2; //l=2 r=3 希望mid向上取整 要+1
if(a[mid]<=n)
l=mid;
else
r=mid-1;
}
return l;
}
//高精度加
string add(string a, string b) {
int la = a.size(), lb = b.size(), f = 0;//la a剩余的需要加的位数 f进位标记
string ans;
while (la || lb || f) { //数字没加完 或者有进位 就循环
int t = (la>0?a[--la]-'0':0) + (lb>0?b[--lb]-'0':0) + f;//取对应位置数据 相加
f = t / 10;
t %= 10;
ans = ans+(char)(t + '0');//内存
}
reverse(ans.begin(),ans.end());
return ans;
}
//dfs 深搜基本模板：
int check(参数)//约束条件判断 有没有路
{
if(满足条件)
return 1;
return 0;
}
void dfs(int step)//step：深度
{
判断边界 //找到迷宫出口/思路
{
相应操作//结束任务
}
for()//循环逼历每一种情况 类似前左右这样的遍历规则
{
if(check);//满足check条件 检查有没有路
标记该节点访问过
dfs(step+1);递归继续下一步
节点恢复初始状态(回溯)
}
}
// 全排列问题
#include <iostream>
#include <iomanip>
using namespace std;
int a[100]={0},b[100]={0},n;
void dfs(int dep){ //深度代表第几个数字
if(dep==n+1){
for(int i=1;i<=n;i++){
cout<<setw(5)<<a[i];
}
cout<<endl;
return;
}
else{
for(int i=1;i<=n;i++){ //尝试所有的数字
if(b[i]==0){ //b[i]==0 表示i没用过 b[i]==1 表示i用过
a[dep]=i;
b[i]=1;//使用过的数字标记为1
dfs(dep+1);
b[i]=0;//标记 重置方便回溯
}
}
}
}
int main(){
cin>>n;
dfs(1);
return 0;
}
//bfs 迷宫
void bfs()
{
node p;
p.x=sx; //存储一个起点
p.y=sy;
queue<node>q;//辅助队列
q.push({});//避免异常
d[sx][sy]=0;
while(!q.empty())
{
node tmp=q.front();//取队头
q.pop();
for(int i=0;i<4;i++)//向四个方向扩散
{
int xx=tmp.x+dx[i];
int yy=tmp.y+dy[i];
//如果新节点可以到达 且 在棋盘内 且没到过 更新步数 入队
if(maze[xx][yy]!='#' && xx>0&&yy>0&&xx<=n&&yy<=m && d[xx][yy]<0)
{
node tp;
tp.x=xx;
tp.y=yy;
d[xx][yy]=d[tmp.x][tmp.y]+1;//更新距离
q.push(tp); //存储新到达的点
}
}
}
}
// lis 最长上升子序列（模板题）
/*
解题思路：DP O(n2)
状态表示：f[i]表示 以w[i]结尾的 上升子序列 的最大长度。
状态转移：f[i] = max(f[i], f[j] + 1)。j∈(0,1,2,..,i-1),且满足 w[i] > w[j]
f[i]最小值为1（自己单独构成一个子序列）
*/
#include <iostream>
using namespace std;
const int N = 1010;
int n;
int w[N], f[N];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> w[i];
int ml = 1; // 存储所有 f[i]之中的最大值
for (int i = 1; i <= n; i++) {
f[i] = 1; // f[i]默认为1 自己开一个新序列 长度至少是
for (int j = 1; j < i; j++) {
if (w[i] > w[j]) f[i] = max(f[i], f[j] + 1); // 前一个小于自己的数结尾的最大上升子序列加上自己，即+1
}
ml = max(ml, f[i]);//记录最大长度ml
}
cout << ml << endl;
return 0;
}
// 最长公共子序列 lcs
/*
解题思路：DP
从最后一个字母划分
状态表示：f(i,j) 字符串a的前i个和字符串b的前j个字母组成的公共子序列 的 最大长度
状态转移：如果a[i]==b[j] f(i,j) = f(i-1,j-1) + 1
a[i]!=b[j] f(i,j) = max(f(i-1,j) , f(i,j-1))
*/
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main() {
cin >> n >> m >> a + 1 >> b + 1;//字符串从下标1开始存
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i] == b[j]) {
f[i][j] = f[i - 1][j - 1] + 1;
} else {
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
}
}
}
cout << f[n][m] << endl;
return 0;
}
//01背包问题
/*
状态表示：
f[i][j] 表示 可选物品前i件 背包容量为j时的 最大背包价值
第i件物品重量为w[i],价值为c[i]
状态转移方程：
f[i][j] = max(f[i-1][j] , f[i-1][j-w[i]] + c[i]); // 比较两种方案
*/
#include <iostream>
using namespace std;
int N,V,v[1001],w[1001],f[1001][1001];
int main(){
cin>>N>>V;
for(int i=1;i<=N;i++){ //n件物品的重量和价值
cin>>v[i]>>w[i];
}
for(int i=1;i<=N;i++){//可选物品数 选择在增加
for(int j=1;j<=V;j++){ //对应你的付出代价的数量
if(j>=v[i]){ //能选新物品
f[i][j]=max(f[i-1][j] , f[i-1][j-v[i]] + w[i]); // 比较两种方案
}else{
f[i][j]=f[i-1][j]; //选不了新物品 直接采用老方案
}
}
}
cout<<f[N][V];
return 0;
}
//一维背包 （优化空间）
#include <bits/stdc++.h>
using namespace std;
int f[1001]={0},N,V,w[1001],v[1001];
int main(){
cin >> N >> V;
for(int i=1;i<=N;i++){
cin >> v[i] >> w[i] ;
}
for(int i=1;i<=N;i++){
for(int j=V;j>=v[i];j--){ //从后向前推 防止重复选择
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout << f[V];
return 0;
}
// 完全背包问题
#include<bits/stdc++.h>
using namespace std;
int n, m, v[31], w[31], f[201];
int main(){
cin >> m >> n;
for(int i = 1; i <= n; i++) cin >> w[i] >> v[i];
for(int i = 1; i <= n; i++){
for(int j = w[i]; j <= m; j++){ // 从能选新用品的位置开始推。增加一个体积，都考虑再加一件新物品。
if(f[j-w[i]] + v[i] > f[j])
f[j] = f[j-w[i]] + v[i];
}
}
cout << "max=" << f[m];
return 0;
}
//多重背包（1）
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int n, m, w[N], v[N], s[N], f[N];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){ // 输入物品的代价 价值 件数
cin >> w[i] >> v[i] >> s[i];
}
for(int i = 1; i<= n; i++){
for(int j = 1; j <= s[i]; j++){ // 一件一件的加物品
for(int k = m; k >= w[i]; k--){ //01 背包 必须从后往前推 避免重复取新物品
f[k] = max(f[k], f[k - w[i]] + v[i]);//选或者不选新物品两种方案
}
}
}
cout << f[m];
return 0;
}
// 多重背包（2） 二进制优化
#include<bits/stdc++.h>
using namespace std;
const int N = 2010;
int n, m, w[N], v[N], s[N], f[N], num;
struct good{
int w, v;
}goods[N * 20];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){ // 输入同时进行二进制优化 s[i]件 优化成 log(s[i]) 件
cin >> w[i] >> v[i] >> s[i];
int k = 1; // 每次分割 k件
while(k <= s[i]){ // 可以分割出k件套
goods[++num] = {k*w[i], k*v[i]};
s[i] -= k;
k *= 2;
}
if(s[i] > 0) goods[++num] = {s[i]*w[i], s[i]*v[i]};// 剩下的部分作为整体
}
// 01背包模板
for(int i = 1; i <= num; i++){
for(int j = m; j >= goods[i].w; j--){
f[j] = max(f[j], f[j - goods[i].w] + goods[i].v);
}
}
cout << f[m];
return 0;
}
// 快速幂
/*
算法思路：将b转换成几个1 2 4 8 ....等二进制数字和 利用位运算
*/
#define ull unsigned long long
ull quick_pow(ull a,ull b,ull p)
{
ull result=1%p;
a=a%p;
while(b!=0)
{
if(b&1) result=result*a%p;
a=a*a%p;
b>>=1;
}
return result;
}
来源在https://www.wolai.com/chasem_01/tixsNZ12fgKQWhJ3hujFPz