【/ɔɪ:/】模板
|
259
|
OI
 警告
别tm偷懒直接复制模板，自己敲一遍

前言

这篇文章仅用于存放各种模板，会简略介绍，不写注释且适当压行，有些会省略缺省源，具体原理请在 /ɔɪ:/ 查看。

正在汇总中……

杂项

缺省源

主要 tuple 是 C++17 的东西但是 CCF 的测评机可以编译通过，学校里部分机房不行。

缺省源
#include<bits/stdc++.h>
using namespace std;
#define dbg(x) cerr<<#x<<':'<<(x)<<' '
#define dbe(x) cerr<<#x<<':'<<(x)<<endl
#define eb emplace_back
#define ep emplace
#define endl '\n'
using ll=long long;
using vi=vector<int>;
using vl=vector<ll>;
using tp=tuple<int,int>;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    
    return 0;
}

对拍

对拍通常由 4 个程序组成：要对拍的程序(zj.cpp)，一定对的暴力程序(bl.cpp)，造数据程序(sj.cpp)，对拍程序(dp.cpp)。（注意这是 Linux 下的对拍，在 windows 下使用需要将 diff 改为 fc，并删去 ./）

对拍
#include<bits/stdc++.h>
using namespace std;
int main(){
    system("g++ -O2 zj.cpp -o zj -Wall -static -std=c++14");
    system("g++ -O2 bl.cpp -o bl -Wall -static -std=c++14");
    system("g++ -O2 sj.cpp -o sj -Wall -static -std=c++14");
    int t=1e8;
    for(int i=1;i<=t;i++){
        cout<<"# "<<i<<endl;
        FILE *fp=fopen("seed.in","w");
        fprintf(fp,"%d",i);
        fclose(fp);
        system("./sj < seed.in > dp.in");
        system("./bl < dp.in > dp.ans");
        double st=clock();
        system("./zj < dp.in > dp.out");
        double ed=clock();
        cout<<ed-st<<" ms\n";
        if(system("diff dp.out dp.ans")){
            cout<<"WA\n";
            break;
        }
        cout<<"AC\n";
    }
    return 0;
}

离散化

离散化
vi lsh;
//lsh.eb(someting);
sort(lsh.begin(),lsh.end());
lsh.resize(unique(lsh.begin(),lsh.end())-lsh.begin());
auto LSH=[&](int x){return lower_bound(lsh.begin(),lsh.end(),x)-lsh.begin();};

高精度

bignum
struct bignum{
	vi a;
	#define bn bignum
	bn():a({0}){}
	bn(int x){if(!x)a={0};else while(x)a.eb(x%10),x/=10;}
	bn(vi x):a(x){}
	bn&operator=(int x){if(!x)a={0};else while(x)a.eb(x%10),x/=10;return *this;}
	inline int size()const{return a.size();}
	bool operator<(const bn&b)const{
		if(a.size()!=b.size())return a.size()<b.size();
		for(int i=a.size()-1;i>=0;i--){
			if(a[i]!=b.a[i])return a[i]<b.a[i];
		}
		return false;
	}
	bool operator==(const bn&b)const{return a==b.a;}
	bool operator!=(const bn&b)const{return !(*this==b);}
	bool operator<=(const bn&b)const{return *this<b||*this==b;}
	friend bn operator+(bn a,bn b){
		if(a.size()<b.size())swap(a,b);
		int jw=0;
		for(int i=0;i<a.size();i++){
			a.a[i]+=jw,jw=0;
			if(i<b.size())a.a[i]+=b.a[i];
			if(a.a[i]>9)a.a[i]-=10,jw=1;
		}
		if(jw)a.a.eb(jw);
		return a;
	}
	friend bn operator-(bn a,bn b){//abs
		if(a<b)swap(a,b);
		int jw=0;
		for(int i=0;i<a.size();i++){
			a.a[i]-=jw,jw=0;
			if(i<b.size())a.a[i]-=b.a[i];
			if(a.a[i]<0)a.a[i]+=10,jw=1;
		}
		while(a.size()>1&&a.a.back()==0)a.a.pop_back();
		return a;
	}
	friend bn operator*(const bn&a,const bn&b){
		vi c(a.size()+b.size());
		for(int i=0;i<a.size();i++){
			for(int j=0;j<b.size();j++){
				c[i+j]+=a.a[i]*b.a[j];
			}
		}
		int jw=0;
		for(int i=0;i<(int)c.size();i++){
			c[i]+=jw,jw=0;
			if(c[i]>9)jw=c[i]/10,c[i]%=10;
		}
		while(c.size()>1&&c.back()==0)c.pop_back();
		if(jw>0)c.eb(jw);
		return c;
	}
	friend bn operator/(const bn&a,const bn&b){
		vi c(a.size());
		bn yu;
		for(int i=a.size()-1;i>=0;i--){
			yu*=(bn)10;
			yu+=(bn)a.a[i];
			while(b<=yu)yu-=b,c[i]++;
		}
		while(c.size()>1&&c.back()==0)c.pop_back();
		return c;
	}
	friend bn operator%(const bn&a,const bn&b){
		bn yu;
		for(int i=a.size()-1;i>=0;i--){
			yu*=(bn)10,yu+=(bn)a.a[i];
			while(b<=yu)yu-=b;
		}
		return yu;
	}
	
