526互联

[ABC294] vp 题解 [E~G]

发布时间 2023-03-26 22:04:53作者: MoyouSayuki

[ABC294] vp 题解

A B C D 略

E - 2xN Grid 双指针模拟

考虑 \(L\) 太大了，无法直接把压缩后的表示法展开，那么我们直接一块一块地考虑即可。

用两个指针 \(i, j\) 表示当前走到了哪一格（解压后），分类讨论。

  1. \(i > j\)，将第二行往后拓展一块，判断第一行当前块 \(i1\) 的颜色是否与新拓展的那块 \(i2\) 颜色相同，如果相同，执行 ans += i >= j ? b[i2].l : i - (j - b[i2].l)，画图不难理解。

  2. \(j > i\)，将第一行往后拓展一块，判断第二行当前块的颜色是否与新拓展的那块颜色相同，如果相同，执行 ans += j >= i ? a[i1].l : j - (i - a[i1].l)，画图不难理解。

  3. \(i == j\) 将第一行或第二行任意一行向后拓展一块

signed main()
{
    int l, n, m;
    cin >> l >> n >> m;
    for(int i = 1; i <= n; i ++)
        cin >> a[i].v >> a[i].l;
    for(int i = 1; i <= m; i ++)
        cin >> b[i].v >> b[i].l;
    
    int ans = 0;
    for(int i = 0, j = 0, i1 = 1, i2 = 1; (i <= l || j <= l) && (i1 <= n || i2 <= m);)
    {
        if(i > j)
        {
            j += b[i2].l;
            if(b[i2].v == a[i1 - 1].v) ans += i >= j ? b[i2].l : i - (j - b[i2].l);
            i2 ++;
        }
        else if(j > i)
        {
            i += a[i1].l;
            if(a[i1].v == b[i2 - 1].v) ans += j >= i ? a[i1].l : j - (i - a[i1].l);
            i1 ++;
        }
        else
        {
            i += a[i1].l;
            i1 ++;
        }
    }
    
    cout << ans << endl;

    return 0;
}

F - Sugar Water 2 二分答案 + 推式子

首先二分一个浓度 \(x\)，将原问题转化为如下的判定性问题：

  • 是否有不少于 \(k\) 瓶糖水的浓度不小于 \(x\)，在 \(nm\) 瓶糖水里。

观察发现，如果一杯糖水有 \(s\) 克糖与 \(t\) 克水，那么如果 \(s = t\dfrac{x}{1-x}\)，它的浓度刚好与 \(x\) 相等，换言之，如果令 \(u = t\dfrac{x}{1-x}\)，那么 \(s - u\) 就是这杯糖水与理想糖水（浓度为 \(x\)）所差的糖克数。

把第一个人的所有糖水的 $s- u $ 算出并扔进数组 \(v\)。

然后我们枚举一下第二个人的所有糖水，令 \(w = s- u\)。

此处分类讨论：

  1. \(w \ge 0\)，则第一个人所有的糖水满足 \(v_i \ge -w\) 的都是可以与当前第二个人的糖水配对的。
  2. \(w < 0\)，则第一个人的糖水至少需要 \(-w\) 克糖才能合法。

可以二分出一个位置 \(pos\) 满足 \(v_1\sim v_{pos - 1} < -w\)，\(v_{pos}\sim v_{n} \ge -w\)，则对于第二个人的这瓶糖水，就有 \(n - pos\) 对糖水浓度时不小于 \(x\) 的，重复进行上述操作，最后与 \(k\) 判断即可。

时间复杂度：\(O(C(n\log n + m\log n))\)，其中 \(C = \log_2100\)，是浓度的二分所需时间。

signed main()
{
    int n, m, k;
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i ++)
        cin >> a[i] >> b[i];
    for(int i = 1; i <= m; i ++)
        cin >> c[i] >> d[i];
    double l = 0, r = 1;
    
    while(r - l > eps)
    {
        double x = (l + r) / 2.0;
        for(int i = 1; i <= n; i ++)
            v[i] = 1.0 * a[i] - b[i] * x / (1 - x);
        sort(v + 1, v + n + 1);
        
        long long cnt = 0;
        for(int i = 1; i <= m; i ++)
        {
            double w = 1.0 * c[i] - d[i] * x / (1 - x);
            auto pos = lower_bound(v + 1, v + n + 1, -w) - 1 - v;
            cnt += n - pos;
        }
        
        if(cnt >= k) l = x;
        else r = x;
    }
    printf("%.14lf\n", l * 100);

    return 0;
}

