CF878D Magic Breeding

不妨考虑一种特殊情况，权值为 \(0/1\) 如何求解？

此时 \(k\) 个数可以表示为 \(n\) 位二进制数，

注意到位是独立的，将每一位拆开后最多只会有 \(\min(2^k,n)\) 种不同的情况。

而 \(2^k < n\) ， 那么我们可以忽略列数而关心列的状态

那么记 \(f_{i,S}\) 表示第 \(i\) 个元素，前 \(k\) 个元素构成的列的状态为 \(S\) 时该位的值。

那么，\(\max\) 操作相当于或， \(\min\) 操作相当于与。

对于一般情况，注意到答案只会是原来的 \(k\) 个元素的权值之一，枚举这个权值 \(v\) ，然后 \(\ge v\) 的位置视为 \(1\) , \(< v\) 的位置视为 \(0\),就转化为 \(0/1\) 的情况。

可以通过 bitset 优化做到 \(\mathcal O(2^k(k+\frac{q}{\omega}))\)

#include <bits/stdc++.h>
using namespace std;
#define pii pair< int , int >
#define fi first
#define sc second
#define mp make_pair

const int MAXN = 1e5 , MAXK = 12;
int n , k , q , a[ MAXK + 5 ][ MAXN + 5 ];
vector< pii > val[ MAXN + 5 ];
bitset< 1 << MAXK > f[ MAXN + 20 ];

int main( ) {
    scanf("%d %d %d",&n,&k,&q);
    for( int i = 1 ; i <= k ; i ++ ) {
        for( int j = 1 ; j <= n ; j ++ ) 
            scanf("%d",&a[ i ][ j ]) , val[ j ].push_back( mp( a[ i ][ j ] , i - 1 ) );
        for( int S = 0 ; S < 1 << k ; S ++ ) f[ i ][ S ] = ( S >> i - 1 ) & 1;
    }
    for( int j = 1 ; j <= n ; j ++ ) sort( val[ j ].begin() , val[ j ].end() );

    int cnt = k;
    for( int i = 1 , t , x , y ; i <= q ; i ++ ) {
        scanf("%d %d %d",&t,&x,&y);
        if( t == 1 ) f[ ++ cnt ] = f[ x ] | f[ y ];
        if( t == 2 ) f[ ++ cnt ] = f[ x ] & f[ y ];
        if( t == 3 ) {
            int ans = 0;
            for( int j = k - 1 , cur = 0 ; j >= 0 ; j -- ) {
                cur |= 1 << val[ y ][ j ].sc;
                if( f[ x ][ cur ] ) { ans = val[ y ][ j ].fi; break; }                         
            }
            printf("%d\n", ans );
        }
    }
    return 0;
}

原文地址：http://www.cnblogs.com/chihik/p/CF878D.html