登录
← 返回首页 | 代码片段 › 1 基础算法 › 基础算法 / 搜索
JSON MD

1 基础算法

含 22 个代码片段
27 行
CPP JSON
【ACM 竞赛通用头文件模板】 ▪ solve() — 每轮测试的主解题函数(多测循环调用) ▪ main() — 程序入口,含 ios 加速、多组测试 t 的循环读入 ▪ 预定义常量:N=2e5+1(数组上限)、MOD=1e9+7(常用模数)、INF=0x3f3f3f3f3f3f3f3f(64位无穷大)、PI=acos(-1.0) ▪ 类型别名:int→long long / LL / ll(防溢出) 适用于大多数 ACM/ICPC 算法题的快速开发起点,开箱即用。
C++ 27 行 CPP
#include <bits/stdc++.h>
#define int long long
#define LL long long
#define ll long long
using namespace std;

const int N = 2e5+1;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);

void solve() {
    
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

// by vanadium-23
CPP-start CPP-start 1.1.1 头文件与宏定义
9 行
CPP JSON
【C++ 最简程序模板】 ▪ main() — 空的程序入口,仅包含 #include <iostream> 和 using namespace std 适用于快速编写单文件测试代码、验证语法特性,或作为最小可运行 C++ 程序的骨架。
C++ 9 行 CPP


#include <iostream>
using namespace std;

int main(){
    
    return 0;
}
gcd 与 lcm gcd 1.1.2 GCD与LCM
6 行
CPP JSON
【最大公约数(GCD)与最小公倍数(LCM)】 ▪ gcd(a, b) — 辗转相除法(欧几里得算法):b==0 时返回 a,否则递归 gcd(b, a%b) ▪ lcm(a, b) — 最小公倍数:a / gcd(a,b) * b(先除后乘防止溢出) 时间复杂度 O(log min(a,b))。适用于约分、周期计算、分数通分等基础数论场景。
C++ 6 行 CPP
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
int lcm(int a,int b){
    return a * b / gcd(a,b);
}
快速幂 binpow 1.1.3 快速幂
9 行
CPP JSON
【快速幂(二分幂)——无 MOD 版】 ▪ binpow(a, b) — 计算 a^b,将指数按二进制拆分:b 的最低位为 1 时乘入结果;a 不断自乘;b 每次右移一位。 时间复杂度 O(log b),空间 O(1)。注意无取模时结果可能溢出(b 较大时需要高精度或换用带 MOD 版)。
C++ 9 行 CPP
long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
快速幂带MOD binpow-mod 1.1.3 快速幂
9 行
CPP JSON
【快速幂(二分幂)——带 MOD 版】 ▪ binpow(a, b) — 计算 a^b % MOD,在每次乘法后取模防止中间结果溢出。算法流程:res=1;b>0 时若 b&1 则 res=res*a%MOD;a=a*a%MOD;b>>=1。 时间复杂度 O(log b),空间 O(1)。适用于大数幂取模(RSA 加密、组合数取模、哈希计算等)。
C++ 9 行 CPP
long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res % MOD;
}
矩阵快速幂 mksm 1.1.3 快速幂
30 行
CPP JSON
【矩阵快速幂(mksm)】 代码包含 qpow 等核心函数,实现了 矩阵快速幂 的算法逻辑。 核心函数: Matrix qpow(Matrix a,int b) — 快速幂 核心结构体:Matrix 关键配置: N=3,mod=1e9+7
C++ 30 行 CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=3,mod=1e9+7;
struct Matrix{
	int mat[N][N];
	Matrix(){memset(mat,0,sizeof(mat));}
	Matrix operator*(const Matrix& o)const{
		Matrix res;
		for(int i=0;i<N;++i){
			for(int k=0;k<N;++k){
				for(int j=0;j<N;++j){
					res.mat[i][j]=(res.mat[i][j]+mat[i][k]*o.mat[k][j])%mod;
				}
			}
		}
		return res;
	}
};

