National Olympiad in Informatics in Provinces 2010 Preparation Tasks with Implemented Algorithms

This is an article recomposed base on my draft for preparing China NOIP 2010 when I was a senior high school student.

Sorry for the mess in terms of coding style. (Too young too simple, no care for coding styles.)

1 Calculating expressions [求表达式的值]

Input Sample [输入样例]

100*21-8+21*2/3-2^2^2*32/2+2*(7+8/2)

Output Sample [输出样例]

1872

Code [程序代码]

#include<stdio.h>
#include<math.h>
#include<string.h>
FILE *in,*out;
char a[1001]={0};
int n,ji=0,f[5]={1,2,3,4,5},wz=0,b[101],shu[1001]={0},m=0,fu[2][1001]={0},k=0;

void swap(int x[],int i,int j)
{int tem;
 tem=x[i];
 x[i]=x[j];
 x[j]=tem;
}

int function(int i,int j)
{if(i==j)
    return(shu[i]);
 else
 {int t=0;
  while(fu[1][t]<i||fu[1][t]>=j) t++;  
  int tem;
  if(fu[0][t]%6==1)
   tem=function(i,fu[1][t])+function(fu[1][t]+1,j);
  else if(fu[0][t]%6==2)
   tem=function(i,fu[1][t])-function(fu[1][t]+1,j);
  else if(fu[0][t]%6==3)
   tem=function(i,fu[1][t])*function(fu[1][t]+1,j);
  else if(fu[0][t]%6==4)
   tem=function(i,fu[1][t])/function(fu[1][t]+1,j);
  else if(fu[0][t]%6==5)
    tem=(int)(pow(function(i,fu[1][t]),function(fu[1][t]+1,j)));
  return(tem);
 }
}

main()
{in=fopen("HQ.in","r");
 out=fopen("HQ.out","w");
 fscanf(in,"%s",a);
 n=strlen(a);

 int i;
 for(i=0;i<n;i++)
   {if(a[i]>=48&&a[i]<=57)
      shu[m]=shu[m]*10+(a[i]-48);
    else if(a[i]=='(')
      {ji+=6;}
    else if(a[i]==')')
      {ji-=6;}
    else if(a[i]=='+')
      {fu[0][k]=f[0]+ji;fu[1][k++]=m;m++;}
    else if(a[i]=='-')
      {fu[0][k]=f[1]+ji;fu[1][k++]=m;m++;}
    else if(a[i]=='*')
      {fu[0][k]=f[2]+ji;fu[1][k++]=m;m++;}
    else if(a[i]=='/')
      {fu[0][k]=f[3]+ji;fu[1][k++]=m;m++;}
    else if(a[i]=='^')
      {fu[0][k]=f[4]+ji;fu[1][k++]=m;m++;}
   }

 int j;
 for(i=0;i<k-1;i++)
    for(j=i;j<k;j++)
      {if((fu[0][i]+1)/2>=(fu[0][j]+1)/2)
         {swap(fu[0],i,j);
          swap(fu[1],i,j);
         }
      }

 fprintf(out,"%d\n",function(0,k));
}

2 Set calculation [集合的运算(交集、并集、减集、减加集)]

Input Sample [输入样例]

9 3 7 6 5
10 5 4 3 2 7

Output Sample [输出样例]

2 3 4 5 6 7 9 10
6 9
3 5 7
2 4 6 9 10

Code [程序代码]

#include<stdio.h>
#include<string.h>
FILE *in,*out;
int an,bn,a[101]={0},b[101]={0},d,z=0;
char c;

void swap(int x[],int i,int j)
{int tem;
 tem=x[i];
 x[i]=x[j];
 x[j]=tem;
}

void paixu(int x[],int len)
{int i,j;
 for(i=0;i<len-1;i++)
   for(j=i;j<len;j++)
      if(x[i]>x[j])
        swap(x,i,j);
}

void bingji(int x[],int y[])
{int i=0,j=0;
 while(i<an&&j<bn)
  {if(x[i]<y[j])
     fprintf(out,"%d ",x[i++]);
   else if(x[i]==y[j])
     {fprintf(out,"%d ",x[i++],j++);}
   else
     fprintf(out,"%d ",y[j++]);
  }
 while(i<an)
   fprintf(out,"%d ",x[i++]);
 while(j<bn)
   fprintf(out,"%d ",y[j++]);
 fprintf(out,"\n");
}

