头像

剑过无声

TYNFMS https://tynfms.github.io/




离线:1天前


最近来访(59)
用户头像
Noslepums
用户头像
voyager1969
用户头像
anji
用户头像
孤独与我
用户头像
ddddf
用户头像
白墙
用户头像
RobertTarjan
用户头像
syt
用户头像
Eric.
用户头像
龚子昂
用户头像
San
用户头像
xtxxueyan
用户头像
13176510189
用户头像
屮牜
用户头像
猪啊猪
用户头像
15084948533
用户头像
Big_Tortoise
用户头像
千城暮雪
用户头像
正在加载中...
用户头像
eyetofreedom

活动打卡代码 AcWing 529. 宝藏

#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. 取石子游戏

#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. 扑克牌

#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. 绿豆蛙的归宿

#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. 破译密码

#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;
}


活动打卡代码 AcWing 214. Devu和鲜花

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

const int N = 20;
const int P = 1e9 + 7;
ll a[N];
int d = 1;

inline int qpow(int a, int p, int k) {
    int res = 1 % k;
    while (p) {
        if (p & 1) res = 1ll * res * a % k;
        a = 1ll * a * a % k;
        p >>= 1;
    }
    return res;
}

int C(ll a, ll b) {
    if (a < b) return 0;
    int u = 1;
    for (ll i = a; i > a - b; i--) 
        u = 1ll * i % P * u % P;
    return 1ll * u * d % P; // Fermat  
}

int main() {
    ll n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) 
        cin >> a[i];
    for (int j = 1; j <= n - 1; j++)
        d = 1ll * j * d % P;
    d = qpow(d, P - 2, P);

    ll res = 0;
    for (int i = 0; i < 1 << n; i++) {
        ll A = m + n - 1, B = n - 1;
        int sgn = 1;
        for (int j = 0; j < n; j++) 
            if (i >> j & 1) {
                sgn *= -1;
                A -= a[j] + 1;
            }
        res = (res + C(A, B) * sgn) % P;
    }

    cout << (res + P) % P << endl;

    return 0;
}


活动打卡代码 AcWing 208. 开关问题

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

const int N = 35;
int n, a[N][N];

int gauss() {
    int r, c;
    for (r = 1, c = 1; c <= n; c++) {
        int t = r;
        for (int i = r + 1; i <= n; i++)
            if (a[i][c]) {
                t = i;
                break;
            }
        if (!a[t][c]) continue;

        for (int i = c; i <= n + 1; i++)
            swap(a[t][i], a[r][i]);

        for (int i = r + 1; i <= n; i++)
            for (int j = n + 1; j >= c; j--)
                a[i][j] ^= a[i][c] & a[r][j];

        r++;
    }

    int res = 1;
    if (r < n + 1) {
        for (int i = r; i <= n; i++) {
            if (a[i][n + 1]) return -1; 
            res <<= 1;
        }
    }

    return res;
}

int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        memset(a, 0, sizeof(a));

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

        int x, y;
        while (cin >> x >> y && x && y) 
            a[y][x] = 1;
        int t = gauss();
        if (t == -1) puts("Oh,it's impossible~!!");
        else cout << t << endl;
    }

    return 0;
}



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

const int N = 15;
int n;
double a[N][N], b[N][N];

void gauss() {
    // 转换为上三角矩阵
    for (int r = 1, c = 1; c <= n; c++, r++) {
        int t = r;
        for (int i = r + 1; i <= n; i++)
            if (fabs(b[i][c]) > fabs(b[t][c]))
                t = i;

        for (int i = 1; i <= n + 1; i++)
            swap(b[t][i], b[r][i]);

        for (int i = n + 1; i >= c; i--)
            b[r][i] /= b[r][c];

        // 消元
        for (int i = r + 1; i <= n; i++)
            for (int j = n + 1; j >= c; j--)
                b[i][j] -= b[i][c] * b[r][j];
    }

    for (int i = n; i > 1; i--) 
        for (int j = i - 1; j; j--) {
            b[j][n + 1] -= b[i][n + 1] * b[j][i];
            b[j][i] = 0.;
        }
}

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

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            b[i][j] += 2 * (a[i][j] - a[0][j]);
            b[i][n + 1] += a[i][j] * a[i][j] - a[0][j] * a[0][j];
        }

    gauss();

    for (int i = 1; i <= n; i++)
        printf("%.3lf ", b[i][n + 1]);
    cout << endl;

    return 0;
}


活动打卡代码 AcWing 1315. 网格

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

const int N = 10010;
int primes[N], cnt;
bool vis[N];
int a[N], b[N];
int sum[N];

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

inline int factor(int n, int p) {
    int res = 0;
    while (n) {
        res += n / p;
        n /= p;
    }
    return res;
}

void mul(int r[], int &len, int x) {
    int t = 0;
    for (int i = 0; i < len; i++) {
        t += r[i] * x;
        r[i] = t % 10;
        t /= 10;
    }
    while (t) {
        r[len++] = t % 10;
        t /= 10;
    }
}

int C(int x, int y, int r[N]) {
    int len = 1;
    r[0] = 1;

    for (int i = 0; i < cnt; i++) {
        int p = primes[i];
        int s = factor(x, p) - factor(y, p) - factor(x - y, p);
        while (s--) mul(r, len, p);
    }

    return len;
}

void sub(int a[], int al, int b[], int bl) {
    int t = 0;
    for (int i = 0; i < al; i++) {
        a[i] -= t + b[i];
        if (a[i] < 0) a[i] += 10, t = 1;
        else t = 0;
    }
}

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

    int n, m;
    cin >> n >> m;
    int al = C(n + m, m, a);
    int bl = C(n + m, n + 1, b);

    sub(a, al, b, bl);

    int k = al - 1;
    while (!a[k] && k > 0) k--;
    while (~k) printf("%d", a[k--]); 

    return 0;
}


活动打卡代码 AcWing 1309. 车的放置

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

const int N = 2010, mod = 100003;
int fact[N], infact[N];

inline int qpow(int a, int p, int k) {
    int res = 1 % k;
    while (p) {
        if (p & 1) res = 1ll * res * a % k;
        a = 1ll * a * a % k;
        p >>= 1;
    }
    return res;
} 

void init() {
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i++) {
        fact[i] = 1ll * fact[i - 1] * i % mod;
        infact[i] = 1ll * infact[i - 1] * qpow(i, mod - 2, mod) % mod;
    }
}

inline int C(int a, int b) {
    if (a < b) return 0;
    return 1ll * fact[a] * infact[a - b] % mod * infact[b] % mod;
}

inline int P(int a, int b) {
    if (a < b) return 0;
    return 1ll * fact[a] * infact[a - b] % mod;
}

int main() {
    init();

    int a, b, c, d, k;
    cin >> a >> b >> c >> d >> k;

    int res = 0;
    for (int i = 0; i <= k; i++)
        res = (res + 1ll * C(b, i) * P(a, i) % mod * C(d, k - i) * P(a + c - i, k - i)) % mod;
    cout << res << endl;

    return 0;
}