3.24考试总结

A 汽油补给

题面：51nod 1288
题解：贪心+单调栈
显然每个点加油加到能到右边第一个比这个点便宜的地方即可

#include<bits/stdc++.h>
using namespace std;
inline void read(int& x)
{
    x = 0; char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
}
#define maxn 100005
#define ll long long
int n, t, d[maxn], p[maxn], r[maxn];
ll s[maxn], ans;
stack<int> st;
int main()
{
    read(n), read(t);
    for (int i = 1; i <= n; ++i)
    {
        read(d[i]); read(p[i]);
        if (d[i] > t)
        {
            puts("-1");
            return 0;
        }
        s[i] = s[i - 1] + d[i];
    }
    s[n + 1] = s[n];
    for (int i = n; i; --i)
    {
        while (!st.empty() && p[st.top()] > p[i]) st.pop();
        r[i] = (st.empty()) ? n + 1 : st.top();
        st.push(i);
    }
    for (int las = 0, tp, i = 1; i <= n; ++i)//las是当前油量
    {
        tp = min(s[r[i] - 1] - s[i - 1], 1ll * t);//需要油量，和邮箱容量取个min.注意r[i]-1.
        if (tp > las)
        {
            ans += 1ll * (tp - las) * p[i];
            las = tp;
        }
        las -= d[i];
    }
    printf("%lldn", ans);
    return 0;
}

B 选址

题面：51nod 2558
题解：最短路+贪心
代码实现能力还是太弱了啊
以及吐槽一下这个题解，没有(LaTex)还一大段真的是看瞎眼

把原来的题解美化了一下
首先用(text{floyd})或者(text{dijskra})求出全源最短路
枚举每一条边((u,v,w))
对于所有点(题解中说是其他点，但这样样例都过不了），按照到(u)的距离从大到小排序
枚举(i)，表示一条路径：(a_{i}rightarrow u rightarrow v rightarrow max(a_{1}sim a_{i-1}))
其中那个(max)表示(v)到那些点的最长距离
这种情况下，最优解必然在路径中点处取得
实现的话后面那个(max)不用每次去扫，直接保存下来就好了（我居然没想到，搞得我还想这复杂度不对啊）
复杂度：(O(nmlog n))

正确性的证明：
Q：为什么对于(a_{i}sim a_{n})我们只要考虑从(u)到这些点？
A：假如经过(v)有一条更短的路，从中点到这些点的路径，一定没有中点到(a_{i})的路长
假如从中点先经过(u)再到(a_{1}sim a_{i-1})，这些路必定比中点到(a_{i})长，也就是之前已经被考虑过了
由于答案必定是某条路径的中点上，所以我们一定会考虑到这条路径，所以这个算法是正确的

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T& x)
{
    x = 0; char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
}
#define maxn 205
#define maxm 40005
int n, m, tp[maxn], a[maxm], b[maxm], w[maxm];
double dis[maxn][maxn], ans = 1e18, tmp;
inline void floyd()
{
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (dis[i][k] + dis[k][j] < dis[i][j])
                    dis[i][j] = dis[i][k] + dis[k][j];
}

int main()
{
    read(n), read(m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) dis[i][j] = 1e18;
    for (int i = 1; i <= n; ++i) dis[i][i] = 0;
    for (int i = 1; i <= m; ++i)
        read(a[i]), read(b[i]), read(w[i]), dis[a[i]][b[i]] = dis[b[i]][a[i]] = w[i];
    floyd();
    for (int i = 1, cnt; i <= m; ++i)
    {
        cnt = 0; tmp = 0;
        for (int j = 1; j <= n; ++j) tp[++cnt] = j;
        sort(tp + 1, tp + cnt + 1, [&](int x, int y) {return dis[a[i]][x] > dis[a[i]][y]; });
        for (int j = 1; j <= cnt; ++j)
        {
            if (tmp >= dis[a[i]][tp[j]] - w[i] && tmp <= dis[a[i]][tp[j]] + w[i]) 
                ans = min(ans, (dis[a[i]][tp[j]] + w[i] + tmp) / 2);//答案是这条路径长度的一半
            tmp = max(tmp, dis[tp[j]][b[i]]);
        }
    }
    printf("%lfn", ans);
    return 0;
}

C 格子染色

题意：51nod 2564(Bzoj 3218)
题解：网络流+主席树优化建图
由于这个题细节实在毒瘤，所以以下参考了各个题解
搜索关键词：Bzoj 3218，UOJ 97，51nod 2564

对于黑白点两个限制显然可以最小割，表示最小付出代价
也就是((S,i,b[i]),(i,T,w[i]))，割掉这条边表示选白色/黑色
如果你把黑白搞反了，那么下面的连边全都要反过来
对于"奇怪的方格"，要连((i,i',p[i]))，和所有满足条件的(j)连((i',j,inf))

这样就保证如果满足条件，(i)要么选白色，要么付出代价（割(p_i)边）

然后我们来考虑限制条件
对于(l_ile a_j le r[i])，上线段树即可
对(1le j<i)，需要上可持久化线段树

