杭电多校2补题记录

1012: String Distance (HDU 6774)

比赛的时候没注意到$m\le 20$，想了半天没想出来怎么做。

AC代码：

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 1000;

char A[maxn], B[30];
int lena, lenb;
int nxt[maxn][27];
int dp[30][30] = {0};

void solve(){
    cin >> (A + 1) >> (B + 1);
    lena = strlen(A + 1);
    lenb = strlen(B + 1);

    int tmp[27];
    fill(tmp, tmp + 27, inf);
    for(int i=lena; i>=0; i--){
        for(int j=0; j<26; j++) nxt[i][j] = tmp[j];
        if(i > 0) tmp[A[i] - 'a'] = i;
    }

    int q, l, r;
    cin >> q;
    for(int i=0; i<q; i++){
        cin >> l >> r;
        dp[0][0] = l - 1;
        for(int j=1; j<=lenb; j++) dp[0][j] = inf;

        for(int j=1; j<=lenb; j++){
            for(int k=0; k<=lenb; k++) dp[j][k] = dp[j-1][k];
            for(int k=1; k<=lenb; k++){
                if(dp[j-1][k-1] < r && nxt[dp[j-1][k-1]][B[j]-'a'] <= r){
                    dp[j][k] = min(dp[j][k], nxt[dp[j-1][k-1]][B[j]-'a']);
                }
            }
        }

        int lcs = 0;
        for(int j=lenb; j>=0; j--){
            if(dp[lenb][j] < inf){
                lcs = j;
                break;
            }
        }
        cout << (r - l + 1) + lenb - 2 * lcs << '\n';
    }
}

signed main(){
    Android;
    int t; cin >> t;
    while(t--) solve();
}

1005: New Equipments (HDU 6767)

想了半天要怎么递归搜索，结果题解用的是网络流。

AC代码：

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const int maxn = 1e5 + 1000;

struct Dinic{
	// 最小费用最大流板子
} max_flow_min_cost;

ll n, m;
ll a[maxn], b[maxn], c[maxn];

void solve(){
    cin >> n >> m;
    for(int i=0; i<n; i++) cin >> a[i] >> b[i] >> c[i];

    ll src = n * n + 2, intern = n * n + 3, dest = n * n + 4;

    for(int k=1; k<=n; k++){
        max_flow_min_cost.init(2 + n * n + 10);
        map<int, int> machine;
        int m_cnt = 0;

        max_flow_min_cost.add_edge(src, intern, k, 0);
        for(int i=0; i<n; i++){
            int opt = max(1ll, min(m, (ll)(-b[i] / (2. * a[i]) + 0.5)));
            int l = max(1ll, min(m - n, opt - (n + 1) / 2));
            int r = l + n;
            max_flow_min_cost.add_edge(intern, i + 1, 1, 0);
            for(int j=l; j<r; j++){
                if(machine.count(j) == 0) machine[j] = ++m_cnt + n;
                max_flow_min_cost.add_edge(i + 1, machine[j], 1, 
                    a[i] * j * j + b[i] * j + c[i]);
            }
        }

        for(pii p: machine){
            max_flow_min_cost.add_edge(p.second, dest, 1, 0);
        }

        cout << max_flow_min_cost.dinic(src, dest).second << (k==n?'\n':' ');
    }
}

signed main(){
    Android;
    int t; cin >> t;
    while(t--) solve();
}

1007: In Search of Gold (HDU 6769)

以下代码，开$O(1/2)$ 优化跑该题的数据会Segmentation fault，关掉优化就没事了，很迷！

使用的编译器为: tdm64-1 9.2.0

AC代码（开$O(1/2)$的情况下，在我的电脑上无法AC）

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 2e4 + 1000;

int testcase;

int n, k;

int head[maxn], nxt[maxn * 2], dest[maxn * 2];
ll a[maxn * 2], b[maxn * 2];
int edge_cnt;

void add_edge(int u, int v, int x, int y){
    nxt[edge_cnt] = head[u];
    dest[edge_cnt] = v;
    a[edge_cnt] = x, b[edge_cnt] = y;
    head[u] = edge_cnt++;
}

ll dp[maxn][30];
ll tmp[40];
int sz[maxn];

void check(int rt, int fa, ll mid){
    sz[rt] = 1;

    dp[rt][0] = 0;
    for(int i=1; i<=k; i++) dp[rt][i] = mid + 1;

    for(int e=head[rt]; ~e; e=nxt[e]){
        int v = dest[e];
        if(v == fa) continue;
        check(v, rt, mid);

        for(int i=0; i<=k; i++) tmp[i] = mid + 1;
        for(int i=0; i<=min(sz[rt], k); i++) {
            for(int j=0; j<=min(sz[v], k) && j + i <= k; j++){
                if(dp[rt][i] + dp[v][j] + b[e] <= mid) tmp[i+j] = min(tmp[i+j], max(dp[rt][i], dp[v][j]+b[e]));
                if(dp[rt][i] + dp[v][j] + a[e] <= mid) tmp[i+j+1] = min(tmp[i+j+1], max(dp[rt][i], dp[v][j]+a[e]));
            }
        }

        sz[rt] += sz[v];
        for(int i=0; i<=min(sz[rt], k); i++) dp[rt][i] = tmp[i];
    }
}

void solve(){
    cin >> n >> k;
    
    ll l = 0, r = 0, mid, ans;
    edge_cnt = 0;
    for(int i=0; i<=n; i++) head[i] = -1;

    for(int i=1; i<n; i++){
        int u, v, x, y;
        cin >> u >> v >> x >> y;
        r += max(x, y);
        add_edge(u, v, x, y);
        add_edge(v, u, x, y);
    }
    while(l <= r){
        mid = (l + r) >> 1;
        check(1, 0, mid);
        if(dp[1][k] <= mid){
            r = mid - 1;
            ans = mid;
        }else{
            l = mid + 1;
        }
    }
    cout << ans << '\n';
}

signed main(){
    Android;
    int t; cin >> t;
    for(int i=1; i<=t; i++){
        testcase = i;
        solve();
    }
}

1011: King of Hot Pot (HDU 6773)