头像

毕天驰

TYNFMS https://tynfms.github.io/




离线:1天前


最近来访(86)
用户头像
1..
用户头像
tingze
用户头像
Jixer
用户头像
咖啡豆
用户头像
眰恦.
用户头像
high-DIO
用户头像
rizon
用户头像
mmkl
用户头像
不头秃的程序柏
用户头像
远山淡影0_0
用户头像
上单盲僧
用户头像
超大只树懒
用户头像
星冈山月
用户头像
Lts
用户头像
无法新建文件夹
用户头像
b11
用户头像
沉吟.
用户头像
fly_fish
用户头像
decoder
用户头像
20090331

活动打卡代码 AcWing 275. 传纸条

毕天驰
2个月前
// Problem: 传纸条
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/277/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

const int N = 60;
int g[N][N], f[N << 1][N][N];
int n, m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> g[i][j];

    for (int k = 2; k <= n + m; k++)
        for (int x1 = max(1, k - m); x1 <= n && x1 < k; x1++) // 1 <= y1 = k - x1 <= m, 1 <= x1 <= n => 1 1
            for (int x2 = max(1, k - m); x2 <= n && x2 < k; x2++) 
                for (int a = 0; a <= 1; a++)
                    for (int b = 0; b <= 1; b++) {
                        int y1 = k - x1, y2 = k - x2;
                        int tmp = g[x1][y1];
                        if (x1 != x2 || k == 2 || k == n + m) {
                            tmp += g[x2][y2];
                            f[k][x1][x2] = max(f[k][x1][x2], f[k - 1][x1 - a][x2 - b] + tmp);
                        }
                    }
            // {
                // if (x1 == x2) continue;
                // int y1 = k - x1, y2 = k - x2;
                // // (x1 - 1, y1), (x2 - 1, y2)
                // // (x1, y1 - 1), (x2 - 1, y2)
                // // (x1 - 1, y1), (x2, y2 - 1)
                // // (x1, y1 - 1), (x2, y2 - 1)
                // f[k][x1][x2] = max(f[k][x1][x2], f[k - 1][x1 - 1][x2 - 1]);
                // f[k][x1][x2] = max(f[k][x1][x2], f[k - 1][x1][x2 - 1]); 
                // f[k][x1][x2] = max(f[k][x1][x2], f[k - 1][x1 - 1][x2]);
                // f[k][x1][x2] = max(f[k][x1][x2], f[k - 1][x1][x2]);
                // f[k][x1][x2] += g[x1][y1] + g[x2][y2];
            // } 

    cout << f[n + m][n][n] << endl;

    return 0;
}



活动打卡代码 AcWing 274. 移动服务

毕天驰
2个月前
// Problem: 移动服务
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/276/
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

const int N = 210, M = 1010;
const int INF = 0x3f3f3f3f;
int g[N][N], n, m;
int request[M];
int f[M][N][N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &g[i][j]);
    for (int i = 1; i <= m; i++)
        scanf("%d", request + i);

    request[0] = 3;
    memset(f, 0x3f, sizeof(f));
    f[0][1][2] = 0;
    for (int i = 0; i < m; i++) 
        for (int x = 1; x <= n; x++)
            for (int y = 1; y <= n; y++) {
                int z = request[i], v = f[i][x][y];
                if (x == y || y == z || z == x) continue;
                int u = request[i + 1];
                f[i + 1][y][z] = min(f[i + 1][y][z], v + g[x][u]);
                f[i + 1][x][z] = min(f[i + 1][x][z], v + g[y][u]);
                f[i + 1][x][y] = min(f[i + 1][x][y], v + g[z][u]);
            }

    int res = INF;
    for (int x = 1; x <= n; x++)
        for (int y = 1; y <= n; y++) {
            int z = request[m];
            if (x == y || y == z || z == x) continue;
            res = min(res, f[m][x][y]);
        }
    printf("%d\n", res);

    return 0;
}



活动打卡代码 AcWing 273. 分级

毕天驰
2个月前
// Problem: 分级
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/275/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

const int N = 2010;
const int INF = 0x3f3f3f3f;
int a[N], n, b[N];
int f[N][N];

