今天看Thinking in Java看到一个吸血鬼数的问题，于是查找UVa里也有类似的问题就动手写了先是用Java写的，不过WA了两次，然后没有发现错误，又用c++写的还是不行。最后发现要排序去重。然后改用Java的SortedSet解决了这个问题，主要就是暴力枚举求解。但是同样的算法Java用了将近5秒。c++只用了1秒。差距啊。还有避免不必要的重复的循环不能为00，还有不能为奇数。尽量提高程序的效率。
题目描述：
Problem D
Vampire Numbers
Input: standard input
Output: standard output
Time Limit: 5 seconds
A number v = xy with an even number (n) of digits formed by multiplying a pair of n/2-digit numbers (where the digits are taken from the original number in any order) x and y together is known as vampire number. Pairs of trailing zeros (Both the numbers have a trailing zero) are not allowed. If v is a vampire number then x and y are called its "fangs." Examples of 4-digit vampire numbers include
1) 21 x 60 = 1260
2) 15 x 93 = 1395
3) 35 x 41 = 1435
4) 30 x 51 = 1530
5) 21 x 87 = 1827
6) 27 x 81 = 2187
7) 80 x 86 = 6880
In this program you will have to find all the 4, 6 and
8 digit even vampire numbers.
Input
The input file contains maximum ten lines of input. Each line contains a single integer n whose value is
4, 6 or 8. Input is terminated by end of file.
Output
For each input n produce all the n-digit vampire numbers that are even in ascending order. Print a blank line after the output for each set of input.
Sample Input:
4
4
Sample Output:
1260
1530
6880
1260
1530
6880
代码如下：
#include<iostream>
#include<cstring>
#include<cstdio> using namespace std; int main()
{
bool isNum(int a,int b);
int n;
int range[] = {1,10,100,1000,10000};
int set[10][10000],flag[10];
memset(set,0,sizeof(range));
memset(flag,0,sizeof(flag));
while(scanf("%d",&n) != -1)
{
if(flag[n] == -1)
{
int k = 0;
for(int i=range[n / 2 - 1]; i<range[n / 2]; i++)
{
for(int j=i; j<range[n / 2]; j++)
{
if(i % 2 != 0 && j % 2 != 0)continue;
if(i % 10 == 0 && j % 10 == 0)continue;
if(isNum(i,j))
{
set[n][k] = i * j;
k++;
}
}
} }
flag[n] = -1;
for(int i=0; ; i++)
{
if(set[n][i] == 0)break;
printf("%d",set[n][i]);
}
printf("\n"); } }
bool isNum(int a,int b)
{
int arr[10];
int mult = a * b;
while(a != 0)
{
arr[a % 10]++;
a /= 10;
}
while(b != 0)
{
arr[b % 10]++;
b /= 10;
}
while(mult != 0)
{
arr[mult % 10]--;
mult /= 10;
}
for(int i=0; i<10; i++){
if(arr[i] != 0)
return false;
}
return true;
}
Java代码：
<pre class="java" name="code">import java.util.*;
public class Main10396 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int[] range = {1,10,100,1000,10000};
Object[] temp = new Object[100000];
int[] flag = new int[10];
SortedSet<Integer> set4 = new TreeSet<Integer>();
SortedSet<Integer> set6 = new TreeSet<Integer>();
SortedSet<Integer> set8 = new TreeSet<Integer>();
while(scan.hasNext()){
int n = scan.nextInt();
int k = 0;
if(flag[n] != -1){
for(int i=range[n / 2 - 1]; i<range[n / 2]; i++){
for(int j=i; j<range[n / 2]; j++){
if((i % 2 != 0)&& (j % 2 != 0))continue;//除去奇数
if(i % 10 == 0 && j % 10 == 0)continue;//除去00
if(isNum(i,j) == true){
if(n == 4){
set4.add(i * j);
}
if(n == 6){
set6.add(i * j);
}
if(n == 8){
set8.add(i * j);
}
}
}
}
}
flag[n] = -1;
if(n == 4){
for(int i : set4){
System.out.println(i);
}
}
if(n == 6){
for(int i : set6){
System.out.println(i);
}
}
if(n == 8){
for(int i : set8){
System.out.println(i);
}
}
System.out.println();
}
}
public static boolean isNum(int a,int b){
int[] arr = new int[10];
int mult = a * b;
while(a != 0){
arr[a % 10]++;
a /= 10;
}
while(b != 0){
arr[b % 10]++;
b /= 10;
}
while(mult != 0){
arr[mult % 10]--;
mult /= 10;
}
for(int i=0; i<10; i++){
if(arr[i] != 0)
return false;
}
return true;
}
}
最后说一句Tinking in Java 讲的不错。