	bn&operator+=(const bn&x){return *this=*this+x;}
	bn&operator-=(const bn&x){return *this=*this-x;}
	bn&operator*=(const bn&x){return *this=*this*x;}
	bn&operator/=(const bn&x){return *this=*this/x;}
	
	friend istream&operator>>(istream&is,bn&x){
		char c;is.get(c);
		while(!('0'<=c&&c<='9'))is.get(c);
		x.a.clear();
		while('0'<=c&&c<='9'){x.a.eb(c-'0');is.get(c);}
		reverse(x.a.begin(),x.a.end());
		return is;
	}
	friend ostream&operator<<(ostream&os,const bn&x){
		for(int i=x.size()-1;i>=0;i--)os<<x.a[i];
		return os;
	}
};

STL

unordered_map

重定义哈希函数：

unordered_map
struct S{
    unsigned int x,y;
    bool operator==(S a)const{
        return x==a.x&&y==a.y;
    }
};
struct SHash{
    ull operator()(S a)const{
        return (a.x<<32)+a.y;
    }
};
unordered_map<S,int,SHash>ma;

deque

手写 deque：

deque
template<typename T>struct Deq{
	vector<T>dq;
	int head,tail;
	Deq(int size=1e6):head(size),tail(size-1){
		dq.resize(size*2+1);
	}
	void push_front(T x){dq[--head]=x;}
	void push_back(T x){dq[++tail]=x;}
	void pop_front(){head++;}
	void pop_back(){tail--;}
	T front(){return dq[head];}
	T back(){return dq[tail];}
	int size(){return tail-head+1;}
	bool empty(){return head==tail+1;}
};

数据结构

树状数组

bit
struct bit{
    int n;
    vi c;
    bit(){}
    bit(int n):n(n){
        c.resize(n+1);
    }
    void add(int x,int d){
        while(x<=n)c[x]+=d,x+=x&-x;
    }
    int cha(int x){
        int ans=0;
        while(x)ans+=c[x],x-=x&-x;
        return ans;
    }
    int ef(int k){
        int x=1<<(31-__builtin_clz(n)),sc=0;
        while((x&-x)>1){
            if(x>n||c[x]>=k)sc=x,x-=(x&-x)>>1;
            else k-=c[x],x+=(x&-x)>>1;
        }
        return k-c[x]?sc:x;
    }
};

线段树

自己敲，看什么模板。

字符串

公约同 /ɔɪ:/

最小表示法

最小表示法
int n=s.size();
s=s+s;
int i=0,j=0,k=0;
while(i<n&&j<n&&k<n){
    if(i==j)j++;
    if(s[i+k]==s[j+k])k++;
    else if(s[i+k]<s[j+k])j=j+k+1,k=0;
    else i=i+k+1,k=0;
}
//ans=min(s.substr(i,n),s.substr(j,n));

manacher

记得在字符串中加入 #

