In mathematics you don't understand things, you just get used to them.

分类 笔记 下的文章

link。

理一下逻辑,主要讲一下我做题时的疑惑和其它题解没提到的细节。

首先容易看到,一个必然不劣的贪心策略是把尽量靠近根的层铺成同样的字符。也许会有疑惑,字符串是否本质不同的判定每个位置地位相等。然而在这题里面字符串个数的贡献是和结点所为根的子树大小有关的,所以这个贪心不劣。

设树的最大深度为 $d$,那么如果我们能实现每层都铺成同样的字符,答案就是不同长度的字符串个数,也就是 $d$。

考虑构造出答案为 $d+1$ 的情况,这时候贪心就跑不出来了,具体情况是,会出现一层既有 a 又有 b,其他层都是 pure a 或 pure b

主要问题就在于 miscellaneous level 放在哪里,才能让答案最小。直觉地,我们认为把它放在尽量低(离根更远)的 level 会更优。但是其实贡献结束的地方是叶子,所以其实我们应该把它放在叶子尽量多的 level。这个时候答案为 $d+1$。

根据以上的推理,我们得出一个论断:最优答案在 $d$ 和 $d+1$ 出现。剩下的问题就是如果判断是前者还是后者。

其实这是一个简单可达性 dp 可以解决的问题,将每一个 level 压成一个 item,其体积为当层的结点个数。但是这个是 $O(n^2)$ 的,要考虑优化。有两种解决的道路,分析后可以发现一个根号规模的结论,或者用 std::bitset 优化 dp。

注意 std::bitset 优化 dp 后状态略有不同……

#include<bits/stdc++.h>
#define cmin(x, y) x = std::min(x, y)
#define cmax(x, y) x = std::max(x, y)
#define fors(i, l, r, ...) for(int i = (l), REP##i = (r), ##__VA_ARGS__; i <= REP##i; ++i)
#define dfors(i, r, l, ...) for(int i = (r), REP##i = (l), ##__VA_ARGS__; i >= REP##i; --i)
// observation: amount different answers would be 2: maximum depth, or, it plus 1
int n, _x, dep[100100], nod[100100], leaf[100100], len, vol[100100];
// params: @nod[i]: amout of nodes at level i; @leaf[i]: amout of leaves at lv i;
//     #vol[i]: volume of i-th item
std::bitset<100100> f[2100]; // if can assign it to j perfectly within lefmost i items
std::vector<int> adj[100100], zip[100100];
void pre_dfs(const int x) {
    nod[dep[x]]++,leaf[dep[x]] += adj[x].empty();
    for(const int y : adj[x]) dep[y] = dep[x]+1,pre_dfs(y);
}
int pre_zip() {
    static int vis[100100], tot;
    fors(i, 1, len) {
        if(!vis[nod[i]]) vol[vis[nod[i]] = ++tot] = nod[i];
        zip[vis[nod[i]]].emplace_back(i);
    }
    return tot; // amount of items
}
signed main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cin >> n >> _x;
    fors(i, 1, n-1, f) std::cin >> f,adj[f].emplace_back(i+1);
    pre_dfs(dep[1] = 1),len = *std::max_element(dep+1, dep+n+1); // processing basic information
    int m = pre_zip(); // compressing levels with same amout of nodes
    fors(i, f[0][0] = 1, m, tmp) {
        f[i] = f[i-1],tmp = zip[i].size();
        for(int j = 1; j <= tmp; j *= 2) tmp -= j,f[i] |= (f[i]<<(vol[i]*j));
        if(tmp > 0) f[i] |= (f[i]<<(vol[i]*tmp));
    }
    std::vector<bool> k(len);
    std::function<void(int, int)> find_path = [&](const int rem, int t) { // reviving way we DP through
        if(rem == 0) return;
        for(const int x : zip[rem]) {
            if(vol[rem] > t || f[rem-1][t]) break;
            t -= vol[rem],k[x-1] = 1;
        }
        find_path(rem-1, t);
    };
    if(f[m][_x]) { // when greedy strategy runs well
        std::cout << len << "\n";
        find_path(m, _x);
        fors(i, 1, n) std::cout << (k[dep[i]-1]?'a':'b');
        return std::cout << "\n", 0;
    }
    std::cout << len+1 << "\n"; // otherwise the answer would be maximum depth plus 1
    int tmp = std::numeric_limits<int>::max(), tmp1 = -1;
    dfors(i, _x, 0) if(f[m][i]) {
        tmp = i; break;
    }
    find_path(m, tmp);
    fors(i, 1, len) if(!k[i-1] && leaf[i] >= _x-tmp) {
        tmp1 = i; break;
    }
    fors(i, 1, n) {
        if(dep[i] == tmp1 && adj[i].empty()) std::cout << (tmp == _x?'b':(++tmp, 'a'));
        else std::cout << (k[dep[i]-1]?'a':'b');
    }
    return std::cout << "\n", 0;
}

