Visits: 210

Codeforces Round #612 (Div. 1)

Garland

DP 题做成贪心 WA 无数次，不愧是我。

const int N = 107;
int n, a[N], f[N][N][N];

inline void upd(int &x, int y) {
    x = min(x, y);
}

int main() {
    rd(n);
    if (n == 1) return print(0), 0;
    for (int i = 1; i <= n; i++) rd(a[i]);
    memset(f, 0x3f, sizeof(f));
    if (a[1]) {
        if (a[1] & 1) {
            upd(f[1][0][a[1]], 0);
        } else {
            upd(f[1][1][a[1]], 0);
        }
    } else {
        for (a[1] = 1; a[1] <= n; a[1]++) {
            if (a[1] & 1) {
                upd(f[1][0][a[1]], 0);
            } else {
                upd(f[1][1][a[1]], 0);
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= min(i - 1, n >> 1); j++)
            for (int k = 1; k <= n; k++) {
                if (a[i]) {
                    if (a[i] & 1) {
                        if (i - 1 - j == n - (n >> 1)) continue;
                        upd(f[i][j][a[i]], f[i-1][j][k] + ((k ^ a[i]) & 1));
                    } else {
                        if (j == (n >> 1)) continue;
                        upd(f[i][j+1][a[i]], f[i-1][j][k] + ((k ^ a[i]) & 1));
                    }
                } else {
                    for (a[i] = 1; a[i] <= n; a[i]++) {
                        if (a[i] & 1) {
                            if (i - 1 - j == n - (n >> 1)) continue;
                            upd(f[i][j][a[i]], f[i-1][j][k] + ((k ^ a[i]) & 1));
                        } else {
                            if (j == (n >> 1)) continue;
                            upd(f[i][j+1][a[i]], f[i-1][j][k] + ((k ^ a[i]) & 1));
                        }
                    }
                    a[i] = 0;
                }
            }
    }
    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= n; i++) ans = min(ans, f[n][n>>1][i]);
    print(ans);
    return 0;
}

Numbers on Tree

sb 构造题，不特判 WA 到死。

const int N = 2e3 + 7;
int n, a[N], rt, ans[N];
vi e[N], p[N];

void dfs(int x) {
    for (int y : e[x]) {
        dfs(y);
        for (auto z : p[y]) p[x].pb(z);
    }
    if (a[x] > (int)p[x].size()) prints("NO"), exit(0);
    vi o;
    while ((int)p[x].size() > a[x]) o.pb(p[x].back()), p[x].pop_back();
    p[x].pb(x);
    while (o.size()) p[x].pb(o.back()), o.pop_back();
}

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) {
        int f;
        rd(f), rd(a[i]);
        if (f) e[f].pb(i);
        else rt = i;
    }
    dfs(rt);
    for (int i = 1; i <= n; i++) ans[p[rt][i-1]] = i;
    prints("YES");
    for (int i = 1; i <= n; i++) print(ans[i], " \n"[i==n]);
    return 0;
}

Madhouse

一道很屑的交互题。

LCC

线段树维护矩阵套路题。

Fedya the Potter Strikes Back

题目太神仙了，先咕咕咕着。

Harry The Potter

题目太神仙了，先咕咕咕着。