void chaji(int x[],int y[])
{int i=0,j=0;
 while(i<an&&j<bn)
  {if(x[i]<y[j])
     fprintf(out,"%d ",x[i++]);
   else if(x[i]==y[j])
     {i++;j++;}
   else
     j++;
  }
 while(i<an)
   fprintf(out,"%d ",x[i++]);
 fprintf(out,"\n");
}

void jiaoji(int x[],int y[])
{int i=0,j=0;
 while(i<an&&j<bn)
  {if(x[i]==y[j])
     fprintf(out,"%d ",x[i++],j++);
   else if(x[i]<y[j])
     i++;
   else
     j++;
  }
 fprintf(out,"\n");
}

void heji(int x[],int y[])
{int i=0,j=0;
 while(i<an&&j<bn)
  {if(x[i]<y[j])
     fprintf(out,"%d ",x[i++]);
   else if(x[i]==y[j])
     {i++;j++;}
   else
     fprintf(out,"%d ",y[j++]);
  }
 while(i<an)
   fprintf(out,"%d ",x[i++]);
 while(j<bn)
   fprintf(out,"%d ",y[j++]);
 fprintf(out,"\n");
}

main()
{in=fopen("set.in","r");
 out=fopen("set.out","w");
 z=0;
 while(1)
 {fscanf(in,"%d%c",&d,&c);
  if(c!=10)
    a[z++]=d;
  else
    {a[z++]=d;
     break;
    }
 }
 an=z; z=0;
 while(1)
 {fscanf(in,"%d%c",&d,&c);
  if(c!=10)
    b[z++]=d;
  else
    {b[z++]=d;
     break;
    }
 }
 bn=z;

 paixu(a,an);
 paixu(b,bn);

 bingji(a,b);
 chaji(a,b);
 jiaoji(a,b);
 heji(a,b);
}

3 Shortest distance between any two points in a matrix [邻接矩阵最短路径—求任意两点之间最短距离]

Input Sample [输入样例]

5
0 2 5 6 4
2 0 3 1 7
5 3 0 4 -1
6 1 4 0 5
4 7 -1 5 0

Output Sample [输出样例]

0 2 5 3 4
2 0 3 1 6
5 3 0 4 9
3 1 4 0 5
4 6 9 5 0

Code [程序代码]

Floyed Algorithm

#include<stdio.h>
#define MAX 2147483647
FILE *in,*out;
int m,n,dis[101][101]={0},d[101][101]={0},via[101][101][101]={0};

main()
{in=fopen("HQ.in","r");
 out=fopen("HQ.out","w");
 fscanf(in,"%d",&n);
 int i,j,k;
 for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
       {fscanf(in,"%d",&dis[i][j]);
        if(dis[i][j]==-1)
          dis[i][j]=MAX;
       }
 for(i=1;i<=n;i++)
    {for(j=1;j<=n;j++)
        d[i][j]=dis[i][j];
     for(k=1;k<=n;k++)
          via[i][j][k]=0;
     if(d[i][j]<MAX)
       via[i][j][i]=via[i][j][j]=1;
    }

 int l;
 for(k=1;k<=n;k++)
   for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        if(d[i][k]+d[k][j]<d[i][j])
            {d[i][j]=d[i][k]+d[k][j];
             for(l=1;l<=n;l++)
                via[i][j][l]=via[i][k][l]||via[k][j][l];
            }

 for(i=1;i<=n;i++)
    {for(j=1;j<=n;j++)
        fprintf(out,"%d ",d[i][j]);
     fprintf(out,"\n");
    }
 for(i=1;i<=n;i++)
    {for(j=1;j<=n;j++)
       printf("%d ",d[i][j]);
     printf("\n");
    }
 getch();
}

4 Shortest distance from one point to any other point in a matrix [邻接矩阵最短路径—求某一源点到其它点最短距离]

Input Sample [输入样例]

5
0 2 5 6 4
2 0 3 1 7
5 3 0 4 -1
6 1 4 0 5
4 7 -1 5 0

Output Sample [输出样例]

0 2 5 3 4

Code [程序代码]

#include<stdio.h>
#define MAX 2147483647
FILE *in,*out;
int m,n,dis[101][101]={0},f[101]={0},flag[101]={0};