link。

朴素 dp 大约就是 $f_x=f_y+v_x\times(d_x-d_y)+s_x$,$y$ 是 $x$ 的祖先。这个式子可以斜率优化,在以 $d_y$ 为横坐标,$f_y$ 为纵坐标的坐标系中,斜率为 $v_x$。

我们应该用单调栈维护一个到根的树链。由于回溯的时候 $v_x$ 不一定单调,取 $f_x$ 的 dp 值时我们应该在完整的凸壳上二分。

插入决策点时,按照普通序列上的斜率优化弹栈(朴素)。很多人的问题是回溯还原栈状态的复杂度,其实你真正修改的值只有插入进去的位置,如果你没有使用 STL 的话弹栈的操作实际上是没有进行的,他们保留在栈中,只需要将栈顶指针还原即可,每次回溯的个数是 $O(1)$ 级别的。

实际插入决策点时,因为时间复杂度的问题需要二分插入位置。如果你以乘代除,注意开 __int128

#include<bits/stdc++.h>
#define cmin(x, y) x = std::min(x, y)
#define cmax(x, y) x = std::max(x, y)
#define fors(i, l, r, ...) for(int i = (l), REP##i = (r), ##__VA_ARGS__; i <= REP##i; ++i)
#define dfors(i, r, l, ...) for(int i = (r), REP##i = (l), ##__VA_ARGS__; i >= REP##i; --i)
typedef long long ll;
int n, q[100100], l = 1, r;
ll f[100100], v[100100], s[100100], d[100100];
std::vector<std::pair<int, ll>> e[100100];
void pre_dfs(const int x, int fa) {
    for(const auto [y, w] : e[x]) if(y != fa) d[y] = d[x]+w,pre_dfs(y, x);
}
ll up(const int i, const int j) { return f[j]-f[i]; }
ll down(const int i, const int j) { return d[j]-d[i]; }
ll cal(const int i, const int j) { return f[j]+v[i]*(d[i]-d[j])+s[i]; }
int bisect_optimal_decision(const ll k) {
    int l = ::l, r = ::r, res = l; l++;
    for(int mid; l <= r;) {
        mid = (l+r)>>1;
        if(up(q[mid-1], q[mid]) <= (__int128)k*down(q[mid-1], q[mid])) l = mid+1,res = mid;
        else r = mid-1;
    }
    return q[res];
}
int bisect_insert_position(const int x) {
    int l = ::l, r = ::r, res = l; l++;
    for(int mid; l <= r;) {
        mid = (l+r)>>1;
        if((__int128)up(q[mid-1], q[mid])*down(q[mid], x) <= (__int128)up(q[mid], x)*down(q[mid-1], q[mid])) l = mid+1,res = mid;
        else r = mid-1;
    }
    return res;
}
void dp_dfs(const int x, const int fa) {
    if(x != 1) f[x] = cal(x, bisect_optimal_decision(v[x]));
    int _r = r, t, tt;
    r = bisect_insert_position(x);
    t = r+1,tt = q[r+1],q[++r] = x;
    for(const auto [y, w] : e[x]) if(y != fa) dp_dfs(y, x);
    q[t] = tt,r = _r;
}
signed main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cin >> n;
    fors(i, 1, n-1, x, y, z) {
        std::cin >> x >> y >> z;
        e[x].emplace_back(y, z);
        e[y].emplace_back(x, z);
    }
    fors(i, 2, n) std::cin >> s[i] >> v[i];
    pre_dfs(1, 0),dp_dfs(1, 0);
    fors(i, 2, n) std::cout << f[i] << " \n"[i == n];
    return 0;
}

