首页 > 数学相关 > 数论应用 > hdu 1586 Sending-数论应用-[解题报告]
2013
12-12

hdu 1586 Sending-数论应用-[解题报告]

Sending

问题描述 :

It’s said that "Writing a love-letter is mush easier than sending it out". After writing the love-letter with the help of ALM, Gardon is now planing how to send it to his Angel.
Er……In fact Gardon is too shy to send it directly. – -b So we needs to find some one to help him …As the old saying goes "You should pay to get something". Gardon must spend some money to buy gifts to someone who helps him. And there are also rules to give somebody gifts:
1. Some helpers need a number of gift.
2. If you ask A to send some gifts to B, besides the quantity of gifts A ordered, you must also give the same quantity of gifts to A as many as gifts you ask A to give B.

For example, there are four people, Angel, Bred, Cici, Dennis. Bred orderd two gifts, Cici and Dennis asked only one for themselves, and the way to send the letter is: Gardon==>Dennis==>Cici==>Bred==>Angel, so Gardon will buy Cici totally three gifts(one orded,the other two are paid for Cici sending gifts to Bred), and buy Dennis totally six gifts (one orded, the other two are paid for Dennis sending gifts to Cici). So totally Gardon need to buy eleven gifts – Bred two, Cici three, and Dennis six.

Now, giving every body’s name, the quantity of gifts he/she ordered, and all person he/she knows (One can ask anybody who he/she knows), could you tell Gardon how many gifts he need to buy?

输入:

Input starts with a integer T, and followed by T test cases.
In the begining of each case there is a integer N, which means how many person in the record.
Then N lines following, and each of them starts with a name. After their name, there are two integers V and C. V means the quantity of gifts he/she ordered, and following C names shows every person he/she knows.
You should know that all name is a word of at most 20 lowercases with a uppercase letter leading, and you can assume that there is no more than 1000 records in each test case. No one knows more than ten of others.
Everyone in the list will have a record except Angel.You’ll always have a record of Gardon.

输出:

For each test case inputed, please tell whether Gardon can send the letter out:
1. If he cannot, print "Please do it yourself!"
2. If he can, but should pay more than or equal with 1,000,000,000 gifts, print "It cost too many!"
3. Otherwise, print the gifts he needs to buy.

样例输入:

1
4
Bred 2 1 Angel
Cici 1 1 Bred
Dennis 1 1 Cici
Gardon 0 2 Dennis Angel

样例输出:

Case 1: 11

 log函数的应用,因为

log(a^b)=b*log(a);

log(a*b)=log(a)+log(b);

比如 log10(123456789)==log10(1.23456789)+8;

log(1.23456789)是log(123456789)的小数部分。

使用 pow()函数将其小数部分还原为1.23456789,然后就得到我们所求的 前4位了。

代码:

#include<cstdio>
#include<string.h>
#include<iostream>
#include<cmath>
using namespace std;
int F[22];
int main()
{
    int k=0;
     double sum,n,m1,m2;
     F[0]=0;F[1]=1;
    for(int i=2;i<21;i++)
            F[i]=F[i-1]+F[i-2];

     m1=-0.5*log10(5);

     m2=log10((1+sqrt(5))/2);
     while(scanf("%lf",&n)==1)
     {
         k=n;
         if(n>20)
            {
         sum=m1+n*m2;
         k=sum;
         sum=sum-k;
         sum=pow(10.0,sum);
         while(sum<1000)sum=sum*10;
         k=sum;
         printf("%d\n",k);
         }
         else printf("%d\n",F[k]);

     }

    return 0;
}

解题转自:http://blog.csdn.net/opaser/article/details/17611561


  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  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;
    }