头像

莫能与之争

四川农业大学




离线:20小时前


最近来访(4)
用户头像
RyanMoriarty
用户头像
_Crush
用户头像
zysmmer
用户头像
十六夜咲夜


请问一下为什么EK算法寻找增广路时,不用DFS,而用BFS呢



活动打卡代码 AcWing 117. 占卜DIY

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

deque<int> cards[14];

int val(char ch) {
    if (ch >= '0' && ch <= '9') return ch - '0' == 0 ? 10 : ch - '0';
    if (ch == 'J') return 11;
    if (ch == 'Q') return 12;
    if (ch == 'K') return 13;
    return 1;
}

int ans, K, id, cur;
int cnt[14];

int main() {
    for (int i = 1; i <= 13; i++) {
        char ch;
        for (int j = 0; j < 4; j++) {
            cin >> ch;
            cards[i].push_back(val(ch));
        }
    }
    K = 4, id = 13, cur = -1;
    while (K) {
        if (id == 13) cur = cards[id].front(), cards[id].pop_front();
        else cur = cards[id].back(), cards[id].pop_back();
        if (cur == 13) --K;
        ++cnt[cur];
        id = cur;
    }
    for (int i = 1; i < 13; i++) if (cnt[i] == 4) ++ans;
    cout << ans << endl;
}


活动打卡代码 AcWing 327. 玉米田

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 13, mod = 1e8;
int n, m;
int S[N];
ll dp[N][1 << N];

void add(ll &x, ll y) {
    x += y; if (x >= mod) x -= mod;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1, x; j <= m; j++) {
            cin >> x; S[i] = (S[i] << 1) | x;
        }
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0, f = 1; j < (1 << N); j++, f = 1) {
            for (int q = 0; q < N; q++) if (((j >> q) & 1) > ((S[i] >> q) & 1)) f = 0;
            if (j & (j << 1)) f = 0;
            if (!f) continue;
            for (int k = 0; k < (1 << N); k++) {
                if ((j & k) == 0) add(dp[i][j], dp[i - 1][k]);
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < (1 << N); i++) add(ans, dp[n][i]);
    cout << ans << endl;
}


活动打卡代码 AcWing 339. 圆形数字

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1010;
string L, R;
int s;
int n, d;
int base = 32;
ll dp[32][64][2][2];

ll dfs(int cur, int cnt, int g, int limit) {
    if (cur == -1) return cnt >= base;
    ll &ans = dp[cur][cnt][g][limit];
    if (ans != -1) return ans;
    ans = 0;
    int f = limit ? (s >> cur) & 1 : 1;
    for (int i = 0; i <= f; i++) {
        if (i == 0) {
            ans += dfs(cur - 1,   ((cur == 0 || !g) ? cnt + 1 : cnt), g && i == 0, limit && i == f);
        } else {
            ans += dfs(cur - 1, cnt - 1, 0, limit && i == f);
        }
    }
    return ans;
}

int chk(const string& num) {
    int res = 0, n = atoi(num.c_str());
    while (n) {
        (n & 1) == 0 ? ++res : --res;
        n >>= 1;
    }
    return res >= 0;
}
ll solve(string num) {
    memset(dp, -1, sizeof dp);
    n = 0;
    s = atoi(num.c_str());
    for (int ss = s; ss; ss >>= 1) ++n;
    return dfs(n - 1, base, 1, 1);
}

int main() {
    while (cin >> L >> R) {
        cout << solve(R) - solve(L) + chk(L) << "\n";
    }
}


活动打卡代码 AcWing 338. 计数问题

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1010;
string L, R, S;
int n, d;
ll dp[10][10][2][2];

ll dfs(int cur, int cnt, int g, int limit) {
    if (cur == n) return cnt;
    ll &ans = dp[cur][cnt][g][limit];
    if (ans != -1) return ans;
    ans = 0;
    int f = limit ? S[cur] - '0' : 9;
    for (int i = 0; i <= f; i++) {
        ans += dfs(cur + 1, cnt + (i == d ? (d != 0 || (!g || cur == n - 1)) : 0), g && i == 0, limit && i == f);
    }
    return ans;
}
int chk(const string& num, int x) {
    int res = 0;
    for (char ch : num) if (ch - '0' == x) ++res;
    return res;
}
ll solve(string num, int x) {
    memset(dp, -1, sizeof dp);
    S = num; d = x;
    n = S.length();
    return dfs(0, 0, 1, 1);
}

int main() {
    while (cin >> L >> R, L != "0" || R != "0") {
        if (atoi(L.c_str()) > atoi(R.c_str())) swap(L, R);
        for (int i = 0; i < 10; i++) cout << abs(solve(R, i) - solve(L, i)) + chk(L, i) << " \n"[i == 9];
    }
}


