Chaos Slover 补档计划 - 插头 DP

2016.01.11 10:44 Mon| 12 visits oi_2016| ChaosSlover补档计划| Text

UVA11270 Tiling Dominoes

广场铺砖问题,时隔多年,我终于会做这题了!可喜可贺,可喜可贺。

使用轮廓线 DP,记录轮廓线上哪些位置已经被覆盖过了,哪些还没有被覆盖过。

代码出人意料地很短。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

int n, m, cur;
long long dp[2][2100];

int main()
{
    while (cin >> n >> m)
    {
        if (n < m) swap(n, m);
        memset(dp, 0, sizeof dp);
        dp[cur = 0][(1 << m) - 1] = 1;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= m; ++j)
            {
                cur ^= 1;
                memset(dp[cur], 0, sizeof dp[cur]);
                for (int k = 0; k < (1 << m); ++k)
                {
                    if (((k << 1) & (1 << m)))
                        dp[cur][(k << 1) - (1 << m)] += dp[cur ^ 1][k];
                    if (j != 1 && ((k << 1) & (1 << m)) && !(k & 1))
                        dp[cur][(k << 1) - (1 << m) + 3] += dp[cur ^ 1][k];
                    if (!((k << 1) & (1 << m)))
                        dp[cur][(k << 1) + 1] += dp[cur ^ 1][k];
                }
            }
        }
        cout << dp[cur][(1 << m) - 1] << endl;
    }
    return 0;
}

URAL1519 Formula 1

括号序列,用一个 int 表示状态。每一行开始的时候为了让右插头移到左面去,直接将状态左移两位就好了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;

char pos[15][15];
int n, m, ex, ey;
map<int, long long> mp[2];

inline int getplug(int state, int pos)
{
    return (state >> (pos << 1)) & 3;
}

inline void setplug(int &state, int pos, int x)
{
    state = (state & ~(3 << (pos << 1))) | (x << (pos << 1));
}

int getrp(int state, int pos)
{
    int re = pos + 1;
    for (int cnt = 1; cnt; ++re)
        switch (getplug(state, re))
        { case 1 : ++cnt; break; case 2 : --cnt; }
    return re - 1;
}

int getlp(int state, int pos)
{
    int re = pos - 1;
    for (int cnt = -1; cnt; --re)
        switch (getplug(state, re))
        { case 1 : ++cnt; break; case 2 : --cnt; }
    return re + 1;
}

void update(int x, int y, int state, long long val)
{
    int lp = getplug(state, y), up = getplug(state, y + 1);
    if (pos[x][y] == '*')
    {
        if (lp == 0 && up == 0) mp[1][state] += val;
        return;
    }
    if (lp == 0 && up == 0)
    {
        if (x == n - 1 || y == m - 1) return;
        setplug(state, y, 1), setplug(state, y + 1, 2);
        mp[1][state] += val;
        return;
    }
    if (lp == 0 || up == 0)
    {
        if (x != n - 1)
            setplug(state, y, lp + up), setplug(state, y + 1, 0),
            mp[1][state] += val;
        if (y != m - 1)
            setplug(state, y, 0), setplug(state, y + 1, lp + up),
            mp[1][state] += val;
        return;
    }
    setplug(state, y, 0), setplug(state, y + 1, 0);
    if (lp == 1 && up == 2 && !(x == ex && y == ey)) return;
    if (lp == 1 && up == 1) setplug(state, getrp(state, y + 1), 1);
    if (lp == 2 && up == 2) setplug(state, getlp(state, y), 2);
    mp[1][state] += val;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        scanf("%s", pos[i]);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (pos[i][j] == '.') ex = i, ey = j;
    mp[0][0] = 1;
    for (int i = 0; i < n; ++i)
    {
        mp[1].clear();
        for (auto j : mp[0])
            mp[1][j.first << 2] = j.second;
        swap(mp[0], mp[1]);
        for (int j = 0; j < m; ++j)
        {
            mp[1].clear();
            for (auto k : mp[0])
                update(i, j, k.first, k.second);
            swap(mp[0], mp[1]);
        }
    }
    cout << mp[0][0] << endl;
    return 0;
}

BZOJ3336 Uva10572 Black and White

最小表示法,说起来其实挺简单的。

  • 一个状态需要用两个 int 来表示,其中一个表示连通性编号,每一个格子所在连通块编号可以用三位来表示,另一个表示染色情况。
  • 对于每一个格子尝试去填白色和黑色,合法性可以从周围格子的颜色推过来。
  • 连通块只能在右下角的两个格子处消失,其他情况不合法。
  • 最后一个格子上方和左方的颜色都和自己不一样的话,只可能有一种情况,即棋盘大小为 2*2 且左上角颜色也和自己不一样。
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
#include <bits/stdc++.h>
using namespace std;

struct data
{
    int state, col;
    data(int _state, int _col) : state(_state), col(_col) {}
    bool operator <(const data &d) const
    { return state == d.state ? col < d.col : state < d.state; } 
};

int test, n, m, a[10];
char pos[10][10];
map<data, int> mp[2];

void decode(int state)
{
    for (int i = m - 1; i >= 0; --i) a[i] = state & 7, state >>= 3;
}

int encode()
{
    int vis[10], tag = 0, re = 0;
    memset(vis, -1, sizeof vis);
    for (int i = 0; i < m; ++i)
        if (vis[a[i]] == -1) vis[a[i]] = tag++;
    for (int i = 0; i < m; ++i)
        re <<= 3, re |= vis[a[i]];
    return re;
}

