C++竞赛常用模板
·
C++模板自取
From: BJHAK
template
干掉病毒软件
system函数可以调用cmd指令，taskkill是cmd指令中结束进程的指令，/f意思是强制结束进程，可以针对某些顽固病毒软件（吗）
#include<bits/stdc++.h>
signed main(){
std::system("taskkill /f /im StudentMain.exe");
return 0;
}
个人基础模板
TIP：c_str函数可以实现字符串拼接，对于freopen中题目名称可以实现只需要修改file函数传入内容即可修改传入文件名称
#include<bits/stdc++.h>
#define inf (long long)0x3f3f3f3f3f3f3f3f
#define sup (long long)0xc0c0c0c0c0c0c0c0
#define int long long
using namespace std;
const int e=1e3+10;
void file(const string topic){
freopen((topic+".in").c_str(),"r",stdin);
freopen((topic+".out").c_str(),"w",stdout);
return;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cout<<fixed<<setprecision(0);
// file("template");
return 0;
}
随机数据生成
TIP：调用此函数之后，rand函数会返回伪随机数，mod是你要取随机数的最大值
#include<bits/stdc++.h>
using namespace std;
const int mod=100;
void random_data(){
srand(time(0)+clock());
return;
}
signed main(){
random_data();
cout<<rand()%mod+1<<'\n';
return 0;
}
EdisonBa对拍 自测
TIP：不用freopen读入文件,std_为你的代码文件，force为暴力文件，data_为随机数据生成文件，n为对拍次数，更改变量名内容即可快速更改指令内容
注意FC指令在cmd中若两文件不同则返回为非0值
具体内容解释：
cmd中A.exe < B.in > C.out意思是运行A程序，让A程序读入B文件，A程序输出结果读入C文件，可以实现不用
freopen就能快速运行程序并输出
fc A.out A.ans意思是比较A.out和A.ans文件内容是否相同，用于比对预期输出文件和实际输出文件
本程序通过字符串拼接和循环提高了操作效率
#include<bits/stdc++.h>
using namespace std;
const int n=10;
bool edisonba(){
const string std_="std",force="force",data_="data";
system((data_+".exe > "+data_+".in").c_str() );
system((force+".exe < "+data_+".in > "+std_+".ans").c_str() );
system((std_+".exe < "+data_+".in > "+std_+".out").c_str() );
if(system(("fc "+std_+".out "+std_+".ans").c_str())!=0)
return 0;
return 1;
}
signed main(){
for(int i=1;i<=n;i++)
if(edisonba()==0){
cout<<i<<'\n';
break;
}
return 0;
}
/*
data.exe > data.in
force.exe < data.in > std.ans
std.exe < data.in > std.out
fc std.out std.ans
*/
EdisonBa对拍 他测
TIP：将现有数据文件进行对拍，number是数据文件的编号，data_是数据文件名称，std是正解代码文件
具体内容解释：
to_string函数可以把数字转化成字符串，例如1转化成“1”
对于一些官方给出的固定格式的多个答案文件，例如题目名+数字，通过循环、字符串拼接操作简化操作流程
#include<bits/stdc++.h>
using namespace std;
const int n=10;
bool edisonba(const string number){
const string data_="data",std_="std";
system((std_+".exe < "+data_+number+".in > "+std_+".out").c_str() );
if(system(("fc "+std_+".out "+std_+number+".ans").c_str() )!=0)
return 0;
return 1;
}
signed main(){
for(int i=1;i<=n;i++)
if(edisonba(to_string(i))==0){
cout<<i<<'\n';
break;
}
return 0;
}
/*
std.exe < data+number.in > std.out
fc std.out std+number.ans
*/
数论
素数筛 $ O(n) $
TIP: 欧拉筛
const int e=1e3+10;
int n,isprime[e],prime[e],top;
void init(){
for(int i=1;i<=n;i++)
isprime[i]=1;
return;
}
void find_prime(){
init();
for(int i=2;i<=n;i++){
if(isprime[i]==1)
prime[++top]=i;
for(int j=1;j<=top&&i*prime[j]<=n;j++){
isprime[i*prime[j]]=0;
if(i%prime[j]==0)break;
}
}
return;
}
二分 $ O(log(n)) $
TIP:存储最大满足条件的h，check函数自己设计
int n,ans=-1;
bool check(int h){
return 0;
}
void bound(){
int l=1,r=n;
while(l<=r){
int mid=l+r>>1;
if(check(mid)==1)
l=mid+1,ans=mid;
else r=mid-1;
}
return;
}
快速幂 $ O(log(n)) $
TIP: x y m o d x^y mod xymod
int fast_pow(int x,int y,int mod){
int res=1;
while(y){
if(y&1)
res=res*x%mod;
x=x*x%mod,y>>=1;
}
return res;
}
LCIS $ O(n^2) $
TIP: $ dp[i][j] $ 为以 $ b[j] $ 结尾 的最长公共上升子序列
转移方程推导
d p [ i ] [ j ] = d p [ i ] [ j − 1 ] dp[i][j] =dp[i][j-1] dp[i][j]=dp[i][j−1] 当 $ a[i]!=b[j] $ 时
$ dp[i][j]=max(dp[i-1][k]+1) $ 当 $ k<=j $ 且 $ b[k]<b[j] $
第三层枚举K的循环可被优化至二层
const int e=1e3+10;
int n,a[e],b[e],dp[e][e],ans;
void solve(){
for(int i=1;i<=n;i++){
int k=0;
for(int j=1;j<=n;j++){
dp[i][j]=dp[i-1][j];
if(a[i]==b[j])
dp[i][j]=max(dp[i][j],dp[i-1][k]+1);
if(b[j]<a[i]&&dp[i-1][j]>dp[i-1][k])
k=j;
ans=max(ans,dp[i][j]);
}
}
return;
}
图论
拓扑排序
TIP: 仅适用于有向图
const int e=1e3+10;
int n,dg[e],a[e],top;
vector<int>mp[e];
void init(){
for(int i=1;i<=n;i++)
for(auto j:mp[i])
dg[j]++;
return;
}
void topo(){
init();
queue<int>q;
for(int i=1;i<=n;i++)
if(dg[i]==0)
q.push(i);
while(q.size()){
int p=q.front();
q.pop();
a[++top]=p;
for(auto i:mp[p]){
dg[i]--;
if(dg[i]==0)
q.push(i);
}
}
return;
}
Floyd O ( n 3 ) O(n^3) O(n3)
TIP: 多源最短路, 邻接矩阵，注意初始化
$ mp[i][j] $ 为i到j的边的权值
const int e=1e3+10;
int n,mp[e][e];
void init(){
memset(mp,0x3f,sizeof(mp));
for(int i=1;i<=n;i++)
mp[i][i]=0;
return;
}
void floyd(){
init();
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
return;
}
Dijkstra O ( n ∗ l o g ( n ) ) O(n*log(n)) O(n∗log(n))
TIP: 单源最短路，堆优化，邻接表存图
struct node{
int h,w;
bool operator < (const node &y)const{
return w<y.w;
}
bool operator > (const node &y)const{
return w>y.w;
}
};
int n,m,st,vis[e],dic[e];
vector<node>mp[e];
void init(){
memset(dic,0x3f,sizeof(dic));
memset(vis,0,sizeof(vis));
dic[st]=0;
return;
}
void dijkstra(){
init();
priority_queue<node,vector<node>,greater<node> >q;
q.push({st,0});
while(q.size()){
node p=q.top();
q.pop();
if(vis[p.h])continue;
vis[p.h]=1;
for(auto i:mp[p.h])
if(i.w+p.w<dic[i.h]){
dic[i.h]=i.w+p.w;
q.push({i.h,dic[i.h]});
}
}
return;
}
Kruskal $ O(n*log(n)) $
TIP: 最小生成树
const int e=1e3+10;
int n,m,fa[e],cnt,ans;
struct node{
int u,v,w;
bool operator < (const node &y)const{
return w<y.w;
}
bool operator > (const node &y)const{
return w>y.w;
}
}a[e];
int find(int h){
return fa[h]==h?h:fa[h]=find(fa[h]);
}
void merge(int u,int v){
fa[u]=v;
return;
}
void kruskal(){
sort(a+1,a+1+m,less<node>());
for(int i=1;i<=m;i++){
int fu=find(a[i].u),fv=find(a[i].v);
if(fu==fv)continue;
merge(fu,fv);
ans+=a[i].w,
cnt++;
if(cnt==n-1)break;
}
return;
}
数据结构
并查集
const int e=1e3+10;
int n,fa[e];
void init(){
for(int i=1;i<e;i++)
fa[i]=i;
return;
}
int find(int h){
return fa[h]==h?h:fa[h]=find(fa[h]);
}
void merge(int x,int y){
fa[find(x)]=find(y);
return;
}
单调栈
TIP:严格下降
const int e=1e3+10;
int n,a[e],st[e],top;
void solve(){
for(int i=1;i<=n;i++){
while(top>0&&a[i]>=a[st[top]])top--;
st[++top]=i;
}
return;
}
单调队列
TIP: 严格下降
const int e=1e3+10;
int n,k,a[e],q[e],top=1,back;
void solve(){
for(int i=1;i<=n;i++){
while(top<=back&&i-q[top]>=k)top++;
while(top<=back&&a[q[back]]>=a[i])back--;
q[++back]=i;
}
return;
}
手打堆
TIP: 大根堆
const int e=1e3+10;
int a[e],top;
void push_up(int h){
int root=h;
while(root>1&&a[root]>a[root/2]){
swap(a[root],a[root/2]);
root/=2;
}
return;
}
void push_down(int h){
int root=h;
while(root*2<=top){
root*=2;
if(root+1<=top&&a[root+1]>a[root])
root++;
if(a[root]<=a[h])
break;
swap(a[root],a[h]);
h=root;
}
return;
}
void insert(int x){
a[++top]=x;
push_up(top);
return;
}
void del(){
if(top==0)
return;
else{
swap(a[1],a[top]);
top--;
push_down(1);
}
return;
}
比较运算符重载
TIP: 用于部分stl（例如优先队列）手动重载
注意 优先队列和数组使用less和greater比较函数效果不同
struct node{
int h,w;
bool operator < (const node &y)const{
return w<y.w;
}
bool operator > (const node &y)const{
return w>y.w;
}
};
priority_queue<node,vector<node>,less<node> >max_root_q;//大根堆
priority_queue<node,vector<node>,greater<node> >min_root_q;//小根堆
背包
01背包
const int e=1e3+10;
int n,m,v[e],w[e],dp[e];
void solve(){
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
return;
}
完全背包
const int e=1e3+10;
int n,m,v[e],w[e],dp[e];
void solve(){
for(int i=1;i<=n;i++)
for(int j=v[i];j<=m;j++)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
return;
}
多重背包 $ O(n*log(n)) $
TIP: 二进制优化，队列数组q比物品数组空间大30倍
const int e=1e3+10;
int n,m,dp[e],top;
struct node{
int p,w,v;
}a[e],q[e*30];
void init(){
for(int i=1;i<=n;i++){
for(int j=1;j<=a[i].p;j*=2)
q[++top]={a[i].p,a[i].w*j,a[i].v*j},
a[i].p-=j;
if(a[i].p>0)
q[++top]={a[i].p,a[i].w*a[i].p,a[i].v*a[i].p};
}
return;
}
void solve(){
init();
for(int i=1;i<=top;i++)
for(int j=m;j>=q[i].w;j--)
dp[j]=max(dp[j],dp[j-q[i].w]+q[i].v);
return;
}
总结
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
31
0- 0
已为社区贡献3条内容
所有评论(0)