活动打卡代码 AcWing 333. 最大子矩阵

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1010;

char mat[N][N];
int mp[N][N], H[N][N], L[N][N], R[N][N];

int chk(char a, char b) {
    return a == b || (a == 'w' && (b == 'a' || b == 'b')) ||
            (a == 'x' && (b == 'b' || b == 'c')) ||
            (a == 'y' && (b == 'a' || b == 'c')) ||
            (a == 'z' && (b == 'a' || b == 'b' || b == 'c'));
}
int n, m, out, ans;

int main() {
    while (cin >> n >> m) {
        out = ans = 0;
        for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> mat[i][j];
        for (char ch = 'a'; ch <= 'c'; ch++) {
            memset(H, 0, sizeof H);
            memset(L, 0, sizeof L);
            memset(R, 0, sizeof R);
            for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) mp[i][j] = chk(mat[i][j], ch);
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) if (mp[i][j]) {
                        H[i][j] = H[i - 1][j] + 1; L[i][j] = R[i][j] = j;
                    }
                for (int j = 1; j <= m; j++) if (mp[i][j] && mp[i][j - 1]) L[i][j] = L[i][j - 1];
                for (int j = m; j >= 1; j--) if (mp[i][j] && mp[i][j + 1]) R[i][j] = R[i][j + 1];
                for (int j = 1; j <= m; j++) {
                    if (mp[i][j] && mp[i - 1][j]) {
                        L[i][j] = max(L[i - 1][j], L[i][j]);
                        R[i][j] = min(R[i - 1][j], R[i][j]);
                    }
                    ans = max(H[i][j] * (R[i][j] - L[i][j] + 1), ans);
                }
            }
            out = max(ans, out);
        }
        cout << out << endl;
    }
}


活动打卡代码 AcWing 332. 股票交易

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 2010;
int n, limit, gap;
ll in[N], out[N], inMax[N], outMax[N], last[N], dp[N][N];
deque<int> iq, oq;
//状态dp[i][j]:现在是第i天,手里有j份股票,最大收益
//转移

//出股票
//dp[i][j] = dp[k][l] + (l - j) * out[i] 决策 k < i - w
//观察到决策是单调增加的,因此直接每次决策取值范围的上界(i - w)变化时,直接更新last[j]所记录的有j只股票时的最优决策k
//last[j] = max{dp[k][j]};
//dp[i][j] = max{last[k] + (k - j) * out[i]} 决策j < k <= j + outMax[i]
//决策k的上下界只与j有关,可用单调队列优化
//分离变量 dp[i][j] = -j * out[i] + max{last[k] + k * out[i]}

//入股票
//dp[i][j] = max{last[k] + (k - j) * in[i]} 决策j - inMax[i] <= k < j
//分离变量 dp[i][j] = -j * in[i] + max{last[k] + k * in[i]}

ll calc(int k, ll i) {
    return last[k] + k * i;
}

int main() {
    cin >> n >> limit >> gap;
    for (int i = 1; i <= n; i++) cin >> in[i] >> out[i] >> inMax[i] >> outMax[i];
    memset(dp, 0xcf, sizeof dp);
    memset(last, 0xcf, sizeof last);
    dp[0][0] = 0; last[0] = 0;
    for (int i = 1; i <= n; i++) {
        iq.clear(); oq.clear();
        if (i - gap - 1 >= 0)
            for (int j = 0; j <= limit; j++) last[j] = max(dp[i - gap - 1][j], last[j]);
        for (int j = 0; j <= limit; j++) dp[i][j] = dp[i - 1][j];
        for (int j = 0; j <= limit; j++) {
            while (!iq.empty() && j - inMax[i] > iq.front()) iq.pop_front();
            if (!iq.empty()) dp[i][j] = max(-j * in[i] + calc(iq.front(), in[i]), dp[i][j]);
            while (!iq.empty() && calc(j, in[i]) >= calc(iq.back(), in[i])) iq.pop_back();
            iq.push_back(j);
        }
        for (int j = limit; j >= 0; j--) {
            while (!oq.empty() && oq.front() > j + outMax[i]) oq.pop_front();
            if (!oq.empty()) dp[i][j] = max(-j * out[i] + calc(oq.front(), out[i]), dp[i][j]);
            while (!oq.empty() && calc(j, out[i]) >= calc(oq.back(), out[i])) oq.pop_back();
            oq.push_back(j);
        }
    }
    ll ans = 0;
    for (int j = 0; j <= limit; j++) ans = max(dp[n][j], ans);
    cout << ans << endl;
}


活动打卡代码 AcWing 330. 估算

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 2010;
ll a[N], cost[N][N], dp[N][26];
int n, k;

