头像

墨染空

Q A Q


访客:37535

离线:1天前


活动打卡代码 AcWing 1194. 岛和桥

$f[s][i][j]$ 表示一条有向路径(不经过重复点),当前路径点集合为 $s$,最后两个点是 $j$ → $i$ 的最大价值
$g[s][i][j]$ 类似,不过是方案数。

较为显然的转移,枚举 $s$ 中的点 $k (i \not= j \not = k)$:

$f[s][i][j] = \max(f[s\ \text{xor}\ 2^k][j][k] + a[i] \times a[j] + \text{w}(i,j,k))$

$\text{w}(i, j, k)$ 表示 $i, j, k$ 如果构成一个环的权值,否则为 $0$。

方案数也是类似的。

初始化两点路径,即 $f[2^i\ \text{or}\ 2^j][i][j] = a[i] \times a[j]$

注意方案数最后要 $/2$,因为会统计两次(我们规定的是有向)

复杂度

$O(2^n\times n^3)$ 用 $\text{lowbit}$ 应该还能省复杂度,但是我不会算

注意特判一个节点的时候

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;

const int N = 13;

int n, m, a[N], Log[1 << N], sum;

bool w[N][N];

LL f[1 << N][N][N], g[1 << N][N][N];

void out(int x) {
    for (int i = 0; i < n; i++)
        printf("%d", x >> i & 1);
}

void inline clear() {
    memset(w, false, sizeof w);
    memset(g, 0, sizeof g);
    memset(f, 0, sizeof f);
    sum = 0;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        clear();
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) scanf("%d", a + i), Log[1 << i] = i, sum += a[i];
        for (int i = 1; i <= m; i++) {
            int a, b; scanf("%d%d", &a, &b);
            --a, --b;
            w[a][b] = w[b][a] = true;
        }
        if (n == 1) { printf("%d %d\n", a[0], 1); continue; }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && w[i][j]) {
                    f[(1 << i) | (1 << j)][i][j] = a[i] * a[j];
                    g[(1 << i) | (1 << j)][i][j] = 1;   
                }
            }
        }
        for (int s = 1; s < (1 << n); s++) {
            for (int A = s, i = Log[s & -s]; A ; A -= 1 << i, i = Log[A & -A]) {
                for (int B = s ^ (1 << i), j = Log[B & -B]; B; B -= 1 << j, j = Log[B & -B]) {
                    if (!w[i][j]) continue;
                    for (int C = s ^ (1 << i) ^ (1 << j), k = Log[C & -C]; C; C -= 1 << k, k = Log[C & -C]) {
                        if (!w[j][k] || !f[s ^ (1 << i)][j][k]) continue;
                        LL val = f[s ^ (1 << i)][j][k] + a[i] * a[j] + (w[i][k] ? a[i] * a[j] * a[k] : 0);
                        if (val > f[s][i][j]) f[s][i][j] = val, g[s][i][j] = g[s ^ (1 << i)][j][k];
                        else if (val == f[s][i][j]) g[s][i][j] += g[s ^ (1 << i)][j][k];
                    }
                }
            } 
        }
        LL res = 0, cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!g[i][j]) continue;
                if (f[(1 << n) - 1][i][j] > res) res = f[(1 << n) - 1][i][j], cnt = g[(1 << n) - 1][i][j];
                else if (f[(1 << n) - 1][i][j] == res) cnt += g[(1 << n) - 1][i][j];
            }
        }
        if (!res) puts("0 0");
        else printf("%lld %lld\n", res + sum, cnt / 2);
    }
    return 0;
}



#include <cstdio>
#include <iostream>

using namespace std;

const int N = 100005;

int n, m;

char op[N][5];

int t[N];

void inline work(char opt[], int &v, int d) {
    if (opt[0] == 'O') v |= d;
    else if (opt[0] == 'A') v &= d;
    else v ^= d;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%s%d", op[i], &t[i]);
    int ans = 0;
    for (int i = 30; ~i; i--) {
        bool ok = true;
        int v0 = 0, v1 = 1;
        for (int j = 1; j <= n; j++)
            work(op[j], v0, t[j] >> i & 1), work(op[j], v1, t[j] >> i & 1);
        if (v0) ans |= 1 << i;
        else if (v1 && m >= (1 << i)) ans |= 1 << i, m -= 1 << i;
    }
    printf("%d\n", ans);
    return 0;
}


