混迹讨论区

帮人改了一道题

P3017 [USACO11MAR] Brownie Slicing G

题意可转化为求蛋糕最小值的最大值，容易想到二分。

原以为是二分套 dp 的，不过写的时候发现直接贪心双指针即可。

// O(n^2 log V)

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn=600;
int r, c, a, b;
int n[maxn][maxn];
int pre[maxn][maxn];
bool f[maxn][maxn];  // 前 i 行被分成 j 块能否满足要求 

inline int sum_rect(int x0, int x1, int y0, int y1){
    return pre[x1][y1] + pre[x0-1][y0-1] - pre[x1][y0-1] - pre[x0-1][y1];
}

inline bool isok(int i, int j, int m){
    // 第 i-j 行能否满足要求 
    int L=1, R=1, part=0;
    while (R <= c){
//      printf("\t\t%d %d\n", L, R);
        if (sum_rect(i, j, L, R) >= m){
            part++;
            L = R+1;
        }
        R++;
    }
    return part >= b;
}

inline bool check(int m){
    memset(f, 0, sizeof f);
    
    int H=1, L=1, parts=0;
    
    while (L <= r){
//      printf("\t%d %d\n", H, L);
        if (isok(H, L, m)){
            parts++;
            H = L+1;
        }
        L++;
    }
    
    return parts >= a;
}

signed main(){
//  freopen("in.txt", "r", stdin);
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> r >> c >> a >> b;
    
    int S = 0;
    for (int i=1; i<=r; i++){
        for (int j=1; j<=c; j++){
            cin >> n[i][j];
            pre[i][j] = n[i][j] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];
            S += n[i][j];
        }
    }
    
    int L=1, R=S/(a*b);
    
    while (L+1 < R){
//      printf("%d %d\n", L, R);
        int mid = (L+R)>>1;
        if (check(mid)){
            L = mid;
        } else {
            R = mid-1;
        }
    }
    
    if (check(R)){
        cout << R;
    } else {
        cout << L;
    }
        
    return 0;
}

P3018 [USACO11MAR] Tree Decoration G

另一道以为是 dp 的贪心，但不难发现各个结点的要求都是硬性的。在保证各个子树满足要求之后，贪心地选代价最小的点满足要求即可。

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn=1e5+10;
vector<int> G[maxn]; 
int p[maxn], c[maxn], t[maxn];
int m[maxn], s[maxn];
int ans;

void dfs(int u){
    if (G[u].empty()){
        s[u] = c[u];
        m[u] = t[u];
        ans += c[u] * t[u];
        return;
    }
    
    m[u] = t[u];
    for (int v: G[u]){
        dfs(v);
        s[u] += s[v];
        m[u] = min(m[u], m[v]);
    }
    
    if (s[u] < c[u]){
        ans += m[u] * (c[u] - s[u]);
        s[u] = c[u];
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;
    
    for (int i=1; i<=n; i++){
        cin >> p[i] >> c[i] >> t[i];
        if (i != 1){
            G[p[i]].push_back(i);
        }
    }
    
    dfs(1);
    
    cout << ans;
    
    return 0;
}

P3019 [USACO11MAR] Meeting Place S

主要考察打字速度。由于快把树剖忘了，浅打了一下。

另外还有一种更快的离线算法，但是我不会。

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn=1100;
int p[maxn];
vector<int> G[maxn];

int siz[maxn], wson[maxn], dep[maxn];
void dfs1(int u){
    dep[u] = dep[p[u]] + 1;
    siz[u] = 1;
    
    for (int v: G[u]){
        dfs1(v);
        siz[u] += siz[v];
        if (siz[v] > siz[wson[u]]){
            wson[u] = v;
        }
    }
}

int top[maxn] /*, dfn[maxn]*/;
void dfs2(int u, int tp){
    top[u] = tp;
    
    if (wson[u]){
        dfs2(wson[u], tp);
    }
    
    for (int v: G[u]){
        if (v == wson[u]){
            continue;
        }
        dfs2(v, v);
    }
}

inline int lca(int a, int b){
    while (top[a] != top[b]){
        if (dep[top[a]] > dep[top[b]]){
            a = p[top[a]];
        } else {
            b = p[top[b]];
        }
    }
    
    return (dep[a] > dep[b])? b: a;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    for (int i=2; i<=n; i++){
        cin >> p[i];
        G[p[i]].push_back(i); 
    }
    
    dfs1(1);
    dfs2(1, 1);
    
    while (m--){
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << '\n';
    }
    
    return 0;
}

P3020 [USACO11MAR] Package Delivery S

最短路板子。2011 年的 USACO 银组这么水的吗？

但是对于打 SPFA 打惯的先天 Dijkstra 打错圣体还是太难了。

P3021 [USACO11MAR] Bovine Bridge Battle S

统计平行四边形。注意到对角顶点向量和相等，用类似 A+B Problem 的技法开个桶，即可变成简单的组合数。