破壁,组合意义法:

五种颜色 $\star,a,b,c,d$。

  • 对于 l.h.s.

钦定 $k$,在 $3n+k$ 个球中选出 $2n$ 个球染色,在靠左的 $n$ 个球中选 $k$ 个染成 $a$ 色,剩余 $n-k$ 个 $b$ 色;在靠有的 $n$ 个球中选 $k$ 个染成 $c$ 色,剩余 $n-k$ 个 $d$ 色。

  • 对于 r.h.s.

有 $3n$ 个 $\star$ 色球,钦定其中 $n$ 个,再拿出一个全 $0$ 序列,选出 $n$ 个赋值为 $1$,此时已经为右式的组合意义了,我们考虑把左右式对起来。

拿出两个指针 pq,分别指向为 $3n$ 个 $\star$ 色球中的未钦定球,和 $0/1$ 序列,两指针同步移动。

q 碰到 $1$,把 p 所指的球染成 $b$ 色,当 p 之前有恰好 $n$ 个「钦定或 $b$ 色」球时停下。那么此时设 p 前面有 $k$ 个钦定球,$n-k$ 个 $b$ 色球,p 后面有 $o$ 个球,那么 q 后面还有 $o+k$ 个数,其中恰好有 $k$ 个 $1$。

p 后面的球放在 q 之后 $0$ 的位置上,把 $1$ 的位置染成 $d$ 色,把 p 前的球和这个拼起来就和 l.h.s. 对上了。


呃呃呃,组合恒等式法。

消去网络中负权边的方法。

首先不能给边势能函数,因为最短路的路径不一定一致。于是在点上做文章,给每个点一个势能函数 $h(x)$,满足 $\forall (x,y)\in E,s.t.h(x)-h(y)+w(x,y)\geqslant0$,这样跑出来的最短路多的权就是 $h(s)-h(t)$。

至于构造方法,每次增广完以后,如果 $(x,y)\in E_r$,则 $y$ 一定是 $x$ 的 successor(不然就不在增广路上),也就是说 $d_x+w(x,y)+h(x)-h(y)=d_y$,其中 $d$ 是 $s$ 到该点的最短路,可得 $(d_y+h(y))-(d_x+h(x))=w(x,y)$。

那么令 $h(x):=h(x)+d(x)$ 即可。

因为不想写指针所以用了 std::vector 管理边的内存……

TS; DR

template<typename type1, typename type2,
    const type1 inf1 = std::numeric_limits<type1>::max(),
    const type2 inf2 = std::numeric_limits<type2>::max()>
