1218862_ce.cc

北京大学ACM 2809 对初学者有很大帮助！

Source
#include<stdio.h>
#include<string.h>
char ch[10001];
int a[1001],b[1001],r[1001],x,an,len,sign_flag,flag,sum;
int count_np(int n,int p)
{
    if(p==0)return 1;
    int i,t=n;
    for(i=1;i<p;i++)n*=t;
    return n;
}    
int main()
{
    char t;
    int i,j,k,l,cn;
    scanf("%d",&cn);
    for(l=1;l<=cn;l++)
    {
        an=0;
        scanf("%d %s",&x,ch);
        printf("POLYNOMIAL %d\n",l);
        printf("%s\n",ch);
        len=strlen(ch);
        j=0;k=0;

        while(j<len)
        {
            a[k]=b[k]=0;
            if(ch[j]=='+')j++;
            if(ch[j]=='-')sign_flag=1,j++;else sign_flag=0;
            if(ch[j]>='0'&&ch[j]<='9')
            {
                while(ch[j]>='0'&&ch[j]<='9')
                {
                    a[k]=a[k]*10+ch[j]-48;
                    j++;
                }    
            }    
            else a[k]=1;
            if(sign_flag)a[k]=-a[k];
            if(ch[j]=='x')
            {
                j++;
                if(ch[j]=='^')
                {
                    j++;
                    b[k]=ch[j++]-48;
                }
                else b[k]=1;    
            }    
            k++;
        }    
        //for(i=0;i<k;i++)printf("i=%d a[i]=%d b[i]=%d\n",i,a[i],b[i]);
        flag=0;
        for(i=0;i<k;i++)
        {
            if(b[i]>0)
            {
                a[i]*=b[i]--;
                if(b[i]>0)
                {
                    if(i>0&&a[i]>0)printf("+");
                    if(a[i]!=1&&a[i]!=-1)printf("%dx",a[i]);
                    else if(a[i]>0)printf("x");
                    else printf("-x");
                    if(b[i]!=1)printf("^%d",b[i]);
                }    
                else
                {
                    if(i>0&&a[i]>0)printf("+");
                    printf("%d",a[i]);
                }    
                flag=1;
            }    
            else b[i]--;
        }    
        if(flag==0)printf("0");
        printf("\n");
        
        flag=0;
        for(i=0;i<k;i++)
        {
            if(b[i]>=0)
            {
                if(b[i]>0)
                {
                    if(i>0&&a[i]>0)printf("+");
                    if(a[i]!=1&&a[i]!=-1)printf("%d(%d)",a[i],x);
                    else if(a[i]>0)printf("(%d)",x);
                    else printf("-(%d)",x);
                    if(b[i]!=1)printf("^%d",b[i]);
                }    
                else
                {
                    if(i>0&&a[i]>0)printf("+");
                    printf("%d",a[i]);
                }    
                r[i]=count_np(x,b[i]);
                r[i]*=a[i];
                flag=1;
            }    
            else r[i]=0;
        }    
        if(flag==0)printf("0");
        printf("\n");
        sum=0;flag=0;
        for(i=0;i<k;i++)
        {
            if(b[i]>=0)
            {
                if(i&&r[i]>=0)printf("+");
                printf("%d",r[i]);
                sum+=r[i];
                flag=1;
            }    
        }    
        if(flag==0)printf("0");
        printf("\n");
        printf("%d\n",sum);
    }    
    return 0;
}