TopCoder TCO2013

2016.03.30 19:16 Wed| 12 visits oi_2016| 2016_刷题日常| Text

1A DirectionBoard

题目需要更改尽量少的边数,使得网格图中每一个点都被一个环所覆盖,也就是令每一个点的入度和出度都恰好为 1。将网格中的点拆点,跑一个最小权匹配就好了。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 500
#define inf 0x3f3f3f3f

int s, t, head[N], v[N], d[N], inc[N], from[N];

struct graph
{
    int next, to, val, cost;
    graph() {}
    graph(int _next, int _to, int _val, int _cost)
    : next(_next), to(_to), val(_val), cost(_cost) {}
} edge[4000];

void add(int x, int y, int z, int w)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y, z, w);
    head[x] = cnt;
    edge[++cnt] = graph(head[y], x, 0, -w);
    head[y] = cnt;
}

queue<int> q;

bool spfa()
{
    memset(v, 0, sizeof v);
    memset(d, 0x3f, sizeof d);
    d[s] = 0; inc[s] = inf; q.push(s), v[s] = 1;
    while (!q.empty())
    {
        int x = q.front(), y; q.pop(), v[x] = 0;
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && d[y = edge[i].to] > d[x] + edge[i].cost)
            {
                d[y] = d[x] + edge[i].cost;
                inc[y] = min(inc[x], edge[i].val), from[y] = i;
                if (!v[y]) q.push(y), v[y] = 1;
            }
    }
    return d[t] != inf;
}

int update()
{
    int x = t;
    while (x != s)
    {
        edge[from[x]].val -= inc[t];
        edge[from[x] ^ 1].val += inc[t];
        x = edge[from[x] ^ 1].to;
    }
    return d[t] * inc[t];
}

int edmonds_karp()
{
    int re = 0;
    while (spfa())
        re += update();
    return re;
}

class DirectionBoard
{
public:
    #define pos(x, y) ((x) * m + (y))
    int getMinimum(vector<string> board)
    {
        int n = board.size(), m = board[0].size();
        s = pos(n + n, 0), t = pos(n + n, 1);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                add(s, pos(n + i, j), 1, 0), add(pos(i, j), t, 1, 0),
                add(pos(n + i, j), pos(i, (j + m - 1) % m), 1, board[i][j] != 'L'),
                add(pos(n + i, j), pos(i, (j + 1) % m), 1, board[i][j] != 'R'),
                add(pos(n + i, j), pos((i + n - 1) % n, j), 1, board[i][j] != 'U'),
                add(pos(n + i, j), pos((i + 1) % n, j), 1, board[i][j] != 'D');
        return edmonds_karp();
    }
};

1B EllysReversals

这题我竟然会 = =

观察一下可以发现,我们可以通过翻转操作翻转任意一段区间,也可以交换相邻元素,总之可以变成各种样子。实际上,一个串可以变成的串就是将里面的元素两两绑起来,任意翻转或组合组成的串。所以直接在串内排个序,然后一起去重就好了。

 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
#include <bits/stdc++.h>
using namespace std;

class EllysReversals
{
public:
    int getMin(vector<string> words)
    {
        for (int i = 0; i < (int)words.size(); ++i)
        {
            int cnt[26][26] = {{0}};
            for (int j = 1; j < (int)words[i].size(); j += 2)
            {
                if (words[i][j] < words[i][j - 1])
                    swap(words[i][j], words[i][j - 1]);
                ++cnt[words[i][j - 1] - 'a'][words[i][j] - 'a'];
            }
            for (int pos = 0, a = 0; a < 26; ++a)
                for (int b = 0; b < 26; ++b)
                    for (int k = 0; k < cnt[a][b]; ++k, pos += 2)
                        words[i][pos] = a + 'a', words[i][pos + 1] = b + 'a';
        }
        map<string, int> mp;
        for (int i = 0; i < (int)words.size(); ++i)
            ++mp[words[i]];
        int re = 0;
        for (auto t : mp)
            re += t.second % 2;
        return re;
    }
};

2B LitPanels

为了去重,可以分别讨论出染色的部分的长、宽恰好为 a、b 的方案数,之后加起来得到最终答案。

枚举 a、b,对于一个 a*b 的矩形,合法的染色方案就是在四条边界上均有一个点,并且在可能的两种留白方式中至少满足一种。分别判断出矩形内的每一个点若染色则会满足的条件,之后 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
#include <bits/stdc++.h>
using namespace std;

#define mod 1000000007