Matrix qpow(Matrix a,int b){
	Matrix res;
	for(int i=0;i<N;++i)res.mat[i][i]=1;
	while(b){
		if(b&1)res=res*a;
		a=a*a;
		b>>=1;
	}
	return res;
}
25 行
CPP JSON
【data】 随机数据生成器模板,用于对拍测试的输入生成。 核心函数: LL fu(无参数) — 核心算法函数 LL Rand(LL L,LL R) — 核心算法函数 说明:freopen("data.in","w",stdout); 适用场景:程序正确性验证(与暴力程序对比测试)
C++ 24 行 CPP
#include<bits/stdc++.h>
#define LL long long
#define Re register LL
using namespace std;
const LL inf=1000,N=20;
LL vis[inf+5];char A[N+5],B[N+5];
inline LL fu(){return rand()%2?-1:1;}
inline LL Rand(LL L,LL R){
	LL a=R-L+1;
	LL b=(LL)rand()*rand()%a+1;
	b=b*rand()%a+1;
	b=b*rand()%a+1;
	b=b*rand()%a+1;
	b=b*rand()%a+1;
	return L+b-1;
}
LL lo[N],tp[N];
int main(){
//	freopen("data.in","w",stdout);
	srand(time(0));
	Re n=rand()%N+1;
	printf("%lld 0\n",n);
	for(Re i=1;i<=n;++i)printf("%lld ",Rand(1,inf));
}
myprogram sakura 1.1.4 对拍
42 行
CPP JSON
【myprogram】 待测程序模板,与标准程序对拍验证正确性。 核心函数: void in(Re &x) — 核心算法函数 void sakura(无参数) — 后缀数组 核心结构体:QAQ0 关键配置: N=5e5+3 适用场景:程序正确性验证(与暴力程序对比测试)
C++ 41 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=5e5+3;
const LL inf=4e18+5;
int n,opt,A[N],B[N];
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
struct QAQ0{
	int x;LL g[N],S[N],dp[N];
	inline void sakura(){
		for(Re i=1;i<=n;++i)in(x),S[i]=S[i-1]+x,dp[i]=inf;
		dp[0]=0,g[0]=S[0];
		for(Re i=1,p=0;i<=n;++i){
			while(p+1<i&&2*S[p+1]-g[p+1]<=S[i])++p;
			dp[i]=dp[p]+(S[i]-S[p])*(S[i]-S[p]),g[i]=S[p];
//			printf("i=%d, p=%d\n",i,p);
//			for(Re j=0;j<=p;++j)
//				if(dp[i]>=(tmp=dp[j]+(S[i]-S[j])*(S[i]-S[j])))
//					dp[i]=tmp,g[i]=S[j];
		}
//		for(Re i=0;i<=n;++i)printf("dp[%d]=%lld\n",i,dp[i]);
		printf("%lld\n",dp[n]);
	}
}T0;
int main(){
//	freopen("456.txt","r",stdin);
	in(n),in(opt);
	if(n<=5000)T0.sakura();
	fclose(stdin);
	fclose(stdout);
	return 0;
}
std sakura 1.1.4 对拍
39 行
CPP JSON
【std】 标准程序(标程/暴力程序)模板,用作对拍的正确性基准。 核心函数: void in(Re &x) — 核心算法函数 void sakura(无参数) — 后缀数组 核心结构体:QAQ0 关键配置: N=5e5+3 说明:for(Re i=0;i<=n;++i)printf("dp[%d]=%lld\n",i,dp[i]);;freopen("456.txt","r",stdin); 适用场景:程序正确性验证(与暴力程序对比测试)
C++ 38 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<set>
#define LL long long
#define Re register int
using namespace std;
const int N=5e5+3;
const LL inf=4e18+5;
int n,opt,A[N],B[N];
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
struct QAQ0{
	int x,g[N];LL tmp,S[N],dp[N];
	inline void sakura(){
		for(Re i=1;i<=n;++i)in(x),S[i]=S[i-1]+x,dp[i]=inf;
		dp[0]=0,g[0]=0;
		for(Re i=1,p=0;i<=n;/*printf("i=%d, p=%d\n",i,p),*/++i)
			for(Re j=0;j<i;++j)
				if(S[i]-S[j]>=S[j]-S[g[j]]&&dp[i]>=(tmp=dp[j]+(S[i]-S[j])*(S[i]-S[j])))
					dp[i]=tmp,g[i]=j,p=j;
//		for(Re i=0;i<=n;++i)printf("dp[%d]=%lld\n",i,dp[i]);
		printf("%lld\n",dp[n]);
	}
}T0;
int main(){
//	freopen("456.txt","r",stdin);
	in(n),in(opt);
	if(n<=5000)T0.sakura();
	fclose(stdin);
	fclose(stdout);
	return 0;
}
对拍 system 1.1.4 对拍
21 行
CPP JSON
【对拍】 对拍(程序正确性测试)相关模板。 说明:break; 适用场景:程序正确性验证(与暴力程序对比测试)
C++ 20 行 CPP
#include<bits/stdc++.h>
#include<windows.h>
#define Re register int 
using namespace std;
int main(){
	Re sec=0.1,HYJ=0;// 随机数据生成时间,大约每0.1秒一次 
	sec*=1e3;
    while(1){
    	printf("第 %d 组数据:\n",++HYJ);
        system("data.exe>data.in");// 随机数据生成到文件 
        system("std.exe<data.in>std.out");// 运行标准程序 
        system("myprogram.exe<data.in>my.out");// 运行自己的程序(可能全WA但能跑通的程序)
        if(system("fc std.out my.out")){// 比较输出文件,fc比较文本文件不同返回1
            system("pause");
			printf("[corrupted string]");
            //break; 
        }
        Sleep(sec);
    }
}
时间随机种子 random 1.1.5 杂项
3 行
CPP JSON
【高质量随机种子生成】 ▪ 使用 chrono::high_resolution_clock::now() 获取高精度时间戳 ▪ time_since_epoch().count() 转为纳秒级整数作为种子 ▪ srand() 设置随机种子 相比 time(0) 的秒级精度,chrono 的纳秒级时间戳提供更好的随机性。适用于需要随机化的算法(随机化快排、哈希防 Hack、模拟退火等)。
C++ 3 行 CPP
auto now = chrono::high_resolution_clock::now();
auto seed = now.time_since_epoch().count();
srand(static_cast<unsigned int>(seed));
扑克牌模板 poker 1.1.5 杂项
215 行
CPP JSON
【扑克牌算法模板】 ▪ Card — 牌面结构:suit(花色 0..3: C/D/H/S)、rank(点数 2..14,A=14) — GetSuit(ch) / GetRank(ch) — 字符→数值转换('C'→0, 'A'→14, 'T'→10 等) — operator< / operator== — 按点数比较/判等 ▪ CombEval — 牌型评估结构(从 5 张手牌 + 公共牌中识别): — Type 枚举:Unspecified→HighCard→Pair→TwoPairs→Three→Straight→Flush→FullHouse→Four→StraightFlush→RoyalFlush(从低到高) — TryHighCard() — 任何牌都至少是高牌 — TryPair() — 判断是否有一对,将对子移到末尾、其余按降序排列 — TryTwoPairs() — 判断是否有两对,将非对子牌移到最前 — TryThree() / TryStraight() / TryFlush() 等 — 依次判断各牌型 适用于德州扑克等扑克游戏的牌力判定与比较。
C++ 215 行 CPP

