首页 > 专题系列 > Java解POJ > POJ 2140 Herd Sums [解题报告] Java
2013
11-10

POJ 2140 Herd Sums [解题报告] Java

Herd Sums

问题描述 :

The cows in farmer John’s herd are numbered and branded with consecutive integers from 1 to N (1 <= N <= 10,000,000). When the cows come to the barn for milking, they always come in sequential order from 1 to N.

Farmer John, who majored in mathematics in college and loves numbers, often looks for patterns. He has noticed that when he has exactly 15 cows in his herd, there are precisely four ways that the numbers on any set of one or more consecutive cows can add up to 15 (the same as the total number of cows). They are: 15, 7+8, 4+5+6, and 1+2+3+4+5.

When the number of cows in the herd is 10, the number of ways he can sum consecutive cows and get 10 drops to 2: namely 1+2+3+4 and 10.

Write a program that will compute the number of ways farmer John can sum the numbers on consecutive cows to equal N. Do not use precomputation to solve this problem.

输入:

* Line 1: A single integer: N

输出:

* Line 1: A single integer that is the number of ways consecutive cow brands can sum to N.

样例输入:

15

样例输出:

4

解题代码:

import java.util.*;   
  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner cin = new Scanner(System.in);   
           
        while(cin.hasNext())   
        {   
            int num = cin.nextInt();   
            int ways = 1;   
               
            int index = num/2+1;   
               
            for(int i = index; i > 1; i--)   
            {   
                int tmpNum = i;   
                for(int j = i - 1; j > 0; j--)   
                {   
                    tmpNum += j;   
                    if(tmpNum == num)   
                    {   
                        ways++;   
                        break;   
                    }else if(tmpNum > num)   
                        break;   
                }   
            }   
            System.out.println(ways);   
               
               
        }   
  
    }   
  
}

  1. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

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

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

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

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