main()
{in=fopen("HQ.in","r");
 out=fopen("HQ.out","w");
 fscanf(in,"%d",&n);
 int i,j;
 for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
       {fscanf(in,"%d",&dis[i][j]);
        if(dis[i][j]==-1)
          dis[i][j]=MAX;
       }
 for(i=2;i<=n;i++)
    f[i]=MAX;
 int min,q=1;
 flag[1]=1;
 for(i=1;i<=n;i++)
    {for(j=1;j<=n;j++)
        if(flag[j]==0&&dis[q][j]!=MAX&&(f[j]>f[q]+dis[q][j]))
          f[j]=f[q]+dis[q][j];
     min=MAX;
     for(j=1;j<=n;j++)
        if(flag[j]==0&&f[j]<min)
          {min=f[j];q=j;}
     flag[q]=1;
    }

 for(i=1;i<=n;i++)
     fprintf(out,"%d ",f[i]);
}

5 Shortest distance from one point to any other point in a chain [链表最短路径—求某一源点到其它点最短距离]

Input Sample [输入样例]

12 5
1 2 6
2 1 6
1 3 5
3 1 5
1 4 2
4 1 2
2 3 2
3 2 2
3 4 3
4 3 3
2 5 1
5 2 1

Output Sample [输出样例]

0 6 5 2 7

Code [程序代码]

#include<stdio.h>
#include<string.h>
#define MAX 2147483647
FILE *in,*out;

int n,m,f[101]={0},flag[101]={0};

typedef struct node1
{int dot;
 int data;
 struct node1 *next;
}bian;

typedef struct node2
{struct node1 *first;
 struct node1 *last;
 int flag;
}dian;

dian ddot[101];

void dfs()//深度优先搜索输出
{int i;
 bian *p;
 for(i=1;i<=m;i++)
    {p=ddot[i].first;
     while(p!=NULL)
       {printf("%d=%d ",p->dot,p->data);
        p=p->next;
       }
     printf("\n");
    }
}

main()
{in=fopen("HQ.in","r");
 out=fopen("HQ.out","w");
 memset(ddot,0,sizeof(ddot));
// printf("%d",sizeof(ddot[1])*101);getch();
 fscanf(in,"%d%d",&n,&m);
 int i,x;
 bian *p;
 for(i=1;i<=n;i++)
    {p=(bian*)malloc(sizeof(bian));
     p->next=NULL;
     fscanf(in,"%d",&x);
     fscanf(in,"%d%d",&p->dot,&p->data);
     if(ddot[x].first==NULL)
       {ddot[x].first=p;
        ddot[x].last=p;
       }
     else
       {ddot[x].last->next=p;
        ddot[x].last=p;
       }
    }
// dfs();

 for(i=2;i<=n;i++)
    f[i]=MAX;

 int q=1,min,r;
 ddot[1].flag=1;
 for(i=1;i<n;i++)
   {min=MAX;
    p=ddot[q].first;
    while(p!=NULL)
       {if(ddot[p->dot].flag==0&&f[p->dot]>(p->data+f[q]))
          f[p->dot]=p->data+f[q];
        if(ddot[p->dot].flag==0&&min>f[p->dot])
          {min=f[p->dot];
           r=p->dot;
          }
        p=p->next;
       }
    ddot[r].flag=1;
    q=r;
   }

 for(i=1;i<=m;i++)
     fprintf(out,"%d ",f[i]);
 for(i=1;i<=m;i++)
     printf("%d ",f[i]);
 getch();
}

6 Build the prime factors table [构建质因数表]

int prime[5000],k=0;
void buildprime(int maxn)
{int i,j,square1,square2,a[45826]={0};
 square1=sqrt(maxn);
 square2=sqrt(square1)+1;
 for(i=2;i<=square2;i++)
    if(!a[i])
       for(j=i*i;j<=square1;j=j+i)
          a[j]=1;
 for(i=2;i<=square1;i++)
    {if(!a[i])
       prime[++k]=i;
    }
}

7 Calculate the maximum prime factor less than 1000000 and build the prime factors table [求1000000以内数的最大质因子及构建素数表]

#define maxb 1000000
long int prime[maxb+1],maxfact[maxb+1];

for(i=0;i<=maxb;i++)
     maxfact[i]=i;
 i=2;
 while(i*i<=maxb)
     {if (maxfact[i]==i)
         {j=i*2;
          while(j<=maxb)
              { while(maxfact[j]%i==0)
                     maxfact[j]=maxfact[j]/i;
                if(maxfact[j]<i)
                   maxfact[j]=i;
                j=j+i;
               }
          }
      i=i+1;
     }
 total=-1;
 for (i=1;i<=b;i++)
         if(maxfact[i]==i)
            {total=total+1;
             prime[total]=i;
            }

