首先输入方式一份，复制自闵神：

(只有全部输入数据都为整数时才可使用此模板)

namespace IO{    char buf[1<<15],*fs,*ft;    inline char gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}    inline int read(){        int x=0,ch=gc();        while(ch<'0'||ch>'9')ch=gc(); while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=gc(); return x; } }using namespace IO;//使用时需要微调;

fread()函数： 头文件：#include 
     
        fread()函数用于从文件流中读取数据，其原型为： 　　size_t  fread(void *buffer, size_t size, size_t count, FILE * stream);  【参数】buffer为接收数据的地址，size为一个单元的大小，count为单元个数，stream为文件流。  fread()函数每次从stream中最多读取count个单元，每个单元大小为size个字节，将读取的数据放到buffer；文件流的位置指针后移 size * count 字节。  【返回值】返回实际读取的单元个数。如果小于count，则可能文件结束或读取出错；可以用ferror()检测是否读取出错，用feof()函数检测是否到达文件结尾。如果size或count为0，则返回0。
     

一般说来，我们都只在输入整数这一部分进行输入优化(大部分时候输入的都是整数)；

如果需要读入一个字符串：

scanf("%s",s);

如果需要读入一行字符串：

getline(cin,s);

输入部分到此结束；

 

输出：

输出一般不进行优化；

输出整数printf("%d\n",ans); 输出long long 整数printf("%lld\n",ans);//linuxprintf("%I64d\n",ans);//windows有些平台都可以使用 输出字符串：printf("%s",s); 输出double类型：printf("%.3lf\n",ans);//保留三位小数； 如果需要对double类型进行一些处理: floor()向下取整 ceil()向上取整

输出部分结束；

 

考前建议打出来的配套文件：

比如：

right.cpp           暴力程序，从dealing.in读入，right.out输出

makedata.cpp    数据制作，发到dealing.in

编译.bat             批处理，编译所有cpp文件

对拍.bat             对拍的批处理，每次运行makedata.exe，dealing.exe，right.exe，比较dealing.out right.out

dealing.cpp        当前程序        

dealing.in          

dealing.out

right.out

cmp.bat             比较right.out和dealing.out

一般还需要几个txt存储以前的版本；

1 @echo off 2 set path=c:/windows/system32 3 fc right.out dealing.out 4 if errorlevel==1 pause 5 pause 6  7  8 //cmp.bat 9 10 11 @echo off12 set path=C:\MinGWStudio\MinGW\bin13 g++ -o dealing.exe dealing.cpp14 g++ -o makedata.exe makedata.cpp15 g++ -o right.exe right.cpp16 set path=C:\Windows\System3217 :loop18 makedata.exe19 dealing.exe20 right.exe21 fc right.out dealing.out 22 if errorlevel==1 pause23 goto loop24 25 26 27 //对拍.bat28 29 30 @echo off31 set path=C:\MinGWStudio\MinGW\bin32 g++ -o dealing.exe dealing.cpp33 g++ -o makedata.exe makedata.cpp34 g++ -o right.exe right.cpp35 set path=C:\Windows\System3236 pause37 38 39 //编译.bat

 

 

 

 

 

 

 

题目分析：

拿到一道题目，如何分析呢？

1.数据范围：数据范围往往决定了我们使用的算法数据量 算法复杂度

100w及以上          O(n)    50w                     O(nlogn)        //此复杂度易被卡10w-30w             O(n^(3/2))或O(nlogn)     //相比而言不易被卡1w-5w                 O(n^(3/2))或O(n^2logn) 1w左右                 O(n^2)1k-5k                   O(n^2logn)100-500              O(n^3) 10-20 O(n!)或各种奇怪的dp 1-10 码农题或搜索

2.相信直觉，敢于猜想，这就是动用你智慧的时候了；

3.保持镇静，冷静分析；

4.对题目既要有理性地推算式，感性的认知也必不可少，通常后者会帮助我们联想到一些经典模型；

题目分析完成；

算法篇：

对于一个情景，该用什么算法，这是一门很深的学问，在此本人浅谈一二；

对于算法而言，复杂度往往与适应力成正比；

每个OIer都学过不少经典模型，我们要做的就是找到这道题目的特点，从而利用更简单的算法来应对；

这是算法的精髓；

一些算法思想的复杂度：(只列举一般情况)

贪心：O(n) 

分治：O(nlogn)

动规：O(nm)

图：O(n^2)

流:O(n^3)

暴力：O(n!)

算法篇完；

 

题目分类：

在此我按所用算法分类；

1.动规题目：

动规实际上是某种意义上的贪心；

