|
@[目錄]（目錄）
題目鏈接
#題解
題目倒不難, 算法思路也容易想到; 可是… 題目考的是(卡時間)
對於每個數A, 放入A*10, A*100, A*..., A*10^10即, 需要一個: unordered_map< int, int> cont[ 10]的結構兩次for( N)的循環, 一次是正向, 一次是逆向; (也可以一次for循環, 但那樣, 又需要一個map來記錄, 空間更大了; 其實卡時間, 不會在出這種問題上, 因為這是線性的沒關係的)
他的時間是: 2 * N * 10 * log(M) ; N是2e5, M是2e5(有10個哈希表, 一個哈希表是最多2e5個) , 即2e5 * 600 = 1e8; **對時間, 一定要精確的計算!! ** (看似可以, 但遇到這種情況, 往往就是卡常數, 經常出現的地方 , 時間非常極限, 但要知道哈希表map 的常數, 是很大的!!!)這道題, 卡時間卡的非常嚴格…
即, 此時要手寫哈希表;
对 unordered_map< int, int> cont[ 10]这个结构, 他是两个key: {a, b} -> int
其中, a是下标[0 - 9], b是个[0, 1e9]的值
方式一:
int Hash_cont_id[ 10][ Hash_size_];
int Hash_cont_val[ 10][ Hash_size_];
照猫画虎, 上面是10个哈希表, 这里也(手写10个哈希表)!
一个哈希表里, 最多是2e5个元素;
这里说下结论:
(1, 如果用朴素线性探测, 是会超时的… 不管Hash_size_是多少)
(2, 如果用平方探测, Hash_size_取到: 600009时, 可以通过)
(3, 不管怎么, Hash_size_必须是质数!!)
方式二:
有时也不要太单板, 对于:{a, b} -> int
其实我们在unordered_map时, 也不需要非得是10个哈希表; 用一个就可以了;
因为: a=[0-9], b=[0,1e9], 那么, 我们在哈希里讲过, 固定长度的元组的哈希, 此时用: b * 10 + a, 就可以映射成一个LL数, 是不冲突的;
… 从实际来看, 我们把两者哈希到一起从而全放到一个哈希表里, 比上面的用10个哈希表的方式, 要更好;
… (什么原因呢? 理论上他俩是一样的, 因为元素个数一样; 是因为高维数组的访问慢吗?)
因此, 用一个哈希表即可:
Ll_ Hash_cont_id[ Hash_size_]; (注意, 以前是存的a, 是int; 现在是个LL)
int Hash_cont_val[ Hash_size_];
他的个数是10*2e5 = 2e6
經過實踐檢測: (1, 用線性探測, Hash_size_取到3000037) (2, 用平方探測, Hash_size_取到3000037) ** (3, 不管怎麼, Hash_size_必須是質數!!) **
|