POJ 1019 解题报告

本文主要是介绍POJ 1019 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题我用的是两次二分，先求出在哪个组（1~1，1~2，1~3，。。。，1~99，。。。等都各自是一个组），然后再次二分，求出是这个组里面哪个数字。

思路是这位神牛是一样的：http://poj.org/showmessage?message_id=345696.但是代码相对于他的差了太多，二分都是自己手写的。lower_bound这个函数以后要多尝试用下。还有用公式求的：http://www.slyar.com/blog/poj-1019-cpp.html。我不觉得有什么可推广到别的题的可能。

thestoryofsnow

1019

Accepted

156K

0MS

C++

3526B

/* 
ID: thestor1 
LANG: C++ 
TASK: poj1019 
*/
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <limits>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cassert>using namespace std;const int MAXNDIGITS = 5;int main()
{// 1 ~ 9// 10 ~ 99// 2147483647	// scanf();std::vector<unsigned long long> totaldigits(MAXNDIGITS + 1, 0), NINEDIGITS(MAXNDIGITS + 1, 0), BASE(MAXNDIGITS + 2, 0), totaldigits2(MAXNDIGITS + 1, 0);totaldigits[0] = 0;NINEDIGITS[0] = 0;BASE[1] = 1;totaldigits2[0] = 0;for (int ndigits = 1; ndigits <= MAXNDIGITS; ++ndigits){totaldigits[ndigits] = totaldigits[ndigits - 1] + (NINEDIGITS[ndigits - 1] + ndigits + NINEDIGITS[ndigits - 1] + (BASE[ndigits] * 10 - BASE[ndigits]) * ndigits) * (BASE[ndigits] * 10 - BASE[ndigits]) / 2;// printf("[debug]%llu + %llu = %llu\n", totaldigits[ndigits - 1], (BASE[ndigits - 1] * 10 - BASE[ndigits - 1]) * ndigits, totaldigits[ndigits]);BASE[ndigits + 1] = BASE[ndigits] * 10;NINEDIGITS[ndigits] = NINEDIGITS[ndigits - 1] + (BASE[ndigits] * 10 - BASE[ndigits]) * ndigits;totaldigits2[ndigits] = totaldigits2[ndigits - 1] + (10 * BASE[ndigits] - BASE[ndigits]) * ndigits;}// for (int ndigits = 0; ndigits <= MAXNDIGITS; ++ndigits)// {// 	printf("ndigits: %2d, totaldigits: %llu, NINEDIGITS: %llu\n", ndigits, totaldigits[ndigits], NINEDIGITS[ndigits]);// }int T;scanf("%d", &T);for (int t = 0; t < T; ++t){int num;scanf("%d", &num);int ndigits = 1;while (totaldigits[ndigits] < num && ndigits <= MAXNDIGITS){ndigits++;}assert (ndigits <= MAXNDIGITS);if (totaldigits[ndigits] == num){printf("9\n");continue;}int low = BASE[ndigits], high = 10 * BASE[ndigits] - 1, mid;unsigned long long digits = 0;while (low <= high){mid = low + (high - low) / 2;digits = totaldigits[ndigits - 1] + (NINEDIGITS[ndigits - 1] + ndigits + NINEDIGITS[ndigits - 1] + (mid - BASE[ndigits] + 1) * ndigits) * (mid - BASE[ndigits] + 1) / 2;if (digits >= num){high = mid - 1;}else{low = mid + 1;}}// assert (totaldigits[ndigits - 1] + (NINEDIGITS[ndigits - 1] + ndigits + NINEDIGITS[ndigits - 1] + (low - BASE[ndigits] + 1) * ndigits) * (low - BASE[ndigits] + 1) / 2 >= digits);// ndigits, low, digitsdigits = totaldigits[ndigits - 1] + (NINEDIGITS[ndigits - 1] + ndigits + NINEDIGITS[ndigits - 1] + (low - 1 - BASE[ndigits] + 1) * ndigits) * (low - 1 - BASE[ndigits] + 1) / 2;// digits -= (NINEDIGITS[ndigits - 1] + (low - BASE[ndigits] + 1) * ndigits);// now it is [1, low]int ndigits2 = 1;while (digits + totaldigits2[ndigits2] < num && ndigits2 <= ndigits){ndigits2++;}assert (ndigits2 <= ndigits);digits += totaldigits2[ndigits2 - 1];low = BASE[ndigits2], high = 10 * BASE[ndigits2] - 1;unsigned long long digits2 = 0;while (low <= high){mid = low + (high - low) / 2;digits2 = digits + (mid - BASE[ndigits2] + 1) * ndigits2;if (digits2 >= num){high = mid - 1;}else{low = mid + 1;}}digits2 = digits + (low - BASE[ndigits2] + 1) * ndigits2;while (digits2 > num){low /= 10;digits2--;}printf("%d\n", low % 10);}return 0;  
}

这篇关于POJ 1019 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---