BZOJ 3758 數數 分段打表

BZOJ 3758 數數 分段打表

題目大意：求[l,r]區間內優美的數的個數。優美的數定義為，將十進制數分解得到的[0,9]之間的數可以分為兩組，並且和相等。

思路：其實第一次聽說要我打表我是拒絕的，因為，你不能讓我打，我就馬上去打，第一我要試一下，因為我不願意打完了以後再cheat一些上去，代碼“咣”一下，很短、很塊，這樣OIer出來一定會罵我，根本沒有這樣的表，就證明上面那個是假的。後來我也經過證實這個表確實是可以打的，我的同學大概打了2分鐘左右，感覺還不錯，後來我在打的時候也要求他們不要cheat，因為我要讓OIer看到，我打完之後是這個樣子，你們打完之後也會是這個樣子！

。。。

打表大法好啊。遇到這種不會的題一定要想想能不能打表，運氣好都能滿分。首先數據范圍過大，肯定不能直接打出所有的表。所以我們要將打表和暴力聯系起來。我們按照5000000為一個塊打表，代碼也不會很長，然後剩下零碎的就可以暴力來搞了。

暴力背包不知道能不能過，但是看到神犇用了二進制優化背包，常數瞬間小的飛起，於是也用了。

CODE：

#include 
#include 
#include 
#include 
#define BLOCK 5000000
using namespace std;

int num[] = {0,2196800,4366880,6782004,9182258,11590745,13996047,16403907,18810719,21199399,23601310,26006639,28401296,30780453,33151141,35517685,37865237,40194471,42514127,44818223,47111407,49526531,51926786,54395976,56858336,59346650,61832643,64321881,66811192,69295186,71781713,74267457,76751555,79230464,81704149,84170195,86626601,89074946,91513942,93959345,96400455,98808942,101214244,103702558,106188552,108643571,111104170,113592810,116080738,118549357,121025141,123509319,125991518,128456408,130927549,133393411,135853348,138306327,140761869,143209568,145654892,148062752,150469564,152958802,155448113,157936753,160424682,162870479,165316242,167797533,170282583,172764227,175244787,177698265,180151503,182627144,185104838,187569465,190034891,192474367,194913068,197301748,199703659,202187653,204674180,207142799,209618583,212099874,214584925,217007522,219446727,221919701,224393574,226859775,229333643,231805293,234281777,236714686,239165608,241610353,244056062,246461391,248856048,251341792,253825890,256310068,258792267,261273911,263754471,266227445,268701319,271155956,273606213,276086573,278564272,281035883,283502662,285965530,288427696,290873607,293317366,295696523,298067211,300546120,303019805,305484695,307955836,310409314,312862552,315328753,317802621,320282981,322760681,325172415,327585453,330052161,332510934,334957902,337405293,339842143,342276694,344643238,346990790,349456836,351913242,354379104,356839041,359314682,361792376,364264026,366740510,369212121,371678900,374145608,376604382,379003316,381388631,383833355,386266143,388702239,391130374,393459608,395779264,398227609,400666605,403119584,405575126,408039753,410505179,412938088,415389010,417851878,420314044,422761012,425208403,427653127,430085916,432434127,434779290,437207061,439626259,441930355,444223539,446668942,449110052,451557751,454003075,456442551,458881252,461325997,463771706,466217617,468661376,471098226,473532777,475968873,478397008,480824779,483243978,485561378,487875963};

inline bool Judge(int x)
{
	int sum = 0;
	for(int i = x; i; i /= 10)
		sum += (i % 10);
	if(sum&1)	return false;
	long long f = 1;
	for(int i = x; i; i /= 10)
		f |= (f << (i % 10));
	return f&(1LL << sum / 2);
}

inline int Ask(int x)
{
	int p = x / BLOCK;
	int re = num[p];
	for(int i = p * BLOCK + 1; i <= x; ++i)
		re += Judge(i);
	return re;
}

int main()
{
	int x,y;
	cin >> x >> y;
	cout << Ask(y) - Ask(x - 1) << endl;
	return 0;
}