头像

逆乾


访客:22195

离线:15天前


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

逆乾
4个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 5;
int n, a[N];
int l[N][N], r[N][N];

int main()
{
    int T;
    cin >> T;
    while (T--) {
        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 (i == j)
                    l[i][j] = r[i][j] = a[i];
                else {
                    int L = l[i][j - 1], R = r[i][j - 1], X = a[j];
                    if (X == R)
                        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 (X == L)
                        r[i][j] = 0;
                    else if (X < L && X < R || X > L && X > R)
                        r[i][j] = X;
                    else if (L < R)
                        r[i][j] = X - 1;
                    else
                        r[i][j] = X + 1;
                }
            }
        cout << (n == 1 || a[1] != l[2][n]) << endl;
    }
    return 0;
}


活动打卡代码 AcWing 1321. 取石子

逆乾
4个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 55, M = 5e4 + 50;
int dp[N][M];

int dfs(int a, int b)
{
    int& v = dp[a][b];
    if (v != -1)
        return v;
    if (!a)
        return v = b & 1;
    if (b == 1)
        return v = dfs(a + 1, 0);
    if (a && !dfs(a - 1, b))
        return v = 1;
    if (b && !dfs(a, b - 1))
        return v = 1;
    if (a > 1 && !dfs(a - 2, b + (b ? 3 : 2)))
        return v = 1;
    if (a && b && !dfs(a - 1, b + 1))
        return v = 1;
    return v = 0;
}

int main()
{
    memset(dp, -1, sizeof dp);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        int a = 0, b = 0;
        while (n--) {
            int x;
            cin >> x;
            if (x == 1)
                a++;
            else
                b += b ? x + 1 : x;
        }
        cout << (dfs(a, b) ? "YES" : "NO") << endl;
    }
    return 0;
}


活动打卡代码 AcWing 1319. 移棋子游戏

逆乾
4个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 2e3 + 5, M = 6e3 + 5;
int n, m, k;
int h[N], e[M], ne[M], idx;
int sg[N];

void add(int u, int v)
{
    e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}

void dfs(int u)
{
    if (sg[u] != -1)
        return;
    unordered_set<int> exist;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        dfs(j);
        exist.insert(sg[j]);
    }
    for (int i = 0;; i++)
        if (!exist.count(i)) {
            sg[u] = i;
            break;
        }
    return;
}

int main()
{
    cin >> n >> m >> k;
    memset(h, -1, sizeof h);
    while (m--) {
        int u, v;
        cin >> u >> v;
        add(u, v);
    }
    memset(sg, -1, sizeof sg);
    for (int i = 1; i <= n; i++)
        if (sg[i] == -1)
            dfs(i);
    int res = 0;
    while (k--) {
        int p;
        cin >> p;
        res ^= sg[p];
    }
    cout << (res ? "win" : "lose") << endl;
    return 0;
}


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

逆乾
4个月前
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 5e4 + 5;
int a, b, d;
int cnt, primes[N];
int mobius[N], sum[N];
bool vis[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] <= n / i; j++) {
            vis[i * primes[j]] = true;
            if (i % primes[j] == 0) {
                mobius[i * primes[j]] = 0;
                break;
            }
            mobius[i * primes[j]] = mobius[i] * -1;
        }
    }
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + mobius[i];
    return;
}

int main()
{
    init(N - 1);
    int T;
    cin >> T;
    while (T--) {
        cin >> 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 * (a / l) * (b / l) * (sum[r] - sum[l - 1]);
        }
        cout << res << endl;
    }
    return 0;
}


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

逆乾
4个月前
#include <bits/stdc++.h>

using namespace std;

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

double dfs(int a, int b, int c, int d, int x, int y)
{
    double& v = dp[a][b][c][d][x][y];
    if (v >= 0)
        return v;
    int a_cnt = a + (x == 1) + (y == 1);
    int b_cnt = b + (x == 2) + (y == 2);
    int c_cnt = c + (x == 3) + (y == 3);
    int d_cnt = d + (x == 4) + (y == 4);
    if (a_cnt >= A && b_cnt >= B && c_cnt >= C && d_cnt >= D)
        return v = 0;
    int sum = a + b + c + d + (x > 0) + (y > 0);
    sum = 54 - sum;
    if (sum <= 0)
        return v = INF;
    v = 1;
    if (a < 13)
        v += (13.0 - a) / sum * dfs(a + 1, b, c, d, x, y);
    if (b < 13)
        v += (13.0 - b) / sum * dfs(a, b + 1, c, d, x, y);
    if (c < 13)
        v += (13.0 - c) / sum * dfs(a, b, c + 1, d, x, y);
    if (d < 13)
        v += (13.0 - d) / sum * dfs(a, b, c, d + 1, x, y);
    if (!x) {
        double t = INF;
        for (int i = 1; i < M; i++)
            t = min(t, 1.0 / sum * dfs(a, b, c, d, i, y));
        v += t;
    }
    if (!y) {
        double t = INF;
        for (int i = 1; i < M; i++)
            t = min(t, 1.0 / sum * dfs(a, b, c, d, x, i));
        v += t;
    }
    return v;
}

