Visits: 226

JOI Final 2018

ストーブ (Stove)

用个堆维护差分后的序列，每次取最小的。

const int N = 1e5 + 7;
int n, k, a[N], ans;

int main() {
    rd(n, k), rda(a, n), ans = n;
    pq<int> q;
    for (int i = 1; i < n; i++)
        q.push(-a[i+1] + a[i] + 1);
    while (k++ < n) ans -= q.top(), q.pop();
    print(ans);
    return 0;
}

美術展 (Art Exhibition)

排序后前缀和统计。

const int N = 5e5 + 7;
const ll inf = 1e18;
int n;
pair<ll, ll> a[N];
ll now = inf, ans;

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) rd(a[i].fi, a[i].se);
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        a[i].se += a[i-1].se;
        now = min(now, a[i-1].se - a[i].fi);
        ans = max(ans, a[i].se - a[i].fi - now);
    }
    print(ans);
    return 0;
}

団子職人 (Dango Maker)

将每个 G 横纵方向的合法情况当成一个点，显然可以得到一个二分图匹配模型。

然后会发现有连边的只可能是 $(x,y)$ 与 $(x+1,y-1)$ 的两个不同方向。

于是对于每一条斜线 DP 即可，总时间复杂度 $\mathcal O(nm)$。

const int N = 3e3 + 7, inf = 1e9;
int n, m, ans, f[2][N][N];
char s[N][N];

inline bool pd(int o, int i, int j) {
    if (!o) return s[i][j-1] == 'R' && s[i][j] == 'G' && s[i][j+1] == 'W';
    return s[i-1][j] == 'R' && s[i][j] == 'G' && s[i+1][j] == 'W';
}

int main() {
    rd(n, m);
    for (int i = 1; i <= n; i++) rds(s[i], m);
    for (int i = 0; i <= n + 1; i++)
        for (int j = 0; j <= m + 1; j++)
            f[0][i][j] = f[1][i][j] = -inf;
    for (int i = 2; i <= n + m; i++) {
        int now = 0, X = 0, Y = 0;
        for (int x = max(1, i - m); x <= min(n, i - 1); x++) {
            int y = i - x;
            if (pd(0, x, y)) f[0][x][y] = max(f[0][x-1][y+1], now) + 1;
            if (pd(1, x, y)) f[1][x][y] = max(f[1][x-1][y+1], now) + 1;
            now = max(now, max(f[0][x-1][y+1], f[1][x-1][y+1]));
            X = x, Y = y;
        }
        ans += max(now, max(f[0][X][Y], f[1][X][Y]));
    }
    print(ans);
    return 0;
}

定期券 (Commuter Pass)

首先跑 $4$ 遍 Dijkstra 求出四个特殊点到每个点的最短路。

把从 $s$ 到 $t$ 的所有可能是最短路的边找出来，发现这一定是个 DAG。

没有代价的部分一定是 DAG 上的一条路径，于是 DAG 上 DP 一下即可，采用记忆化搜索会很方便。

总时间复杂度 $\mathcal O(m \log n)$。

const int N = 1e5 + 7;
const ll inf = 1e18;
int n, m, s, t, a, b;
ll ds[N], dt[N], da[N], db[N], ans;
vector<pi> e[N];

bool v[N];
pq<pair<ll, int>> q;

inline void dij(int S, ll *d) {
    for (int i = 1; i <= n; i++) d[i] = inf, v[i] = 0;
    d[S] = 0, q.push(mp(0, S));
    while (q.size()) {
        int x = q.top().se;
        q.pop();
        if (v[x]) continue;
        v[x] = 1;
        for (pi o : e[x]) {
            int y = o.fi, z = o.se;
            if (d[y] > d[x] + z)
                d[y] = d[x] + z, q.push(mp(-d[y], y));
        }
    }
}

vi g[N];
ll fa[N], fb[N];

void dfs(int x) {
    if (v[x]) return;
    v[x] = 1;
    fa[x] = da[x], fb[x] = db[x];
    for (int y : g[x])
        dfs(y), fa[x] = min(fa[x], fa[y]), fb[x] = min(fb[x], fb[y]);
    ans = min(ans, min(fa[x] + db[x], fb[x] + da[x]));
}

int main() {
    rd(n, m), rd(s, t), rd(a, b);
    for (int i = 1, x, y, z; i <= m; i++)
        rd(x, y, z), e[x].pb(mp(y, z)), e[y].pb(mp(x, z));
    dij(s, ds), dij(t, dt), dij(a, da), dij(b, db);
    ans = da[b];
    for (int x = 1; x <= n; x++)
        for (pi o : e[x]) {
            int y = o.fi, z = o.se;
            if (ds[x] + z + dt[y] == ds[t]) g[x].pb(y);
        }
    for (int i = 1; i <= n; i++) v[i] = 0;
    dfs(s);
    print(ans);
    return 0;
}

毒蛇の脱走 (Snake Escaping)

毒瘤题。

注意到对于每次询问 $\max(c_?,c_0,c_1) \le 6$。

对于 $c_?$ 暴力枚举；对于 $c_0,c_2$ 容斥，需要 FWT 预处理。

总时间复杂度 $\mathcal O(l2^l + 2^{\lfloor \frac l3 \rfloor}q)$。

随手跑了个 LOJ 最优解是怎么回事。。。

const int N = 20;
int l, n, q, a[1<<N|7], b[1<<N|7], c[1<<N|7];
string s, t;
int cx, c0, c1, kx, k0, k1, ans;

int main() {
    rd(l, q), n = 1 << l, rds(s);
    for (int i = 0; i < n; i++) a[i] = b[i] = c[i] = s[i] & 15;
    for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
        for (int i = 0; i < n; i += o)
            for (int j = 0; j < k; j++)
                b[i+j+k] += b[i+j], c[i+j] += c[i+j+k];
    while (q--) {
        rds(t), cx = c0 = c1 = kx = k0 = k1 = ans = 0;
        for (int i = 0; i < l; i++)
            switch (t[i]) {
                case '?' : ++cx, kx |= 1 << (l - 1 - i); break;
                case '0' : ++c0, k0 |= 1 << (l - 1 - i); break;
                case '1' : ++c1, k1 |= 1 << (l - 1 - i); break;
            }
        if (cx <= c0 && cx <= c1) {
            ans = a[k1];
            for (int s = kx; s; s = (s - 1) & kx) ans += a[s|k1];
            print(ans);
        } else if (c1 <= c0) {
            ans = (__builtin_popcount(k1) & 1) ? -b[kx] : b[kx];
            for (int s = k1; s; s = (s - 1) & k1)
                ans += (__builtin_popcount(s ^ k1) & 1) ? -b[kx^s] : b[kx^s];
            print(ans);
        } else {
            kx = (n - 1) ^ kx;
            ans = (__builtin_popcount(k0) & 1) ? -c[kx] : c[kx];
            for (int s = k0; s; s = (s - 1) & k0)
                ans += (__builtin_popcount(s ^ k0) & 1) ? -c[kx^s] : c[kx^s];
            print(ans);
        }
    }
    return 0;
}