个人用的 模板 不喜勿喷
1.这个是自己非用STL写的板子 优化极差 还是建议STL
void sortfast(int l,int r){
int i,j,mid,p;
i=l;j=r;
mid=a[(l+r)/2];
do{
while(a[i]<mid) i++;
while(a[j]>mid) j--;
if(i<=j)
{
p=a[i];a[i]=a[j];a[j]=p;
}
}
while(i<=j);
if(l>j) sortfast(l,j);
if(i<r) sortfast(i,r);
}
2.一个并没用什么卵用的冒泡排序 适用于写一写红题
void maopao(int m,int n){
for(int i=n;i>0;i--){
for(int j=1;j<i;j++){
if(a[j]>=a[j+1])
sqrt(a[j],a[j+1]);
}
}
}
3.这个是考试必备的freopen (据说我们这届机房有个人退役前次次炸freopen)
//freopen
freopen("std.in","r",stdin);
freopen("std.out","w",stdout);
/*中间开始写代码*/
fclose(stdin);fclose(stdout);
4.这是一个不怎么建议用的指针建树
//建树
typedef struct node;
typedef node*tree;
struct node{
char data;
tree lchild,rchild;
}; tree bt;
void build(tree &bt){
int x=0;
while(s[x]!='!'){
bt=new node;
bt->data=s[x];//s[x]是在main函数里输入的
build(bt->lchild);
build(bt->rchild);
x++;
}
}
5.个人建议用链式前向星
//链式前向星
int tot,head[N>>1];
struct point{
int n;
int v;
ll w;
int nex;
}p[N];
void add(int a,int b){
p[++tot]=(point){a,b,head[a]};
head[a]=tot;
}
6.这个堆我没咋用 用stl的大根堆
//堆
void put(int d)
{
int now,next;
heap[++heap_size]=d
now=heap_size;
while(now>1)
{
next=now>>1;//>>相当于/2
if(heap[now]>=heap[next])return;//符合条件，返回
swap(heap[now],heap[next]);
}
}
7.据说是一个优化cin的方法 但是有个bug 有人在csp的考场上试过
//时间差
ios::sync_with_stdio(false);
//优化。打消iostream的输入输出缓存
使得cin cout 时间和printf scanf 相差无几
8.压缩过的完全背包的板子 直接背诵即可
//完全背包
const ll MAXN=1e6+7;
ll f[10000005],v[10000005],c[10005],tiji,num;
int main(){
cin>>tiji>>num;
for(ll i=1;i<=num;i++) cin>>v[i]>>c[i];
for(ll i=1;i<=num;i++)
for(ll j=v[i];j<=tiji;j++)
f[j]=max(f[j],f[j-v[i]]+c[i]);
cout<<f[tiji];
return 0;
}
9.一个最基础的01背包 没什么好说的
//01背包问题
const int MAXN=1e6;
ll f[MAXN],v[MAXN],c[MAXN],tiji,num;
int main(){
cin>>tiji>>num;
for(ll i=1;i<=num;i++) cin>>v[i]>>c[i];
for(ll i=1;i<=num;i++)
for(ll j=tiji;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+c[i]);
cout<<f[tiji];
return 0;
}
10.快读的模板
//快读
inline int read(){
int x=0; bool f=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=0;
for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
if(f) return x;
return 0-x;
}
//模板2
int read() {
int s=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9') {if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){s=(s<<3)+(s<<1)+(ch^48);ch=getchar();}
return s*f;
}
11. 多重背包
//多重背包
for(int i=1;i<=n;i++)
{
if(w[i]*a[i]>m)
{
for(int c=0;c<=m;c++)
{
if(c>=w[i])
f[c]=max(f[c],f[c-w[i]]+v[i]);
}
}
else
{
k=1;amount=a[i];
while(k<amount)
{
for(int c=k*w[i];c>=0;c--)
{
if(c>=w[i])
f[c]=max(f[c],f[c-w[i]]+k*v[i]);
}
amount-=k;
k<<=1;
}
for(int c=amount*w[i];c>=0;c--)
{
f[c]=max(f[c],f[c-w[i]]+amount*v[i]);
}
}
}