学步园

题目链接~~>

HDU 1597 find the nth digit

做题感悟：开始做时直接就考虑到了二分可以解决这个问题，没考虑找规律等等，本以为自己想的方法很好，但是百度了一下。

方法一：

            解题思路：用二分的方法求出在第几个数可以满足 n ，然后就可以对 9 取余了。

代码：

#include<stdio.h>
__int64 f[67000] ;
__int64 binary(__int64 le,__int64 rt,__int64 n)// 二分查找求上界
{
    __int64 mid ;
    while(le<rt)
    {
        mid=le+(rt-le)/2 ;
        if(f[mid]<=n)  le=mid+1 ;
        else   rt=mid ;
    }
    return  le ;
}
int main()
{
    __int64 n,i ;
    f[0]=0 ;
    for(i=1 ;i<=66000 ;i++)
       f[i]=f[i-1]+i ;
    int T ;
    scanf("%d",&T) ;
    while(T--)
    {
        scanf("%I64d",&n) ;
        __int64 x=binary(1,66000,n),temp ;// 二分查找在第几个数里
        if(f[x-1]==n)
                   printf("%I64d\n",(x-1)%9 ? (x-1)%9 : 9) ;
        else
        {
            if(f[x-1]>n)
                  x=x-1 ;
            temp=n-f[x-1] ;
            printf("%I64d\n",temp%9 ? temp%9 : 9) ;
        }
    }
    return 0 ;
}

方法二：

          解题思路：感觉和第一种方法差不多，但是很容易超时。

代码：

#include <stdio.h>
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m,a=1;
        scanf("%d",&m);
        n=m ;  // 去掉这个就超时
        while(n>a)
        {
            n-=a;
            a++;
        }
        printf("%d\n",n%9==0?9:n%9);
    }
    return 0;
}

方法三：

            直接上代码，没看懂，如果有明白的请指教。

代码：

#include <iostream>
#include <math.h>
using namespace std;

int main(){
int n;
double m;
double i,j;
unsigned long k;
scanf("%d",&n);
while(n--){
   scanf("%lf",&m);

   i = ceil((sqrt(1+8*m)-1)/2);

   k =m - i*(i-1)/2;
    
   if (k%9==0)
   {
    printf("9\n");
   }else{
    printf("%ld\n",k%9);
   }
}
return 0;
}

 HDU 2141 Can you find it?

做题感悟： 开始做这题时虽然懂得三层 for 循环超时，但是还是试了一下，结果……然后又把三个数组合并，然后二分，超内存……最后把两个数组合并Wa了，虽然Wa了但是看到希望了，仔细想了一下，AC。。。

做题思路：合并两个数组，二分查找。

代码：

#include<stdio.h>
#include<algorithm>
using namespace std ;
__int64 f[300005],fx[1005] ;
__int64 binary(__int64 le,__int64 rt,__int64 n) // 二分
{
    __int64 mid ;
    while(le<rt)
    {
        mid=le+(rt-le)/2 ;
        if(f[mid]==n) return  mid ;
        else if(f[mid]>n)  rt=mid ;
        else   le=mid+1 ;
    }
    return -1 ;
}
int main()
{
    __int64 g1[505],g2[505],g3[505] ;
    __int64 a,b,c,i,p=1,T,x,j ;
    while(scanf("%I64d%I64d%I64d",&a,&b,&c)!=EOF)
    {
        for(i=0 ;i<a ;i++)
           scanf("%I64d",&g1[i]) ;
        for(i=0 ;i<b ;i++)
           scanf("%I64d",&g2[i]) ;
        for(i=0 ;i<c ;i++)
           scanf("%I64d",&g3[i]) ;
        sort(g1,g1+a) ;
        __int64 r=0 ;
        for(i=0 ;i<b ;i++)
          for(j=0 ;j<c ;j++)
                 f[r++]=g2[i]+g3[j] ;
        sort(f,f+r) ;
        printf("Case %I64d:\n",p++) ;
        scanf("%I64d",&T) ;
        while(T--)
        {
            scanf("%I64d",&x) ;
            __int64 mx=-1 ;
            for(i=0 ;i<a ;i++)
            {
               mx=-1 ;
//               if(g1[i]>x) // 有可能存在负数，所以不可以这样
//               {
//                   mx=-1 ;
//                   break ;
//               }
               mx=binary(0,r,x-g1[i]) ;
               if(mx!=-1) break ;
            }
            printf("%s\n",mx!=-1 ? "YES" : "NO") ;
            mx=-1 ;
        }
    }
    return 0 ;
}