POJ2527+多项式除法

模拟一遍即可。
注意一些特殊情况，见代码。
  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<math.h>
  4 #include<algorithm>
  5 #include<string.h>
  6 using namespace std;
  7 
  8 const int maxn = 10005;
  9 
 10 struct Ploy{
 11     int cnt;//项的数目
 12     int coe[ maxn ];//各项系数
 13     int exp[ maxn ];//各项指数
 14 }a;
 15 struct Ploy2{
 16     int coe1,coe2;
 17     int exp1,exp2;
 18 }b;
 19 struct Ploy3{
 20     int coe,exp;
 21 }tmp;
 22 
 23 bool Judge( int aim ){
 24     //bool f = false;
 25     for( int i=a.cnt-1;i>=0;i-- ){
 26         if( a.coe[i]!=0&&a.exp[i]>=aim ){
 27             //f = true;
 28             return true ;
 29         }
 30     }
 31     return false;
 32 }
 33 
 34 void solve( int n,int k ){
 35     //ans.cnt = 0;
 36     while( 1 ){
 37         //if( Judge(k)==false ) break;
 38         int i;
 39         for( i=a.cnt-1;i>=0;i-- ){
 40             if( a.coe[i]!=0 ){
 41                 tmp.coe = a.coe[i];
 42                 tmp.exp = a.exp[i];
 43                 break;
 44             }
 45         }
 46         if( tmp.exp<k ) break;
 47         int delta_exp = tmp.exp-k;
 48         int delta_coe = tmp.coe;//商
 49         b.exp1 = tmp.exp,b.coe1 = tmp.coe;
 50         b.exp2 = delta_exp,b.coe2 = delta_coe;
 51         //bool f1 = false,f2 = false;
 52         for( int i=0;i<a.cnt;i++ ){
 53             if( a.exp[i]==b.exp1 ){
 54                 a.coe[i] -= b.coe1;
 55                 //f1 = true;
 56             }
 57             if( a.exp[i]==b.exp2 ){
 58                 a.coe[i] -= b.coe2;
 59                 //f2 = true;
 60             }
 61         }
 62     }
 63 }
 64 
 65 int main(){
 66     //freopen("in.txt","r",stdin);
 67     //freopen("out.txt","w",stdout);
 68     int n,k;
 69     while( scanf("%d%d",&n,&k)==2 ){
 70         if( n==k&&k==-1 ) break;
 71         a.cnt = 0;
 72         for( int i=0;i<=n;i++ ){
 73             a.cnt ++;
 74             scanf("%d",&a.coe[i]);
 75             a.exp[i] = i;
 76         }
 77         if( k==0 ){
 78             puts("0");
 79             continue;
 80         }
 81         //printf("input
");
 82         bool f = false;
 83         for( int i=0;i<a.cnt;i++ ){
 84             if( a.coe[i]!=0 ){
 85                 f = true;
 86                 break;
 87             }
 88         }
 89         if( f==false ) {
 90             puts("0");
 91             continue;
 92         }//多项式全为0
 93         if( k>n ){
 94             for( int i=0;i<a.cnt;i++ ){
 95                 if( i==0 ) printf("%d",a.coe[i]);
 96                 else printf(" %d",a.coe[i]);
 97             }
 98             printf("
");
 99             continue;
100         }//商为0
101         //printf("solve
");
102         solve( n,k );
103         f = false;
104         for( int i=0;i<a.cnt;i++ ){
105             if( a.coe[i]!=0 ){
106                 f = true;
107                 break;
108             }
109         }
110         if( f==false ) {
111             puts("0");
112             continue;
113         }//刚好整除
114         int pos = a.cnt-1;
115         for( int i=a.cnt-1;i>=0;i-- ){
116             if( a.coe[i]!=0 ){
117                 pos = i;
118                 break;
119             }
120         }
121         for( int i=0;i<=pos;i++ ){
122             if( i==0 ) printf("%d",a.coe[i]);
123             else {
124                 printf(" %d",a.coe[i]);
125             }
126         }
127         printf("
");
128     }
129     return 0;
130 }
View Code
keep moving...