NOIP 前夕模板整理

归并排序：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 int a[],s[],n;

 void megre_sort(int l,int r)

 {

     if(l==r) return ;

     int mid=(l+r)/;

     megre_sort(l,mid);megre_sort(mid+,r);

     int i=l,j=mid+,k=l;

     while(i<=mid&&j<=r)

     {

         if(a[i]<=a[j])

           s[k++]=a[i++];

         else

           s[k++]=a[j++];

     }

     while(i<=mid)

       s[k++]=a[i++];

     while(j<=r)

       s[k++]=a[j++];

     for(int i=;i<=r;i++)

       a[i]=s[i];

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++)

       scanf("%d",&a[i]);

     megre_sort(,n);

     for(int i=;i<=n;i++)

       printf("%d ",a[i]);

     return ;

 }

高精度：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 int a[],b[],c[],len1,len2;

 char s1[],s2[],s3[];

 void add()

 {

     for(int i=;i<len1;i++)

       a[len1-i]=s1[i]-'';

     for(int i=;i<len2;i++)

       b[len2-i]=s2[i]-'';

     int lenc=,x=;

     while(lenc<=len1||lenc<=len2)

     {

         c[lenc]=a[lenc]+b[lenc]+x;

         x=c[lenc]/;

         c[lenc]%=;

         lenc++;

     }

     c[lenc]=x;

     if(c[lenc]==)

       lenc--;

     for(int i=lenc;i>=;i--)

       cout<<c[i];

     cout<<endl;

 }

 void jian()

 {

     memset(c,,sizeof(c));memset(a,,sizeof(a));memset(b,,sizeof(b));

     if(strlen(s1)<strlen(s2)||((strlen(s1)==strlen(s2))&&strcmp(s1,s2)<))

     {

         strcpy(s3,s1);strcpy(s1,s2);strcpy(s2,s3);

         cout<<'-';

     }

     len1=strlen(s1);len2=strlen(s2);

     for(int i=;i<len1;i++)

       a[len1-i]=s1[i]-'';

     for(int i=;i<len2;i++)

       b[len2-i]=s2[i]-'';

     int lenc=;

     while(lenc<=len1||lenc<=len2)

     {

         if(a[lenc]<b[lenc])

         {

             a[lenc]+=;a[lenc+]--;

         }

         c[lenc]=a[lenc]-b[lenc];

         lenc++;

     }

     while(c[lenc]==&&lenc>)

       lenc--;

     for(int i=lenc;i>=;i--)

       cout<<c[i];

     cout<<endl;

 }

 void cheng()//高精乘

 {

     for(int i=;i<len1;i++)

       a[len1-i]=s1[i]-'';

     for(int i=;i<len2;i++)

       b[len2-i]=s2[i]-'';

       memset(c,,sizeof(c));

       for(int i=;i<=len1;i++)

       {

         int x=;

             for(int j=;j<=len2;j++)

             {

                 c[i+j-]=a[i]*b[j]+x+c[i+j-];

                 x=c[i+j-]/;

                 c[i+j-]%=;

         }

         c[i+len2]=x;

     }

       int lenc=len1+len2;

       while(c[lenc]==&&lenc>) lenc--;

     for(int i=lenc;i>=;i--)

       printf("%d",c[i]);

     printf("\n");

 }

 int main()

 {

     gets(s1);gets(s2);

     len1=strlen(s1);len2=strlen(s2);

     add();

     jian();

     cheng();

     return ;

 }

二分答案：

　　跳石头

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 int l;

 int n,m,a[];

 int check(int x)

 {

     int k=,last=;

     for(int i=;i<=n;i++)

     {

         if(a[i]-last<x)

           k++;

         else

           last=a[i];

     }

     if(k>m) return ;

     else return ;

 }

 int main()

 {

     scanf("%d%d%d",&l,&n,&m);

     for(int i=;i<=n;i++)

       scanf("%d",&a[i]);

     n++;a[n]=l;

     int left=,right=l,mid;

     while(left<=right)

     {

         mid=(left+right)/;

         if(check(mid)) left=mid+;

         else right=mid-;

     }

     printf("%d",left-);

     return ;

 }

Floyd：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 int f[][],n,map[][],t;

 int main()

 {

     cin>>n;

     memset(map,0x3f,sizeof(map));

     for(int i=;i<=n;i++)

       for(int j=;j<=n;j++)

         scanf("%d",&map[i][j]);

     for(int k=;k<=n;k++)

       for(int i=;i<=n;i++)

         for(int j=;j<=n;j++)

           if(i!=j&&j!=k&&k!=i&&map[i][k]+map[k][j]<map[i][j])

           map[i][j]=map[i][k]+map[k][j];

     scanf("%d",&t);

     while(t--)

     {

         int x,y;

         scanf("%d%d",&x,&y);

         printf("%d\n",map[x][y]);

     }

     return ;

 }

SPFA：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #define N 510

 using namespace std;

 int map[N][N],dis[N],n,m;

 bool exist[N];

 int SPFA(int x,int y)

 {

     queue<int> q;

     memset(dis,0x3f,sizeof(dis));memset(exist,false,sizeof(exist));

     q.push(x);dis[x]=;exist[x]=true;

     while(!q.empty())

     {

         int h=q.front();q.pop();exist[h]=false;

         for(int i=;i<=n;i++)

         {

             if(dis[i]>dis[h]+map[h][i])

             {

                 dis[i]=dis[h]+map[h][i];

                 if(exist[i]==false)

                     q.push(i),exist[h]=true;

             }

         }

     }

     return dis[y];

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++)

       for(int j=;j<=n;j++)

         scanf("%d",&map[i][j]);

     scanf("%d",&m);

     while(m--)

     {

         int x,y;

         scanf("%d%d",&x,&y);

         printf("%d\n",SPFA(x,y));

     }

     return ;

 }