G - Distance Queries on a Tree 树链剖分

树链剖分维护边的板子，把边权信息放到深节点即可。

const int N = 5e5 + 10, INF = (int)1e18;

vector<int> g[N];

struct thr
{
    int a, b, c;
} q[N];

struct owo
{
    int l, r, dat;
} tr[N << 2];

int id[N], top[N], hson[N], fa[N], siz[N], dep[N], timestamp;
int w[N], Temp[N];
void dfs1(int u, int f)
{
    fa[u] = f, dep[u] = dep[f] + 1, siz[u] = 1;
    int mx = -1;
    for (auto v : g[u])
    {
        if (v == f)
            continue;
        dfs1(v, u), siz[u] += siz[v];
        if (mx < siz[v]) hson[u] = v, mx = siz[v];
    }
}

void dfs2(int u, int anc)
{
    id[u] = ++timestamp, top[u] = anc, w[id[u]] = Temp[u];
    if (!hson[u])
        return;
    dfs2(hson[u], anc);
    for (auto v : g[u])
    {
        if (v == hson[u] || v == fa[u])
            continue;
        dfs2(v, v);
    }
}

#define ls k << 1
#define rs k << 1 | 1
#define dat(k) tr[k].dat

owo up(owo k, owo l, owo r)
{
    k.dat = l.dat + r.dat;
    return k;
}

void up(int k) { dat(k) = dat(ls) + dat(rs); }

void build(int k, int l, int r) // 建线段树
{
    tr[k] = {l, r, 0};
    if (l == r) tr[k] = {l, r, w[l]};
    else
    {
        int mid = l + r >> 1;
        build(ls, l, mid), build(rs, mid + 1, r), up(k);
    }
}

void update(int k, int x, int v) // 线段树区间修改
{
    int l = tr[k].l, r = tr[k].r, mid = l + r >> 1;
    if (x == l && r == x)
    {
        dat(k) = v;
        return;
    }
    if (x <= mid) update(ls, x, v);
    if (x > mid)  update(rs, x, v);
    up(k);
}

owo query(int k, int ql, int qr) // 线段树区间查询
{
    int l = tr[k].l, r = tr[k].r, mid = l + r >> 1;
    if (ql <= l && qr >= r)
        return tr[k];
    owo tmp = {0, 0, 0}, L, R;
    if (ql > mid)
        return query(rs, ql, qr);
    if (qr <= mid)
        return query(ls, ql, qr);
    L = query(ls, ql, qr), R = query(rs, ql, qr);
    return up(tmp, L, R);
}

int Dquery(int u, int v) // 树剖 查询路径点权
{
    int ans = 0;
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        ans = ans + query(1, id[top[u]], id[u]).dat;
        u = fa[top[u]];
    }
    if(u != v)
    {
        if (dep[u] < dep[v]) swap(u, v);
        ans += query(1, id[v] + 1, id[u]).dat; // 注意此处
    }
    return ans;
}

#undef ls
#undef rs

signed main()
{
    int n;
    cin >> n;
    for(int i = 1; i < n; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        q[i] = {a, b, c};
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs1(1, 1);
    
    for(int i = 1; i <= n; i ++)
        if(q[i].a == fa[q[i].b])
            Temp[q[i].b] = q[i].c;
        else 
            Temp[q[i].a] = q[i].c;
            
    Temp[1] = 0;
    
    dfs2(1, 1);
    build(1, 1, n);
    
    int T;
    cin >> T;
    while (T--)
    {
        int op, a, b;
        cin >> op >> a >> b;
        if(op == 1)
        {
            if(dep[q[a].a] < dep[q[a].b])
                update(1, id[q[a].b], b);
            else 
                update(1, id[q[a].a], b);
        }
        else 
            cout << Dquery(a, b) << "\n";
    }
    
    return 0;
}