慧记

主题

算法模板 ​

exp函数 ​

求一个数以e为底，以n为指数

c++
double T= exp(a)

即e的a次；

题目示例： ​

image-20231014162828683

c++
#include <iostream>
#include<cmath>
#include<iomanip>
using namespace std;
int main(){
    int t;
    cin>>t;
    double a[t],b[t],c[t],d[t];
     
    for(int i = 0;i < t;i++){
        cin>>a[i]>>b[i]>>c[i];
        d[i] =exp(a[i])*b[i];
    }
    for(int i = 0;i < t;i++){
        cout<<fixed<<setprecision(c[i])<<d[i]<<endl;
    }    
}

保留小数点后特定位数的精度 ​

使用 <iomanip> 头文件中的 fixed 和 setprecision 函数

out<<fixed<<setprecision(x)<<d[i]<<endl;

求最大公约数 ​

C++
int gcb(int a, int b)
{
    int c = 0;
    while(c = a % b)
    {
        a = b;
        b = c;
    }
    return b;
}

求最小公倍数 ​

c++
//暴力求
    int main()
{
    int a, b;
    while(cin >> a >> b)
    {
        int m = max(a, b);//a,b中的较大值
        while(1)
        {
            if(m % a == 0 && m % b == 0)
            {
                cout << m <<endl;
                break;
            }
            m++;//从较大的数开始,一个数一个数往后判断
        }
    }
    return 0;
}
c++
//优化算法
//最小公倍数 = 两数之积除以最大公约数
a/gcb(a,b)*b

判素数 ​

c++
bool is_prime(int n){
   
	if(n<=1) return false;
	for(int i=2;i<n/i;i++){
   
		if(n%i==0) return false
	}
	return true;
}

​

find在string的使用 ​

image-20231113155410096

代码 ​

c++
#include<iostream>
#include<string>
using namespace std;
int main()
{
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        s[i]=tolower(s[i]);
    }
    int t=s.find("bob");
    cout<<t;
    return 0;
}
c++
// 自定义的查找函数，找到返回0，未找到返回-1
int customFind(const string& str, const string& target) {
    size_t pos = str.find(target);
    if (pos != string::npos) {
        // 找到了，返回0
        return 0;
    } else {
        // 未找到，返回自定义的未找到标志，比如 -1
        return -1;
    }
}

字母大小写tolower，toupper ​

image-20231113213922113

代码： ​

c++
#include<iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, k;
    string s;
    cin >> n >> k;
    cin >> s;

    // 转换前 k 个字符为小写
    transform(s.begin(), s.begin() + k, s.begin(), ::toupper);

    // 转换剩余字符为大写
    transform(s.begin() + k, s.end(), s.begin() + k, ::tolower);

    cout << s;

    return 0;
}

去前导0 ​

c++
  while(s[0] == '0') {
    s.erase(s.begin());
  }

反转 ​

c++
 reverse(s.begin(),s.begin()+k);

全排列计数 ​

image-20231113220613435

代码 ​

c++
#include<bits/stdc++.h>
using namespace std;
int a[20];
int n;
bool prime(int n) {//判断素数
    if (n == 1)return false;
    else
    {
        for (int i = 2; i <= sqrt(n); i++) {
            if (n % i == 0)
                return false;
        }
    }
    return true;
}
bool judge(int a[20]) {//判断任意相邻的两个数是否为素数
    for (int i = 1; i < n; i++) {
        if (prime(a[i] + a[i + 1]))
            return false;
    }
    return true;
}
int main() {
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        a[i] = i;
    }
    do {
        if (!judge(a))
            continue;
        ans++;
    } while (next_permutation(a + 1, a + 1 + n));
    //next_permutation(num,num+n)函数是对数组num中的前n个元素进行全排列，同时并改变num数组的值
    cout << ans;
    return 0;
}

字符串分割 ​

image-20231123083910065

c++
#include<iostream>
#include<string>
using namespace std;
int main()
{
	string s="sfsa";
	string a=s.substr(0,3);
	string b=s.substr();
	string c=s.substr(2,3);
	cout<<a<<endl;
	cout<<b<<endl;
	cout<<c<<endl;
	return 0;
}
bash
sfs
sfsa
sa