struct mcf_graph {
    const int n;
    struct edge {
        int to, nxt;
        type1 c; type2 f;
        edge(int to, int nxt, type1 c, type2 f) : to(to), nxt(nxt), c(c), f(f) {}
    };
    int *head, *pre, *id, *vis;
    std::vector<edge> e;
    type2 *h, *dis;
    mcf_graph(const int n) : n(n),
        head(new int[n+1]), pre(new int[n+1]), id(new int[n+1]), vis(new int[n+1]),
        h(new type2[n+1]), dis(new type2[n+1]) { std::memset(head, -1, (n+1)<<2); }
    void add_edge(const int x, const int y, type1 c, type2 f) {
        assert(1 <= x && x <= n && 1 <= y && y <= n);
        e.emplace_back(y, head[x], c, f),head[x] = int(e.size())-1;
        e.emplace_back(x, head[y], 0, -f),head[y] = int(e.size())-1;
    }
    void initialize_potentials(const int s) {
        std::queue<int> q;
        std::fill(h+1, h+n+1, inf2);
        std::memset(vis+1, 0, n<<2);
        for(q.push(s), vis[s] = 1, h[s] = 0; q.size(); vis[q.front()] = 0, q.pop()) {
            for(int now = q.front(), i = head[now], y; ~i; i = e[i].nxt) {
                if(e[i].c && (h[y = e[i].to] == inf2 || h[y] > h[now]+e[i].f)) {
                    h[y] = h[now]+e[i].f;
                    if(!vis[y]) q.push(y),vis[y] = 1;
                }
            }
        }
    }
    bool augment(const int s, const int t) {
        std::priority_queue<std::pair<type2, int>, std::vector<std::pair<type2, int>>, std::greater<std::pair<type2, int>>> q;
        std::fill(dis+1, dis+n+1, inf2);
        std::memset(vis+1, 0, n<<2);
        for(q.emplace(dis[s] = 0, s); q.size();) {
            int now = q.top().second;
            q.pop();
            if(vis[now]) continue;
            vis[now] = 1;
            for(int i = head[now], y; ~i; i = e[i].nxt) {
                if(e[i].c && (dis[y = e[i].to] == inf2 || dis[y] > dis[now]+e[i].f+h[now]-h[y])) {
                    dis[y] = dis[now]+e[i].f+h[now]-h[y];
                    pre[y] = now,id[y] = i;
                    if(!vis[y]) q.emplace(dis[y], y);
                }
            }
        }
        return dis[t] < inf2;
    }
    std::pair<type1, type2> get(const int s, const int t) {
        assert(1 <= s && s <= n && 1 <= t && t <= n);
        type1 res1 = 0; type2 res2 = 0;
        initialize_potentials(s);
        while(augment(s, t)) {
            type1 cur = inf1;
            for(int i = 1; i <= n; ++i) h[i] += dis[i];
            for(int i = t; i != s; i = pre[i]) cmin(cur, e[id[i]].c);
            for(int i = t; i != s; i = pre[i]) e[id[i]].c -= cur,e[id[i]^1].c += cur;
            res1 += cur,res2 += cur*h[t];
        }
        return std::make_pair(res1, res2);
    }
};

现在来看一年前的傻逼代码太丑了,换了个好看的:

template <class Cap, class Cost>
struct mcf_graph {
  using pcc = pair<Cap, Cost>;
  struct edge {
    int v, rv;
    Cap c;
    Cost w;
  };
  const int _n;
  vi<vi<edge>> e;
  mcf_graph() : mcf_graph(0) {}
  explicit mcf_graph(int n) : _n(n), e(n + 1) {}
  void add_edge(int from, int to, const Cap& c, const Cost& w) {
    assert(1 <= from && from <= _n);
    assert(1 <= to && to <= _n);
    e[from].pb({to, int(e[to].size()) + (from == to), c, w});
    e[to].pb({from, int(e[from].size()) - 1, 0, -w});
  }
  pcc flow(int s, int t) {
    assert(1 <= s && s <= _n);
    assert(1 <= t && t <= _n);
    return flow(s, t, numeric_limits<Cap>::max(), numeric_limits<Cost>::max());
  }
  pcc flow(int s, int t, const Cap& flow_limit, const Cost& cost_limit) {
    vi<Cost> h(_n + 1, cost_limit), dst(_n + 1, cost_limit);
    vi<bool> vis(_n + 1);
    vi<int> pre(_n + 1), id(_n + 1);
    auto dual = [&](int s) {
      queue<int> que;
      for (que.push(s), h[s] = 0, vis[s] = 1; !que.empty();
           vis[que.front()] = 0, que.pop())
        for (int x = que.front(), i = 0, y; i < int(e[x].size()); ++i)
          if (e[x][i].c && h[y = e[x][i].v] > h[x] + e[x][i].w) {
            h[y] = h[x] + e[x][i].w;
            if (!vis[y]) que.push(y), vis[y] = 1;
          }
    };
    auto aug = [&](int s, int t) {
      using pci = pair<Cost, int>;
      priority_queue<pci, vi<pci>, greater<pci>> que;
      dst.assign(_n + 1, cost_limit);
      vis.assign(_n + 1, 0);
      for (que.emplace(dst[s] = 0, s); !que.empty();) {
        int x = que.top().second;
        que.pop();
        if (!vis[x]) {
          vis[x] = 1;
          for (int i = 0, y; i < int(e[x].size()); ++i) {
            y = e[x][i].v;
            if (e[x][i].c && dst[y] > dst[x] + e[x][i].w - h[y] + h[x]) {
              dst[y] = dst[x] + e[x][i].w + h[x] - h[y];
              pre[y] = x, id[y] = i;
              if (!vis[y]) que.emplace(dst[y], y);
            }
          }
        }
      }
      return dst[t] < cost_limit;
    };
    Cap flow = 0;
    Cost cost = 0;
    dual(s);
    while (aug(s, t)) {
      Cap cur = flow_limit;
      for (int i = 1; i <= _n; ++i) h[i] += dst[i];
      for (int u = t; u != s; u = pre[u]) cmin(cur, e[pre[u]][id[u]].c);
      for (int u = t; u != s; u = pre[u])
        e[pre[u]][id[u]].c -= cur, e[u][e[pre[u]][id[u]].rv].c += cur;
      flow += cur, cost += cur * h[t];
    }
    return pcc(flow, cost);
  }
};

