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; }
page revision: 0, last edited: 16 Nov 2006 09:42