判断回文 ​

c++
#include<iostream>
#include<cstring>
#include <algorithm>

using namespace std;
int main()
{
  string s;
  string s1;
  cin>>s;
  s1 =s;
  reverse(s.begin(),s.end());

  if(s==s1){
    cout<<"Y";
  }
  else{
    cout<<"N";
  }
}

走迷宫bdf ​

image-20240409164953791

c++
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII; 

const int N = 110;

int n, m;
int a, b, c, h;
int g[N][N], d[N][N];

int bfs()
{
    queue<PII> q;
    
    memset(d, -1, sizeof d);
    d[a][b] = 0;
    q.push({a, b});

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while (!q.empty())
    {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int x = t.first + dx[i], y = t.second + dy[i];

            if (x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] == 1 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q.push({x, y});
            }
            if (c == x && h == y) return d[x][y];
        }
    } 
    
    return -1; 
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> g[i][j];
        }
    }
    cin >> a >> b >> c >> h;

    cout << bfs() << endl;

    return 0;
}

背包 ​

c++
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )//条件j >= v[i]
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;

    return 0;
}

完全背包 ​

c++
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int f[N];
int v[N], w[N];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++)
        for (int j = v[i]; j <= m; j++)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;

    return 0;
}

最长公共子序列 ​

c++
//本题可作为最长公共子序列的模板题 
#include <bits/stdc++.h>

using namespace std;

int arr1[1009],arr2[1009];
int dp[1009][1009];
//dp[i][j]表示arr1中以下标i结尾和arr2中以下标j结尾的最长公共子序列的长度
 
int main()
{
    int N,M;
    cin>>N>>M; 
    for(int i=1;i<=N;i++)cin>>arr1[i];
    for(int i=1;i<=M;i++)cin>>arr2[i];
    
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            if(arr1[i]==arr2[j])
            {
                //若两个序列当前末尾元素相等，由左上角状态转移而来 
                //则当前最长公共子序列的长度等于序列1以i-1结尾、序列2以j-1结尾的最长公共子序列的长度+1 
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else 
            {
                //若两个序列当前末尾元素不相等，由左侧或上侧状态转移而来
                //取序列1以i-1结尾而序列2以j结尾 和 序列1以i结尾而序列2以j-1结尾的子序列长度较大值 
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }    
    //序列1以N结尾、序列2以M结尾的最长公共子序列长度dp[N][M]即为最终答案 
    cout<<dp[N][M]<<endl;
    
    #if 0  
    //下方演示如何求出具体的最长公共子序列
    //对于dp矩阵,从dp[N][M]开始回溯，有三种回溯方向：向左、向上、向左上
    //若当前arr1[x]==arr2[y],该元素恰好是最长公共子序列的一部分，记录之并向左上角回溯
    //若当前dp[x-1][y]>dp[x][y-1],前者公共子序列更长，则向上回溯，x--；
    //反之则向左回溯，y--
    //直到回溯至边界坐标(1,1),此时容器内的元素是倒序存放的，逆转一下再输出即可 
    vector<int>v;
    int x=N,y=M;
    while(x&&y)
    {
        if(arr1[x]==arr2[y])//两个序列当前末尾元素相等(第一种情况)
        {
            v.push_back(arr1[x]);//该元素是最长公共子序列的一部分，保存之
            //两个序列同时缩短，向左上角回溯 
            x--;
            y--;
        }
        //arr1[x]和arr2[y]，哪个公共子序列更长就选取并缩短哪个 
        else if(dp[x-1][y]>dp[x][y-1])
        {
            //序列1以x-1结尾、序列2以y结尾的最长公共子序列更长 
            //则往上侧走，令序列1缩短 
            x--;
        }
        else 
        {
            //序列1以x结尾、序列2以y-1结尾的最长公共子长度更大
            //则往左侧走，令序列2缩短 
            y--;
        } 
        //当两个序列缩短至最长公共子序列长度相同(末尾元素相同)时,回到第一种情况 
    }
    reverse(v.begin(),v.end());
    for(int i=0;i<v.size();i++)
    {
        cout<<v[i]<<" ";
    }
    cout<<endl;
    #endif //删除#if 0和#endif即可执行 
    return 0;
}

NiM博弈 ​

c++
#include <iostream>

using namespace std;

int main(void)
{
    int t;
    cin >> t;
    for (int i=0;i<t;i++)
    {
        int n;
        cin>>n;
        int res = 0;
        for (int j=0;j<n;j++)
        {
            int x;
            cin >> x;
            res ^= x;
        }
        if (res)
            cout << "NO" << endl;
        else
            cout << "YES" << endl;
    }
    return 0;
}

向量求三角形面积 ​

c++
#include<bits/stdc++.h>
using namespace std;
const int Max=1010; 
int main(){
    cout<<fixed<<setprecision(2);
    int N;
    cin>>N;
    for(int i=0;i<N;++i){
        double x1,y1,x2,y2,x3,y3;
        cin>>x1>>y1>>x2>>y2>>x3>>y3;
        double a1=x2-x1,b1=y2-y1,a2=x3-x1,b2=y3-y1;
        cout<<fabs(a1*b2-a2*b1)/2<<endl;
    }
    
}

gcd ​

c++
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
    int c = 0;
    while(c = a % b)
    {
        a = b;
        b = c;
    }
    return b;
}
int main (){
  int n;
  cin>>n;
  while (n--) {
    int a,b;
    cin>>a>>b;
   cout << gcd(a,b)<<endl;
  }
}

