首页 > 专题系列 > Java解POJ > POJ 2190 ISBN [解题报告] Java
2013
11-10

POJ 2190 ISBN [解题报告] Java

ISBN

问题描述 :

Farmer John’s cows enjoy reading books, and FJ has discovered that his cows produce more milk when they read books of a somewhat intellectual nature. He decides to update the barn library to replace all of the cheap romance novels with textbooks on algorithms and mathematics. Unfortunately, a shipment of these new books has fallen in the mud and their ISBN numbers are now hard to read.

An ISBN (International Standard Book Number) is a ten digit code that uniquely identifies a book. The first nine digits represent the book and the last digit is used to make sure the ISBN is correct. To verify that an ISBN number is correct, you calculate a sum that is 10 times the first digit plus 9 times the second digit plus 8 times the third digit … all the way until you add 1 times the last digit. If the final number leaves no remainder when divided by 11, the code is a valid ISBN.

For example 0201103311 is a valid ISBN, since

10*0 + 9*2 + 8*0 + 7*1 + 6*1 + 5*0 + 4*3 + 3*3 + 2*1 + 1*1 = 55.

Each of the first nine digits can take a value between 0 and 9. Sometimes it is necessary to make the last digit equal to ten; this is done by writing the last digit as X. For example, 156881111X is a valid ISBN number.

Your task is to fill in the missing digit from a given ISBN number where the missing digit is represented as ‘?’.

输入:

* Line 1: A single line with a ten digit ISBN number that contains ‘?’ in a single position

输出:

* Line 1: The missing digit (0..9 or X). Output -1 if there is no acceptable digit for the position marked ‘?’ that gives a valid ISBN.

样例输入:

15688?111X

样例输出:

1

解题代码:

//* @author: [email protected]
import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  String a=in.next();
  int t=0;
  int n=-1;
  for(int i=0;i< 10;i++)
  {
	char c=a.charAt(i);
	if(c!='?'&&c!='X'){
	  t+=(c-'0')*(10-i);
	}
	else if(c=='X') t+=10;
	else if(c=='?') n=10-i;
   }
   int ans=-1;
   if(n!=1)
    for(int i=0;i< 10;i++)
    {
	if((t+n*i)%11==0){
		ans=i;
		break;
	}
    }
    else if(n==1)
    {
	for(int i=0;i< 11;i++)
	  if((t+i)%11==0){
		ans=i;
		break;
	  }
    }
    if(ans==10) System.out.println("X");
    else
	System.out.println(ans);
  }
}

  1. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  2. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