USACO23DEC AU题解

Flight Routes G

既然所有单向边 $(u,v)$ 都满足 $u<v$，从原图取出点集 $[x,n]$ 就一定满足给定三角形 $[x,n-1]$ 行的限制。于是可以反过来递推，当前考虑到第 $x-1$ 行，顺次从 $x$ 到 $n$ 检查是否需要连接 $(x-1,i)$ 即可。

#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 750 + 10;
bitset<maxn> v[maxn];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i=1;i<n;++i)
    {
        string s;
        cin >> s;
        for (int j=i+1;j<=n;++j)
            if (s[j-i-1] == '1')
                v[i][j] = 1;
    }
    int ans = 0;
    for (int i=n-1;i>=1;--i)
    {
        auto b = v[i];
        for (int x; (x=b._Find_first())<b.size();)
        {
            b.flip(x);
            b ^= v[x];
            ++ans;
        }
    }
    cout << ans << endl;
    return 0;
}

Minimum Longest Trip G

DAG 最长路是容易的，考虑归纳地求出字典序排名和答案。先按照最长路长度将点分层，并只保留连接相邻层的边。按从小到大处理每个层级，最小层级没有出边，显然字典序排名相同。接下来考虑推导出下一层。具体的，对于 $u$，枚举出边 $(u,v)$，按照边权为第一关键字，$v$ 在上一层的排名为第二关键字排序，即可得到 $u$ 的最佳转移。再将同一层级所有的转移类似地排序，便得到当前层的排名。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int maxn = 200000 + 10;
constexpr int maxm = 400000 + 10;
struct edge
{
    int v, w, nxt;
} e[maxm << 1];
int h[maxn], cnt;
void addedge(int u, int v, int w)
{
    e[++cnt].nxt = h[u];
    e[h[u]=cnt].v = v;
    e[cnt].w = w;
}
int dep[maxn];
void dfs(int u)
{
    for (int i=h[u];i;i=e[i].nxt)
    {
        int v = e[i].v;
        if (!dep[v]) dfs(v);
        dep[u] = max(dep[u], dep[v]);
    }
    ++dep[u];
}
int rk[maxn];
i64 ans[maxn];
int tot;
vector<int> c[maxn];
struct ppi
{
    int x, y, z;
    inline ppi(int a=0, int b=0, int c=0) : x(a), y(b), z(c) {}
} sa[maxn];
struct cmp
{
    inline bool operator()(const ppi& a, const ppi& b) const
    {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    }
};
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i=1;i<=m;++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        addedge(u, v, w);
    }
    for (int i=1;i<=n;++i)
        if (!dep[i]) dfs(i);
    for (int i=1;i<=n;++i)
        c[dep[i]].emplace_back(i);
    for (int t=2;t<=n&&c[t].size();++t)
    {
        int top = 0;
        for (int u : c[t])
        {
            int mn = 0, to = 0;
            for (int i=h[u];i;i=e[i].nxt)
            {
                int v = e[i].v;
                if (dep[v] != dep[u] - 1) continue;
                if (!to || mn > e[i].w || (mn == e[i].w && rk[v] < rk[to]))
                {
                    to = v;
                    mn = e[i].w;
                }
            }
            ans[u] = mn + ans[to];
            sa[++top] = (ppi(mn, rk[to], u));
        }
        sort(sa+1, sa+top+1, cmp());
        for (int i=1;i<=top;++i) rk[sa[i].z] = ++tot;
    }
    for (int i=1;i<=n;++i)
        cout << dep[i] - 1 << ' ' << ans[i] << '\n';
    return 0;
}

Haybale Distribution G

$f_x$ 表示将所有干草集中到 $x$ 的花费，对于任意的 $a,b$，$f$ 都是单谷的。

$f$ 显然有最小值，假设在 $x$ 点取到最小值 $f_x$，设位置不在 $x$ 之前的点有 $k$ 个，则 $kb-(n-k)a=f_{x-1}-f_x\ge 0$，即 $k(a+b)-na\ge 0$，而 $k$ 随着 $x$ 左移不会减小，所以差也不会减小，右半边同理。故得证。

简单三分即可。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int maxn = 200000 + 10;
constexpr int maxm = 1000000 + 10;
i64 a[maxm], b[maxm];
int n;
i64 p, q;
i64 check(int x)
{
    return q * ((a[maxm - 1] - a[x]) - x * (n - b[x])) + p * (x * b[x - 1] - a[x - 1]);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i=1;i<=n;++i)
    {
        int x;
        cin >> x;
        ++x;
        a[x] += x;
        ++b[x];
    }
    for (int i=1;i<maxm;++i) a[i] += a[i - 1], b[i] += b[i - 1];
    int m;
    cin >> m;
    while (m--)
    {
        cin >> p >> q;
        int L = 1, R = maxm - 1;
        while (R - L > 1)
        {
            int M0 = L + (R - L + 1) / 3, M1 = R - (R - L + 1) / 3;
            if (check(M0) <= check(M1)) R = M1;
            else L = M0;
        }
        cout << min(check(L), check(R)) << endl;
    }
    return 0;
}