最小公倍数 ​

c++
//优化算法
//最小公倍数 = 两数之积除以最大公约数
a/gcb(a,b)*b

前缀和 ​

二维前缀和 ​

大数求余数 ​

c++
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s="12345678901234567890123456789012345678901234567890";
  int sum=(int)s.size();
  int ans=0;
  for(int i=0;i<sum;++i){
    ans=(ans*10+s[i]-'0')%2023;
  }
  cout<<ans;
  return 0;
}

dp ​

数字三角形 ​

c++
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;

int w[N][N], f[N][N];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            cin >> w[i][j];

    for (int i = n; i >= 1; i -- )
        for (int j = 1; j <= i; j ++ )
            f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + w[i][j];

    cout << f[1][1];
    return 0;
}
/***
作者：yxc
链接：https://www.acwing.com/video/2294/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
***/

最长上升子序列 ​

前缀和 ​

#include<bits/stdc++.h>
using namespace std;

const int N = 100010;

int a[N],sum[N],n,m;

int main()
{
    cin>>n>>m;
    for(int i = 1; i <= n; i ++ )
    {
        cin>>a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    int l,r;
    while(m -- )
    {
        cin>>l>>r;
        cout<<sum[r] - sum[l - 1]<<endl;
    }
    return 0;
}

二维前缀和 ​

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;
int n,m,q,x1,x2,y1,y2;
int a[N][N],sum[N][N];

int main()
{
    cin>>n>>m>>q;
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ )
        {
            cin>>a[i][j];
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];//矩阵前缀和初始化
        }
    while(q -- )
    {
        cin>>x1>>y1>>x2>>y2;
        cout<<sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]<<endl;//计算x1y1为左上角，x2y2为右下角的矩阵的和
    }

    return 0;
}

日期 ​

import os
import sys

from datetime import *  # import datetime

dt1 = datetime(2022, 1, 1)
cnt = 0
for i in range(0, 366):
    s = "%02d%02d%02d" % (dt1.year, dt1.month, dt1.day)  # 转换成字符串
    dt1 += timedelta(days=1)  # timedelta有三种：days,seconds,microseconds
    if '012' in s or '123' in s or '234' in s or '345' in s or '456' in s or '678' in s or '789' in s:
        cnt += 1
print(cnt)

进制转换 ​

# 定义一个 9 进制数的字符串
num_9 = "2022"  # 这里的 "123" 表示一个 9 进制数

# 将 9 进制数转换为十进制数
num_10 = int(num_9, 9)

# 输出结果
print(f"9 进制数 {num_9} 转换为十进制数为 {num_10}")

Released under the MIT License.

Copyright © 2024 lihuibear