关于那几道黑题，是被机惨了，悲。

\(2024\)-\(8\)-\(30\) 通过 \(600\) 题

\(2024\)-\(9\)-\(2\) 橙名

\(2024\)-\(11\)-\(25\) 咕值跌破 \(190\)

python

import sys
sys.setrecursionlimit(1000000)
sys.set_int_max_str_digits(1)

万能头文件

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define int long long
using namespace __gnu_cxx;
using namespace __gnu_pbds;
using namespace std;
signed main()
{   
    return 0;
}

便捷函数

快读写：

ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);

快读：

int read()
{
    int res=0,flag=1;
    char ch;
    if((ch=getchar())=='-')
    flag=-1;
    else
    res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
    {
        res=res*10+ch-'0';
    }
    return res*flag;
}

快写：

void write(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}

cmp:

bool cmp(node a,node b)
{
    return a < b;
}

质数：

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

分解质因数:

void divide(int n)
{
    for(int i = 2;i<=n/i;i++)
    {
        int s = 0;
        if(n%i==0)
        {
            while(n%i==0) n/=i,s++;
            cout<<i<<' '<<s<<endl;
        }
        if(n>1) cout<<n<<' '<<1<<endl;
    }
}

求互质数：

int phi(int n)
{
    int res = n;
    for(int i = 2;i<=n/i;i++)
    {
        if(n%i==0)
        {
            res = res/i*(i-1);
            while(n%i==0)
            {       
                n/=i;
            }
        }
    }
    if(n>1) res = res/n*(n-1);
    return res;
}

O2/O3

O2:

#pragma GCC optimize(2)

O3:

#pragma GCC optimize(3)

常用函数

sort：

sort(a,a+n,less<int>());
sort(a,a+n,greater<int>());

memset:

memset(a,0,sizeof(a));

abs/fabs:

abs(a);//fabs(a);

getline:

getline(a);

substr:

substr(a,pos,len);//从 pos起，截取len个字符在a中

unique:

int len=unique(a,a+n)-a;

__gcd:

int ans=__gcd(a,b);

常用代码

bfs

#include<bits/stdc++.h>
using namespace std;
int dir[4][2]={1,0,0,1,-1,0,0,-1}; 
bool vis[55][55];
char mp[55][55];
int n,m;
struct node
{
    int x,y;
    int step;
};
int bfs()
{
    queue<node>q;
    q.push({1,1});
    vis[1][1] = true;
    while(!q.empty())
    {
        node fr=q.front();
        q.pop();
        if(fr.x == n&&fr.y == m)
        {
            return fr.step;
        }
        for(int i = 0 ; i < 4 ; i ++ )
        {
            int tx = dir[i][0] + fr.x;
            int ty = dir[i][1] + fr.y;
            if(tx > n || ty > m || tx < 1 || ty < 1)
                continue;
            if(mp[tx][ty] == '#')
                continue;
            if(vis[tx][ty])
                continue;
                q.push({tx,ty,fr.step+1});
                vis[tx][ty] = true;
        }
    }
    return -1;
}

int main()
{
    cin >> n >> m ;
    for(int i = 1 ; i <= n ; i ++ )
    {
        for(int j = 1 ; j <= m ; j ++ )
        {
            cin >> mp[i][j];
        }
    }
    cout<<bfs()<<endl;
    return 0;
}

bfs优先队列优化

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
char mp[25][25];
bool vis[25][25];
int dir_x[]={0,1,0,-1,0};
int dir_y[]={0,0,1,0,-1};
struct node
{
    int x,y;
    int time;
    friend bool operator <(node x,node y)
    {
        return x.time > y.time;
    }
};
priority_queue<node>q;
int bfs()
{
    while(!q.empty())
    {
        node fr=q.top();
        q.pop();
        if(mp[fr.x][fr.y]=='W')
        {
            return fr.time;
        }
        for(int i=1;i<=n;i++)
        {
            int tx=dir_x[i]+fr.x;
            int ty=dir_y[i]+fr.y;
            if(tx>n||ty>m||tx<1||ty<1)
            {
                    continue;
            }
            if(vis[tx][ty])
            {
                continue;
            }
            if(mp[tx][ty]=='#')
            {
                continue;
            }
            if(mp[tx][ty]>='1'&&mp[tx][ty]<='9')
            {
                q.push({tx,ty,fr.time+1+mp[tx][ty]-'0'});
            }
            else
            {
                q.push({tx,ty,fr.time+1});
            }
            vis[tx][ty]=true;
        }
    }
    return -1;
}
signed main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>mp[i][j];
            if(mp[i][j]=='Z')
            {
                q.push({i,j,0});
                vis[i][j]=true;
            }
        }
    }
    int ans=bfs();
    if(ans==-1)
    {
        cout<<"IMPOSSIBLE\n";
        return 0;
    }
    cout<<ans;
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

