CFR 637 C. Promocodes with Mistakes ( Ad hoc, Bruteforce )
題意:
給若干個條碼,由六個 0 ~ 9 之間的數字組成。求一個最大 K,保證就算打錯 K 個數字,依然可以確定是哪個條碼。
數據範圍:
條碼的數量 1 ≤ N ≤ 1000
解法:
首先顯然如果 N = 1,那一定是 K = 6,全部打錯都行。否則顯然 K = 3 以上不可能,因此只考慮 K ≤ 2。
用 '$' 符號表示打錯,也就是 wild card,那麼問題等價對於所有條碼用 '$' 覆蓋 K * 2 個數字後,是否唯一。
時間 / 空間複雜度:
O( N * 2 ^ 6 )
int N; vs code; void init(){ cin >> N; code = vs( N ); for( int i = 0; i < N; ++i ) cin >> code[ i ]; if( N == 1 ) cout << 6 << endl, exit( 0 ); } map< string, int > mask_code_cnt[ 6 + 1 ]; void preprocess(){ for( int i = 0; i < 1 << 6; ++i ) for( int j = 0; j < N; ++j ){ string s = code[ j ]; for( int k = 0; k < 6; ++k ) if( i >> k & 1 ) s[ k ] = '$'; ++mask_code_cnt[ __builtin_popcount( i ) ][ s ]; } } void solve(){ int ans = 2; for( int i = 2; i >= 1; --i ){ int ng = 0; for( int j = 0; j < 1 << 6; ++j ) if( __builtin_popcount( j ) == i * 2 ) for( int k = 0; k < N; ++k ){ string s = code[ k ]; for( int l = 0; l < 6; ++l ) if( j >> l & 1 ) s[ l ] = '$'; if( mask_code_cnt[ i * 2 ][ s ] > 1 ) ng = 1; } if( ng ) upmin( ans, i - 1 ); } cout << ans << endl; }