头像

莫能与之争

四川农业大学




离线:14小时前



请问一下 long double 的精度是多少啊,为什么看有些代码用 long double 代替 long long,long double具体有什么妙用呢




请问一下单调队列优化,其本质是不是也是一种四边形不等式优化呢,单调队列是不是意味着其决策一定是单调的呢




为什么写for循环会超时,写while就不会超时啊,
而且while循环只有20ms+



活动打卡代码 AcWing 287. 积蓄程度

要特殊处理一下1号节点是汇点的情况:
只需要在两次扫描完后,
将以这个点为源点的水系流量,设置为边的流量即可。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <cassert>
#include <vector>

#define fileio freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define dbg(x) cout << #x << " : " << x << endl;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;

int read() {
    int ret = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1 ; ch = getchar();}
    while (ch >= '0' && ch <= '9') {ret = ret * 10 + ch - '0'; ch = getchar();}
    return f * ret;
}

void write(int x) {
    if (x > 9) write(x / 10);
    putchar('0' + (x % 10));
}
const int N = 2e5 + 7, M = N << 1;
int all[N], down[N];
int head[N], ver[M], nxt[M], edge[M], tot;
int dg[N];

void add(int u, int v, int w) {
    ver[++tot] = v; edge[tot] = w;
    nxt[tot] = head[u]; head[u] = tot;
}

void dfs_d(int u, int fa) {
    down[u] = 0;
    if (dg[u] == 1) {
        down[u] = inf;
        if (u != 1) return;
    }
    for (int i = head[u]; i; i = nxt[i]) {
        int y = ver[i];
        if (y == fa) continue;
        dfs_d(y, u);
        down[u] += min(edge[i], down[y]);
    }
}


void dfs_f(int u, int fa) {
    for (int i = head[u]; i; i = nxt[i]) {
        int y = ver[i];
        if (y == fa) continue;
        if (dg[y] == 1) {
            all[y] = min(all[u] - edge[i], edge[i]);
        } else {
            all[y] = down[y] + min(all[u] - min(edge[i], down[y]), edge[i]);
            dfs_f(y, u);
        }
    }
}

int u, v, w;
int main() {
    fastio;
    int t; cin >> t;
    while (t--) {
        memset(head, 0, sizeof head);
        memset(dg, 0, sizeof dg);
        memset(all, 0, sizeof all);
        tot = 0;
        int n; cin >> n;
        for (int i = 1; i < n; i++) {
            cin >> u >> v >> w;
            add(u, v, w); add(v, u, w);
            ++dg[u]; ++dg[v];
        }
        dfs_d(1, 0);
        all[1] = down[1];
        dfs_f(1, 0);

        // 特判
        if (dg[1] == 1) all[1] = edge[head[1]];

        int ans = -inf;
        for (int i = 1; i <= n; i++) {
            ans = max(all[i], ans);
        }
        cout << ans << endl;
    }
}


活动打卡代码 AcWing 286. 选课

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <climits>
#include <cmath>
#include <cassert>
#include <vector>

#define fileio freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define dbg(x) cout << #x << " : " << x << endl;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int inf = 0x3f3f3f3f;
int read() {
    int ret = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1 ; ch = getchar();}
    while (ch >= '0' && ch <= '9') {ret = ret * 10 + ch - '0'; ch = getchar();}
    return f * ret;
}

void write(int x) {
    if (x > 9) write(x / 10);
    putchar('0' + (x % 10));
}

const int N = 310;
int head[N], ver[N << 1], nxt[N << 1], tot;

void add(int u, int v) {
    ver[++tot] = v;
    nxt[tot] = head[u]; head[u] = tot;
}

int x, y, n, m;
int score[N];
int dp[N][N];

void dfs(int u) {
    for (int i = head[u]; ~i; i = nxt[i]) {
        int y = ver[i];
        dfs(y);
        for (int j = m; j >= 1; j--) {
            for (int k = 1; k <= j; k++) {
                dp[u][j] = max(dp[u][j - k] + dp[y][k], dp[u][j]);
            }
        }
    }
    if (u) {
        for (int j = m; j >= 1; j--)
            dp[u][j] = dp[u][j - 1] + score[u];
    }
}

int main() {
    memset(head, -1, sizeof head);
    n = read(), m = read();
    for(int i = 1; i <= n; i++) {
        x = read(); y = read();
        if (x) add(x, i);
        else add(0, i);
        score[i] = y;
    }
    dfs(0);
    cout << dp[0][m] << endl;
}


活动打卡代码 AcWing 284. 金字塔

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <climits>
#include <cmath>
#include <cassert>
#include <vector>

#define fileio freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define dbg(x) cout << #x << " : " << x << endl;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int inf = 0x3f3f3f3f;
int read() {
    int ret = 0; char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') {ret = ret * 10 + ch - '0'; ch = getchar();}
    return ret;
}

void write(int x) {
    if (x > 9) write(x / 10);
    putchar('0' + (x % 10));
}

char str[310];
ll dp[310][310];
int len;
const ll mod = 1e9;

ll dfs(int l, int r) {
    if (l > r) return 0;
    if (l == r) return 1;
    if (dp[l][r] != -1ll) return dp[l][r];
    dp[l][r] = 0;
    for (int k = l + 2; k <= r; k++) {
        if (str[k] == str[l]) {
            dp[l][r] = (dp[l][r] + dfs(l + 1, k - 1) * dfs(k, r) % mod) % mod;
        }
    }
    return dp[l][r];
}

int main() {
    cin >> str + 1;
    memset(dp, -1, sizeof dp);
    len = strlen(str + 1);
    cout << dfs(1, len);
}



好家伙



