首页 > 专题系列 > Java解POJ > POJ 2527 Polynomial Remains [解题报告] Java
2013
11-11

POJ 2527 Polynomial Remains [解题报告] Java

Polynomial Remains

问题描述 :

Given the polynomial

a(x) = an xn + … + a1 x + a0,


compute the remainder r(x) when a(x) is divided by xk+1.

输入:

The input consists of a number of cases. The first line of each case specifies the two integers n and k (0 <= n, k <= 10000). The next n+1 integers give the coefficients of a(x), starting from a0 and ending with an. The input is terminated if n = k = -1.

输出:

For each case, output the coefficients of the remainder on one line, starting from the constant coefficient r0. If the remainder is 0, print only the constant coefficient. Otherwise, print only the first d+1 coefficients for a remainder of degree d. Separate the coefficients by a single space.

You may assume that the coefficients of the remainder can be represented by 32-bit integers.

样例输入:

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

样例输出:

3 2
-3 -1
-2
-1 2 -3
0
0
1 2 3 4

解题代码:

//* @author: 
import java.util.*;
public class Main{
 public static void main(String args[]){

  int val[]=new int[10001];
 
  Scanner in=new Scanner(System.in);
  while(true){
     int n=in.nextInt();
     int k=in.nextInt();
     if(n==-1&&k==-1) break;
     for(int i = 0; i <= n; i++){
         val[i]=in.nextInt();
       }
      for(int i = n; i >= k; i--){
	if (val[i] == 0){
	 continue;
	}
	val[i - k] -= val[i];
	val[i] = 0;
      }
	int s= n;
	while (val[s] == 0 && s > 0){
			s--;
	}
	for (int j = 0; j < s; j++){
          System.out.printf("%d ", val[j]);
	}
	  System.out.printf("%d\n", val[s]);
	}
    }
}

  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  3. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。