Task 8

Задача решается за время O(N log N), если для всех масок построить одно дерево, и в каждой вершине для поиска ребра использовать map.

#include <map>
#include <iostream>
#include <vector>
 
using namespace std;
 
typedef map<long long, int> m1;
vector<m1> T;
long long pckt[6];
int N;
 
int src( int k, int n)
{
    if( k == N-1)
    {
        if( T[n][pckt[k]] != 0 || T[n][-1] != 0 )
        {
            cout << "1" << endl;
            return 1;
        }
    }
    if( T[n][pckt[k]] != 0)
    {
        if(src(k+1, T[n][pckt[k]])) return 1;
    }
    if( T[n][-1] != 0)
    {
        if(src(k+1, T[n][-1])) return 1;
    }
    return 0;
}
 
int main( void )
{
 
    int i;
    int l[6];
    int K;
    int M;
    int n = 1;
    char temp[1000];
 
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
 
    cin >> N;
    for( i = 0; i < N; i++)
    {
        cin >> l[i];
    }
    cin >> K;
    T.resize(1);
    for( i = 0; i < K; i++)
    {
        int p = 0;
        int next = 0;
        cin >> temp;
        for( int h = 0; h < N; h++)
        {
            long long m = 0;
            for( int j = 0; j < l[h]; j++)
            {
                if( temp[p] == 'x' )
                {
                    p += l[h];
                    m = -1;
                    break;
                }
                m |= (long long)(((long long)temp[p] - '0') << ((long long)l[h] - (long long)j - 1));
                p++;
            }
            if(T[next][m] == 0)
            {
                T[next][m] = n;
                n++;
                T.resize(n);
            }
            next = T[next][m];
        }
 
    }
    cin >> M;
    for( i = 0; i < M; i++)
    {
        int p = 0;
        cin >> temp;
        for( int h = 0; h < N; h++)
        {
            long long m = 0;
            for( int j = 0; j < l[h]; j++)
            {
                if( temp[p] == 'x' )
                {
                    p += l[h];
                    m = -1;
                    break;
                }
                m |= (long long)(((long long)temp[p] - '0') << ((long long)l[h] - (long long)j - 1));
                p++;
            }
            pckt[h] = m;
        }
        if(src(0, 0) == 0) cout << "0" << endl;
    }
 
    return 0;
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.