struct Card
{
    int suit, rank; // 花色 0..3, 点数 2..14

    Card() : Card(0, 0) {}
    Card(char suit_ch, char rank_ch) : Card(GetSuit(suit_ch), GetRank(rank_ch)) {}
    Card(int suit, int rank) : suit(suit), rank(rank) {}

    static int GetSuit(char ch)
    {
        if (ch == 'C') return 0;
        if (ch == 'D') return 1;
        if (ch == 'H') return 2;
        return 3; // 'S'
    }
    static int GetRank(char ch)
    {
        if (ch == 'A') return 14;
        if (ch == 'K') return 13;
        if (ch == 'Q') return 12;
        if (ch == 'J') return 11;
        if (ch == 'T') return 10;
        return ch - '0';
    }

    bool operator < (const Card &rhs) const { return rank < rhs.rank; }
    bool operator == (const Card &rhs) const { return rank == rhs.rank && suit == rhs.suit; }
};


struct CombEval
{
    enum class Type : int
    {
        Unspecified = 0,
        HighCard,      // 高牌
        Pair,          // 一对
        TwoPairs,      // 两对
        Three,         // 三条
        Straight,      // 顺子
        Flush,         // 同花
        FullHouse,     // 葫芦
        Four,          // 四条
        StraightFlush, // 同花顺
        RoyalFlush,    // 皇家同花顺
    };

    CombEval() : CombEval(Type::Unspecified, {}) {}
    CombEval(Type type, const vector<Card> &cards) : type(type), cards(cards) {}

    

    // 高牌 — 任何牌都至少是高牌
    bool TryHighCard() { return true; }

    // 一对 — 找出唯一一对,将其余牌按点数降序排列到前面
    bool TryPair()
    {
        int id = -1;
        for (int i = 0; id == -1 && i <= 3; i++)
            if (cards[i].rank == cards[i + 1].rank)
                id = i;
        if (id == -1) return false;

        int main_rank = cards[id].rank;
        // 将对子移到末尾,其余牌按降序前置
        for (int i = 0, cnt = 0; i <= 4; i++)
            if (cards[i].rank != main_rank)
            {
                for (int j = i; j > cnt; j--)
                    swap(cards[j], cards[j - 1]);
                cnt++;
            }
        return true;
    }

    // 两对 — 找出两对,将非对子牌移到最前
    bool TryTwoPairs()
    {
        int id1 = -1, id2 = -1;
        for (int i = 0; i <= 3; i++)
            if (cards[i].rank == cards[i + 1].rank)
            {
                if (id1 == -1) id1 = i;
                else id2 = i;
                i++;
            }
        if (id1 == -1 || id2 == -1) return false;

        // 将单牌移到最前,便于比较
        for (int j = 8 - id1 * 2 - id2 * 2; j; j--)
            swap(cards[j], cards[j - 1]);
        return true;
    }

    // 三条 — 找出唯一三条,将其余牌按降序前置
    bool TryThree()
    {
        int id = -1;
        for (int i = 0; id == -1 && i <= 2; i++)
            if (cards[i].rank == cards[i + 1].rank && cards[i].rank == cards[i + 2].rank)
                id = i;
        if (id == -1) return false;

        int main_rank = cards[id].rank;
        for (int i = 0, cnt = 0; i <= 4; i++)
            if (cards[i].rank != main_rank)
            {
                for (int j = i; j > cnt; j--)
                    swap(cards[j], cards[j - 1]);
                cnt++;
            }
        return true;
    }

    // 顺子 — 判断是否连续;处理 A-2-3-4-5 特殊顺
    bool TryStraight()
    {
        for (int i = 1; i <= 3; i++)
            if (cards[i].rank != cards[i - 1].rank + 1)
                return false;
        if (cards[4].rank == cards[3].rank + 1)
            return true;
        // A-2-3-4-5 特殊顺:cards = {2,3,4,5,14}
        if (cards[4].rank == 14 && cards[0].rank == 2)
        {
            // 将 A 移到末尾 ⇒ {2,3,4,5,14} → {14,2,3,4,5},便于比较
            for (int i = 4; i; i--)
                swap(cards[i], cards[i - 1]);
            return true;
        }
        return false;
    }

