首页 > ACM题库 > HDU-杭电 > HDU 3049-Data Processing-数论-[解题报告]HOJ
2014
02-27

HDU 3049-Data Processing-数论-[解题报告]HOJ

Data Processing

问题描述 :

Chinachen is a football fanatic, and his favorite football club is Juventus fc. In order to buy a ticket of Juv, he finds a part-time job in Professor Qu’s lab.
And now, Chinachen have received an arduous task――Data Processing.
The data was made up with N positive integer (n1, n2, n3, … ), he may calculate the numberXX’s puzzle , you can assume XX’s puzzlemod N =0. Because the number is too big to count, so P mod 1000003 is instead.
Chinachen is puzzled about it, and can’t find a good method to finish the mission, so he asked you to help him.

输入:

The first line of input is a T, indicating the test cases number.
There are two lines in each case. The first line of the case is an integer N, and N<=40000. The next line include N integer numbers n1,n2,n3… (ni<=N).

输出:

The first line of input is a T, indicating the test cases number.
There are two lines in each case. The first line of the case is an integer N, and N<=40000. The next line include N integer numbers n1,n2,n3… (ni<=N).

样例输入:

2
3
1 1 3
4
1 2 1 4

样例输出:

Case 1:4
Case 2:6
Hint
Hint: You may use “scanf” to input the data.

这题给定的数一定能被N整除,最后要%1000003,那么我们就%1000003*N;这样我们就不要担心数据过大的问题;

#include<stdio.h>
#include<stdlib.h>
int main()
{
   int T,n,x;
   __int64 num[40002];
   scanf( "%d",&T );
   for( int i=1; i<=T; i++ )
   {
        scanf( "%d",&n );
        __int64 ans=0,m=1000003;
        m*=n;
        num[0]=1;
        for( int j=1;j<=40000;j++ )
        {
           num[ j ]=num[j-1]<<1;
           if( num[j]>=m )
                 num[j]-= m;     
        }
        for( int j=0;j<n; j++ )
        {
             scanf( "%d",&x );
             ans+=num[x];
             if( ans >= m )
                ans -= m;      
        }
        ans/=n;
        printf( "Case %d:%I64d\n",i,ans );
   } 
   return 0;  
}

参考:http://www.cnblogs.com/bo-tao/archive/2011/08/31/2161265.html


  1. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  2. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.