二叉搜索树模板（用法见主函数）

#include <iostream>  
using namespace std;  
struct TreeNode {  
    int val;  
    TreeNode *left, *right;  
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}  
};  
class BST {  
public:  
    TreeNode *root;  
    BST() : root(nullptr) {}  
  
    void tree_push(int val) { //插入值  
        root = tree_push(root, val);  
    }  
    TreeNode* tree_push(TreeNode *node, int val) {  
        if (node == nullptr) {  
            return new TreeNode(val);  
        }  
        if (val < node->val) {  
            node->left = tree_push(node->left, val);  
        } else if (val > node->val) {  
            node->right = tree_push(node->right, val);  
        }  
        return node;  
    }  
    TreeNode* search(TreeNode* node, int val) {  
        if (node == nullptr || node->val == val) {  
            return node;  
        }  
        if (val < node->val) {  
            return search(node->left, val);  
        } else {  
            return search(node->right, val);  
        }  
    }  
    bool find(int val) {  //判断值是否在BST中
        return search(root, val) != nullptr;  
    }  
    TreeNode* deleteNode(TreeNode* root, int key) {  
        if (root == nullptr) return nullptr;  
  
        if (key < root->val) {  
            root->left = deleteNode(root->left, key);  
        } else if (key > root->val) {  
            root->right = deleteNode(root->right, key);  
        } else {  
            if (root->left && root->right) {  
                TreeNode* temp = root->right;  
                while (temp->left) {  
                    temp = temp->left;  
                }  
                root->val = temp->val;  
                root->right = deleteNode(root->right, temp->val);  
            }   
            TreeNode* temp = root;  
            if (root->left == nullptr) {  
                root = root->right;  
            } else if (root->right == nullptr) {  
                root = root->left;  
            }  
            delete temp;  
        }  
  
        return root;  
    } 
    void Del(int val) {  // 删除节点的函数 
        root = deleteNode(root, val);  
    }  
    void iTR(TreeNode* node) {  //中序遍历
        if (node != nullptr) {  
            iTR(node->left);  
            cout << node->val << " ";  
            iTR(node->right);  
        }  
    }  
};  
int main() {  
    BST bst;  
    int n, t;  
    cin >> n;  
    for (int i = 1; i <= n; i++) {  
        int val;  
        cin >> val;  
        bst.tree_push(val);  
    }  
    cin >> t; 
    while (t--) {  
        string s;  
        cin >> s;  
        if (s == "itr") {  
            bst.iTR(bst.root);  
            cout << endl; 
        } else if (s == "find") {  
            int val;  
            cin >> val;  
            bool flag = bst.find(val);  
            if (flag) {  
                cout << "YES\n";  
            } else {  
                cout << "NO\n";  
            }  
        } else if (s == "push") {  
            int val;  
            cin >> val;  
            bst.tree_push(val);  
        } else if (s == "delete") {
            int val;
            cin>>val;
            bst.Del(val);
        } 
    }   
    return 0;  
}

扩展欧几里德求逆

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace std;
using namespace __gnu_pbds;
inline int extended_gcd(int a,int b,int &x,int &y) 
{
    if(!b) 
    {
        x=1;
        y=0;
        return a;
    }
    int gcd;
    gcd=extended_gcd(b,a%b,y,x);
    y-=(a/b)*x;
    return gcd;
}
inline int inv(int b,int mod) 
{
    int x,y;
    int gcd=extended_gcd(b,mod,x,y);
    return gcd!=1?-1:(x%mod+mod)%mod;
}
signed main() 
{
    int a,b;
    cin>>a>>b;
    int ans=inv(a,b);
    cout<<ans;
    return 0;
}

༺ཌༀཉི蒟༒蒻༃ༀད༻ 一枚