[UVa] 10049 - Self-describing Sequence

題目網址: http://goo.gl/YH2Vad

題意: 有個序列正整數的特質為k在序列中會出現連續f(k)次，還是直接看題目好了解....，然後題目要求f(n)，1 <= n <= 2000000000。



解法:由於n會到2000000000，所以應該不可能直接開個陣列模擬巴...，要解這題要先定義另一個數列 s，滿足 s(x) 為 f 數列中 f(t) = x 且 t 盡量大，舉 s 數列的前幾項， s(1) = 1, s(2) = 3, s(3) = 5, s(4) = 8, s(5) = 11...，如果看題目的附表應該能很快理解，接著要可以推出 s(n) 的算法為 s(n) = s(n-1) + f(n) ，而獲得 s 數列後，就可以推出 f(n) = k, s(k) > n 且 k 盡量小，只要求出所需的 s 數列，以 binary search 在 s 數列找出滿足條件的 lower bound 即可，而藉由題目的測資，可以慢慢估出 s 數列只需要求到約 700,000 ，就可以推出長度為2*10^9的 f 數列了，而 s(n) 可以由下往上的方式遞推出來，可以勉強算是DP巴。

TAG: DP, binary search

注意:

程式碼:

	/**
	* Tittle: 10049 - Self-describing Sequence
	* Author: Cheng-Shih, Wong
	* Date: 2015/03/09
	* File: 10049 - Self-describing Sequence.cpp - solve it
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 1000005
	// declarations
	int n;
	int dp[N];
	int dpl;
	// functions
	int f( int v, int l, int r )
	{
	int mid;
	while( l <= r ) {
	mid = (l+r)/2;
	if( dp[mid] >= v ) r = mid-1;
	else l = mid+1;
	}
	return l;
	}
	// main function
	int main( void )
	{
	// init
	dp[1] = 1;
	dp[2] = 3;
	dpl = 2;
	FOR( i, 3, 700000 )
	dp[i] = dp[i-1]+f(i,1,dpl++);
	// input
	while( scanf( "%d", &n )==1 && n ) {
	// solve & output
	printf( "%d\n", f(n,1,dpl) );
	}
	return 0;
	}

view raw 10049 - Self-describing Sequence.cpp hosted with ❤ by GitHub