int solve() {
    for (int i = 1; i <= n; i++) {
        int minv = INF;
        for (int j = 1; j <= n; j++) {
            minv = min(minv, f[i - 1][j]);
            f[i][j] = minv + abs(a[i] - b[j]);
        }
    }

    int res = INF;
    for (int i = 1; i <= n; i++)
        res = min(res, f[n][i]);
    return res;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = a[i];
    }

    sort(b + 1, b + n + 1);
    int res = solve();
    reverse(a + 1, a + n + 1);
    res = min(res, solve());

    cout << res << endl;

    return 0;
}




毕天驰
2个月前
// Problem: 最长公共上升子序列
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/274/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

const int N = 3010;
int f[N][N], n, a[N], b[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];

    for (int i = 1; i <= n; i++) {
        int maxv = 1;
        for (int j = 1; j <= n; j++) {
            f[i][j] = f[i - 1][j];
            if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
            if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1);
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i++)
        res = max(res, f[n][i]);
    cout << res << endl;

    return 0;
}



毕天驰
2个月前
// Problem: 杨老师的照相排列
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/273/
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = 31;
int n, a[N];
ll f[N][N][N][N][N];

int main() {
    while (cin >> n && n) {
        memset(a, 0, sizeof(a));
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        memset(f, 0, sizeof(f));
        f[0][0][0][0][0] = 1;

        for (int a1 = 0; a1 <= a[1]; a1++)
            for (int a2 = 0; a2 <= min(a1, a[2]); a2++)
                for (int a3 = 0; a3 <= min(a2, a[3]); a3++) 
                    for (int a4 = 0; a4 <= min(a3, a[4]); a4++) 
                        for (int a5 = 0; a5 <= min(a4, a[5]); a5++) {
                            ll &x = f[a1][a2][a3][a4][a5]; 
                            if (a1 && a1 - 1 >= a2) x += f[a1 - 1][a2][a3][a4][a5];
                            if (a2 && a2 - 1 >= a3) x += f[a1][a2 - 1][a3][a4][a5];
                            if (a3 && a3 - 1 >= a4) x += f[a1][a2][a3 - 1][a4][a5];
                            if (a4 && a4 - 1 >= a5) x += f[a1][a2][a3][a4 - 1][a5];
                            if (a5)                 x += f[a1][a2][a3][a4][a5 - 1];
                        }

        cout << f[a[1]][a[2]][a[3]][a[4]][a[5]] << endl;
    }

    return 0;
}


活动打卡代码 AcWing 529. 宝藏

毕天驰
3个月前
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 12, M = 1 << N;
const int INF = 0x3f3f3f3f;
int n, m;
int d[N][N];
int f[M][N], g[M];

int main() {
    cin >> n >> m;

    memset(d, 0x3f, sizeof(d));
    for (int i = 0; i < n; i++)
        d[i][i] = 0;

    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;
        x--, y--;
        d[x][y] = d[y][x] = min(d[x][y], z);
    }

    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 & i; j; j = (j - 1) & i) 
            if ((g[j] & i) == i) {
                int rest = i ^ j;
                int cost = 0;
                for (int k = 0; k < n; k++)
                    if (rest >> k & 1) {
                        int t = INF;
                        for (int x = 0; x < n; x++)
                            if (j >> x & 1)
                                t = min(t, d[k][x]);
                        cost += t;
                    }

                for (int k = 1; k < n; k++)
                    f[i][k] = min(f[i][k], f[j][k - 1] + cost * k);
            }

    int res = INF;
    for (int i = 0; i < n; i++)
        res = min(res, f[(1 << n) - 1][i]);
    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 1322. 取石子游戏

毕天驰
3个月前
#include <iostream>
using namespace std;

const int N = 1010;
int n;
int a[N];
int l[N][N], r[N][N];

int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        for (int len = 1; len <= n; len++) 
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                if (len == 1) l[i][j] = r[i][j] = a[i];
                else {
                    int L = l[i][j - 1], R = r[i][j - 1], X = a[j];
                    if (R == X) l[i][j] = 0;
                    else if (X < L && X < R || X > L && X > R) l[i][j] = X;
                    else if (L > R) l[i][j] = X - 1;
                    else l[i][j] = X + 1;

                    L = l[i + 1][j], R = r[i + 1][j], X = a[i];
                    if (L == X) r[i][j] = 0;
                    else if (X < L && X < R || X > L && X > R) r[i][j] = X;
                    else if (R > L) r[i][j] = X - 1;
                    else r[i][j] = X + 1;
                }
            }

        if (n == 1) puts("1");
        else cout << (l[2][n] != a[1]) << endl; 
    }

    return 0;
}