int main() {
    while (scanf("%d%d", &n, &k), n || k) {
        for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        for (int l = 1; l <= n; l++) {
            priority_queue<ll> mxq;
            priority_queue<ll, vector<ll>, greater<ll>> mnq;
            ll mns = 0, mxs = 0;
            mnq.push(a[l]); mns += a[l];
            for (int r = l + 1; r <= n; r++) {
                if (a[r] < mnq.top()) mxq.push(a[r]), mxs += a[r];
                else mnq.push(a[r]), mns += a[r];
                while (mnq.size() > mxq.size() + 1) {
                    int tp = mnq.top(); mnq.pop();
                    mxq.push(tp);
                    mxs += tp; mns -= tp;
                }
                while (mxq.size() > mnq.size() + 1) {
                    int tp = mxq.top(); mxq.pop();
                    mnq.push(tp);
                    mxs -= tp; mns += tp;
                }
                ll med = mnq.size() > mxq.size() ? mnq.top() : mxq.top();
                ll x = mnq.size(), y = mxq.size();
                cost[l][r] = mns - x * med + y * med - mxs;
            }
        }
        memset(dp, 0x3f, sizeof dp);
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int g = 1; g <= k; g++) {
                for (int last = 0; last < i; last++) {
                    dp[i][g] = min(dp[last][g - 1] + cost[last + 1][i], dp[i][g]);
                }
            }
        }
        printf("%lld\n", dp[n][k]);
    }
}


活动打卡代码 AcWing 331. 干草堆

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1e5 + 7;
int a[N], dp[N], last[N], sum[N], q[N];
int n, l, r;

ll calc(int i) {
    return last[i] + sum[i];
}

int main() {
    cin >> n;
    for (int i = n; i >= 1; i--) cin >> a[i];
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
    // 转移方程:f[i] = f[j] + 1 ;
    // 决策取值范围:sum[i] - sum[j] >= last[j] ==> sum[i] >= last[j] + sum[j];
    q[r++] = 0;
    for (int i = 1; i <= n; i++) {
        while (l < r - 1 && calc(q[l + 1]) <= sum[i]) l++;
        dp[i] = dp[q[l]] + 1;
        last[i] = sum[i] - sum[q[l]];
        while (l < r && calc(i) <= calc(q[r - 1])) r--;
        q[r++] = i;
    }
    cout << dp[n] << endl;
}



#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct sgt {
#define lson (id << 1)
#define rson (id << 1 | 1)
#define mid (st[id].l + st[id].r >> 1)
    static const int N = 2e5 + 7;
    int index;
    struct node {
        int l, r, lz;
        ll sum;
    }st[N << 2];
    void pushnow(int id, int v) {
        st[id].sum = v;
        st[id].lz = 1;
    }
    void pushup(int id) {
//        st[id].sum = st[lson].sum + st[rson].sum;
    }
    void pushdown(int id) {
        if (st[id].lz) {
            pushnow(lson, st[id].sum); pushnow(rson, st[id].sum);
            st[id].lz = 0;
        }
    }
    void build(int id, int l, int r) {
        st[id].l = l; st[id].r = r;
        if (l == r) {
            return;
        }
        build(lson, l, mid); build(rson, mid + 1, r); pushup(id);
    }
    void update(int id, int l, int r, int v) {
        if (st[id].l > r || st[id].r < l) return;
        if (st[id].l >= l && st[id].r <= r) {
            pushnow(id, v);
            return;
        }
        pushdown(id);
        update(lson, l, r, v); update(rson, l, r, v);
        pushup(id);
    }
    ll query(int id, int l, int r) {
        if (st[id].l > r || st[id].r < l) return 0;
        if (st[id].l >= l && st[id].r <= r) {
            return st[id].sum;
        }
        pushdown(id);
        if (l <= mid) return query(lson, l, r);
        else return query(rson, l, r);
    }
}st;

const int N = 3e4 + 7, M = 1e5 + 7;

int n, s;
int l[N], r[N];
ll dp[N][2];

int main() {
    st.build(1, 1, M << 1);
    cin >> n >> s;
    s += M; l[0] = r[0] = M;
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
        l[i] += M; r[i] += M;
        int li = st.query(1, l[i], l[i]), ri = st.query(1, r[i], r[i]);
        st.update(1, l[i], r[i], i);
        dp[i][0] = min(dp[li][0] + abs(l[i] - l[li]), dp[li][1] + abs(l[i] - r[li]));
        dp[i][1] = min(dp[ri][0] + abs(r[i] - l[ri]), dp[ri][1] + abs(r[i] - r[ri]));
    }
    cout << min(dp[n][0] + abs(l[n] - s), dp[n][1] + abs(r[n] - s)) << endl;
}