好长时间没做题了,拿这个来练练手…
 
时限居然有 5s ,看来得做好极限优化的准备。
开始想的是用一个 int [4][4][5] 数组记录每格周围有同种羊的格数,然后 dfs 时每放一格就改变周围 8 格的数字。运行下貌似很慢,在我的机器上都 10s 多。
于是想到以前写过五子棋的位运算优化,这题一共 16 格,每格数字最多不大于 4,因此可用一个 64位 unsigned int 放下,每格数字只用 4 bit 表示即可。位运算的优点是可同时操作 64 位,这样只用一句便可同时改变周围 8 格的数据。
可惜在我的机器上依然跑到了 6s,考虑到还开着耗 CPU 的 APE 在听,正常应该能跑进 5s 吧。结果提交一看在评测机上只用了 2.1s 。。。哦 … 咱的机器看来该淘汰了 = = 按 6:2 来算不加位运算优化的估计也能进 5s 了…
 
TASK: wissqu
LANG: C++
 
Compiling…
Compile: OK
 
Executing…
   Test 1: TEST OK [2.117 secs, 2940 KB]
 
All tests OK.
 
#include<cstdlib>
#include<fstream>
#include<iterator>
#include<algorithm>
using namespace std;

class farm{
    int cnt, cowat[16], cowleft[5];
    bool nochange[16];
    unsigned long long ajtcnt[5];
    const unsigned long long mask, maskl, maskr;
    pair<int, int> putorder[16];
    int dfscow[16], dfspos[16];

    void addcow(int cowidx, int posidx){
        switch(posidx){
            /*
                0  1  2  3
                4  5  6  7
                8  9 10 11
               12 13 14 15
            */
            case 0:
            case 4:
                ajtcnt[cowidx] += maskl >> (5 posidx) * 4;
                break;
            case 3:
                ajtcnt[cowidx] += maskr >> (5 posidx) * 4;
                break;
            case 1:
            case 2:
                ajtcnt[cowidx] += mask >> (5 posidx) * 4;
                break;
            case 5:
            case 6:
            case 9:
            case 10:
            case 13:
            case 14:
                ajtcnt[cowidx] += mask << (posidx 5) * 4;
                break;
            case 8:
            case 12:
                ajtcnt[cowidx] += maskl << (posidx 5) * 4;
                break;
            case 7:
            case 11:
            case 15:
                ajtcnt[cowidx] += maskr << (posidx 5) * 4;
                break;
        }
        cowat[posidx] = cowidx;
    }
    int replace(int newcow, int posidx){
        int oldcow = cowat[posidx];
        unsigned long long m;
        switch(posidx){
            case 0:
            case 4:
                m = maskl >> (5 posidx) * 4;
                ajtcnt[newcow] += m;
                ajtcnt[oldcow] -= m;
                break;
            case 3:
                m = maskr >> (5 posidx) * 4;
                ajtcnt[newcow] += m;
                ajtcnt[oldcow] -= m;
                break;
            case 1:
            case 2:
                m = mask >> (5 posidx) * 4;
                ajtcnt[newcow] += m;
                ajtcnt[oldcow] -= m;
                break;
            case 5:
            case 6:
            case 9:
            case 10:
            case 13:
            case 14:
                m = mask << (posidx 5) * 4;
                ajtcnt[newcow] += m;
                ajtcnt[oldcow] -= m;
                break;
            case 8:
            case 12:
                m = maskl << (posidx 5) * 4;
                ajtcnt[newcow] += m;
                ajtcnt[oldcow] -= m;
                break;
            case 7:
            case 11:
            case 15:
                m = maskr << (posidx 5) * 4;
                ajtcnt[newcow] += m;
                ajtcnt[oldcow] -= m;
                break;
        }
        cowat[posidx] = newcow;
        return oldcow;
    }
    bool putable(int cowidx, int posidx) const {
        return !((ajtcnt[cowidx] >> posidx*4) & 0xF);
    }
    void dfs(int idx){
        int oldcow;
        if(idx == 16){
            if(!(cnt++)){
                for(int i = 0; i < 16; ++i)
                    putorder[i] = make_pair(dfscow[i], dfspos[i]);
            }
            return;
        }
        int &cow(dfscow[idx]), &pos(dfspos[idx]);
        for(cow = 0; cow < 5; ++cow)if(cowleft[cow]){
            cowleft[cow];
            for(pos = 0; pos < 16; ++pos)if(nochange[pos] && putable(cow, pos)){
                nochange[pos] = false;
                oldcow = replace(cow, pos);
                dfs(idx + 1);
                replace(oldcow, pos);
                nochange[pos] = true;
            }
            ++cowleft[cow];
        }
    }
public:
    template<class Iter>
    farm(Iter beg, Iter end): cnt(0), mask (0x011101110111ULL),
        maskl(0x011001100110ULL), maskr(0x001100110011ULL){
        fill_n(ajtcnt, 5, 0);
        fill_n(cowleft, 5, 3);
        fill_n(nochange, 16, true);
        for(int i=0; beg != end; ++beg, ++i)
            addcow(*beg ‘A’, i);
    }
    void calput(void){
        int oldcow, &pos(dfspos[0]);
        dfscow[0] = 3;
        for(pos = 0; pos < 16; ++pos)if(putable(3, pos)){
            nochange[pos] = false;
            oldcow = replace(3, pos);
            dfs(1);
            replace(oldcow, pos);
            nochange[pos] = true;
        }
    }
    ostream& output(ostream& os){
        for(int i=0; i<16; ++i){
            div_t pos = div(putorder[i].second, 4);
            os << char(putorder[i].first + ‘A’) << ‘ ‘
                << pos.quot + 1 << ‘ ‘ << pos.rem + 1 << ‘\n’;
        }
        os << cnt << ‘\n’;
        return os;
    }
};

int main(){
    ifstream fin("wissqu.in");
    farm wissqu((istream_iterator<char>(fin)), istream_iterator<char>());
    fin.close();
    ofstream fout("wissqu.out");
    wissqu.calput();
    wissqu.output(fout);
    fout.close();
}

Advertisements