首页 > ACM题库 > 九度OJ > 九度-1016-火星A+B[解题代码]
2013
12-12

九度-1016-火星A+B[解题代码]

题目来源:2006年浙江大学计算机及软件工程研究生机试真题

题目描述:
    读入两个不超过25位的火星正整数A和B,计算A+B。需要注意的是:在火星上,整数不是单一进制的,第n位的进制就是第n个素数。例如:地球上的10进制数2,在火星上记为“1,0”,因为火星个位数是2进制的;地球上的10进制数38,在火星上记为“1,1,1,0”,因为火星个位数是2进制的,十位数是3进制的,百位数是5进制的,千位数是7进制的……
输入:
    测试输入包含若干测试用例,每个测试用例占一行,包含两个火星正整数A和B,火星整数的相邻两位数用逗号分隔,A和B之间有一个空格间隔。当A或B为0时输入结束,相应的结果不要输出。
输出:
    对每个测试用例输出1行,即火星表示法的A+B的值。
样例输入:
1,0 2,1
4,2,0 1,2,0
1 10,6,4,2,1
0 0
样例输出:
1,0,1
1,1,1,0
1,0,0,0,0,0

java 代码如下:
import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
	static final int  sarr[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281};
	public static void main(String[] args) {
		Scanner s = new Scanner(new BufferedInputStream(System.in));
		while(s.hasNext()){
			String s1 = s.next();
			String s2 = s.next();
			if(s1.equals("0") && s2.equals("0"))
				break;
			String[] nums1 = s1.split(",");
			String[] nums2 = s2.split(",");
			int[] num1 = new int[nums1.length];
			int[] num2 = new int[nums2.length];
			for(int i=0; i<num1.length;i++)
				num1[i] = Integer.parseInt(nums1[i]);
			for(int i=0; i<num2.length;i++)
				num2[i] = Integer.parseInt(nums2[i]);
			int len1 = num1.length;
			int len2 = num2.length;
			if(len1 > len2)
				add(num1,num2,len1,len2,len1-len2);
			else
				add(num2,num1,len2,len1,len2-len1);
		}
	}
	static void add(int[] num1,int[] num2,int l,int s,int k){
		int count = 0;
		int jin = 0;
		int[] reslut = new int[l];
		int last = reslut.length;
		for(int i=l-1; i>=0; i--){
			int a = num1[i];
			int b = 0;
			if(i-k>=0)
				b = num2[i-k];
			last--;
			if( a+b+jin >= sarr[count]){
				reslut[last] = a+b+jin - sarr[count];
				jin = 1;
			}else{
				reslut[last] = a+b+jin;
				jin = 0;
			}
			++count;
		}
		if(jin == 1)
			System.out.print(1+",");
		for(int i=0; i<reslut.length; i++){
			if(i== reslut.length-1)
				System.out.println(reslut[i]);
			else
				System.out.print(reslut[i]+",");
		}
			
	}
}

/**************************************************************
	Problem: 1016
	User: coder
	Language: Java
	Result: Accepted
	Time:390 ms
	Memory:21544 kb
****************************************************************/


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

  2. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了