活动打卡代码 AcWing 218. 扑克牌

毕天驰
3个月前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 14;
const double INF = 1e20;
int A, B, C, D;
double f[N][N][N][N][5][5];

double dp(int a, int b, int c, int d, int x, int y) {
    if (a > 13 || b > 13 || c > 13 || d > 13) 
        return INF;
    double &v = f[a][b][c][d][x][y];
    if (v >= 0) return v;
    int as = a + (x == 0) + (y == 0);
    int bs = b + (x == 1) + (y == 1);
    int cs = c + (x == 2) + (y == 2);
    int ds = d + (x == 3) + (y == 3);
    if (as >= A && bs >= B && cs >= C && ds >= D) 
        return v = 0;

    int sum = a + b + c + d + (x != 4) + (y != 4);
    sum = 54 - sum;
    if (sum <= 0) return v = INF;

    v = 1;
    if (a < 13) v += (13. - a) / sum * dp(a + 1, b, c, d, x, y);
    if (b < 13) v += (13. - b) / sum * dp(a, b + 1, c, d, x, y);
    if (c < 13) v += (13. - c) / sum * dp(a, b, c + 1, d, x, y);
    if (d < 13) v += (13. - d) / sum * dp(a, b, c, d + 1, x, y);
    if (x == 4) {
        double t = INF;
        for (int i = 0; i < 4; i++)
            t = min(t, 1.0 / sum * dp(a, b, c, d, i, y));
        v += t;
    }
    if (y == 4) {
        double t = INF;
        for (int i = 0; i < 4; i++)
            t = min(t, 1.0 / sum * dp(a, b, c, d, x, i));
        v += t;
    }

    return v;
}

int main() {
    cin >> A >> B >> C >> D;
    memset(f, -1, sizeof(f));

    double t = dp(0, 0, 0, 0, 4, 4);
    if (t > INF / 2.) t = -1;
    printf("%.3lf\n", t);

    return 0;
}


活动打卡代码 AcWing 217. 绿豆蛙的归宿

毕天驰
3个月前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010, M = 200010;
int n, m;
int h[N], e[M], ne[M], w[M], idx;
int dout[N];
double f[N];

inline void add(int x, int y, int z) {
    e[++idx] = y, w[idx] = z, ne[idx] = h[x], h[x] = idx;
}

double dp(int x) {
    if (f[x] >= 0.) return f[x];
    f[x] = 0.;
    for (int i = h[x]; i; i = ne[i]) {
        int y = e[i], z = w[i];
        f[x] += (z + dp(y)) / dout[x];
    }
    return f[x];
}

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

    for (int i = 0, x, y, z; i < m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
        dout[x]++;
    }

    memset(f, -1, sizeof(f));

    printf("%.2lf\n", dp(1));

    return 0;
}


活动打卡代码 AcWing 215. 破译密码

毕天驰
3个月前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = 50010;
int primes[N], cnt;
bool vis[N];
int mobius[N], sum[N];

void init(int n) {
    mobius[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            primes[cnt++] = i;
            mobius[i] = -1;
        }
        for (int j = 0; primes[j] * i <= n; j++) {
            int tmp = primes[j] * i;
            vis[tmp] = 1;
            if (!(i % primes[j])) {
                mobius[tmp] = 0;
                break;
            }
            mobius[tmp] = -mobius[i]; 
        }
    }

    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + mobius[i];
}

int main() {
    init(N - 1);

    int tt;
    scanf("%d", &tt);
    while (tt--) {
        int a, b, d;
        scanf("%d%d%d", &a, &b, &d);
        a /= d, b /= d;
        int n = min(a, b);
        ll res = 0;
        for (int l = 1, r; l <= n; l = r + 1) {
            r = min(n, min(a / (a / l), b / (b / l)));
            res += 1ll * (sum[r] - sum[l - 1]) * (a / l) * (b / l);
        }

        cout << res << endl;
    }

    return 0;
}