read()+print()
inline int read() { char ch; bool bj=0; while(!isdigit(ch=getchar())) bj|=(ch=='-'); int res=ch^(3<<4); while(isdigit(ch=getchar())) res=(res<<1)+(res<<3)+(ch^(3<<4)); return bj?-res:res; } void printnum(int x) { if(x>9)printnum(x/10); putchar(x%10+'0'); } inline void print(int x,char ch) { if(x<0) { putchar('-'); x=-x; } printnum(x); putchar(ch); }
fread() From Internet
struct ios{ inline char read(){ static const int IN_LEN=1<<18|1; static char buf[IN_LEN],*s,*t; return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++; } template <typename _Tp> inline ios & operator >> (_Tp&x){ static char c11,boo; for(c11=read(),boo=0;!isdigit(c11);c11=read()){ if(c11==-1)return *this; boo|=c11=='-'; } for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0'); boo&&(x=-x); return *this; } }io;
基础模板
高精度+重载运算符 From Internet
const int MAX=100; struct node { int num[MAX]; node & operator = (const char*); node & operator = (int); node(); node(int); bool operator > (const node &) const; bool operator < (const node &) const; bool operator <= (const node &) const; bool operator >= (const node &) const; bool operator != (const node &) const; bool operator == (const node &) const; node operator + (const node &) const; node operator - (const node &) const; node operator * (const node &) const; node operator / (const node &) const; node operator % (const node &) const; node & operator += (const node &); node & operator -= (const node &); node & operator *= (const node &); node & operator /= (const node &); node & operator %= (const node &); }; node & node::operator = (const char* c) { memset(num,0,sizeof(num)); int n=strlen(c),j=1,k=1; for (int i=1; i<=n; i++) { if (k==10000) j++,k=1; num[j]+=k*(c[n-i]-'0'); k*=10; } num[0]=j; return *this; } node & node::operator = (int a) { char s[MAX]; sprintf(s,"%d",a); return *this=s; } node::node() { memset(num,0,sizeof(num)); num[0]=1; } node::node (int n) { *this = n; } bool node::operator > (const node &b) const { if (num[0]!=b.num[0]) return num[0]>b.num[0]; for (int i=num[0]; i>=1; i--) if (num[i]!=b.num[i]) return (num[i]>b.num[i]); return false; } bool node::operator < (const node &b) const { return b>*this; } bool node::operator <= (const node &b) const { return !(*this>b); } bool node::operator >= (const node &b) const { return !(b>*this); } bool node::operator != (const node &b) const { return (b>*this)||(*this>b); } bool node::operator == (const node &b) const { return !(b>*this)&&!(*this>b); } node node::operator + (const node &b) const { node c; c.num[0] = max(num[0], b.num[0]); for (int i=1; i<=c.num[0]; i++) { c.num[i]+=num[i]+b.num[i]; if (c.num[i]>=10000) { c.num[i]-=10000; c.num[i+1]++; } } if (c.num[c.num[0]+1]>0) c.num[0]++; return c; } node node::operator - (const node &b) const { node c; c.num[0] = num[0]; for (int i=1; i<=c.num[0]; i++) { c.num[i]+=num[i]-b.num[i]; if (c.num[i]<0) { c.num[i]+=10000; c.num[i+1]--; } } while (c.num[c.num[0]]==0&&c.num[0]>1) c.num[0]--; return c; } node & node::operator += (const node &b) { return *this=*this+b; } node & node::operator -= (const node &b) { return *this=*this-b; } node node::operator * (const node &b) const { node c; c.num[0] = num[0]+b.num[0]+1; for (int i=1; i<=num[0]; i++) { for (int j=1; j<=b.num[0]; j++) { c.num[i+j-1]+=num[i]*b.num[j]; c.num[i+j]+=c.num[i+j-1]/10000; c.num[i+j-1]%=10000; } } while (c.num[c.num[0]]==0&&c.num[0]>1) c.num[0]--; return c; } node & node::operator *= (const node &b) { return *this=*this*b; } node node::operator % (const node &b) const { node c, d; c.num[0] = num[0]+b.num[0]+1; d.num[0] = 0; for (int i=num[0]; i>=1; i--) { memmove(d.num+2, d.num+1, sizeof(d.num)-sizeof(int)*2); d.num[0]++; d.num[1]=num[i]; int left=0, right=9999, mid; while (left < right) { mid = (left+right)/2; if (b*node(mid) <= d) left=mid+1; else right=mid; } c.num[i]=right-1; d=d-b*node(right-1); } while (c.num[c.num[0]]==0&&c.num[0]>1) c.num[0]--; return d; } node & node::operator /= (const node &b) { return *this=*this/b; } node & node::operator %= (const node &b) { return *this=*this%b; } node node::operator / (const node& b) const { node c, d; c.num[0] = num[0]+b.num[0]+1; d.num[0] = 0; for (int i=num[0]; i>=1; i--) { memmove(d.num+2, d.num+1, sizeof(d.num)-sizeof(int)*2); d.num[0]++; d.num[1]=num[i]; int left=0, right=9999, mid; while (left < right) { mid = (left+right)/2; if (b*node(mid) <= d) left=mid+1; else right=mid; } c.num[i]=right-1; d=d-b*node(right-1); } while (c.num[c.num[0]]==0&&c.num[0]>1) c.num[0]--; return c; } ostream & operator << (ostream & o, node &n) { o<<n.num[n.num[0]]; for (int i=n.num[0]-1; i>=1; i--) { o.width(4); o.fill('0'); o<<n.num[i]; } return o; } istream & operator >> (istream & in, node &n) { char s[MAX]; in>>s; n=s; return in; }
排序算法
归并排序
void Div(int l,int r){ if(l==r)return; int mid=(l+r)>>1; Div(l,mid); Div(mid+1,r); int i=l,j=mid+1,p=l; while(i<=mid&&j<=r) if(a[i]<a[j])tmp[p++]=a[i++]; else tmp[p++]=a[j++]; while(i<=mid)tmp[p++]=a[i++]; while(j<=r)tmp[p++]=a[j++]; for(int i=l;i<=r;i++)a[i]=tmp[i]; }
快速排序
sort(a+1,a+n+1); sort(a+1,a+n+1,greater<int>());
离散化
inline void Dcz(){ for(int i=1;i<=n;i++)tmp[i]=a[i]; sort(tmp+1,tmp+n+1); newn=unique(tmp+1,tmp+n+1)-tmp-1; for(int i=1;i<=n;i++)a[i]=lower_bound(tmp+1,tmp+newn+1,a[i])-tmp; }
数据结构
前缀和
一维
inline int cal(int x,int y){ return sum[y]-sum[x-1]; } int main(){ for(int i=1;i<=n;i++){ a[i]=read(); sum[i]=sum[i-1]+a[i]; } return 0; }
二维
#define y1 Sol_y1 #define y2 Sol_y2 inline int ask(int x1,int y1,int x2,int y2) { return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]; } int main(){ for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) { a[i][j]=read(); sum[i][j]=sum[i-1][j]+sum[i][j-1]+a[i][j]-sum[i-1][j-1]; } return 0; }
二叉堆
手工堆(小根)
inline void heapdown(){ int i,j; i=1; while((i<<1)<=a[0]){ if((i<<1)==a[0]||a[i<<1]<a[i<<1|1])j=i<<1; else j=i<<1|1; if(a[i]>a[j]){ swap(a[i],a[j]); i=j; } else break; } } inline void heapup(){ int i=a[0]; while(i>1&&a[i]<a[i>>1]){ swap(a[i],a[i>>1]); i>>=1; } } inline void Insert(int x){ a[++a[0]]=x; heapup(); } inline void Delete(){ a[1]=a[a[0]]; a[0]--; heapdown(); }
STL
#include<queue> priority_queue<int>q//大根堆 priority_queue<int,vector<int>,greater<int> >q//小根堆
并查集
路径压缩
int GetFather(int x){ return x==prt[x]?x:prt[x]=GetFather(prt[x]); } inline void Union(int x,int y){ prt[GetFather(x)]=GetFather(y); } inline bool query(int x,int y){ return GetFather(x)==GetFather(y); } int main(){ // for(int i=1;i<=n;i++)prt[i]=i; // return 0; }
按秩合并
int GetFather(int x){ return x==prt[x]?x:GetFather(prt[x]); } inline void Union(int x,int y){ int f1=GetFather(x),f2=GetFather(y); if(f1==f2)return; if(size[f1]>size[f2])prt[f2]=f1,size[f1]+=size[f2]; else prt[f1]=f2,size[f2]+=size[f1]; } inline bool query(int x,int y){ return GetFather(x)==GetFather(y); } int main(){ // for(int i=1;i<=n;i++)prt[i]=i,size[i]=1; // return 0; }