活动打卡代码 AcWing 529. 宝藏

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 12, M = 1 << N, INF = 0x3f3f3f3f;
int n, m, d[N][N], g[M], f[M][N], ans = INF;
/*
f[i][j] 表示以 i 为子集 高度为 j 的生成树 的 最小花费
设u为i的子集且u能到i子集中所有的点, cost(j) 表示 j 扩散一层的边权之和
f[i][j] = min{ f[i][j - 1] + cost[j] * j }
*/
int main(){


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

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(i != j) d[i][j] = INF;

    for(int i = 1; i <= m; i++){
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        u--, v--;
        d[u][v] = d[v][u] = min(d[u][v], w);
    }

    for(int i = 1; i < (1 << n); i++)
        for(int j = 0; j < n; j++)
            if(i >> j & 1) for(int k = 0; k < n; k++)
                if(d[j][k] != INF)
                    g[i] |= 1 << k;

    memset(f, 0x3f, sizeof f);
    for(int i = 0; i < n; i++)
        f[1 << i][0] = 0;
    for(int i = 1; i < (1 << n); i++){
        for(int j = i - 1; j; j = i & (j - 1)){
            if((g[j] & i) == i){
                int cost = 0, st = i ^ j;
                for(int k = 0; k < n; k++){
                    if(st >> k & 1){
                        int t = INF;
                        for(int u = 0; u < n; u++)
                            if(j >> u & 1)
                                t = min(t, d[u][k]);
                        cost += t;
                    }
                }
                for(int k = 1; k < n; k++)
                    f[i][k] = min(f[i][k], f[j][k - 1] + cost * k);
            }
        }
    }
    for(int i = 0; i < n; i++)
        ans = min(ans, f[(1 << n) - 1][i]);
    printf("%d\n", ans);
}


活动打卡代码 AcWing 1426. 魔法

墨染空
1个月前
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;

typedef long long LL;

const int N = 105, M = 2505, L = 20;
const LL INF = 1e18;

int n, m, K, l;
LL d[N][N], w[N][N], g[L][N][N], f[N], t[N];

struct E{
    int u, v, w;
} e[M];

int main() {
    memset(g, 0x3f, sizeof g);
    scanf("%d%d%d", &n, &m, &K);
    l = log2(K);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) if (i != j) d[i][j] = INF;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
        d[e[i].u][e[i].v] = min(d[e[i].u][e[i].v], (LL)e[i].w);
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            w[i][j] = d[i][j];
            for (int k = 1; k <= m; k++)
                w[i][j] = min(w[i][j], d[i][e[k].u] - e[k].w + d[e[k].v][j]);
            g[0][i][j] = w[i][j];
        }
    }
    for (int c = 1; c <= l; c++) 
        for (int i = 1; i <= n; i++) 
            for (int j = 1; j <= n; j++) 
                for (int k = 1; k <= n; k++) 
                    g[c][i][j] = min(g[c][i][j], g[c - 1][i][k] + g[c - 1][k][j]);
    for (int i = 1; i <= n; i++) f[i] = d[1][i];
    for (int c = 0; c <= l; c++) {
        if (K >> c & 1) {
            for (int i = 1; i <= n; i++) t[i] = f[i];
            memset(f, 0x3f, sizeof f);
            for (int i = 1; i <= n; i++) 
                for (int j = 1; j <= n; j++) f[i] = min(f[i], t[j] + g[c][j][i]);
        }
    }
    printf("%lld\n", f[n]);
    return 0;
}



墨染空
1个月前

全网都是矩阵快速幂,我只会倍增DP

其实这题与 AcWing 345. 牛站 还是比较像的,那题可以矩阵快速幂 / 倍增,这题也行。

先 $Floyd$ 预处理两点之间不用魔法最短距离 $d_{i, j}$ 复杂度 $O(n^3)$

然后预处理两点之间至多用一个魔法的最短距离 $w_{i, j}$,初始为 $w_{i, j} = d_{i, j}$,枚举 $i, j$ 和一条边 $(u, v, t)$ $w_{i, j} = \min(d[i][u] - t + d[v][j])$,复杂度 $O(n^2m)$

然后把 $w$ 数组当做邻接矩阵的新图,所以问题变成了走恰好 $k$ 条边的最短路(可以理解多走不会变差,因为满足 $w_{i, i} <= 0$),这个问题就是 AcWing 345. 牛站 ,具体做法看 AcWing 345. 牛站的倍增 DP 思路,复杂度 $O(n^3 \log K)$

注意细节,走 $0$ 条边的最短路是 $d_{1, n}$,注意 $f$ 的初始值。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;

typedef long long LL;

const int N = 105, M = 2505, L = 20;
const LL INF = 1e18;

int n, m, K, l;
LL d[N][N], w[N][N], g[L][N][N], f[N], t[N];

struct E{
    int u, v, w;
} e[M];

