POJ 1019(プッシュ)

タイトルリンク:http://poj.org/problem?id=1019
数学が悪いのは硬傷だと思います...
各シーケンス1,2...kを一組と見なし、前処理a[i]は第i組が何ビット共有しているかを示す
繰返し式a[i]=a[i-1]+(int)log 10(1.0*i)+1であってもよい.
(int)log 10(1.0*i)+1はi番目の数字の桁数を表す
f[i]で前のiグループが何ビットあるかを表す
繰返し式f[i]=f[i-1]+a[i];
まず,nが何番目のグループにあるかを二分検索で判断し,nが何番目のグループにあるかのビットを算出する.
次いで、シーケンス1,2...kにおいてn−f[k−1]番目のビットが見出され、求められる
まず、シーケンスにおいてそのビットが存在する数、例えば1,2,3,...10が10番目のビットを見つけ、そのビットが10番目の数、すなわち10,
次に、そのビットがその数の中の何番目かを決定し、これは余剰をとることによって判断することができる.
もう1つの考え方は文字列処理に変換することであり,この方法は他の人を参考にする.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;

typedef __int64 LL;
const int INF=0x3f3f3f3f;
const int maxn=32000;
int T,n;
LL a[maxn],f[maxn];

void work(){
	f[0]=0;a[0]=0;
	for(int i=1;i<maxn;i++){
		a[i]=a[i-1]+(int)log10(1.0*i)+1;
		f[i]=f[i-1]+a[i];
	}
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
#endif
	work();
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		int len=0,i=1;
		int k=lower_bound(f,f+maxn,n)-f;
		int pos=n-f[k-1];
		for(i=1;len<pos;i++){
			len+=(int)log10(i*1.0)+1;
		}
		printf("%d
",(i-1)/(int)pow(10.0,len-pos)%10);
	}
	return 0;
}

文字列方式:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;

const int INF=0x3f3f3f3f;
const int maxn=32000;
int T,n;

typedef __int64 LL;

string toString(int x){
	string s;
	while(x){
		s.push_back(x%10+'0');
		x/=10;
	}
	reverse(s.begin(),s.end());
	return s;
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
#endif
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		LL top=2,len=1;
		string s="1";
		while(len<n){
			s+=toString(top);
			len+=s.length();
			top++;
		}
		cout<<s[s.length()-(len-n)-1]<<endl;
	}
	return 0;
}