https://projecteuler.net/problem=393

Fork: https://www.shuizilong.com/house/archives/ural-1519-formula-1/

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int hh = 12, ww = 12, _W = 15, MaxH = 10 * 15511;
bool O[hh+1][ww+1]; int A, B, X, Y; int h, w, l, s;
long long ans, d;

struct hashTable {
    int state[MaxH], head[MaxH], next[MaxH], sz;
    long long key[MaxH];
    
    inline void clear() {
        sz = 0;
        memset(head, -1, sizeof(head));
    }
    inline void insert(int s) {
        int x = s % MaxH;
        for ( int it = head[x] ; it != -1 ; it = next[it] ) {
            if ( state[it] == s ) {
                key[it] += d;
                return;
            }
        }
        state[sz] = s, key[sz] = d;
        next[sz] = head[x];
        head[x] = sz++;
    }
} H[2] , *src , *des;

int n;


inline int countBits(int x){
    x = (x & 0x00005555) + ((x & 0x0000aaaa) >> 1);
    x = (x & 0x00003333) + ((x & 0x0000cccc) >> 2);
    x = (x & 0x00000f0f) + ((x & 0x0000f0f0) >> 4);
    x = (x & 0x000000ff) + ((x & 0x0000ff00) >> 8);
    return x;
}


int eatLeft(int s, int i){
    int An = 0;
    for (i--;;i--){
        if (!(s & (1 << i))) continue;
        if (s & (1 << _W + i)) An++;
        else {if (An==0){s ^= 1 << (_W + i); return s;} An--;}
    }
}
int eatRight(int s, int i){
    int An = 0;
    for (i++;;i++){
        if (!(s & (1 << i))) continue;
        if (!(s & (1 << _W + i))) An++;
        else {if (An==0){s ^= 1 << (_W + i); return s;} An--;}
    }
}




bool _O(){
    for (int i=0;i<w;i++)
        if (!O[h-1][i]) return false;
    return true;
}



void init(){
    
    h = w = n;
    
    for (int i=0;i<h;i++)
        for (int j=0;j<w;j++)
            O[i][j] = false;
    
    
    while (_O()) h--;
    
    
    for (int i=0;i<h;i++)
        O[h][i] = O[i][w] = true;
    
}



void solve(){
    
    src = H, des = src + 1, d = 1;
    des->clear(), des->insert(0); src->clear();
    ans = 0;
    
    int _w = w;
    
    for (int i = 0; i < h; i ++){
        
        for (int j = 0; j < src->sz; j ++)
            des->state[j] <<= 1;
        
        w = _w;
        
        while (O[i][w-1]) w--;
        
      //  cout << w << " " << i << endl;
        
        for (int j = 0; j < w; j ++){
            
            if (O[i][j]) continue;
            
            swap(src, des), des->clear();
            
           // cout << " " << j << endl;
            
            for (int k = 0; k < src->sz; k ++){
                s = src->state[k], d = src->key[k];
                A = s & (1 << j), B = s & (1 << (j+1));
                
         //       cout << "  " << k << " " << src->sz << endl;
                
                if (!A && !B){
                    if (!O[i+1][j] && !O[i][j+1]) des->insert(s ^ (3 << j | 1 <<( _W + j + 1)));
                }
                else{
                    
                    X = s & (1 << (_W + j)), Y = s & (1 << (_W + j + 1));
                    
                    if (A && B){
                        
                        if (X){
                            if (Y){ //'))'
                                des->insert(eatLeft(s, j) ^ (3 << j | 3 << _W + j));
                            }
                            else { //')('
                                des->insert(s ^ (3 << j | 1 << _W + j));
                            }
                        }
                        else {
                            if (Y){ //'()'                            if (Y){ //'()'
                                
                                //  ans += d;
                                
                                d *= 2;
                                
                                if (i + 1 == h && j + 1 == w && countBits(s)==2) ans += d;
                                
                                //   d *= 2;
                                
                                
                                
                                // if (
                                
                                des->insert(s ^ (3 << j) ^ X ^ Y);
                                
                                d /= 2;
                                
                            }
                            else { //'(('
                                des->insert(eatRight(s, j+1) ^ (3 << j));
                            }
                        }
                        
                        
                    }
                    else {
                        if (A){
                            if (!O[i+1][j]) des->insert(s);
                            
                            if (!O[i][j+1]) {
                                if (X) des->insert(s ^ (3 << j | 3 << (_W + j)));
                                else des->insert(s ^ (3 << j));
                            }
                        }
                        else {
                            if (!O[i][j+1]) des->insert(s);
                            if (!O[i+1][j]) {
                                if (Y) des->insert(s ^ (3 << j | 3 << (_W + j)));
                                else des->insert(s ^ (3 << j));
                            }
                        }
                    }
                }
                
            }
        }
    }
}


int main(){
    
#ifndef ONLINE_JUDGE
    freopen("/users/xiaodao/desktop/Exercise/in.txt", "r", stdin);
    //freopen("/users/xiaodao/desktop/Exercise/out.txt", "w", stdout);
#endif
    
    //freopen("in.txt", "r", stdin);
    while (cin >> n){
        init(); ans = 0;  solve();
        cout << ans << endl;
    }
}

Posted by xiaodao
Category: 日常