本文主要是介绍HDU 1597 find the nth digit HDU 2141 Can you find it?，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接~~>
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 ;
}
这篇关于HDU 1597 find the nth digit HDU 2141 Can you find it?的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