8 The non-increase longest subsequence length [最长非升子序列长度]

Input Sample [输入样例]

5
5 4 3 2 1

Output Sample [输出样例]

5

Code [程序代码]

#include<stdio.h>
FILE *in,*out;
int n,a[100001]={0},b[100001]={0},len=1;

void work(int i)
{int mid,l=1,r=len;
 while(l<=r)
   {mid=(l+r)/2;
    if(b[mid]==a[i])
      return;
    else if(b[mid]>a[i])
      l=mid+1;
    else r=mid-1;
   }
 if(l>len)
   {len++;
    b[len]=a[i];
   }
 else b[l]=a[i];
// printf("%d************/n",i);getch();
}

main()
{in=fopen("xulie.in","r");
 fscanf(in,"%d",&n);
 int i;
 for(i=1;i<=n;i++)
    fscanf(in,"%d",&a[i]);
 fclose(in);
 b[1]=a[1];
 for(i=2;i<=n;i++)
   if(a[i]!=0)
    work(i);
 out=fopen("xulie.out","w");
 if(n!=0)
 fprintf(out,"%d\n",len);
 else
 fprintf(out,"%d\n",0);
 fclose(out);
}

9 Random Numbers [随机数用法]

#include<time.h>
#include<stdlib.h>
main()
{goto l1;
 printf("%d",5);
 l1:  
 srand((int)time(NULL));
 printf("%d",rand()%100);
}

9 long integer plus and multiply [长整数加法与乘法]

#include<stdio.h>
#include<string.h>
#include<math.h>
int c[40][101]={0},answer[201]={0};
int a[101]={0},b[101]={0};

void Sum(int x[],int y[],int tem[])
{int i;
 tem[200]=(y[100]>=x[100]? y[100]:x[100]);
 for(i=0;i<tem[200];i++)
       {tem[i]+=x[i]+y[i];
        tem[i+1]=tem[i]/10000;
        tem[i]=tem[i]%10000;
       }
 if(tem[tem[200]]>0)
    tem[200]++;
}

void Quadrature(int x[],int y[],int tem[])
{int i,j;
 tem[200]=y[100]+x[100]-1;
 for(i=0;i<x[100];i++)
    for(j=0;j<y[100];j++)
       {tem[i+j]+=x[i]*y[j];
        tem[i+j+1]+=tem[i+j]/10000;
        tem[i+j]=tem[i+j]%10000;
       }
 if(tem[tem[200]]>0)
    tem[200]++;
}
void Subtract(int x[],int y[],int tem[])
{int i;
 tem[200]=x[100];
 for(i=0;i<tem[200];i++)
    tem[i]=x[i]-y[i];
 for(i=0;i<tem[200]-1;i++)
   if(tem[i]<0)
     {tem[i+1]=tem[i+1]-1;
      tem[i]=tem[i]+10000;
     }
 while(tem[tem[200]-1]==0) tem[200]--;
}

void shuru(int x[])
{int i=0,wz,quan;
 char tmp[401];
 scanf("%s",tmp);
 tmp[400]=strlen(tmp);
 wz=-1;
 quan=1;
 for(i=tmp[400]-1;i>=0;i--)
    {if(quan==1)
       wz++;
     x[wz]+=(tmp[i]-48)*quan;
     quan*=10;
     if(quan>1000) quan=1;
    }
 x[100]=tmp[400]/4+1;
}

void shuchu(int first,int end,int x[])
{int i;
 printf("%d",x[first]);
 for(i=first-1;i>=end;i--)
     {printf("%d%d%d%d",x[i]/1000,x[i]/100%10,x[i]/10%10,x[i]%10);}
 printf("\n");
 getch();
}

main()
{int i;
 shuru(a);
 shuru(b);

 memset(answer,0,sizeof(answer));//求和
 Sum(a,b,answer);
 shuchu(answer[200]-1,0,answer);

 memset(answer,0,sizeof(answer));//求积
 Quadrature(a,b,answer);
 shuchu(answer[200]-1,0,answer);

 memset(answer,0,sizeof(answer));//求差
 if(a[100]<b[100]||(a[100]==b[100]&&a[a[100]-1]<b[b[100]-1]))
   {Subtract(b,a,answer);printf("-");
    shuchu(answer[200]-1,0,answer);}
 else
   {Subtract(a,b,answer);
    shuchu(answer[200]-1,0,answer);}
}

* first generated at 2017-12-02 07:32:08 © http://articles.johannhuang.com

Subscribe by RSS