0w1

CFR 637 C. Promocodes with Mistakes ( Ad hoc, Bruteforce )

Problem - C - Codeforces

題意:
給若干個條碼,由六個 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;
}