manacher
vi d(n,1);
  int p=0,r=0;
  for(int i=1;i<n;i++){
	if(i<r)d[i]=min(d[p*2-i],r-i+1);
	while(0<=i-d[i]&&i+d[i]<n&&s[i-d[i]]==s[i+d[i]])d[i]++;
	if(i+d[i]-1>r)r=i+d[i]-1,p=i;
}

Z Algorithm

Z算法
vi z(n,0);
int l=0,r=0;
for(int i=1;i<n;i++){
    if(i<r)z[i]=min(z[i-l],r-i+1);
    while(i+z[i]<n&&s[z[i]]==s[i+z[i]])z[i]++;
    if(i+z[i]-1>r)r=i+z[i]-1,l=i;
}
z[0]=n;

KMP

KMP
vi pi(n+1);
for(int i=2;i<=n;i++){
    int j=pi[i-1];
    while(j>0&&s[j+1]!=s[i])j=pi[j];
    j+=(s[j+1]==s[i]);
    pi[i]=j;
}

数学&数论

modint

modint
template<int Mod>struct modint{
	int x;
	modint():x(0){}
	modint(int x):x(x<0?x+Mod:x){}
	modint& operator=(int y){return x=(y<0?y+Mod:y),*this;}
	modint operator+(const modint& y){return x+y.x>=Mod?x+y.x-Mod:x+y.x;}
	modint operator-(const modint& y){return x-y.x<0?x-y.x+Mod:x-y.x;}
	modint operator*(const modint& y){return (ll)x*y.x%Mod;}
	modint operator^(int y)const{
		modint ans=1,a=*this;
		while(y){
			if(y&1)ans=ans*a;
			a=a*a;
			y>>=1;
		}
		return ans;
	}
	modint operator/(const modint& y){return *this*(y^(Mod-2));}
	modint& operator+=(const modint& y){return *this=*this+y;}
	modint& operator-=(const modint& y){return *this=*this-y;}
	modint& operator*=(const modint& y){return *this=*this*y;}
	modint& operator^=(int y){return *this=*this^y;}
	modint& operator/=(const modint& y){return *this=*this/y;}
	bool operator==(const modint& y){return x==y.x;}
	bool operator!=(const modint& y){return x!=y.x;}
	friend istream& operator>>(istream& is,modint& y){return is>>y.x;}
	friend ostream& operator<<(ostream& os,const modint& y){return os<<y.x;}
};
const int P=1e9+7;
using mint=modint<P>;

快速幂

快速幂
int ksm(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=(ll)ans*a%P;
        a=(ll)a*a%P;
        b>>=1;
    }
    return ans;
}

线性筛

线性筛
vi prm,v(N+1);
for(int i=2;i<=N;i++){
    if(v[i]==0)v[i]=i,prm.emplace_back(i);
    for(auto p:prm){
        if(p*i>N||v[i]<p)break;
        v[i*p]=p;
    }
}

EXGCD

做了些许简化。

exgcd
function<int(int,int,ll&,ll&)>exgcd=[&](int a,int b,ll& x,ll& y){
    if(b==0){x=1,y=0;return a;}
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
};

线性组合计数(线性求逆元)

功能有快速幂，求 inv[i],fct[i],invfct[i]，求 $\binom{n}{m}$ 和 $\binom{n}{a_1,a_2,\dots ,a_k}$。放在main函数外面,记得使用前要调用init初始化。

线性求逆元
const int P=1e9+9;
namespace modint{
    vi fct,inv,invfct;
    int ksm(int a,int b){
        int ans=1;
        while(b){
            if(b&1)ans=(ll)ans*a%P;
            a=(ll)a*a%P;
            b>>=1;
        }
        return ans;
    }
    void init(int n){
        fct.resize(n+1);
        inv.resize(n+1);
        invfct.resize(n+1);
        fct[0]=1;
        for(int i=1;i<=n;i++){
            fct[i]=(ll)fct[i-1]*i%P;
        }
        invfct[n]=ksm(fct[n],P-2);
        for(int i=n;i>=1;i--){
            inv[i]=(ll)fct[i-1]*invfct[i]%P;
            invfct[i-1]=(ll)i*invfct[i]%P;
        }
    }
    int binom(int n,int m){
        return (ll)fct[n]*invfct[m]%P*invfct[n-m]%P;
    }
    int binom(int n,vi m){
        int ans=fct[n];
        for(auto v:m){
            ans=(ll)ans*invfct[v]%P;
        }
        return ans;
    }
}