Dijkstra:

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<ctime>

 using namespace std;

 int n,map[][],dis[];

 bool exist[];

 int dij(int x,int y)

 {

     dis[x]=;

     for(int i=;i<=n;i++)

     {

         int k=,minl=0x5f;

         for(int j=;j<=n;j++)

             if(exist[j]==false&&dis[j]<minl)

                 minl=dis[j],k=j;

         if(k==) break;

         exist[k]=true;

         for(int j=;j<=n;j++)

             if(dis[j]>dis[k]+map[k][j])

              dis[j]=dis[k]+map[k][j];

     }

     return dis[y];

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++)

       for(int j=;j<=n;j++)

         scanf("%d",&map[i][j]);

     int t;

     scanf("%d",&t);

     while(t--)

     {

         int x,y;

         scanf("%d%d",&x,&y);

         memset(dis,0x3f,sizeof(dis));

         memset(exist,false,sizeof(exist));

         printf("%d\n",dij(x,y));

     }

     return ;

 }

并查集：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 int fa[],n,m,q;

 int find(int x)

 {

     if(fa[x]==x) return fa[x];

     else return fa[x]=find(fa[x]);

 }

 void un(int x,int y)

 {

     int rx=find(x),ry=find(y);

     if(rx!=ry) fa[rx]=ry;

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++)

       fa[i]=i;

     for(int i=,x,y;i<=m;i++)

     {

         scanf("%d%d",&x,&y);

         int rx=find(x),ry=find(y);

         if(rx==ry) continue;

         else un(rx,ry);

     }

     scanf("%d",&q);

     while(q--)

     {

         int x,y;

         scanf("%d%d",&x,&y);

         int rx=find(x),ry=find(y);

         if(rx==ry) printf("Yes\n");

         else printf("No\n");

     }

     return ;

 }

Kursual:

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 struct node{

     int from,to,value;

     bool operator < (const node &a)const

     {

         return value<a.value;

     }

 }e[*];

 int n,m,fa[*];

 int find(int x)

 {

     if(fa[x]==x) return fa[x];

     else return fa[x]=find(fa[x]);

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int x,y,z,i=;i<=m;i++)

     {

         scanf("%d%d%d",&x,&y,&z);

         e[i].from=x;e[i].to=y;e[i].value=z;

     }

     sort(e+,e+m+);

     int cnt=,MST=;

     for(int i=;i<=n;i++)

       fa[i]=i;

     while(cnt<=n-)

     {

         cnt++;

         int x=e[cnt].from,y=e[cnt].to;

         int rx=find(x),ry=find(y);

         if(rx==ry) continue;

         else{

             fa[rx]=ry;MST+=e[cnt].value;

         }

     }

     printf("%d",MST);

     return ;

 }

Prim：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 int n,map[][],dis[],mst;

 bool exist[];

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++)

       for(int j=;j<=n;j++)

         scanf("%d",&map[i][j]);

     memset(exist,true,sizeof(exist));

     memset(dis,0x3f,sizeof(dis));

     dis[]=;

     for(int i=;i<=n;i++)

     {

         int k=;

         for(int j=;j<=n;j++)

           if(exist[j]==true&&dis[j]<dis[k])

             k=j;

         exist[k]=false;

         for(int j=;j<=n;j++)

         {

             if(exist[j]&&map[k][j]<dis[j])

               dis[j]=map[k][j];

         }

     }

     for(int i=;i<=n;i++)

       mst+=dis[i];

     printf("%d",mst);

     return ;

 }

拓扑：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #define N 510

 using namespace std;

 int ru[N],map[N][N],n,m;

 queue<int> q;

 int main()

 {

     scanf("%d%d",&n,&m);

     memset(ru,,sizeof(ru));

     memset(map,,sizeof(map));

     for(int x,y,i=;i<=n;i++)

     {

         scanf("%d%d",&x,&y);

         map[x][y]=;

         ru[y]++;

     }

     for(int i=;i<=n;i++)

       if(ru[i]==)

           q.push(i);

     while(!q.empty())

     {

         int x=q.front();q.pop();

         cout<<x<<' ';

         for(int i=;i<=n;i++)

         {

             if(map[x][i]==)

               ru[i]--;

             if(ru[i]==)

               q.push(i);

         }

     }

     return ;

 }

分解质因数：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<ctime>

using namespace std;

int n,ss[],a[],head;

bool ff[];

bool sss(int k)

{

    bool yes=true;

    for(int i=;i<k;i++)

      if(k%i==)

        yes=false;

    if(yes==false)

    {

        ff[k]=;

        return ;

    }

    else{

        head++;

        a[head]=k;

        for(int i=;i*k<;i++)

          ff[i*k]=;

        return ;

    }

}

void printff(int pp)

  {

      printf("%d=",n);

      for(int i=;i<pp;i++)

        {

            printf("%d*",ss[i]);

        }

    printf("%d\n",ss[pp]);

  }

void dfs(int k,int m,int p)

{

    for(int i=m;i<=head;i++)

      if(k%a[i]==)

      {

           if(k/a[i]==)

           {

              ss[p]=a[i];printff(p);

              exit();// 在搜索中卡时啥的比较有用，由搜索直接退出

         }

         else{

             ss[p]=a[i];

             dfs(k/a[i],i,p+);

         }

      }

}

int main()

{

    for(int i=;i<=;i++)

      if(ff[i]==)

        sss(i);

    scanf("%d",&n);

    dfs(n,,);

    return ;

}

// 其实这个题暴力枚举就好了

巴特西

NOIP 前夕模板整理

最新文章

热门文章

巴特西

NOIP 前夕 模板整理

最新文章

热门文章

NOIP 前夕模板整理