class LitPanels
{
public:
    int solve(int x, int y, int sx, int sy)
    {
        int mp[45][45] = {{0}};
        for (int i = 1; i <= x; ++i)
            mp[i][1] |= 1, mp[i][y] |= 2;
        for (int i = 1; i <= y; ++i)
            mp[1][i] |= 4, mp[x][i] |= 8;
        for (int i = 1; i <= x; ++i)
            for (int j = 1; j <= y; ++j)
                if ((i > sx || j > sy) && (i <= x - sx || j <= y - sy))
                    mp[i][j] |= 16;
        for (int i = 1; i <= x; ++i)
            for (int j = 1; j <= y; ++j)
                if ((i > sx || j <= y - sy) && (i <= x - sx || j > sy))
                    mp[i][j] |= 32;
        int dp[2][64] = {{0}};
        dp[1][0] = 1;
        for (int i = 1; i <= x; ++i)
            for (int j = 1; j <= y; ++j)
            {
                memcpy(dp[0], dp[1], sizeof dp[1]);
                for (int k = 0; k <= 63; ++k)
                    dp[1][k|mp[i][j]] = (dp[1][k|mp[i][j]] + dp[0][k]) % mod;
            }
        return ((dp[1][31] + dp[1][47]) % mod + dp[1][15]) % mod;
    }
    int countPatterns(int X, int Y, int sx, int sy)
    {
        int re = 0;
        for (int i = 1; i <= X; ++i)
            for (int j = 1; j <= Y; ++j)
                re = (re + 1ll * solve(i, j, sx, sy)
                    * (X - i + 1) % mod * (Y - j + 1) % mod) % mod;
        return re + 1;
    }
};

3A TrichyInequality

这题好难 QAQ 听说有 O((m-n)2) 的解法,然而我既不会又不想去会 233

还是挺显然的,有 $ans = \sum_{x_1=1}^t \sum_{x_2=1}^t\dots \sum_{x_n=1}^t {s-x_1-x_2-\dots-x_n \choose m-n}$。

发现 $s-x\choose m-n$ 是一个 $m-n$ 次多项式(我在这里竟然想了好久好久),于是可以将它写成 $\sum_{k=0}^{m-n}a_kx^k$ 的形式。再提到上面的式子的前面去,于是答案就变成了下面的样子:

然后,后面一大截相当于一个一个的变量往里加,可以用矩阵乘法处理了,而系数 a 可以暴力把组合数展开计算,最终乘到一起就好了。

 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
#include <bits/stdc++.h>
using namespace std;

#define mod 1000000007

struct matrix
{
    int n, t[105][105];
    matrix(int _n) : n(_n) { memset(t, 0, sizeof t); }
    friend matrix operator *(matrix a, matrix b)
    {
        matrix re(a.n);
        for (int i = 0; i <= re.n; ++i)
            for (int j = 0; j <= re.n; ++j)
                for (int k = 0; k <= re.n; ++k)
                    (re.t[i][j] += 1ll * a.t[i][k] * b.t[k][j] % mod) %= mod;
        return re;
    }
    friend matrix pow(matrix a, int b)
    {
        matrix re(a.n);
        for (int i = 0; i <= re.n; ++i)
            re.t[i][i] = 1;
        while (b)
        {
            if (b & 1) re = re * a;
            a = a * a; b >>= 1;
        }
        return re;
    }
};

class TrickyInequality
{
    int sum[105] = {0}, c[105][105] = {{0}}, coe[105] = {0};
    int power(int a, int b)
    {
        int re = 1;
        while (b)
        {
            if (b & 1) re = 1ll * re * a % mod;
            a = 1ll * a * a % mod; b >>= 1;
        }
        return re;
    }
public:
    int countSolutions(long long s, int t, int n, int m)
    {
        for (int i = 1; i <= t; ++i)
            for (int j = 0, t = 1; j <= m - n; ++j)
                sum[j] = (sum[j] + t) % mod, t = 1ll * t * i % mod;
        for (int i = 0; i <= m - n; ++i)
            for (int j = 0; j <= i; ++j)
                if (j == 0) c[i][j] = 1;
                else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
        matrix trans(m - n);
        for (int i = 0; i <= m - n; ++i)
            for (int j = i; j <= m - n; ++j)
                trans.t[i][j] = 1ll * c[j][j - i] * sum[j - i] % mod;
        trans = pow(trans, n);
        coe[0] = 1;
        for (int i = 1; i <= m - n; ++i)
            coe[0] = 1ll * coe[0] * i % mod;
        coe[0] = power(coe[0], mod - 2);
        for (long long i = s - m + n + 1; i <= s; ++i)
            for (int j = m - n; j >= 0; --j)
                if (j == 0)
                    coe[j] = i % mod * coe[j] % mod;
                else
                    coe[j] = (i % mod * coe[j] % mod - coe[j - 1] + mod) % mod;
        int re = 0;
        for (int i = 0; i <= m - n; ++i)
            re = (re + 1ll * coe[i] * trans.t[0][i]) % mod;
        return re;
    }
};