Yuki 6 使いものにならないハッシュ ( Deque )
No.6 使いものにならないハッシュ - yukicoder
題意:
給 L, R,代表所求區間 [ L, R ] 中,如程式碼中的 get_hash() 函數,最長區間 [ l, r ] 滿足 get_hash( i | l ≤ i ≤ r ) 皆相異,其最大可能的 l。
資料規模:
L, R ≤ 2e5
解法:
用 deque,從後面掃回來,每次遇到碰撞就從 deque 的後面 pop 出來。
時間 / 空間複雜度:
O( R )
#include <bits/stdc++.h> using namespace std; int get_hash( int v ){ if( v < 10 ) return v; int u = 0; while( v ) u += v % 10, v /= 10; return get_hash( u ); } signed main(){ int L, R; cin >> L >> R; vector< int > cnt( 10 ); deque< int > dq; int maxlen = 0, ans = -1; for( int i = R; i >= L; --i ){ int ng = i == 1; for( int j = 2; j * j <= i; ++j ) ng |= i % j == 0; if( ng ) continue; int hv = get_hash( i ); while( cnt[ hv ] ) --cnt[ dq.back() ], dq.pop_back(); ++cnt[ hv ], dq.emplace_front( hv ); if( maxlen < dq.size() ) maxlen = dq.size(), ans = i; } cout << ans << endl; return 0; }