int main() {
    memset(g, 0x3f, sizeof g);
    scanf("%d%d%d", &n, &m, &K);
    l = log2(K);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) if (i != j) d[i][j] = INF;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
        d[e[i].u][e[i].v] = min(d[e[i].u][e[i].v], (LL)e[i].w);
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            w[i][j] = d[i][j];
            for (int k = 1; k <= m; k++)
                w[i][j] = min(w[i][j], d[i][e[k].u] - e[k].w + d[e[k].v][j]);
            g[0][i][j] = w[i][j];
        }
    }
    for (int c = 1; c <= l; c++) 
        for (int i = 1; i <= n; i++) 
            for (int j = 1; j <= n; j++) 
                for (int k = 1; k <= n; k++) 
                    g[c][i][j] = min(g[c][i][j], g[c - 1][i][k] + g[c - 1][k][j]);
    for (int i = 1; i <= n; i++) f[i] = d[1][i];
    for (int c = 0; c <= l; c++) {
        if (K >> c & 1) {
            for (int i = 1; i <= n; i++) t[i] = f[i];
            memset(f, 0x3f, sizeof f);
            for (int i = 1; i <= n; i++) 
                for (int j = 1; j <= n; j++) f[i] = min(f[i], t[j] + g[c][j][i]);
        }
    }
    printf("%lld\n", f[n]);
    return 0;
}


活动打卡代码 AcWing 1425. 跑步

墨染空
1个月前
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;

const int N = 100005, S = 350;

typedef long long LL;

int n, t, P, f[N], g[S][N], ans;

int main() {
    scanf("%d%d", &n, &P);
    t = sqrt(n) + 1;
    f[0] = 1;
    for (int i = 1; i < t; i++)
        for (int j = i; j <= n; j++) (f[j] += f[j - i]) %= P;
    g[0][0] = 1;
    for (int i = 1; i <= t; i++) {
        for (int j = i; j <= n; j++) {
            g[i][j] = g[i][j - i];
            if (j >= t) (g[i][j] += g[i - 1][j - t]) %= P;
        }
    }
    for (int i = 0; i <= n; i++) {
        int s = 0;
        for (int j = 0; j <= t; j++) (s += g[j][n - i]) %= P;
        ans = (ans + (LL)f[i] * s) % P;
    }
    printf("%d\n", ans);
}


活动打卡代码 AcWing 1424. 文具订购

墨染空
1个月前
#include <iostream>
using namespace std;

int n, a, b, c;

int x, y, z, s;

int main() {
    scanf("%d", &n);
    int d = n / 14; n %= 14;
    a = b = c = d;
    bool ok = false;
    if (n == 0) ok = true;
    for (int i = 0; i <= 2; i++) {
        for (int j = 0; j <= 4; j++) {
            for (int k = 0; k <= 5; k++) {
                if (i * 7 + j * 4 + k * 3 == n && i + j + k > s) {
                    s = i + j + k, x = i, y = j, z = k;
                    ok = true;
                } 
            }
        }
    }
    if (!ok) puts("-1");
    else printf("%d %d %d\n", a + x, b + y, c + z);
    return 0;
}


活动打卡代码 AcWing 1704. 建设城市

墨染空
1个月前
#include <cstdio>
#include <iostream>

using namespace std;

typedef long long LL;

const int N = 100005, P = 998244353, L = 300000;

int m, n, x, y, ans = 0, fact[N * 3], infact[N * 3];

int inline power(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = (LL)res * a % P;
        a = (LL)a * a % P;
        b >>= 1;
    }
    return res;
}

int inline C(int a, int b) {
    return (LL)fact[a] * infact[b] % P * infact[a - b] % P;
}

int inline work(int n, int m) {
    if (n == 0) return 1;
    return C(n + m - 1, n - 1);
}

int main() {
    fact[0] = infact[0] = 1;
    for (int i = 1; i <= L; i++) fact[i] = (LL)fact[i - 1] * i % P;
    infact[L] = power(fact[L], P - 2);
    for (int i = L - 1; i; i--) infact[i] = (LL)infact[i + 1] * (i + 1) % P;
    scanf("%d%d%d%d", &m, &n, &x, &y);
    for (int i = 1; i <= m; i++) {
        if (x <= n && n < y) {
            ans = (ans + (LL)work(x - 1 + 1, i - 1) * work(2 * n - y + 1, i - 1) % P * work(n - x + 1, m - i) % P * work(y - n - 1 + 1, m - i)) % P;
        } else if (x <= n && y <= n) {
            ans = (ans + (LL)work(n + 1, m - 1) * work(x - 1 + 1, i - 1) % P * work(n - y + 1, m - i)) % P;
        } else {
            ans = (ans + (LL)work(n + 1, m - 1) * work(x - n - 1 + 1, m - i) % P * work(2 * n - y + 1, i - 1)) % P;
        }
    }
    printf("%d\n", ans);
    return 0;
}