    // 同花 — 所有牌花色相同
    bool TryFlush()
    {
        for (const Card &card : cards)
            if (card.suit != cards[0].suit)
                return false;
        return true;
    }

    // 葫芦 — 三条 + 一对
    bool TryFullHouse()
    {
        if (!TryThree()) return false;
        return cards[0].rank == cards[1].rank;
    }

    // 四条 — 四张相同点数
    bool TryFour()
    {
        if (!TryThree()) return false;
        return cards[1].rank == cards[2].rank;
    }

    // 同花顺
    bool TryStraightFlush() { return TryFlush() && TryStraight(); }

    // 皇家同花顺 — 同花顺且最小牌为 10(10,J,Q,K,A)
    bool TryRoyalFlush()
    {
        if (!TryStraightFlush()) return false;
        return cards[0].rank == 10;
    }

    
    void Sort()
    {
        sort(cards.begin(), cards.end());
    }

    
    bool operator < (const CombEval &rhs) const
    {
        if (type != rhs.type)
            return int(type) < int(rhs.type);
        // 从最大牌开始比较
        for (int i = 4; i >= 0; i--)
            if ((cards[i] < rhs.cards[i]) || (rhs.cards[i] < cards[i]))
                return cards[i] < rhs.cards[i];
        return false;
    }
    bool operator == (const CombEval &rhs) const
    {
        return !(*this < rhs) && !(rhs < *this);
    }

    Type type;
    vector<Card> cards;
};