link。

调起来真的呕吐,网上又没篇题解。大概是个不错的题。

首先行和列一定是独立的,所以我们把行列分开考虑。这样的问题就弱化为:在一个长度为 $n$ 的格子带上,有 $n$ 个物品,每个物品 $x$ 对应一个区间 $[l_x,r_x]$,分配每个物品的居所使得各住各的,求出其中的固定点。

把物品放在左部,把格子放在右部,即构造一个二部图。那么问题就是求出其最大匹配的必要边。先考虑如何求这个的最大匹配,这是个经典贪心吧,把每个区间按 $l$ 排序,然后枚举位置,优先填入 $r$ 小的物品。跑完后(即规定好方向后)对整个图跑缩点,两端点不在同一连通块的边即为必要边。

这个的边数是 $O(n^2)$ 的,因为连边一下连一个区间,考虑利用这个来优化。线段树的高度不高吧,而且能够用来刻画一个区间,于是用这个东西来优化连边。

具体一点是,线段树上父亲对两个儿子连边,物品就对线段树上自己的区间连边即可。注意清空的时候带脑子……

#include<bits/stdc++.h>
using namespace std;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
void eof(const char IO) {if(IO == -1) exit(0);}
template<typename T=int> T read() {
    T x=0; char IO=getchar(); bool f=0; eof(IO);
    while(IO<'0' || IO>'9')    f|=IO=='-',eof(IO=getchar());
    while(IO>='0' && IO<='9')    x=x*10+(IO&15),eof(IO=getchar());
    return f?-x:x;
}
int n,A[100100],B[100100],C[100100],D[100100],rec1[100100],rec2[100100],tot,ans1[100100],ans2[100100];
int col[400100],dfn[400100],low[400100],dfsnt,colnt,sta[400100],top,mat[400100],inst[400100];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
struct node{
    int l,r,id;
    friend bool operator<(const node& x,const node& y) {return x.l < y.l;}
} cur[100100];
vector<node> ans;
vector<vector<int>> e;
void DFS(const int now) {
    inst[sta[++top] = now] = 1;
    dfn[now] = low[now] = ++dfsnt;
    for(const int y : e[now]) {
        if(!dfn[y]) DFS(y),cmin(low[now], low[y]);
        else if(inst[y]) cmin(low[now], dfn[y]);
    }
    if(low[now]^dfn[now]) return;
    colnt++;
    int y; do {
        inst[y = sta[top--]] = 0;
        col[y] = colnt;
    } while(y != now);
}
#define mem(x, w, n) memset(x, w, n)
void sweep() {
    e.clear();
    mem(col, 0, min(size_t(n*4*30), sizeof(col)));
    mem(dfn, 0, min(size_t(n*4*30), sizeof(dfn)));
    mem(low, 0, min(size_t(n*4*30), sizeof(low)));
    mem(sta, 0, min(size_t(n*4*30), sizeof(sta)));
    mem(inst, 0, min(size_t(n*4*30), sizeof(inst)));
    mem(mat, 0, min(size_t(n*4*30), sizeof(mat)));
    // puts("DEBUGGING ----------");
    // for(int* i : {col, dfn, low, sta, inst}) {
    //     for(int j = 0;  j < 233; ++j) printf(" %d",i[j]);
    //     puts("");
    // }
    // puts("END___D__D__D____D___D_");
    tot = dfsnt = colnt = top = 0;
    while(q.size()) q.pop();
}
int tr[400100],reid[400100];
void addedge(const int one, const int ano) {
    // printf("add:%d %d\n",one,ano);
    if(one >= int(e.size())) e.resize(one+1);
    e[one].push_back(ano);
}
void build(const int now, int l, int r) {
    // printf("  %d  %d\n",l,r);
    tr[now] = ++tot;
    if(l == r) return reid[l] = tot,void();
    int mid = (l+r)>>1;
    build(now<<1, l, mid),build(now<<1|1, mid+1, r);
    addedge(tr[now], tr[now<<1]),addedge(tr[now], tr[now<<1|1]);
}
void lin(int x,int y,int k,const int now = 1,int l = 1,int r = n) {
    if(l>y || r<x || x>y) return;
    if(l>=x && r<=y) return addedge(k, tr[now]),void();
    int mid = (l+r)>>1;
    lin(x, y, k, now<<1, l, mid),lin(x, y, k, now<<1|1, mid+1, r);
}
bool solve(int rec[], int ans[]) {
    sweep();
    static int l[100100], r[100100];
    for(int i=1; i<=n; ++i) l[i] = cur[i].l,r[i] = cur[i].r;
    sort(cur + 1, cur + n + 1);
    for(int i=1, p=1; i<=n; ++i) {
        while(p <= n && cur[p].l <= i) q.emplace(cur[p].r, cur[p].id),p++;
        if(!q.size() || q.top().first<i) return 0;
        mat[q.top().second] = i;
        q.pop();
    }
    tot = n;
    build(1, 1, n);
    // printf("  tot: %d\n", tot);
    // for(int i=1; i<=4*n; ++i) printf(" %d",tr[i]);
    // puts("");
    for(int i=1; i<=n; ++i) {
        addedge(reid[mat[i]], i);
        lin(l[i], mat[i]-1, i);
        lin(mat[i]+1, r[i], i);
    }
    for(int i=1; i<=tot; ++i) if(!dfn[i]) DFS(i);
    // for(int i=1; i<=tot; ++i) printf(" %d",col[i]);
    for(int i=1; i<=n; ++i) rec[i] = col[i] != col[reid[mat[i]]],ans[i] = mat[i];
    return 1;
}
signed main() {
    while(n = read(),233) {
        for(int i=1; i<=n; ++i) A[i] = read(),B[i] = read(),C[i] = read(),D[i] = read();
        for(int i=1; i<=n; ++i) cur[i] = (node){A[i], C[i], i};
        if(!solve(rec1, ans1)) {
            puts("-1");
            goto Fail;
        }
        for(int i=1; i<=n; ++i) cur[i] = (node){B[i], D[i], i};
        if(!solve(rec2, ans2)) {
            puts("-1");
            goto Fail;
        }
        vector<node>().swap(ans);
        for(int i=1; i<=n; ++i) if(rec1[i] && rec2[i]) ans.push_back((node){i, ans1[i], ans2[i]});
        cout<<ans.size()<<endl;
        for(const auto [x, y, z] : ans) printf("%d %d %d\n", x, y, z);
        Fail:;
    }
    return 0;
}