首页 > 代码库 > BZOJ 3758 数数 分段打表
BZOJ 3758 数数 分段打表
题目大意:求[l,r]区间内优美的数的个数。优美的数定义为,将十进制数分解得到的[0,9]之间的数可以分为两组,并且和相等。
思路:其实第一次听说要我打表我是拒绝的,因为,你不能让我打,我就马上去打,第一我要试一下,因为我不愿意打完了以后再cheat一些上去,代码“咣”一下,很短、很块,这样OIer出来一定会骂我,根本没有这样的表,就证明上面那个是假的。后来我也经过证实这个表确实是可以打的,我的同学大概打了2分钟左右,感觉还不错,后来我在打的时候也要求他们不要cheat,因为我要让OIer看到,我打完之后是这个样子,你们打完之后也会是这个样子!
。。。
打表大法好啊。遇到这种不会的题一定要想想能不能打表,运气好都能满分。首先数据范围过大,肯定不能直接打出所有的表。所以我们要将打表和暴力联系起来。我们按照5000000为一个块打表,代码也不会很长,然后剩下零碎的就可以暴力来搞了。
暴力背包不知道能不能过,但是看到神犇用了二进制优化背包,常数瞬间小的飞起,于是也用了。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #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; }
BZOJ 3758 数数 分段打表
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。