一般动规分为这么几类： 比较入门的: 资源分配型 区间型 等等 比较难搞的： 状压dp 插头dp 数位dp 等等 一般的动态规划都可以通过分析来解决，但是复杂度往往得不到保证； 以下是一些常用的优化技巧： 决策单调性：具体可见[超级教主]此题 斜率优化：具体见[玩具装箱] 四边形不等式优化； 矩阵乘法优化dp 等等 dp其实就是枚举所有情况，然后比较一下； 所以设置的状态一定要可以表示出所有情况； 但有时候状态是可以简化的： 比如一道题目在一个大区间上分块： 如果小区间的值与区间大小无关，就没必要枚举区间大小，可以从上一个点转移；

2.图论题目：包括流和图的这类模型的问题；

并查集最短路拓扑排序连通性 双联通 2-sat 差分 树上问题流等等

3.数论题：

知识点一般有：

BSGS置换筛法快速幂博弈欧拉函数卡特兰数矩阵乘法高斯消元乘法逆元排列组合容斥莫比乌斯反演FFTgcdex_gcd等等

　　这类题目真的很需要练习；

 

 

模板类：

初始化：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
            #include
           
             #include
            
           
          
         
        
       
      
     

高精度：

struct bignum{    int num[40];    int len;    bignum(){memset(num,0,sizeof(num));len=1;}    bignum operator=(const char* s)    {        len=strlen(s); for(int i=0;i
     
      =10) { c.num[k+1]+=c.num[k]/10; c.num[k]%=10; k++; } c.len=k; } return c; } friend bignum operator+(bignum& a,bignum& b){ bignum c; int len=max(a.len,b.len); for(int i=1;i<=len;i++) { c.num[i]+=a.num[i]+b.num[i]; if(c.num[i]>=10) { c.num[i+1]+=c.num[i]/10; c.num[i]%=10; } } while(c.num[len]>=10)c.num[len+1]+=c.num[len]/10,c.num[len]%=10,len++; c.len=len; return c; } };
     

平衡树：

splay:

int cnt=1,root=0;struct node{    int v,siz,fa,ch[2];    void set(int x,int y,int vv){x=v,siz=y,fa=vv,ch[0]=ch[1]=0;}}e[maxn];void updata(int x){e[x].siz=e[e[x].ch[0]].siz+e[e[x].ch[1]].siz+1;}void totate(int x,int d){ int y=e[x].fa; e[x].fa=e[y].fa; e[e[x].ch[d^1]].fa=y; e[y].fa=x; if(e[x].fa) e[e[x].fa].ch[ y== e[e[x].fa].ch[1] ]=x; e[y].ch[d]=e[x].ch[d^1]; e[x].ch[d^1]=y; updata(y);updata(x); } void splay(int x,int S){ while(e[x].fa!=S){ if(e[e[x].fa].fa==S)rotate(x,e[e[x].fa].ch[1]==x); else { int y=e[x].fa,z=e[y].fa; int d=(e[z].ch[1]==y); if(e[y].ch[d]==x) rotate(y,d),rotate(x,d); else rotate(x,d^1),rotate(x,d); } } if(S==0)root=x; } int find(int key){ int x=root; while(x&&e[x].key!=key)x=e[x].ch[key>e[x].v]; if(x)splay(x,0); return x; } void insert(int key){ if(!root)e[root=++cnt].set(key,1,0); else { int x=root,y=0; while(x){ y=x; x=e[x].ch[key>e[x].v]; } e[x=++cnt].set(key,1,y); e[y].ch[key>e[y].v]=x; splay(x,0); } } void delet(int key){ int x=find(key); if(!x)return; int y=e[x].ch[0],z=e[x].ch[1]; while(e[y].ch[1])y=e[y].ch[1]; while(e[z].ch[0])z=e[z].ch[0]; if(!y&&!z){root=0;return;} if(!y){ splay(z,0);e[z].ch[0]=0;updata(z); return; } if(!z){ splay(y,0);e[y].ch[1]=0;updata(y); return; } splay(y,0);splay(z,y); e[z].ch[0]=0; updata(z);updata(y); } int getKth(int k){ if(!root)return 0; int x=root,ret=0; while(x){ if(k==e[e[x].ch[0]].siz+1)break; if(k>e[e[x].ch[0]].siz+1) k-=e[e[x].ch[0]].siz+1,x=e[x].ch[1]; else x=e[x].ch[0]; } splay(x,0); return x; }

kmp:

//s串为模式串n=strlen(s);int j=-1;next[0]=-1;for(int i=1;i

//s串模式串，a串待匹配串int j=-1;for(int i=0;i