整数分块

整数分块
int sum=0;
for(int l=1,r;l<=n;l=r+1){
    r=n/(n/l);
    sum+=(r-l+1)*(n/l);
}

矩阵乘法

矩阵乘法
struct JZ{
    vector<vl>a;
    int n,m;
    JZ(){}
    JZ(vector<vl>&a):a(a),n(a.size()){
        m=(a.size()?a[0].size():0);
    }
    JZ(int n,int m):n(n),m(m){
        a.resize(n,vl(m));
    }
    friend JZ operator*(const JZ& a,const JZ& b){
        vector<vl>c(a.n,vl(b.m));
        for(int i=0;i<a.n;i++){
            for(int j=0;j<b.m;j++){
                for(int k=0;k<a.m;k++){
                    c[i][j]+=a.a[i][k]*b.a[k][j];
                }
            }
        }
        return c;
    }
};

高斯消元

模板题 P3389 【模板】高斯消元法：

高斯消元
#include<bits/stdc++.h>
using namespace std;
#define dbg(x) cerr<<#x<<':'<<(x)<<' '
#define dbe(x) cerr<<#x<<':'<<(x)<<endl
#define eb emplace_back
using ll=long long;
using vi=vector<int>;
using vl=vector<ll>;
using tp=tuple<int,int>;
using db=long double;
db eps=1e-7;
bool is0(db x){return -eps<x&&x<eps;}
struct FC{
    int m;
    vector<db>a;
    db b;
    FC(){}
    FC(int m):m(m){a.resize(m+1);}
    friend ostream& operator<<(ostream& os,const FC& x){
        for(int i=1;i<=x.m;i++)os<<x.a[i]<<" ";
        os<<"| "<<x.b;
        return os;
    }
    friend istream& operator>>(istream& is,FC& x){
        for(int i=1;i<=x.m;i++)is>>x.a[i];
        is>>x.b;
        return is;
    }
    friend FC operator*(FC x,db y){
        for(int i=1;i<=x.m;i++)x.a[i]*=y;
        x.b*=y;
        return x;
    }
    friend FC operator+(FC x,FC y){
        for(int i=1;i<=x.m;i++)x.a[i]+=y.a[i];
        x.b+=y.b;
        return x;
    }
};
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,m;
    cin>>n;
    m=n;
    vector<FC>fc(n+1,FC(m));
    for(int i=1;i<=n;i++){
        cin>>fc[i];
    }
    vi zy(m+1);
    for(int i=1,j=1;i<=n&&j<=m;i++,j++){
        while(j<=m){
            bool sf=false;
            for(int k=i;k<=n;k++){
                if(!is0(fc[k].a[j])){
                    swap(fc[i],fc[k]),sf=true;
                    break;
                }
            }
            if(!sf)j++;
            else break;
        }
        if(j>m)break;
        zy[j]=i;
        for(int k=1;k<=n;k++){
            if(is0(fc[k].a[j])||k==i)continue;
            db o=-fc[k].a[j]/fc[i].a[j];
            fc[k]=fc[k]+fc[i]*o;
        }
    }
    bool no_sol=false,inf_sol=(*min_element(zy.begin()+1,zy.end())==0);
    for(int i=1;i<=n;i++){
        if(is0(fc[i].b))continue;
        bool sf=true;
        for(int j=1;j<=m;j++){
            if(!is0(fc[i].a[j])){sf=false;break;}
        }
        if(sf){no_sol=true;break;}
    }
    if(no_sol||inf_sol)cout<<"No Solution\n";
    else{
        cout<<fixed<<setprecision(2);
        for(int j=1;j<=m;j++){
            cout<<fc[zy[j]].b/fc[zy[j]].a[j]<<endl;
        }
    }
    return 0;
}
C++OI模板

评论

  1. Peiyuan
    2 月前
    2025-10-06 14:34:32

    %%%%%%%%%%%%

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