int main()
{
    scanf("%d %d %d %d", &A, &B, &C, &D);
    memset(dp, -1, sizeof dp);
    double res = dfs(0, 0, 0, 0, 0, 0);
    if (res > INF / 2)
        res = -1;
    printf("%.3lf\n", res);
    return 0;
}


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

逆乾
4个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5, M = 2e5 + 5;
int n, m;
int h[N], e[M], val[M], ne[M], idx;
int dout[N];
double dp[N];

void add(int u, int v, int w)
{
    e[idx] = v, val[idx] = w, ne[idx] = h[u], h[u] = idx++;
}

void dfs(int u)
{
    if (dp[u] >= 0)
        return;
    dp[u] = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        dfs(j);
        dp[u] += (val[i] + dp[j]) / dout[u];
    }
    return;
}

int main()
{
    scanf("%d %d", &n, &m);
    memset(h, -1, sizeof h);
    while (m--) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        add(u, v, w);
        dout[u]++;
    }
    memset(dp, -1, sizeof dp);
    dfs(1);
    printf("%.2lf\n", dp[1]);
    return 0;
}



逆乾
4个月前

快速乘的板子(好吧, 这个叫法只是为了跟快速幂对应,其实更多人习惯把这个板子叫作龟速乘,因为这个算法把 $O(1)$ 的乘法变成了 $O(logn)$ 的加法)。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL quickmul(LL a, LL b, LL mod)
{
    LL res = 0;
    while (b) {
        if (b & 1)
            res = (res + a) % mod;
        a = 2 * a % mod;
        b >>= 1;
    }
    return res;
}

int main()
{
    LL a, b, mod;
    cin >> a >> b >> mod;
    cout << quickmul(a, b, mod) << endl;
    return 0;
}



逆乾
4个月前

快速幂的板子,只是当 $b = 0, p = 1$ 时,答案应该是 $0$ 而不是 $1$,所以在 $quickpow$ 中,一开始定义的 $res$ 先对 $p$ 取个模(个人比较习惯用 $mod$).

#include <bits/stdc++.h>

using namespace std;

int quickpow(int a, int b, int mod)
{
    int res = 1 % mod;
    while (b) {
        if (b & 1)
            res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return res;
}

int main()
{
    int a, b, mod;
    cin >> a >> b >> mod;
    cout << quickpow(a, b, mod) << endl;
    return 0;
}


活动打卡代码 AcWing 529. 宝藏

逆乾
4个月前
#include <bits/stdc++.h>

using namespace std;

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

int main()
{
    cin >> n >> m;
    memset(d, 0x3f, sizeof d);
    for (int i = 0; i < n; i++)
        d[i][i] = 0;
    while (m--) {
        int u, v, w;
        cin >> 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(dp, 0x3f, sizeof dp);
    for (int i = 0; i < n; i++)
        dp[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 remain = i ^ j;
                int cost = 0;
                for (int u = 0; u < n; u++)
                    if (remain >> u & 1) {
                        int t = INF;
                        for (int v = 0; v < n; v++)
                            if (j >> v & 1)
                                t = min(t, d[u][v]);
                        cost += t;
                    }
                for (int k = 1; k < n; k++)
                    dp[i][k] = min(dp[i][k], dp[j][k - 1] + cost * k);
            }
    int res = INF;
    for (int i = 0; i < n; i++)
        res = min(res, dp[(1 << n) - 1][i]);
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 98. 分形之城

逆乾
5个月前
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PLL;

PLL solve(LL n, LL m)
{
    if (!n)
        return { 0, 0 };
    LL len = 1ll << (n - 1), cnt = 1ll << (2 * (n - 1));
    PLL p = solve(n - 1, m % cnt);
    LL x = p.first, y = p.second;
    LL t = m / cnt;
    if (!t)
        return { y, x };
    if (t == 1)
        return { x, y + len };
    if (t == 2)
        return { x + len, y + len };
    return { 2 * len - y - 1, len - x - 1 };
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        LL n, a, b;
        scanf("%lld %lld %lld", &n, &a, &b);
        PLL pa = solve(n, a - 1), pb = solve(n, b - 1);
        double x = pa.first - pb.first, y = pa.second - pb.second;
        printf("%.0lf\n", 10 * sqrt(x * x + y * y));
    }
    return 0;
}