AC自动机：（能自动AC题目的机器，∩_∩）

namespace AC{    int n,len=0;    char s[1010000],ch[10100][55];    int cnt[10100];    int f[505000],linkk[505000][26],flag[505000],next[505000];    void add(int x){ int now=0; for(int i=0;i

后缀数组：

void getsa(int m){    int *x=t1,*y=t2;    for(int i=0;i
     
      =0;i--)sa[--c[x[i]]]=i; for(int j=1,p=1;p
      
       <<=1,m=p){ p=0; for(int i=n-j;i
       
        =j)y[p++]=sa[i]-j; for(int i=0;i
       
      
     

树链剖分： 

struct node{    int y,next;}e[maxn];int linkk[maxn],len=0;int top[maxn],dep[maxn],son[maxn],fa[maxn],siz[maxn],pre[maxn],nex[maxn],dfs_clock=0;int dfs1(int x){    siz[x]=1; pre[x]=++dfs_clock; for(int i=linkk[x];i;i=e[i].next){ if(e[i].y==fa[x])continue; dfs1(e[i].y); fa[e[i].y]=x; dep[e[i].y]=dep[x]+1; siz[x]+=siz[e[i].y]; if(siz[e[i].y]>siz[son[x]])son[x]=e[i].y; } nex[x]=dfs_clock; } int dfs2(int x){ if(son[x]){ top[son[x]]=top[x]; dfs2(son[x]); } for(int i=linkk[x];i;i=e[i].y){ if(e[i].y==son[x]||e[i].y==fa[x])continue; top[e[i].y]=e[i].y; dfs2(e[i].y); } }

倍增求lca：

struct node{    int y,next;}e[maxn];int linkk[maxn],len=0;int dep[maxn],fa[maxn][25],d[maxn][25];void dfs(int x){    for(int i=linkk[x];i;i=e[i].next){ if(e[i].y==fa[x][0])continue; dep[e[i].y]=dep[x]+1; d[e[i].y][0]=e[i].v; fa[e[i].y][0]=x; dfs(e[i].y); } } int lca(int x,int y){ dfs(1); limit=(int)log2(n*1.0)+1; for(int j=1;j<=limit;j++) for(int i=1;i<=n;i++) d[i][j]=d[i][j-1]+d[fa[i][j-1]][j-1],fa[i][j]=fa[fa[i][j-1]][j-1]; if(dep[x]>dep[y])swap(x,y); int sum=0; for(int i=limit;i>=0;i--)if(dep[y]-dep[x]>=(1<
     
      =0;i--)if(fa[x][i]!=fa[y][i])sum+=d[y][i]+d[x][i],x=fa[x][i],y=fa[y][i]; sum+=fa[x][0]+fa[y][0]; return sum; }
     

SPFA：（SPFA适用性很强）

void SPFA(int s){    memset(d,10,sizeof(d));    d[s]=tail=head=0;q[++tail]=s;    int x;vis[x]=1;    while(++head<=tail){        x=q[head]; for(int i=linkk[x];i;i=e[i].next) if(d[x]+e[i].v

dij：

const int maxn(201000);struct node{    int v,y,next;}e[maxn];int linkk[maxn],len=0;int d[maxn],vis[maxn];void dij(int s){ priority_queue< pii,vector
     
      ,greater
      
        > q; q.push(make_pair(0,s)); int x; while(!q.empty()){ x=q.top().second; if(vis[x])continue; vis[x]=1; for(int i=linkk[x];i;i=e[i].next){ if(d[e[i].y]>d[x]+e[i].v){ d[e[i].y]=d[x]+e[i].v; q.push(make_pair(d[e[i].y],e[i].y)); } } } }
      
     

最短路拓展：

1.p1957第k短路

提要：A*在解决某些路径问题的时候可以发挥奇效，注意！

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
            #include
           
             #include
            
           
          
         
        
       
      
     

2.p1218过路费

提要：floyed时搜索最外层k的顺序，可能会被某些题目利用。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std; int g[254][254],d[252][252],C[252]; int m,n,k; struct node { int v,id; }c[252]; bool mycmp(node b,node c) { return b.v
           
            >n>>m>>k; for(int i=1;i<=n;i++) { cin>>c[i].v; C[i]=c[i].v; c[i].id=i; g[i][i]=c[i].v; } int x,y,v; for(int i=1;i<=m;i++) { cin>>x>>y>>v; if(v
            
             >x>>y; cout<
             
              <
             
            
           
          
         
        
       
      
     

3.求经过某条边的最短路数量p1525 [haoi2012]道路

算法过程：先求一遍最短路，只走属于最短路的边，就可以把原图转化成DAG图，然后就可以在这个图上进行dp；

附一份代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define up(i,j,n) for(int i=j;i<=n;i++)#define LL long long#define pii pair
           
             #define FILE "dealing"inline bool chkmin(int &x,int y){ return x>y?(x=y,true):false;}inline bool chkmax(int &x,int y){ return x
            
             '9'){ if(ch=='-')d=1;ch=gc();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();} return d?-x:x; }}using namespace IO;namespace OI{ const int maxn(20000),inf(1000000000),mod(1000000007); struct node{ int y,next,x,v; }e[maxn<<5]; int linkk[maxn],len=0; int n,m; void insert(int x,int y,int v){ e[++len].y=y; e[len].x=x; e[len].v=v; e[len].next=linkk[x]; linkk[x]=len; return; } void init(){ int x,y,v; n=read(),m=read(); up(i,1,m)x=read(),y=read(),v=read(),insert(x,y,v); return; } int d[maxn],q[maxn*10],ru[maxn],v[maxn],tail=0,head=0,vis[maxn],s,f[maxn],cnt[maxn],ans[maxn]; int dfs(int x){ if(f[x])return f[x]; f[x]=1; for(int i=linkk[x];i;i=e[i].next) if(d[x]+e[i].v==d[e[i].y])ru[e[i].y]++,f[x]+=dfs(e[i].y); return f[x]; } void spfa(){ tail=head=0; memset(f,0,sizeof(f)); memset(cnt,0,sizeof(cnt)); memset(d,10,sizeof(d)); memset(vis,0,sizeof(vis)); memset(ru,0,sizeof(ru)); memset(v,0,sizeof v); q[++tail]=s;int x; d[s]=0; while(++head<=tail){ x=q[head]; vis[x]=0; for(int i=linkk[x];i;i=e[i].next){ if(e[i].v+d[x]
            
           
          
         
        
       
      
     

 

 

 

线段树：

线段树例题a:（以前的代码真心不能看......）

#include
     
      #include
      
       #include
       
        using namespace std;int a[500][2];int maxx[500];int b[101000]; int n,m,q; int v[101000]; int main() { ios::sync_with_stdio(false); cin>>n; int m=(int)sqrt(n*1.0); int sum=0,st=1; int tail=0; for(int i=1;i<=n;i++) { b[i]=tail+1; sum++; if(sum==m||i==n) { a[++tail][0]=st,a[tail][1]=i; st=i+1; sum=0; continue; } } int x,y,ma=0; for(int i=1;i<=n;i++) { ma=-1000000000; cin>>q>>x>>y; if(q==1) { int group=b[x]; v[x]=y; maxx[group]=-10000000; for(int j=a[group][0];j<=a[group][1];j++)maxx[group]=max(maxx[group],v[j]); continue; } if(q==2) { if(x>y)swap(x,y); while(a[b[x]][1]<=y) { if(x==a[b[x]][0]) { ma=max(ma,maxx[b[x]]); x=a[b[x]][1]+1; if(x>=y)break; } else { for(int j=x;j<=a[b[x]][1];j++) ma=max(ma,v[j]); x=a[b[x]][1]+1; } } if(x>y) { cout<
        
         <
        
       
      
     

线段树的应用方面：

1.求一些区间内的可合并的信息，例如最长的区间长度之类的，node节点内多储存几个信息维护即可；

2.与树的dfs序相结合，可以维护某些树上信息

3.......

总的来说，一切需要动态维护的可以拆分成线段的且需维护的信息可合并的东西一般都可以用线段树优化；

 

数论：

1.同余原理：

 

gcd：

求x，y最大公约数：

设x=ay+r;

所以r=x%y；

设d为x,y的一个公因数；

所以d|x,d|y

因为r=x-ay

所以d|r

所以x,y和y,r的最大公因数是一样的

所以就这么迭代即可；

gcd(int a,int b){
   return b?gcd(b,a%b):a;}

ex_gcd:

证明和上面的差不多：

void gcd(int a,int b,int &d,int &x,int &y){    if(!b){d=a,x=1,y=0;return;}    gcd(b,a%b,d,x,y);    int t=x;    x=y;    y=t-a/b*x;}

乘法逆元：

LL inv(LL a,LL n){    LL d,x,y;    gcd(a,n,d,x,y);    return d==1?(x%n+n)%n:-1;} 或者a^((mod-2)) 或者a^(phi(mod)-1)

顺序求逆元：

inv[i]=(mod-mod/i)*inv[mod%i] %mod