Kalorona

「Fortuna OJ」Aug 1st – Group A 解题报告

A – 水叮当的舞步

真的是玄妙重重。

我们先思考正常的暴力搜索：枚举每一次按下的颜色，然后检查继续更新。考虑用 IDA* 优化这个过程，首先估值函数就是剩下的颜色个数，因为至少需要更新这些颜色才有可能到达最终状态。然后注意控制 BFS 求连通块的个数的优化就行了。很好的一道题。

// A.cpp
#include <bits/stdc++.h>
#define pr pair<int, int>

using namespace std;

const int MAX_N = 10;
const int dirx[4] = {0, 0, -1, 1}, diry[4] = {-1, 1, 0, 0};

int n, mp[MAX_N][MAX_N], tail;
bool connected[MAX_N][MAX_N], col[MAX_N];

pr q[MAX_N << 15];

void bfs(int color)
{
    for (int i = 1; i <= tail; i++)
    {
        int x = q[i].first, y = q[i].second;
        for (int dir = 0; dir < 4; dir++)
        {
            int dstx = x + dirx[dir], dsty = y + diry[dir];
            if (dstx <= n && dstx >= 1 && dsty <= n && dsty >= 1 && mp[dstx][dsty] == color && connected[dstx][dsty] == false)
            {
                connected[dstx][dsty] = true;
                q[++tail] = make_pair(dstx, dsty);
            }
        }
    }
}

bool dfs(int dep, int limit)
{
    if (tail == n * n)
        return true;
    memset(col, 0, sizeof(col));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (connected[i][j] == false)
                col[mp[i][j]] = true;
    int tt = 0;
    for (int i = 0; i <= 5; i++)
        if (col[i])
            tt++;
    if (tt + dep > limit)
        return false;
    int tp = tail;
    for (int i = 0; i <= 5; i++)
    {
        bfs(i);
        if (tail == tp)
            continue;
        if (dfs(dep + 1, limit))
            return true;
        for (int j = tp + 1; j <= tail; j++)
            connected[q[j].first][q[j].second] = false;
        tail = tp;
    }
    return false;
}

int main()
{
    while (scanf("%d", &n) && n != 0)
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                scanf("%d", &mp[i][j]);
        bool flag = true;
        for (int limit = 0; limit <= 64; limit++)
        {
            memset(connected, 0, sizeof(connected));
            q[1] = make_pair(1, 1);
            connected[1][1] = true;
            tail = 1;
            bfs(mp[1][1]);
            if (dfs(0, limit))
            {
                printf("%d\n", limit);
                break;
            }
        }
    }
    return 0;
}

B – Vani和Cl2捉迷藏

先用 Floyd 做传递闭包，然后枚举所有的点，在新的网络上连接可达的点（也就是二分图）。二分匹配之后用\(n\)减去最大流即可。

// B.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 510, INF = 0x3f3f3f3f;

int n, m, head[MAX_N], current, cur[MAX_N], st, ed, dep[MAX_N];
bool mp[MAX_N][MAX_N];

struct edge
{
    int to, nxt, weight;
} edges[MAX_N * MAX_N << 1];

void addpath(int src, int dst, int weight)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    edges[current].weight = weight, head[src] = current++;
}

void addtube(int src, int dst, int weight)
{
    addpath(src, dst, weight);
    addpath(dst, src, 0);
}

bool bfs()
{
    memset(dep, 0, sizeof(dep));
    queue<int> q;
    dep[st] = 1, q.push(st);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (edges[i].weight > 0 && dep[edges[i].to] == 0)
                dep[edges[i].to] = dep[u] + 1, q.push(edges[i].to);
    }
    return dep[ed] != 0;
}

int dfs(int u, int flow)
{
    if (u == ed || flow == 0)
        return flow;
    for (int &i = cur[u]; i != -1; i = edges[i].nxt)
    {
        if (edges[i].weight > 0 && dep[edges[i].to] == dep[u] + 1)
        {
            int di = dfs(edges[i].to, min(flow, edges[i].weight));
            if (di)
            {
                edges[i].weight -= di, edges[i ^ 1].weight += di;
                return di;
            }
        }
    }
    return 0;
}

int dinic()
{
    int ans = 0;
    while (bfs())
    {
        memcpy(cur, head, sizeof(head));
        while (int di = dfs(st, INF))
            ans += di;
    }
    return ans;
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1, x, y; i <= m; i++)
        scanf("%d%d", &x, &y), mp[x][y] = true;
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                mp[i][j] |= mp[i][k] && mp[k][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (mp[i][j])
                addtube(i, j + n, 1);
    st = 2 * n + 1, ed = st + 1;
    for (int i = 1; i <= n; i++)
        addtube(st, i, 1), addtube(i + n, ed, 1);
    printf("%d", n - dinic());
    return 0;
}

C – 粉刷匠

这道题是 DP 计数。我们考虑设置一个状态：\( dp[i][j] \)表示前\(i\)种颜色都涂完了、且有\(j\)对不合法相邻颜色的方案数。我们考虑先枚举\(i, j\)，再枚举要把这种颜色分组的组数\(x\)，再枚举要\(y\)组颜色放入不合法的组数中间，使其合法（\(y \leq j\)）。

那么我们考虑转移：

\[ dp[i + 1][j + c_{i + 1} – x – y] += dp[i][j] {c_{i + 1} – 1 \choose x – 1} {j \choose y} {(\sum_{w = 1}^i c_w) – y + 1 \choose x – y} \]

注释：
  1. \(j + c_{i + 1} – x – y\)是放置之后的非法数量。
  2. \( {c_{i + 1} – 1 \choose x – 1} \)是经典插板法。
  3. \( {j \choose y} \)是选择非法位置的方案数。
  4. \( {(\sum_{w = 1}^i c_w) – y + 1 \choose x – y} \)是在之前的位置中选择一些地方放置剩余非法的组的方案数。
// C.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll MAX_K = 16, MAX_C = 7, MAX_N = MAX_K * MAX_C, mod = 1000000007;

ll T, n, k, ci[MAX_K], dp[MAX_N][MAX_N], sum[MAX_N], C[MAX_N][MAX_N];

ll comb(ll a, ll b) { return C[a][b]; }

signed main()
{
    C[0][0] = 1;
    for (int i = 1; i < MAX_N; i++)
    {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j <= i - 1; j++)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }
    scanf("%lld", &T);
    while (T--)
    {
        scanf("%lld", &k), n = 0, sum[0] = 0;
        for (int i = 1; i <= k; i++)
            scanf("%lld", &ci[i]), n += ci[i], sum[i] = sum[i - 1] + ci[i];
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for (int i = 1; i <= k; i++)
            for (int j = 0; j <= sum[i - 1]; j++)
                if (dp[i - 1][j])
                    for (int x = 1; x <= ci[i]; x++)
                        for (int y = 0; y <= min(1LL * j, ci[i]); y++)
                            (dp[i][j + ci[i] - x - y] += dp[i - 1][j] * comb(ci[i] - 1, x - 1) % mod * comb(j, y) % mod * comb(sum[i - 1] - j + 1, x - y) % mod) %= mod;
        printf("%lld\n", dp[k][0]);
    }
    return 0;
}

2 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *