雅礼10.6

虽然我喜欢简洁的题面，但太简洁也不一定是好事。至少请别带来误解。

Adore

Prob.

求能避开边界与给定点的路径的最小距离的最大值。

Sol.

题目应该理解为

$$ \max_{\text{path}} \min_{p \in \text{path}, x \in \text{stars}} ||p - x|| $$

注意到一条从上到下连接各点的路径的最长边即可被我们通过。
所以把上下边界视为点求 MST 即可，求出的连接上下边界的最长的边的一半即为答案。

Code

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxk = 6e3 + 1000, maxn = 1e6 + 100;
const long long INF = 0x3f3f3f3f3f3f3f3f;
int x[maxk], y[maxk], d[maxk];
struct E{int v, n, w;}e[maxn << 1];
int h[maxn], ec = 1;
inline void add_edge(int u, int v, int w){e[ec] = (E){v, h[u], w}; h[u] = ec++;}
int n, m, k; long long ans;
void dfs(int u = k, int f = 0, long long ret = 0)
{
    if(u == k + 1) {ans = ret; return;}
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f)
        dfs(v, u, max(ret, 1ll * e[i].w));
}
long long calc(int a, int b)
{
    if(a > b) swap(a, b);
    if(a == k && b == k + 1) return 1ll * m * m;
    if(b == k) return 1ll * (m - y[a]) * (m - y[a]);
    if(b == k + 1) return 1ll * y[a] * y[a];
    return 1ll * (y[b] - y[a]) * (y[b] - y[a]) + 1ll * (x[b] - x[a]) * (x[b] - x[a]);
}
bool vis[maxn];
int fa[maxn];
int main()
{
    freopen("starway.in", "r", stdin);
    freopen("starway.out", "w", stdout);
    read(n, m, k);
    for(int i = 0; i < k; ++i) read(x[i], y[i]);
    memset(d, INF, sizeof d); d[k] = 0;
    for(int i = 0; i < k + 2; ++i)
    {
        long long _min = INF, num;
        for(int j = 0; j < k + 2; ++j) if(d[j] < _min && !vis[j]) _min = d[j], num = j;
        vis[num] = true;
        if(_min) add_edge(num, fa[num], _min), add_edge(fa[num], num, _min);
        for(int j = 0; j < k + 2; ++j) if(!vis[j] && calc(j, num) < d[j]) d[j] = calc(j, num), fa[j] = num;
    }
    dfs();
    printf("%.9lf\n", sqrt(ans) / 2);
    return 0;
}

knows

Prob.

给一个二分图，删一条边有花费，但可以把跟他有交的边全部删除。问删除全部边的最小花费。

Sol.

注意到删除任何一个极长递增子序列后都会清除全部边。
用 $ f_i $ 表示删除以 $ i $ 结尾的极长子序列的最小花费，考虑转移 $ f_i = \min_{j<i,p_j<p_i} f_j + w_i $。
直接计算是 $ O(n) $ 的，需要提速。
发现当 $ j'<j<i,p_{j'}<p_j<p_i $ 时，$ j' $ 是无用决策，这启发我们关注什么情况才是值得使用的决策：当 $ k<j<i,p_j<p_k<p_i, j $是上一轮考虑的决策点时， $ k $ 也需要考虑。
可以证明，如此 $ k $ 最多只有 $ O(\lg n) $ 个。用数据结构维护 $ p $ 的逆数组也可以在 $ O(\lg n) $ 的时间内得到该 $ k $。转移提速到 $ O(\lg^2 n) $，本题可以承受。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 2e5 + 100, INF = 0x3f3f3f3f;
struct Info{int m; Info(int a = 0):m(a){}Info operator+(const Info& rhs){return Info(max(m, rhs.m));}} I[maxn << 2];
int f[maxn], w[maxn], p[maxn], t;
inline void modify(int u, int v)
{
    for(I[u += t] = Info(v), u >>= 1; u; u >>= 1)
        I[u] = I[u << 1] + I[u << 1 | 1];
}
inline int query(int u, int v)
{
    Info ret;
    for(u += t - 1, v += t + 1; u ^ v ^ 1; u >>= 1, v >>= 1)
    {
        if(~u & 1) ret = ret + I[u ^ 1];
        if( v & 1) ret = ret + I[v ^ 1];
    }
    return ret.m;
}
int main()
{
    freopen("knows.in", "r", stdin);
    freopen("knows.out", "w", stdout);
    int n; read(n);
    for(int i = 1; i <= n; ++i) read(p[i]);
    for(int i = 1; i <= n; ++i) read(w[i]);
    p[++n] = n, w[n] = 0;
    t = 1; while(t <= n + 3) t <<= 1;
    memset(f, INF, sizeof f); f[0] = 0; p[0] = 0;
    for(int i = 1; i <= n; ++i)
    {
        int j = 0, pre = -1; 
        while((pre = query(p[j] + 1, p[i])) && pre != j)
            f[i] = min(f[i], f[pre]), j = pre;
        if(f[i] != INF) f[i] += w[i]; else f[i] = w[i];
        modify(p[i], i);
    }
    printf("%d\n", f[n]);
    return 0;
}

lost

Prob.

给一棵树，求 $ f(u) = \min_{v \in \text{anc}(u)} \frac{c_u-c_v}{dist(u,v)} $ 。

Sol.

本质上求凸包切线。
在此之前我根本不会做这种题……所以先从简单的情形讲讲做法……
考虑数轴上的情况，将每一个值看成一个点 $ (u, w_u) $ ，所求即为此点与之前点连线斜率最小值。
可以发现，新点与目标点连线、目标点与目标点的目标点连线……其斜率有单调性。
考虑用栈维护。若栈顶点与新点的斜率大于栈顶点与自身目标点连线的斜率，则退栈。

树上情况使用可持久化栈。
这里不需要用主席树维护可持久化数组，只要对在树上的节点，记录每个点的目标点。
不用暴力，倍增二分退栈。

Code

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 5e5 + 1000;
const double eps = 1e-8;
int w[maxn], fa[maxn], l[maxn], f[maxn][20], d[maxn];
double ans[maxn];
inline double slope(int x, int y){return (w[x] - w[y]) / (double)(d[x] - d[y]);}
queue<int> Q; 
struct E{int v, n;}e[maxn << 1];
int h[maxn], ec = 1;
inline void add_edge(int u, int v){e[ec] = (E){v, h[u]}; h[u] = ec++;}
int main()
{
    freopen("lost.in", "r", stdin);
    freopen("lost.out", "w", stdout);
    int n; read(n);
    for(int i = 1; i <= n; i++) read(w[i]);
    for(int i = 2; i <= n; i++) read(fa[i]), add_edge(fa[i], i);
    Q.push(1);
    while(!Q.empty())
    {
        int u = Q.front(), y = u; Q.pop();
        d[u] = d[fa[u]] + 1;
        l[u] = f[u][0] = fa[u];
        for(int i = 1; i < 17; ++i) f[u][i] = f[f[u][i - 1]][i - 1];
        for(int i = 16; ~i; --i)
        {
            int z = f[y][i];
            if(!l[z]) continue;
            if(slope(l[z], z) > slope(z, u)) y = z;
        }
        l[u] = f[u][0] = y = l[y], ans[u] = -slope(u, y);
        for(int i = 1; i < 17; i++) f[u][i] = f[f[u][i - 1]][i - 1];
        for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) Q.push(v);
    }
    // for (int i=2;i<=n;i++) if (fabs(ans[i])<eps) ans[i]=fabs(ans[i]);
    for(int i = 2; i <= n; i++) printf("%.10lf\n", ans[i]);
    return 0;
}