void update(int x, int y, data d, int val, int now)
{
    int cu = x && (d.col >> y & 1) == now,
        cl = y && (d.col >> (y - 1) & 1) == now,
        cul = x && y && (d.col >> m) == now;
    if (cu && cl && cul) return;
    if (x == n - 1 && y == m - 1 && !cu && !cl && cul) return;
    decode(d.state);
    if (x && !cu)
    {
        int cnt1 = 0, cnt2 = 0;
        for (int i = 0; i < m; ++i)
        {
            if (a[i] == a[y]) ++cnt1;
            if ((d.col >> i & 1) != now) ++cnt2;
        }
        if (cnt1 == 1)
        {
            if (cnt2 > 1) return;
            if (x < n - 1 || y < m - 2) return;
        }
    }
    if (!cu && !cl) a[y] = m;
    else if (cl && !cu) a[y] = a[y - 1];
    else if (cl && cu)
        for (int i = 0, t = a[y]; i <= m; ++i)
            if (a[i] == t) a[i] = a[y - 1];
    d.state = encode();
    if (d.col >> y & 1) d.col |= 1 << m;
    else d.col ^= (d.col >> m) << m;
    if (now) d.col |= 1 << y;
    else d.col ^= (d.col >> y & 1) << y;
    mp[1][d] += val;
}

int main()
{
    cin >> test;
    while (test--)
    {
        cin >> n >> m;
        for (int i = 0; i < n; ++i)
            scanf("%s", pos[i]);
        mp[0].clear();
        mp[0][data(0, 0)] = 1;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
            {
                mp[1].clear();
                for (map<data, int>::iterator t = mp[0].begin(); t != mp[0].end(); ++t)
                {
                    if (pos[i][j] != '#')
                        update(i, j, t->first, t->second, 0);
                    if (pos[i][j] != 'o')
                        update(i, j, t->first, t->second, 1);
                }
                swap(mp[0], mp[1]);
            }
        int ans = 0;
        for (map<data, int>::iterator t = mp[0].begin(); t != mp[0].end(); ++t)
        {
            decode(t->first.state);
            for (int j = 0; j <= m; ++j)
                if (j == m) ans += t->second;
                else if (a[j] >= 2) break;
        }
        cout << ans << endl;
    }
    return 0;
}

BZOJ1494 [NOI2007]生成树计数

记录每个状态之前 k 个格子的连通情况,用插头 DP 来求出转移矩阵。我真的会写最小表示法了,可喜可贺。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>
using namespace std;

#define mod 65521

map<int, int> mp;
int k, tot, a[10];
long long n;

struct matrix
{
    int t[60][60];
    matrix() { memset(t, 0, sizeof t); }
    friend matrix operator *(const matrix &a, const matrix &b)
    {
        matrix re;
        for (int i = 0; i < tot; ++i)
            for (int j = 0; j < tot; ++j)
                for (int k = 0; k < tot; ++k)
                    re.t[i][j] = (re.t[i][j] + 1ll * a.t[i][k] * b.t[k][j]) % mod;
        return re;
    }
    friend matrix pow(matrix a, long long b)
    {
        matrix re;
        for (int i = 0; i < tot; ++i) re.t[i][i] = 1;
        while (b)
        {
            if (b & 1) re = re * a;
            a = a * a, b >>= 1;
        }
        return re;
    }
} f, g;

void decode(int state)
{
    for (int i = k - 1; i >= 0; --i)
        a[i] = state & 7, state >>= 3;
}

int encode()
{
    int vis[10], tag = 0, re = 0;
    memset(vis, -1, sizeof vis);
    for (int i = 1; i <= k; ++i)
        if (vis[a[i]] == -1) vis[a[i]] = tag++;
    for (int i = 1; i <= k; ++i)
        re = (re << 3) | vis[a[i]];
    return re;
}

int calc()
{
    int cnt[10], re = 1;
    memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= k; ++i)
        ++cnt[a[i]];
    for (int i = 0; i < k; ++i)
        if (cnt[i])
            re = re * pow(cnt[i], cnt[i] - 2) + 0.5;
    return re;
}

void solve(int x, int state)
{
    for (int s = 0; s < 1 << k; ++s)
    {
        decode(state);
        int vis[10] = {0};
        for (int i = 1; i <= k; ++i)
            if (i == k && !(s & 1)) goto owari;
            else if (!a[i]) break;
        for (int i = 0; i < k; ++i)
            if (s >> i & 1) ++vis[a[i]];
        for (int i = 0; i < k; ++i)
            if (vis[a[i]] >= 2) goto owari;
        for (int i = 0; i < k; ++i)
            if (s >> i & 1)
                for (int j = 0, t = a[i]; j < k; ++j)
                    if (a[j] == t) a[j] = k;
        a[k] = k;
        ++f.t[x][mp[encode()]];
        owari :;
    }
}

void dfs(int x)
{
    if (x == k + 1)
    {
        for (int i = 1; i <= k; ++i)
        {
            bool flag = 0;
            for (int j = 1; j < i; ++j)
                if (a[j] == a[i] - 1) flag = 1;
            if (a[i] && !flag) return;
        }
        g.t[0][tot] = calc();
        mp[encode()] = tot++;
        return;
    }
    for (int i = 0; i < x; ++i)
        a[x] = i, dfs(x + 1);
}

int main()
{
    cin >> k >> n;
    dfs(1);
    for (map<int, int>::iterator t = mp.begin(); t != mp.end(); ++t)
        solve(t->second, t->first);
    cout << (g * pow(f, n - k)).t[0][0] << endl;
    return 0;
}