活动打卡代码 AcWing 1703. 荆轲刺秦王

墨染空
1个月前
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#define rint register int
using namespace std;

const int N = 351, S = 16, INF = 2e9;

int n, m, c1, c2, d, a[N][N];

int sx, sy, tx, ty, ansT = INF, ansC1, ansC2;

int g[N][N];

bool ban[N][N], vis[N][N], st[N][N][S][S];

struct Node{
    int x, y, c;
    bool operator < (const Node &b) const {
        return c < b.c;
    }
};

priority_queue<Node> Q;

struct State{
    int x, y, c1, c2, t;
} q[N * N * S * S];

int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

int gx[8] = { 0, 0, 1, -1, -1, -1, 1, 1 };
int gy[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

bool inline check(int nx, int ny) {
    return nx >= 1 && nx <= n && ny >= 1 && ny <= m;
}

void inline bfs0() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (a[i][j]) Q.push((Node){ i, j, a[i][j] });
        }
    while (!Q.empty()) {
        Node u = Q.top(); Q.pop();
        if (vis[u.x][u.y]) continue;
        vis[u.x][u.y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = u.x + dx[i], ny = u.y + dy[i];
            if (check(nx, ny) && a[u.x][u.y] - 1 > a[nx][ny]) {
                a[nx][ny] = a[u.x][u.y] - 1;
                Q.push((Node) { nx, ny, a[nx][ny] });
            }
        }
    }
}

void inline bfs() {
    int hh = 0, tt = -1;
    q[++tt] = (State){ sx, sy, 0, 0, 0 };
    while (hh <= tt) {
        State u = q[hh++]; 
        if (u.x == tx && u.y == ty) {
            if (u.t < ansT) {
                ansT = u.t, ansC1 = u.c1, ansC2 = u.c2;
            } else if (u.t == ansT) {
                if (u.c1 + u.c2 < ansC1 + ansC2 || (u.c1 + u.c2 == ansC1 + ansC2 && u.c1 < ansC1)) {
                    ansT = u.t, ansC1 = u.c1, ansC2 = u.c2;
                }
            }
            continue;
        } 
        if (u.t >= ansT) continue;
        for (rint i = 0; i < 8; i++) {
            rint nx = u.x + gx[i], ny = u.y + gy[i];
            if (!check(nx, ny)) continue;
            rint c = u.c1 + (a[nx][ny] ? 1 : 0);
            if (!ban[nx][ny] && (!a[nx][ny] || u.c1 < c1) && !st[nx][ny][c][u.c2]) {
                st[nx][ny][c][u.c2] = true;
                q[++tt] = (State) { nx, ny, c, u.c2, u.t + 1 };
            } 
        }
        if (u.c2 < c2) {
            for (rint i = 0; i < 4; i++) {
                rint nx = u.x + d * dx[i], ny = u.y + d * dy[i];
                if (!check(nx, ny)) continue;
                rint c = u.c1 + (a[nx][ny] ? 1 : 0);;
                if (!ban[nx][ny] && (!a[nx][ny] || u.c1 < c1) && !st[nx][ny][c][u.c2 + 1]) {
                    st[nx][ny][c][u.c2 + 1] = true;
                    q[++tt] = (State) { nx, ny, c, u.c2 + 1, u.t + 1 };
                }
            }
        }
    }
}

int main() {
    scanf("%d%d%d%d%d", &n, &m, &c1, &c2, &d);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char s[5]; scanf("%s", s);
            int len = strlen(s);
            if (s[0] == 'S') sx = i, sy = j;
            else if (s[0] == 'T') tx = i, ty = j;
            else if (s[0] != '.') {
                int x = 0;
                for (int k = 0; k < len; k++) x = x * 10 + s[k] - '0';
                a[i][j] = x;
                ban[i][j] = true;
            }
        }
    }
    bfs0();
    bfs();
    if (ansT == INF) puts("-1");
    else printf("%d %d %d\n", ansT, ansC1, ansC2);
    return 0;
}


活动打卡代码 AcWing 1702. 未了

墨染空
1个月前
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 200005;

typedef long long LL;

int n, L, v, a[N], q, t;

LL s[N];

bool inline check(int x) {
    return (double)(L + s[x]) / v > t; 
}

int main() {
    scanf("%d%d%d", &n, &L, &v);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    sort(a + 1, a + 1 + n, greater<int>());
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
    scanf("%d", &q);
    while (q--) {
        scanf("%d", &t);
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        if (!check(r)) puts("-1");
        else printf("%d\n", r);
    }
    return 0;
}