首页 > 代码库 > poj1019（Number Sequence）
poj1019（Number Sequence）
题目地址：Number Sequence
题目大意：
有一串序列由阿拉伯数字够成11212312341234512345612345671234567812345678912345678910123456789101112345678910.......然后问你第几位数字是什么输出该数字。
解题思路：
排列组合。假如算第79位数字为多少，先计算出它在那个1-n的区间，可以看出79在1-12这段数字的区间，然后计算出前面1、1-2、1-3....1-11所有数的总和有多少位减去之后，再通过模拟在1-12区间内具体看79在1-12区间里的第几位，找到输出，可以看出前9个区间很容易看出C（1，1）、C（2，1）...C（9，1）。但是到第十个的时候就变了：
1 C（1，1）
1-2 C（2，1）
...
1-9 C（9，1）
1-10 C（10，1）+C（1，1）
1-11 C（11，1）+C（2，1）
...
1-99 C（99，1）+C（99-10+1，1）
1-100 C（100，1）+C（100-10+1，1）+C（1，1）
1-101 C（101，1）+C（101-10+1，1）+C（101-100+1，1）
...
依次类推因为输入的i 为2147483647，所以大约1-1000000 的时候位数就应该足够了。
具体看代码：
1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 //#include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 #define PI 3.1415927 21 /***************************************/ 22 const int INF = 0x7f7f7f7f; 23 const double eps = 1e-8; 24 const double PIE=acos(-1.0); 25 const int d1x[]= {0,-1,0,1}; 26 const int d1y[]= {-1,0,1,0}; 27 const int d2x[]= {0,-1,0,1}; 28 const int d2y[]= {1,0,-1,0}; 29 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 30 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 31 const int dirx[]= {-1,1,-2,2,-2,2,-1,1}; 32 const int diry[]= {-2,-2,-1,-1,1,1,2,2}; 33 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/ 34 /***************************************/ 35 void openfile() 36 { 37 freopen("data.in","rb",stdin); 38 freopen("data.out","wb",stdout); 39 } 40 priority_queue<int> qi1; 41 priority_queue<int, vector<int>, greater<int> >qi2; 42 /**********************华丽丽的分割线,以上为模板部分*****************/ 43 44 int main() 45 { 46 int cas; 47 scanf("%d",&cas); 48 while(cas--) 49 { 50 int n; 51 scanf("%d",&n); 52 long long sum=0; 53 int i,j; 54 long long a[10]; 55 memset(a,0,sizeof(a)); 56 int d=0; 57 long long ce1=0,ce2=0; 58 for(i=1;; i++) 59 { 60 if (i==10) 61 { 62 d=1; 63 a[d]=10; 64 } 65 else if (i==100) 66 { 67 d=2; 68 a[d]=100; 69 } 70 else if (i==1000) 71 { 72 d=3; 73 a[d]=1000; 74 } 75 else if (i==10000) 76 { 77 d=4; 78 a[d]=10000; 79 } 80 else if (i==100000) 81 { 82 d=5; 83 a[d]=100000; 84 } 85 sum+=i; 86 for(j=1; j<=d; j++) 87 { 88 sum+=i-a[j]+1; //计算前面区间多少个。 89 } 90 if(sum<n) 91 ce1=sum; 92 else 93 { 94 ce2=i; //记住i在哪个区间内 95 break; 96 } 97 } 98 long long cnt=1; 99 long long sum1=0;100 int Ce1=0,Ce2=0;101 for(i=1; i<=ce2; i++) //具体找到哪个数包含第i位102 {103 if (i>=100000)104 {105 cnt=6;106 }107 else if (i>=10000)108 {109 cnt=5;110 }111 else if (i>=1000)112 {113 cnt=4;114 }115 else if (i>=100)116 {117 cnt=3;118 }119 else if (i>=10)120 {121 cnt=2;122 }123 sum1+=cnt;124 if (sum1>=(n-ce1))125 {126 Ce2=i; 127 break;128 }129 else130 Ce1=sum1;131 }132 int f=n-ce1-Ce1; //然后找到包含第i位的数f 计算出i位为数f的第几位133 int ff;134 for(i=0;i<=cnt-f;i++)135 {136 if (i==cnt-f)137 {138 ff=Ce2%10;139 }140 else141 Ce2/=10;142 }143 printf("%d\n",ff);144 }145 return 0;146 }
poj1019（Number Sequence）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。