CombEval GetCombEval(const vector<Card> &cards)
{
    CombEval ret;
    ret.cards = cards;
    ret.Sort();

    bool ok = false;
    if (!ok && ret.TryRoyalFlush())    ret.type = CombEval::Type::RoyalFlush,    ok = true;
    ret.Sort();
    if (!ok && ret.TryStraightFlush()) ret.type = CombEval::Type::StraightFlush, ok = true;
    if (!ok && ret.TryFour())          ret.type = CombEval::Type::Four,          ok = true;
    if (!ok && ret.TryFullHouse())     ret.type = CombEval::Type::FullHouse,     ok = true;
    if (!ok && ret.TryFlush())         ret.type = CombEval::Type::Flush,         ok = true;
    if (!ok && ret.TryStraight())      ret.type = CombEval::Type::Straight,      ok = true;
    if (!ok && ret.TryThree())         ret.type = CombEval::Type::Three,         ok = true;
    if (!ok && ret.TryTwoPairs())      ret.type = CombEval::Type::TwoPairs,      ok = true;
    if (!ok && ret.TryPair())          ret.type = CombEval::Type::Pair,          ok = true;
    if (!ok && ret.TryHighCard())      ret.type = CombEval::Type::HighCard,      ok = true;
    return ret;
}
n进制 转 m进制 n_to_ten 1.1.5 杂项
28 行
CPP JSON
【n进制 转 m进制】 进制转换模板,在不同进制间转换数值表示。 核心函数: int n_to_ten(无参数) — 核心算法函数 void ten_to_m(无参数) — 核心算法函数 关键配置: N=1e5+3
C++ 27 行 CPP
#include<cstdio>
const int N=1e5+3;
int n,m,x,tmp,ansl;char a[N],ans[N];
inline int n_to_ten(){
	int x=0;
	for(int i=0;a[i];++i){
        x*=n;
        if (a[i]>='A'&&a[i]<='F')x+=(a[i]-'A'+10);
        else x+=(a[i]-'0');
   }
   return x;
}
inline void ten_to_m(){
	do{
		tmp=x%m;
		if(tmp<10)ans[++ansl]='0'+tmp;
		else ans[++ansl]='A'+tmp-10;
		x/=m;
		
	}while(x);
}
int main(){
   scanf("%d%s%d",&n,a,&m);
   x=n_to_ten();
   ten_to_m();
   for(int i=ansl;i;--i)printf("%c",ans[i]);puts("");
}
归并排序 optimize 1.1.5 杂项
36 行
CPP JSON
【归并排序】 归并排序模板,O(N log N) 排序 + 统计逆序对。 核心函数: void in(int &x) — 核心算法函数 void merge(Re L,Re mid,Re R) — 合并操作 void Sort(Re L,Re R) — 核心算法函数 关键配置: N=5e5+3 说明:printf("%lld",gs);//�������Ը���
C++ 35 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#define Re register int
const int N=5e5+3;
int fu,n,s[N],b[N];long long gs;char ch;
inline void in(int &x){
	fu=x=0;ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
void merge(Re L,Re mid,Re R){
    Re i=L,j=mid+1,w=L;
    while(i<=mid&&j<=R){
        if(s[i]<=s[j])b[w++]=s[i++];
        else b[w++]=s[j++],gs+=mid-i+1;
    }
    for(;i<=mid;i++)b[w++]=s[i];
    for(;j<=R;j++)b[w++]=s[j];
    for(i=L;i<=R;i++)s[i]=b[i];
}
inline void Sort(Re L,Re R){
    if(L<R){
        Re mid=L+R>>1;
        Sort(L,mid),Sort(mid+1,R);
        merge(L,mid,R);
    }
}
int main(){
    in(n);
    for(Re i=1;i<=n;i++)in(s[i]);
    Sort(1,n);
    for(Re i=1;i<=n;i++)printf("%d ",s[i]); 
}
快排 mysort 1.1.5 杂项
21 行
CPP JSON
【快排】 基础算法/工具类模板。 核心函数: void mysort(int left, int right) — 核心算法函数
C++ 20 行 CPP
#include<bits/stdc++.h>
using namespace std;
int data[100100],n;
void mysort(int left, int right){
	int mid=data[(left+right)/2];
	int i=left,j=right;
	while(i<=j){
		while(data[i]<mid)i++;
		while(data[j]>mid)j--;
		if(i<=j)swap(data[i++],data[j--]);
	}
	if(j>left)mysort(left,j);
	if(i<right)mysort(i,right);
}
int main(){	
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&data[i]);
	mysort(1,n);
	for(int i=1;i<=n;i++)printf("%d ",data[i]);
}
快读 +快输 (int) int+double 1.1.5 杂项
22 行
CPP JSON
【快读 +快输 (int)(int+double)】 快速读入(Fast I/O)模板,加速整数读入。 核心函数: void in(Re &x) — 核心算法函数 void print(Re x) — 核心算法函数 LD LDin(无参数) — 核心算法函数
C++ 21 行 CPP
#include<cstdio>
#define LD double
#define Re register int
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void print(Re x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);putchar(x%10+'0');
}
inline LD LDin(){
	LD X=0,Y=1.0;int f=0;char c=getchar();
	while(c<'0'||c>'9')f|=c=='-',c=getchar(); 
	while(c>='0'&&c<='9')X=X*10+(c^48),c=getchar(); 
	if(c=='.'){c=getchar();while(c>='0'&&c<='9')X+=(Y/=10)*(c^48),c=getchar();}
	return f?-X:X;
}
int main(){}
快速幂+龟速乘 cf_flow 1.1.5 杂项
36 行
CPP JSON
【快速幂+龟速乘】 基础算法/工具类模板。 核心函数: int cf_flow(Re a,Re k) — 核心算法函数 int cf(Re a,Re b) — 核心算法函数 int mi_slow(Re a,Re k) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数
C++ 35 行 CPP
#include<cstdio>
#define LL long long
#define Re register int
int a,b,P;
inline int cf_flow(Re a,Re k){// 递归 快速乘
	if(!k)return 0;
	Re x=1,y=cf_flow(a,k>>1);
	x=(LL)y+y%P;
	if(k&1)x=(LL)x+a%P;
	return x%P;
}
inline int cf(Re a,Re b){// 二进制法 快速乘 
	Re x=0;
	while(b){
		if(b&1)x=(x+a)%P;
		a=a*2%P,b>>=1;
	}
	return x%P;
}
inline int mi_slow(Re a,Re k){// 递归 快速幂 
	if(!k)return 1%P;
	Re x=1,y=mi_slow(a,k>>1);
	x=(LL)y*y%P;
	if(k&1)x=(LL)x*a%P;
	return x%P;
}
inline int mi(Re x,Re k){// 二进制法 快速幂 
	Re s=1;
    while(k){
    	if(k&1)s=(LL)s*x%P;
    	x=(LL)x*x%P,k>>=1;
    }
    return s%P;
}
int main(){}
模拟退火 (A Star not a Tree?) 坐标系随机移动 1.1.5 杂项
51 行
CPP JSON
【模拟退火 (A Star not a Tree?)(坐标系随机移动)】 随机化算法模板(模拟退火/爬山法),求近似全局最优解。 核心函数: void in(Re &x) — 核心算法函数 LD calc(LD x,LD y) — 计算函数 void Srand(Re seed) — 核心算法函数 void fire(无参数) — 核心算法函数 关键配置: N=1e6+3 说明:freopen("123.txt","r",stdin);
C++ 50 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=1e6+3;
int n,HYJ,X[N],Y[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline LD calc(LD x,LD y){
	LD tmp=0;
	for(Re i=1;i<=n;++i)tmp+=sqrt((x-X[i])*(x-X[i])+(y-Y[i])*(y-Y[i]));
	return tmp;
}
inline void Srand(Re seed){
	srand(seed);Re a=rand()%10+1;
	while(a--)srand(rand());
}
LD ans,ansx,ansy;
const LD deltaT=0.99,maxT=4995,minT=1e-12;
inline void fire(){
	LD x=ansx,y=ansy,nowT=maxT;
	while(nowT>minT){
		LD nx=x+((rand()<<1)-RAND_MAX)*nowT;
		LD ny=y+((rand()<<1)-RAND_MAX)*nowT;
		LD nans=calc(nx,ny),deltaE=nans-ans;
		if(deltaE<0)ans=nans,ansx=x=nx,ansy=y=ny;
		else if(exp(-deltaE/nowT)>(LD)rand()/RAND_MAX)x=nx,y=ny;
		nowT*=deltaT;
	}
}
int main(){
//	freopen("123.txt","r",stdin);
	in(HYJ),Srand(20030825);
	while(HYJ--){
		in(n);
		for(Re i=1;i<=n;++i)in(X[i]),in(Y[i]);
		ans=calc(X[1],Y[1]),ansx=X[1],ansy=Y[1];
		fire(),fire(),fire(),fire(),fire();
		printf("%.lf\n",ans);
		if(HYJ)puts("");
	}
}
模拟退火 (均分数据) 序列随机swap 1.1.5 杂项
59 行
CPP JSON
【模拟退火 (均分数据)(序列随机swap)】 随机化算法模板(模拟退火/爬山法),求近似全局最优解。 核心函数: void in(Re &x) — 核心算法函数 void Srand(Re seed) — 核心算法函数 void Random(Re *A,Re n) — 核心算法函数 LD calc(Re *A) — 计算函数 void fire(无参数) — 核心算法函数 关键配置: N=23 说明:freopen("123.txt","r",stdin);
C++ 58 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=23;
int n,m,S,A[N];LD x0;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void Srand(Re seed){
	srand(seed);Re a=rand()%10+1;
	while(a--)srand(rand());
}
inline void Random(Re *A,Re n){
	for(Re i=1;i<=n;++i)swap(A[i],A[rand()%n+1]);
}
int x[N];
inline LD calc(Re *A){
	for(Re i=1;i<=m;++i)x[i]=0;
	for(Re i=1;i<=n;++i){
		Re w=1;
		for(Re j=2;j<=m;++j)if(x[j]<x[w])w=j;
		x[w]+=A[i];
	}
	LD tmp=0;
	for(Re i=1;i<=m;++i)tmp+=(x[i]-x0)*(x[i]-x0);
	return tmp/m;
}
int nowA[N],ansA[N];LD ans;
const LD deltaT=0.995,maxT=4995,minT=1e-15;
inline void fire(){
	for(Re i=1;i<=n;++i)nowA[i]=ansA[i];LD nowT=maxT;
	while(nowT>minT){
		Re x=rand()%n+1,y=rand()%n+1;
		swap(nowA[x],nowA[y]);
		LD nans=calc(nowA),deltaE=nans-ans;
		if(deltaE<0){for(Re i=1;i<=n;++i)ansA[i]=nowA[i];ans=nans;}
		else if(exp(-deltaE/nowT)>(LD)rand()/RAND_MAX);
		else swap(nowA[x],nowA[y]);
		nowT*=deltaT;
	}
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m);
	for(Re i=1;i<=n;++i)in(A[i]),S+=A[i];x0=(LD)S/m;
	for(Re i=1;i<=n;++i)ansA[i]=A[i];
	Srand(965579261),Random(ansA,n),Srand(20030825);
	ans=calc(ansA),fire(),fire(),fire(),fire(),fire();
	printf("%.2lf\n",sqrt(ans));
}
高精度乘法 普通写法 1.1.5 杂项
29 行
CPP JSON
【高精度乘法(普通写法)】 高精度/大整数运算模板。
C++ 28 行 CPP
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int main(){
    char a1[10005],b1[10005];
    int a[100005],b[100005],c[100005],lena,lenb,lenc,i,j,x;
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    gets(a1);gets(b1);
    lena=strlen(a1);lenb=strlen(b1);
    for(i=0;i<=lena-1;i++) a[lena-i]=a1[i]-48;
    for(i=0;i<=lenb-1;i++) b[lenb-i]=b1[i]-48;
	for(i=1;i<=lena;i++){
	    x=0;                                               
	    for(j=1;j<=lenb;j++){
	        c[i+j-1]=a[i]*b[j]+x+c[i+j-1];
	        x=c[i+j-1]/10;
	        c[i+j-1] %= 10;
	    }
	    c[i+lenb]=x;                             
	}
	lenc=lena+lenb;
	while(c[lenc]==0&&lenc>1)lenc--;
	for(i=lenc;i>=1;i--)cout<<c[i];
	cout<<endl;
}
高精度加法 普通写法 1.1.5 杂项
24 行
CPP JSON
【高精度加法(普通写法)】 高精度/大整数运算模板。
C++ 23 行 CPP
#include<bits/stdc++.h>
using namespace std;
int a[1000],b[1000],c[1000];
char st[1000];
int main(){
    scanf("%s",st);
    int lena,lenb,lenc;
    lena =strlen(st);
    for(int i=1;i<=lena;i++)a[i]=st[lena-i]-'0';
    scanf("%s",st);
    lenb=strlen(st);
    for(int i=1;i<=lenb;i++)b[i]=st[lenb-i]-'0';
    if(lena>lenb)lenc=lena;
    else lenc=lenb;
    for(int i=1;i<=lenc;i++){
        c[i]=a[i]+b[i]+c[i];
        c[i+1]=c[i+1]+c[i]/10;
        c[i]=c[i]%10;
    }
    if(c[lenc+1])lenc++;
    for(int i=lenc;i>0;i--)printf("%d",c[i]);
    return 0;	
}
高精模板 (史上最全没有之一) 结构体 1.1.5 杂项
235 行
CPP JSON
【高精模板 (史上最全没有之一)(结构体)】 基础算法/工具类模板。 核心函数: void CL(无参数) — 核心算法函数 void pr(无参数) — 核心算法函数 void re_l(无参数) — 核心算法函数 LL toint(无参数) — 核心算法函数 核心结构体:Int 关键配置: N=1e4+10
C++ 234 行 CPP
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int base=1e8;
const int N=1e4+10;
int aux[N<<3];
struct Int{
    int s[N],l;
    inline void CL(){l=0;memset(s,0,sizeof(s));}
    inline void pr(){
        printf("%d",s[l]);
        for(Re i=l-1;i;i--)printf("%08d",s[i]);
    }
    inline void re_l(){
        Re i,x=0,k=1,L=0,fl,o;char c=getchar();
        for(;c<'0'||c>'9';c=getchar());
        for(;c>='0'&&c<='9';c=getchar()){if(!(L-1)&&!aux[L])L--;aux[++L]=c-'0';}
        CL();l=L/8+((o=L%8)>0);
        for(i=1;i<=o;i++)x=x*10+aux[i];
        if(o)s[l]=x;fl=!o?l+1:l;
        for(i=o+1,x=0;i<=L;i++,k++){
            x=x*10+aux[i];
            if(!(k^8))s[--fl]=x,x=k=0;
        }
        if(!l)l=1;
    }
    inline LL toint(){
        LL x=0;
        for(Re i=l;i;i--)x=x*base+s[i];
        return x;
    }
    inline Int operator=(Re b){
        CL();
        do s[++l]=b%base,b/=base;while(b>0);
        return *this;
    }
    inline Int operator=(LL b){
        CL();
        do s[++l]=b%base,b/=base;while(b>0);
        return *this;
    }
    inline Int operator+(const Re &b){
        Int c=*this;LL x=b;
        for(Re i=1;i<=l&&x;i++)x=x+c.s[i],c.s[i]=x%base,x/=base;
        if(x)c.s[++c.l]=x;
        return c;
    }
    inline Int operator+(const LL &b){
        Int c=*this;LL x=b;
        for(Re i=1;i<=l&&x;i++)x=x+c.s[i],c.s[i]=x%base,x/=base;
        if(x)c.s[++c.l]=x;
        return c;
    }
    inline Int operator+(Int &b){
        if(b.l<3)return *this+b.toint();
        Int c;LL x=0;Re k=l<b.l?b.l:l;c.CL(),c.l=k;
        for(Re i=1;i<=k;i++)x=x+s[i]+b.s[i],c.s[i]=x%base,x/=base;
        if(x)c.s[++c.l]=x;
        return c;
    }
    inline Int operator-(const Int &b){
        Int c,d=*this;LL x=0;c.CL();
        for(Re i=1;i<=l;i++){
            if((x=d.s[i])<b.s[i])d.s[i+1]--,x+=base;
            c.s[i]=x-b.s[i];
        }
        c.l=l;
        for(;!c.s[c.l]&&c.l>1;c.l--);
        return c;
    }
    inline Int operator-(const Re &b){Int c;return *this-(c=b);}
    inline Int operator-(const LL&b){Int c;return *this-(c=b);}
    inline Int operator*(const Re &b){
        Int c;LL x=0;c.CL();
        for(Re i=1;i<=l;i++)x=x+1LL*s[i]*b,c.s[i]=x%base,x/=base;
        for(c.l=l;x;x/=base)c.s[++c.l]=x%base;
        return c;
    }
    inline Int operator*(Int&b){
        if(b.l<2)return *this*b.toint();
        Int c;LL x;Re i,j,k;c.CL();
        for(i=1;i<=l;i++){
            x=0;
            for(j=1;j<=b.l;j++)x=x+1LL*s[i]*b.s[j]+c.s[k=i+j-1],c.s[k]=x%base,x/=base;
            if(x)c.s[i+b.l]=x;
        }
        for(c.l=l+b.l;!c.s[c.l]&&c.l>1;c.l--);
        return c;
    }
    inline Int operator*(const LL &b){
        Int c;
        if(b>2e9){c=b;return *this*c;}
        LL x=0;c.CL();
        for(Re i=1;i<=l;i++)x=x+b*s[i],c.s[i]=x%base,x/=base;
        for(c.l=l;x;x/=base)c.s[++c.l]=x%base;
        return c;
    }
    inline Int operator/(const Re &b){
        Int c;LL x=0;c.CL();
        for(Re i=l;i;i--)c.s[i]=(x*base+s[i])/b,x=(x*base+s[i])%b;
        for(c.l=l;!c.s[c.l]&&c.l>1;c.l--);
        return c;
    }
    inline Int operator/(const LL&b){
        Int c;LL x=0;c.CL();
        for(Re i=l;i;i--)c.s[i]=(x*base+s[i])/b,x=(x*base+s[i])%b;
        for(c.l=l;!c.s[c.l]&&c.l>1;c.l--);
        return c;
    }
    inline Int operator/(Int&b){
        if(b.l<2)return *this/b.toint();
        Int c,d;Re i,j,le,r,mid,k;c.CL();d.CL();
        for(i=l;i;i--){
            for(j=++d.l;j>1;j--)d.s[j]=d.s[j-1];
            d.s[1]=s[i];
            if(d<b)continue;
            le=k=0;r=base-1;
            while(le<=r){
                mid=(le+r)>>1;
                if(b*mid<=d)le=mid+1,k=mid;
                else r=mid-1;
            }
            c.s[i]=k,d=d-b*k;
        }
        for(c.l=l;!c.s[c.l]&&c.l>1;c.l--);
        return c;
    }
    inline Int operator%(const Re &b){
        Int c;LL x=0;c.CL();
        for(Re i=l;i;i--)x=(x*base+s[i])%b;
        return c=x;
    }
    inline Int operator%(const LL&b){
        Int c;LL x=0;c.CL();
        for(Re i=l;i;i--)x=(x*base+s[i])%b;
        return c=x;
    }
    inline Int operator%(Int&b){
        if(b.l<2)return *this%b.toint();
        Int c;Re i,j,le,r,mid,k;c.CL();
        for(i=l;i;i--){
            for(j=++c.l;j>1;j--)c.s[j]=c.s[j-1];
            c.s[1]=s[i];
            if(c<b)continue;
            le=k=0,r=base-1;
            while(le<=r){
                mid=(le+r)>>1;
                if(b*mid<=c)le=mid+1,k=mid;
                else r=mid-1;
            }
            c=c-b*k;
        }
        for(;!c.s[c.l]&&c.l>1;c.l--);
        return c;
    }
    inline Int operator+=(Int&b){return *this=*this+b;}
    inline Int operator+=(LL&b){return *this=*this+b;}
    inline Int operator+=(Re &b){return *this=*this+b;}
    inline Int operator-=(Int&b){return *this=*this-b;}
    inline Int operator-=(LL&b){return *this=*this-b;}
    inline Int operator-=(Re &b){return *this=*this-b;}
    inline Int operator*=(Int&b){return *this=*this*b;}
    inline Int operator*=(LL&b){return *this=*this*b;}
    inline Int operator*=(Re &b){return *this=*this*b;}
    inline Int operator/=(Int&b){return *this=*this/b;}
    inline Int operator/=(LL&b){return *this=*this/b;}
    inline Int operator/=(Re &b){return *this=*this/b;}
    inline Int operator%=(Int&b){return *this=*this%b;}
    inline Int operator%=(LL&b){return *this=*this%b;}
    inline Int operator%=(Re &b){return *this=*this%b;}
    inline bool operator<(const Int&b)const{
        if(l^b.l)return l<b.l;
        for(Re i=l;i;i--)if(s[i]^b.s[i])return s[i]<b.s[i];
        return 0;
    }
    inline bool operator<=(const Int&b)const{
        if(l^b.l)return l<b.l;
        for(Re i=l;i;i--)if(s[i]^b.s[i])return s[i]<b.s[i];
        return 1;
    }
    inline bool operator>(const Int&b)const{
        if(l^b.l)return l>b.l;
        for(Re i=l;i;i--)
            if(s[i]^b.s[i])return s[i]>b.s[i];
        return 0;
    }
    inline bool operator>=(const Int&b)const{
        if(l^b.l)return l>b.l;
        for(Re i=l;i;i--)if(s[i]^b.s[i])return s[i]>b.s[i];
        return 1;
    }
    inline bool operator==(const Int&b)const{
        if(l^b.l)return 0;
        for(Re i=l;i;i--)if(s[i]^b.s[i])return 0;
        return 1;
    }
    inline bool operator!=(const Int&b)const{
        if(l^b.l)return 1;
        for(Re i=l;i;i--)if(s[i]^b.s[i])return 1;
        return 0;
    }
    inline bool operator<(LL b)const{Int c;return *this<(c=b);}
    inline bool operator<=(LL b)const{Int c;return *this<=(c=b);}
    inline bool operator>(LL b)const{Int c;return *this>(c=b);}
    inline bool operator>=(LL b)const{Int c;return *this>=(c=b);}
    inline bool operator==(LL b)const{Int c;return *this==(c=b);}
    inline bool operator!=(LL b)const{Int c;return *this!=(c=b);}
    inline bool operator<(Re b)const{Int c;return *this<(c=b);}
    inline bool operator<=(Re b)const{Int c;return *this<=(c=b);}
    inline bool operator>(Re b)const{Int c;return *this>(c=b);}
    inline bool operator>=(Re b)const{Int c;return *this>=(c=b);}
    inline bool operator==(Re b)const{Int c;return *this==(c=b);}
    inline bool operator!=(Re b)const{Int c;return *this!=(c=b);}
};
Int a,b;
int main(){
    a.re_l();
    b.re_l();
    a.pr();printf("+");b.pr();printf("=");(a+b).pr();printf("\n");
    a.pr();printf("-");b.pr();printf("=");
    if(a<b){putchar('-');(b-a).pr();}
    else(a-b).pr();printf("\n");
    a.pr();printf("*");b.pr();printf("=");(a*b).pr();printf("\n");
    a.pr();printf("/");b.pr();printf("=");(a/b).pr();printf("\n");
    a.pr();printf("%%");b.pr();printf("=");(a%b).pr();printf("\n");
    if(a<b)printf("a<b\n");
    if(a<=b)printf("a<=b\n");
    if(a>b)printf("a>b\n");
    if(a>=b)printf("a>=b\n");
    if(a==b)printf("a==b\n");
    if(a!=b)printf("a!=b\n");
}
已复制