2018 GCJ Round 2

a.cpp

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int n;
    scanf("%d", &n);

    vector<vector<char>> ans(111, vector<char>(111, '.'));
    int inp[n], l = 0;
    int mx = 1;
    for (int i = 0; i < n; i++) {
        scanf("%d", &inp[i]);

        if (inp[i] == 0)
            continue;

        for (int j = l; j < l + inp[i]; j++) {
            int diff = abs(i - j);
            if (diff == 0)
                continue;

            if (j < i) { // from left
                int row = 0, col = j;
                for (int k = 0; k < diff; k++) {
                    ans[row + k][col + k] = '\\';
                    mx = max(mx, row + k + 2);
                }
            } else { // from right
                int row = 0, col = j;
                for (int k = 0; k < diff; k++) {
                    ans[row + k][col - k] = '/';
                    mx = max(mx, row + k + 2);
                }
            }
        }

        l += inp[i];
    }

    if (inp[0] == 0 || inp[n - 1] == 0) {
        printf("IMPOSSIBLE\n");
        return;
    }

    printf("%d\n", mx);
    for (int i = 0; i < mx; i++) {
        for (int j = 0; j < n; j++) {
            printf("%c", ans[i][j]);
        }
        printf("\n");
    }
}

int main()
{
    int ncase;
    scanf("%d", &ncase);
    for (int i = 1; i <= ncase; i++) {
        printf("Case #%d: ", i);
        solve();
    }

    return 0;
}

b.cpp

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> ii;

int dp[555][555];

int solve()
{
    memset(dp, 0, sizeof(dp));

    int n, m;
    scanf("%d %d", &n, &m);

    // f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}
    // 設 f[i][v][u]表示前 i 件物品付出兩種代價分別為 v 和 u 時可獲得的最大價值。

    vector<ii> items;
    for (int i = 0; i <= 40; i++)
        for (int j = 0; j <= 40; j++) {
            if (i == 0 && j == 0)
                continue;
            // printf("%d %d\n", i, j);
            items.push_back(ii(i, j));
        }

    for (int i = 0; i < (int)items.size(); i++) {
        for (int v = n; v >= 0; v--) {
            if (v - items[i].first < 0)
                continue;
            for (int u = m; u >= 0; u--) {
                if (u - items[i].second >= 0)
                    dp[v][u] =
                        max(dp[v][u], dp[v - items[i].first][u - items[i].second] + 1);
            }
        }
    }

    return dp[n][m];
}

int main()
{
    int ncase;
    scanf("%d", &ncase);
    for (int i = 1; i <= ncase; i++) {
        printf("Case #%d: %d\n", i, solve());
    }

    return 0;
}

c.cpp

#include <bits/stdc++.h>

using namespace std;

const int MAX_V = 555;
int V;
vector<int> g[MAX_V];
int match[MAX_V];
bool used[MAX_V];

void add_edge(int u, int v)
{
    g[u].push_back(v);
    g[v].push_back(u);
}

bool dfs(int v)
{
    used[v] = true;
    for (size_t i = 0; i < g[v].size(); i++) {
        int u = g[v][i], w = match[u];
        if (w < 0 || (!used[w] && dfs(w))) {
            match[v] = u;
            match[u] = v;
            return true;
        }
    }
    return false;
}

int bipartite_matching() 
{
    int res = 0;
    memset(match, -1, sizeof(match));
    for (int v = 0; v < V; v++) {
        if (match[v] == -1) {
            memset(used, false, sizeof(used));
            if (dfs(v)) {
                res++;
            }
        }
    }
    return res;
}

int solve()
{
    int n;
    scanf("%d", &n);
    V = n;

    // read
    int inp[n][n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            scanf("%d", &inp[i][j]);
        }

    int stay = 0;
    for (int i = -n; i <= n; i++) {
        if (i == 0)
            continue;

        for (int j = 0; j < n; j++)
            g[j].clear();

        // build
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++) {
                if (inp[j][k] == i) {
                    // row [0, n - 1]
                    // col [n, n + n - 1]
                    add_edge(j, n + k);
                }
            }

        // run
        stay += bipartite_matching();
        // printf("%d %d\n", i, stay);
    }

    return n * n - stay;
}

int main()
{
    int ncase;
    scanf("%d", &ncase);
    for (int i = 1; i <= ncase; i++) {
        printf("Case #%d: %d\n", i, solve());
    }

    return 0;
}