首页 > ACM题库 > HDU-杭电 > HDU 2947-Bicycle Puzzle-最小生成树-[解题报告]HOJ
2014
02-24

HDU 2947-Bicycle Puzzle-最小生成树-[解题报告]HOJ

Bicycle Puzzle

问题描述 :

Per and Gunnar has found a wonderful online bicycle picture puzzle fiash solitaire game, and since they are very competitive, they want to find out who is best.

The purpose of the game is to descramble a picture of a bicycle. At the start of each game, the picture of the bicycle is cut into W times H equally sized rectangles and scrambled randomly.


Then the player repeatedly chooses two arbitrary rectangles and swaps them. He continues to swap rectangles until the picture is complete again. The game keeps track of the number of swaps, which is the score for that particular playthrough.

After Gunnar has played a game, he sends his score (along with W and H) to Per, and challenges Per to beat this score. Per soon realizes that if he is unlucky with the scrambling, it is impossible to beat Gunnar’s score.

Per quickly writes a program to find out the probability that he can beat Gunnar’s score (assuming that all scrambled pictures are equally probable) if he plays optimally.

But he is not sure whether his program is correct and wants to verify its correctness by challenging you to write the same program.

输入:

The first line of the input consists of a single number T, the number of scenarios. Each scenario is given by a line with three integers W, H and S, where S is Gunnar’s last score.

输出:

The first line of the input consists of a single number T, the number of scenarios. Each scenario is given by a line with three integers W, H and S, where S is Gunnar’s last score.

样例输入:

3
1 1 1
1 2 1
3 1 2

样例输出:

1
1/2
2/3

#include <stdio.h>
long long eular(long long n){
    long long ret=1,i;
    for(i=2;i*i<=n;i++)
        if (n%i==0){
            n/=i,ret*=i-1;
            while (n%i==0)
                n/=i,ret*=i;
        }
        if (n>1)
            ret*=n-1;
        return ret;    //n的欧拉数
}
int main(){
    long long n;
    while(scanf("%lld",&n)==1&&n){
        long long sum=n*(n+1)/2-n;
        sum-=eular(n)*n/2;
        printf("%lld\n",sum%1000000007);
    }
    return 0;
}

解题参考:http://blog.csdn.net/jjaw2013/article/details/19035353


  1. 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.

  2. if(j){
    int ans=a ;
    for(int x=j-1;x>=0;x–){
    if(!a ) break;
    ans=min(ans,a );
    sum+=ans;
    }
    }
    求解释,,dp的思路是什么呢?

  3. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!