这张图意会一下即可，因为我这样连边相当于把这张图上的全部反过来
自上而下连inf，也就是((rt,ls/rs,inf))
叶子节点直接连对应的点，也就是((leaf_i,i,inf))
因为所有新建节点所代表的区间都是包括(i)点的
(root[i])的区间([l,r])表示(lle a_jle r)且(1le j<i)的点
对于每一个区间，从(root[i-1]rightarrow root[i])连(inf)
每次更新只会更新一条链，因为主席树是新建一份，所以要向上一个版本连边
我是没想出来怎么连p的限制，不过想出来估计也写不出来
不知道为什么一开始我代码莫名的比样例大1……
以及如果你一开始build(root[0],1,cnt)，常数*=2 别问我为什么
如果你没写那一行，代码中有几行要特判一下（主要就是不要连到编号0的点上去），标出来了

#include<bits/stdc++.h>
using namespace std;
inline void read(int& x)
{
    x = 0; char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
}
#define maxn 10005
#define maxm 400005
#define inf 0x3f3f3f3f
int n, a[maxn], b[maxn], w[maxn], l[maxn], r[maxn], p[maxn], ans;
int cnt, tp[maxn << 3];
namespace Graph
{
    struct Edge
    {
        int fr, to, val;
    }eg[maxm];
    int head[maxm], edgenum = 1;
    int cur[maxm], deep[maxm], vis[maxm], S, T, maxflow;
    inline void add(int fr, int to, int val)
    {
        eg[++edgenum] = { head[fr],to,val };
        head[fr] = edgenum;
    }
    inline void Add(int fr, int to, int val) { add(fr, to, val), add(to, fr, 0); }
    queue<int> q;
#define to eg[i].to
    bool bfs()
    {
        for (int i = 1; i <= T; ++i) deep[i] = inf, cur[i] = head[i];
        q.push(S), deep[S] = 0;
        while (!q.empty())
        {
            int tp = q.front(); q.pop();
            for (int i = head[tp]; i; i = eg[i].fr)
                if (deep[to] > deep[tp] + 1 && eg[i].val)
                {
                    deep[to] = deep[tp] + 1;
                    if (!vis[to]) vis[to] = 1, q.push(to);
                }
            vis[tp] = 0;
        }
        return deep[T] != inf;
    }
    int dfs(int rt, int flow)
    {
        if (rt == T)
        {
            maxflow += flow;
            return flow;
        }
        int tmpflow, used = 0;
        for (int& i = cur[rt]; i; i = eg[i].fr)
            if (deep[to] == deep[rt] + 1 && eg[i].val)
                if (tmpflow = dfs(to, min(flow - used, eg[i].val)))
                {
                    used += tmpflow;
                    eg[i].val -= tmpflow;
                    eg[i ^ 1].val += tmpflow;
                    if (used == flow) break;
                }
        return used;
    }
    inline void dinic() { while (bfs()) dfs(S, inf); }
#undef to
}
using namespace Graph;
namespace PresidentTree
{
    int root[maxn], ls[maxm], rs[maxm], tot;
    void build(int& rt, int l, int r)
    {
        rt = ++tot;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(ls[rt], l, mid), build(rs[rt], mid + 1, r);
    }
    void insert(int& rt, int las, int l, int r, int pos, int from)//from就是连边的起始点
    {
        rt = ++tot;
        if (l == r)
        {
            if (las) Add(2 * n + rt, 2 * n + las, inf);//!!!，连向前一个版本
            Add(2 * n + rt, from, inf);//叶子节点连对应点
            return;
        }
        ls[rt] = ls[las], rs[rt] = rs[las];
        int mid = (l + r) >> 1;
        if (pos <= mid) insert(ls[rt], ls[las], l, mid, pos, from);
        else insert(rs[rt], rs[las], mid + 1, r, pos, from);
        if(ls[rt]) Add(2 * n + rt, 2 * n + ls[rt], inf);//!!!
        if(rs[rt]) Add(2 * n + rt, 2 * n + rs[rt], inf);//!!!
    }
    void link(int rt, int l, int r, int fr, int to, int from)//连(i',j,inf)
    {
        if(!rt) return;//!!!
        if (fr <= l && to >= r)
        {
            Add(from, 2 * n + rt, inf);
            return;
        }
        int mid = (l + r) >> 1;
        if (fr <= mid) link(ls[rt], l, mid, fr, to, from);
        if (to > mid) link(rs[rt], mid + 1, r, fr, to, from);
    }
}
using namespace PresidentTree;
int main()
{
    read(n);
    for (int i = 1; i <= n; ++i)
    {
        read(a[i]), read(b[i]), read(w[i]), read(l[i]), read(r[i]), read(p[i]);
        tp[++cnt] = a[i], tp[++cnt] = l[i], tp[++cnt] = r[i];
        ans += b[i] + w[i];
    }
    sort(tp + 1, tp + cnt + 1);
    cnt = unique(tp + 1, tp + cnt + 1) - tp - 1;
    for (int i = 1; i <= n; ++i)
    {
        a[i] = lower_bound(tp + 1, tp + cnt + 1, a[i]) - tp;
        l[i] = lower_bound(tp + 1, tp + cnt + 1, l[i]) - tp;
        r[i] = lower_bound(tp + 1, tp + cnt + 1, r[i]) - tp;//先离散化
    }
    //build(root[0], 1, cnt);
    for (int i = 1; i <= n; ++i)
    {
        link(root[i - 1], 1, cnt, l[i], r[i], i + n);
        insert(root[i], root[i - 1], 1, cnt, a[i], i);
    }
    S = 2 * n + tot + 1, T = S + 1;
    for (int i = 1; i <= n; ++i)
        Add(S, i, b[i]), Add(i, T, w[i]), Add(i, i + n, p[i]);
    dinic();
    printf("%dn", ans - maxflow);
    return 0;
}