noip模板

数据结构栈intstrack[maxn];inthead;boolb[maxn];voidpush(intx){strack[++head]=x;b[x]=true;};intpop(){intret;ret=strack[head--];b[ret]=false;returnret;};boolempty(){returnhead0;}队列intqueue[2*maxn];inttail,head;boolb[maxn];voidpush(intx){queue[++tail]=x;bool[x]=true;};intpop(){intret;ret=queue[++head];b[ret]=false;returnret;};boolempty(){returnhead=tail;};当然有的时候你手写的数据结构需要比较大的空间，这样队列就会造成很多损失，所以相应的就有两种解决方法：一：STL；二：循环队列，只需改两个地方（代码如下）；head=(head+1)%n+1;//把head++改tail=(tail+1)%n+1;//把tail++改树状数组intlowbit(intx){returnx&-x;};intgetsum(intn)//求1～n见的和{intret=0;while(n){ret+=c[n];n-=lowbit(n);};returnret;};voidadd(intn,intx)//给a[n]加上x{a[n]+=x;while(n=maxn){c[n]+=x;n+=lowbit(n);应用模型：树状数组求逆序对：voidupdate(intn){while(n=maxn){c[n]+=1;n+=lowbit(n);};};for(inti=1;i=n;++i)//主程序里面加上这个{update(reflect[i]);ans+=i-getsum(reflect[i]);//reflect是离散化后的数组}STL关于每个STL我只会写一下是什么，怎么用（举例子的形式），不会说的太细Vector不定长度数组#includevectorvectorintfirst;//第一种定义方法intmyints[]={16,2,77,29};vectorintsecond(myints,myints+4);//第二种定义方法sort(second.begin(),second.end());//对vector排序a=second[i];//可以这么使用//以下是对vector的操作Vectorintopt;opt.begin();//返回起始地址opt.end();//返回结束地址opt.size();//返回大小opt.empty();//返回是否vector为空opt.back();//返回最后一个push进的数opt.pop_back();//把最后一个数弹出（不返回）opt.push_back(intx);//把x从后面push进去opt.erase(opt.begin(),opt.begin()+3);//删掉前三个元素opt.erase(opt.begin()+5);//删掉第6个元素Queue队列，操作与Stack一样。Priority_queue相当于堆#includequeuepriority_queueintBigheap;//定义一个大根堆priority_queueint,vectorint,greaterintSmallheap;//定义一个小根对（注意两个尖括号间有空格）//以下是操作priority_queueintopt;opt.top();//返回堆顶元素的值（不弹出）opt.pop();//弹出堆顶元素（无返回值）opt.push(x);Stackstackintopt;opt.front();//返回opt.size();opt.empty();opt.push();opt.pop();//弹出Deque双向队，操作与Stack一样Bitset压位神器，只普及一下，不会用。Setsetintfirst;intmyints[]={10,20,30,40,50};setintsecond(myints,myints+5);setintthird(second);setintfourth(second.begin(),second.end());third.rbegin();third.rend();//rend相当于begin，rbegin相当于endthird.size();//返回大小third.insert(60);third.erase(it);third.erase(50);//删除元素'50'third.find(10);//找元素'10'third.lower_bound(30);third.upper_bound(30);//'30'出现的第一个位置/最后一个位置third.clear();//清除Multiset与Set用法一样，只是允许重复元素。Mapmapchar,intfirst;first[‘a’]=10;first.insert(make_pair(‘b’,20));it++;++it;it--;--it;first.erase(1);//删除元素firstt.count(1);//看有没有关系Algorithm里其他好用的函数Next_permutationinta[]={1,2,3,4};next_permutation(a,a+3);//下一个全排列//现在a数组变成了:1243Lower_bound与Upper_boundlower_bound(first,last,val);//有返回值upper_bound(first,last,val);Mergemerge(first,first+5,second,second+5,v.begin(),compare);sortboolcompare(inta,intb){returnab;};//compare函数的例子sort(起始地址,结束地址,compare函数);ReverseReverse(myvector.begin(),myvector.end());Uniqueboolmyfunction(inti,intj){return(i==j);}unique(起始地址,结束地址,去重条件函数);//按照函数里面编写的规则去重，当然也可以没有第三个参数Random_shuffle留一个概念，不会用，生成数据的时候用。数论快速幂#defineullunsignedlonglongullqpow(ullx,ully,ullp)//x^ymodp{ullret=1;while(y){if(y&1)ret=ret*x%p;x=x*x%p;y=1;};returnret;}筛法求素数欧拉筛法inttot=0;voideuler(intn){memset(check,0,sizeof(check));for(inti=1;i=n;i++){if(!check[i])prime[++tot]=i;for(intk=1;k=tot;k++){if(i*prime[k]n)break;check[i*prime[k]]=1;if(i%check[k]==0)break;};};};验证素数普通方法boolflag=true;for(inti=1;i=trunc(sqrt(prime));i++)if(prime%i==0)flag=false;//置不是素数标志最大公约数和最小公倍数gcd为最大公约数，lcm为最小公倍数a∗b=gcd∗lcm;intgcd(inta,intb)//注意此处a要大于b{returnb==0?a:gcd(b,a%b);};intlcm(inta,intb){returna*b/gcd(a,b);};扩展欧几里德intx,y;intgcd(inta,intb){intret,t;if(b==0){x=1;y=0;returna;};ret=gcd(b,a%b);t=y;y=x-(a%b)*y;x=t;returnret；}//不理解建议背过逆元所谓逆元就是ab≡1(modp)，a和b就在模p的意义下逆元。利用同余的性质：ab≡1(modp)⇒ab−1≡0(modp)⇒ab+pt=1故可以用扩展欧几里德求解#includeiostream#includecstdiousingnamespacestd;longlongx,y,a,b,ans;longlonggcd(longlonga,longlongb){longlongt,ret;if(b==0){x=1;y=0;returna;}ret=gcd(b,a%b);t=y;y=x-(a/b)*y;x=t;returnret;}intmain(){cinab;ans=gcd(a,b);while(xb)x-=b;while(x0)x+=b;coutxendl;return0;}Catalan数原理理解：(两个应用模板)括号化矩阵连乘：P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n-1)种)出栈次序一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?intmain()//求第n个卡特兰数{cinn;h[0]=1;h[1]=1;for(inti=2;i=n;i++)for(intj=0;j=i-1;j++)h[i]=h[i]+h[j]*h[i-j-1];couth[n];return0;}高精读入、储存与输出以下代码块均包含以下语句:ints[255];//255位的数读入与储存:voidread(){charss[255];scanf(%s,ss);for(inti=1;i=strlen(ss);i++)s[i]=ss[strlen(ss)-i+1]-'0';s[0]=strlen(ss);//存长度};输出:voidprint(){for(inti=s[0];i=1;i++)couts[i];};高精度加法高精加单精voidadd(int*s,intx)//s存高精度数，x是要加的单精度{intk=1;s[k]+=x;while(s[k]=10){s[k+1]+=s[k]/10;s[k++]%=10;};s[0]=k;};高精加高精voidadd(int*s1,int*s2,int*ans){intlen;len=max(s1[0],s2[0]);for(inti=1;i=len;i++){ans[i]+=s1[i]+s2[i];if(ans[i]=10){ans[i+1]+=ans[i]/10;ans[i]%=10;};};if(ans[len+1]!=0)len++;ans[0]=len;};高精度乘法高精乘单精voidmultiply(int*s,intx){for(inti=1;i=n;i++){c[i]+=s[i]*x;c[i+1]+=(s[i]*b)/10;c[i]%=10;};c[0]=s[0]+1;while(c[c[0]]=10){c[c[0]+1]+=c[c[0]]/10;c[c[0]]%=10;c[0]++;};while(c[0]1&&c[c[0]]==0){c[0]--;};};高精乘高精voidmultiply(int*s1,int*s2,int*ans){for(inti=1;i=s1[0];i++)for(itnj=1;j=s2[0];j++){ans[i+j-1]+=s1[i]*s2[j];ans[i+j]+=ans[i+j-1]/10;ans[i+j-1]%=10;};ans[0]=s1[0]+s2[0]+1;while(ans[0]1&&