活动打卡代码 AcWing 283. 多边形

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <climits>
#include <cmath>
#include <cassert>
#include <vector>

#define fileio freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define dbg(x) cout << #x << " : " << x << endl;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int inf = 0x3f3f3f3f;
int read() {
    int ret = 0; char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') {ret = ret * 10 + ch - '0'; ch = getchar();}
    return ret;
}

void write(int x) {
    if (x > 9) write(x / 10);
    putchar('0' + (x % 10));
}

const int N = 210;
int a[N];
char op[N];
int dp[N][N];
int dp2[N][N];

int main() {
    memset(dp, -0x3f, sizeof dp);
    memset(dp2, 0x3f, sizeof dp2);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> op[i];
        cin >> a[i];
        op[i + n] = op[i];
        a[i + n] = a[i];
        dp[i][i] = dp[i + n][i + n] = dp2[i][i] = dp2[i + n][i + n] = a[i];
    }

    int mx = -0x3f3f3f3f;
    int times = 0;
    for (int len = 2; len <= n; len++) {
        for (int L = 1; L + len - 1 <= 2 * n; L++) {
            int R = L + len - 1;
            for (int k = L; k < R; k++) {
                if (op[k + 1] == 't') {
                    dp[L][R] = max(dp[L][k] + dp[k + 1][R], dp[L][R]);
                    dp2[L][R] = min(dp2[L][k] + dp2[k + 1][R], dp2[L][R]);
                } else {
                    dp[L][R] = max(dp[L][k] * dp[k + 1][R], dp[L][R]);
                    dp[L][R] = max(dp2[L][k] * dp2[k + 1][R], dp[L][R]);
                    dp2[L][R] = min(dp2[L][k] * dp[k + 1][R], dp2[L][R]);
                    dp2[L][R] = min(dp[L][k] * dp2[k + 1][R], dp2[L][R]);
                    dp2[L][R] = min(dp2[L][k] * dp2[k + 1][R], dp2[L][R]);
                    times++;
                }
            }
        }
    }
    for (int st = 1; st <= n; st++) mx = max(dp[st][st + n - 1], mx);
    cout << mx << endl;
    for (int st = 1; st <= n; st++) if (dp[st][st + n - 1] == mx) cout << st << ' ';
}


活动打卡代码 AcWing 280. 陪审团

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <climits>
#include <cmath>
#include <cassert>
#include <vector>

#include <bits/stdc++.h>
#define fileio freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define dbg(x) cout << #x << " : " << x << endl;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int read() {
    int ret = 0; char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') {ret = ret * 10 + ch - '0'; ch = getchar();}
    return ret;
}

void write(int x) {
    if (x > 9) write(x / 10);
    putchar('0' + (x % 10));
}

const int N = 210;
int p[N], d[N];
int dp[21][810];
int base = 400;
bool choose[N][20][810];
int kase;
int ans1, ans2;

void print(int i, int m, int dif) {
    if (m == 0) return;
    if (choose[i][m][base + dif]) {
        print(i - 1, m - 1, dif - (d[i] - p[i]));
        cout << ' ' << i;
    } else {
        print(i - 1, m, dif);
    }
}

int main() {
    int n, m;
    while (cin >> n >> m, n || m) {
        for (int i = 1; i <= n; i++) {
            cin >> p[i] >> d[i];
        }
        // dp[j][k] max sum of pi and di when choose k people which difference is k.
        memset(dp, -0x3f, sizeof dp);
        dp[0][base + 0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= 1; j--) {
                for (int k = m * -20; k <= m * 20; k++) {
                    choose[i][j][base + k] = false;
                    if (k - (d[i] - p[i]) >= -20 * m && k - (d[i] - p[i]) <= 20 * m)
                        if (dp[j - 1][base + k - (d[i] - p[i])] + p[i] + d[i] > dp[j][base + k]) {
                            dp[j][base + k] = dp[j - 1][base + k - (d[i] - p[i])] + p[i] + d[i];
                            choose[i][j][base + k] = true;
                        }
                }
            }
        }
        ans1 = -100, ans2 = -100;
        for (int dif = 0; dif <= 20 * m; dif++) {
            if (dp[m][base + dif] >= 0) {
                ans1 = dif;
                ans2 = dp[m][base + dif];
            }
            if (dp[m][base - dif] >= 0) {
                if (dp[m][base - dif] > ans2) {
                    ans1 = -dif;
                    ans2 = dp[m][base - dif];
                }
            }
            if (ans1 != -100) break;
        }
        cout << "Jury #" << ++kase << endl;
        printf("Best jury has value %d for prosecution and value %d for defence:\n", (ans2 - ans1) / 2, (ans1 + ans2) / 2);
        print(n, m, ans1);
        puts("\n");
        //for (int i = n; i >= 1; i--) {
        //    if (choose[i][num][base + ans1]) {
        //        --num;
        //        cout << ' ' << i;
        //    }
        //}
    }
}



活动打卡代码 AcWing 282. 石子合并

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <climits>
#include <cmath>
#include <cassert>
#include <vector>

#define fileio freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define dbg(x) cout << #x << " : " << x << endl;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int read() {
    int ret = 0; char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') {ret = ret * 10 + ch - '0'; ch = getchar();}
    return ret;
}

void write(int x) {
    if (x > 9) write(x / 10);
    putchar('0' + (x % 10));
}

const int N = 310;
int a[N], pre[N];
int dp[N][N];
int n;

int main() {
    cin >> n;
    memset(dp, 0x3f, sizeof dp);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
        dp[i][i] = 0;
    }
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            for (int k = l; k < r; k++) {
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + pre[r] - pre[l - 1]);
            }
        }
    }
    cout << dp[1][n] << endl;
}