[JOISC 2019] 做题记录

_MengShang_ · 2025-11-07 09:24:57 · 个人记录

P14340 [JOISC 2019] 考试 / Examination - 洛谷

每个人的信息 (S_i,T_i) 视为 (S_i,T_i,S_i+T_i)，直接套三维偏序，排序一维，归并一维，数据结构维护一维。

const int maxn = 1e5 + 5;
int n, m, ans[maxn], num[maxn << 1], cnt; 
struct Node { int x, y, z, qid; } a[maxn << 1]; int tot;
int id[maxn << 1], tmp[maxn << 1], pt;
inline bool cmp(const int& i, const int& j) { return a[i].x > a[j].x; }

int val[maxn << 1];
inline void add(int x, int d) { for (; x <= cnt; x+= x & -x) val[x]+= d; }
inline int qry(int x) { int res = 0; for (; x; x-= x & -x) res+= val[x]; return res; }

inline void cdq(int l, int r)
{
    if (l == r) return; int mid = l + r >> 1; cdq(l, mid); cdq(mid + 1, r); 
    int p1 = l, p2 = mid + 1; for (; p2 <= r; ++p2)
    {
        while (p1 <= mid && a[id[p1]].y >= a[id[p2]].y) { if (!a[id[p1]].qid) add(a[id[p1]].z, 1); ++p1; }
        if (a[id[p2]].qid) ans[a[id[p2]].qid]+= qry(cnt) - qry(a[id[p2]].z - 1);
    }
    for (--p1; p1 >= l; --p1) if (!a[id[p1]].qid) add(a[id[p1]].z, -1);
    p1 = l, p2 = mid + 1, pt = l; 
    while (p1 <= mid && p2 <= r) tmp[pt++] = a[id[p1]].y >= a[id[p2]].y ? id[p1++] : id[p2++];
    while (p1 <= mid) tmp[pt++] = id[p1++];
    while (p2 <= r) tmp[pt++] = id[p2++];
    rep(i, l, r) id[i] = tmp[i];
}

int main()
{
    read(n, m); int x, y, z; num[1] = 0; num[cnt = 2] = 2e9;
    rep(i, 1, n) read(x, y), a[++tot] = {x, y, x + y, 0}, num[++cnt] = x + y; 
    rep(i, 1, m) read(x, y, z), a[++tot] = {x, y, z, i}, num[++cnt] = z;
    sort(num + 1, num + cnt + 1); cnt = unique(num + 1, num + cnt + 1) - num;
    rep(i, 1, tot) a[i].z = lower_bound(num + 1, num + cnt + 1, a[i].z) - num;
    rep(i, 1, tot) id[i] = i; 
    sort(id + 1, id + tot + 1, [&](const int& i, const int& j) 
    { 
        if (a[i].x != a[j].x) return a[i].x > a[j].x; 
        return a[i].qid < a[j].qid;
    }); 
    cdq(1, tot); 
    rep(i, 1, m) write(ans[i]), pc(0xa); 
    return 0; 
}

P14341 [JOISC 2019] 海狸的会面 / Meetings - 洛谷

发现 u,v,w 聚集的地点一定是 u,v,w 两两求 \text{lca} 后深度最大的 \text{lca}。

设当前递归到的 \text{root} 为 x，在 x 的子树中随机一个点 y，并对 x 子树中的所有点 z 分别询问 (x,y,z)，以确定 z 是否在 x\to y 的链上，或者在 x\to y 的链上某个点的子树内。

对于链上的点可以通过一次询问比较两个点的深度，直接排序即可。

mt19937 rnd((unsigned)time(NULL)); 
inline int rd(const int& l, const int& r) { return rnd() % (r - l + 1) + l; }

int Query(int u, int v, int w); 
void Bridge(int u, int v);

inline void divide(int x, const vector<int>& node, const int& n)
{
    if (node.size() == 1) { if (x < node[0]) Bridge(x, node[0]); else Bridge(node[0], x); return; }
    vector<int> pos = node; shuffle(pos.begin(), pos.end(), rnd);
    vector<int> id(n); for (int i = 0; i < (int)pos.size(); ++i) id[pos[i]] = i; 
    int y = pos[0]; vector<int> tmp; vector<vector<int>> son(pos.size() + 1); 
    for (int i = 1; i < (int)pos.size(); ++i)
    {
        int z = pos[i]; int lca = Query(x, y, z);
        if (lca != z) { if (lca == x) son.back().pbk(z); else son[id[lca]].pbk(z); } 
        else tmp.pbk(z);
    }
    tmp.pbk(y); 
    for (int i = 0; i < (int)pos.size(); ++i) if (son[i].size()) divide(pos[i], son[i], n);
    if (son.back().size()) divide(x, son.back(), n);
    sort(tmp.begin(), tmp.end(), [=](const int& a, const int& b) { return Query(a, b, x) == a; });
    for (int i = 0; i < (int)tmp.size(); ++i)
    {
        if (i == 0) { if (tmp[i] < x) Bridge(tmp[i], x); else Bridge(x, tmp[i]); }
        else { if (tmp[i] < tmp[i - 1]) Bridge(tmp[i], tmp[i - 1]); else Bridge(tmp[i - 1], tmp[i]); }
    }
}

void Solve(int n)
{
    int rt = rd(0, n - 1); 
    vector<int> pos; for (int i = 0; i < n; ++i) if (i != rt) pos.pbk(i); 
    divide(rt, pos, n);
}

P14342 [JOISC 2019] 馕 / Naan - 洛谷

先求出每个人的 n 等分点。

从左到右分配馕属于谁。对于每个位置 j，从剩余的还未被分配的人中选择最小的 x_j 作为 X_j，并把 [X_{j-1},X_j] 分给他。由于每次都这样分，所以必有 X_{j-1}\le x_{j-1}，一定满足要求。

需要注意 x_j 计算的方法。

const int maxn = 2005; const ll inf = 1e18;

inline ll gcd(ll x, ll y) { if (x < y) swap(x, y); return y == 0 ? x : gcd(y, x % y); }
struct Div{ ll x, y; Div(ll _x, ll _y) : x(_x), y(_y) {} Div() : x(0), y(1) {} };
bool operator < (const Div& a, const Div& b) { return (ld)a.x / a.y < (ld)b.x / b.y; }
bool operator > (const Div& a, const Div& b) { return (ld)a.x / a.y > (ld)b.x / b.y; }
bool operator <= (const Div& a, const Div& b) { return (ld)a.x / a.y <= (ld)b.x / b.y; }
bool operator >= (const Div& a, const Div& b) { return (ld)a.x / a.y >= (ld)b.x / b.y; }
bool operator == (const Div& a, const Div& b) { return a.x == b.x && a.y == b.y; }

int n, l; ll v[maxn][maxn]; Div pos[maxn][maxn], ans1[maxn]; int ans2[maxn], vis[maxn];

int main()
{
    read(n, l); rep(i, 1, n) rep(j, 1, l) read(v[i][j]); 
    rep(i, 1, n)
    {
        ll sum = 0; rep(j, 1, l) sum+= v[i][j];
        Div ned = Div(sum, n);
        int p = 1; ll cur = 0;
        for (int j = 1; j <= n; ++j)
        {
            while (p < l && Div(cur + v[i][p], j) < ned) { cur+= v[i][p]; ++p; }
            ll num = (ll)n * v[i][p] * (p - 1) + sum * j - cur * n;
            ll den = (ll)n * v[i][p];
            pos[i][j] = Div(num, den);
        }
    }
    rep(i, 1, n)
    {
        int p = 0; 
        rep(j, 1, n) if (!vis[j] && (p == 0 || pos[p][i] > pos[j][i])) p = j;
        ans1[i] = pos[p][i]; ans2[i] = p; vis[p] = 1;
    }
    rep(i, 1, n - 1) write(ans1[i].x), pc(' '), write(ans1[i].y), pc(0xa); 
    rep(i, 1, n) write(ans2[i]), pc(' ');
    return 0; 
}

P14343 [JOISC 2019] 两个天线 / Two Antennas - 洛谷

对于两个天线 i,j(i<j)，若它们能够互相通信，则需要满足：

• a[i]\le j-i\le b[i]
• a[j]\le j-i\le b[j]

即

• j\in[i+a[i],i+b[i]]
• i\in[j-b[j],j-a[j]]

考虑将所有查询离线，并按照右端点 R 排序。从 1 到 n 扫描右端点 j。对于每个 j，考虑所有左端点 i<j，计算它们与 j 的通信成本，即 |h[i]-h[j]|。

考虑在扫描线时通过线段树维护信息。具体的，需要使它支持：

• 单点更新：激活/失效天线。
• 区间更新：用当前天线高度更新历史最大值。
• 区间查询：查询历史最大值。

容易使用吉司机线段树维护（好像比板子题还水？）。

const int maxn = 2e5 + 5, inf = 1e9; 
int n, m, h[maxn], a[maxn], b[maxn], ans[maxn];   

#define ls (p << 1)
#define rs (ls | 1)
struct Node{ int mnc, mxc, mxd, tgmn, tgmx; } t[maxn << 2];
inline void update(int p) 
{ 
    t[p].mnc = min(t[ls].mnc, t[rs].mnc); 
    t[p].mxc = max(t[ls].mxc, t[rs].mxc);
    t[p].mxd = max(t[ls].mxd, t[rs].mxd);
}
inline void add(int p, int d)
{
    if (t[p].mnc != inf) chkmx(t[p].mxd, -t[p].mnc + d);
    if (t[p].mxc != -inf) chkmx(t[p].mxd, t[p].mxc - d);
    chkmn(t[p].tgmn, d); chkmx(t[p].tgmx, d);
}
inline void pushdown(int p)
{
    if (t[p].tgmn != inf) { add(ls, t[p].tgmn); add(rs, t[p].tgmn); t[p].tgmn = inf; }
    if (t[p].tgmx != -inf) { add(ls, t[p].tgmx); add(rs, t[p].tgmx); t[p].tgmx = -inf; }
}
inline void build(int p, int l, int r)
{
    t[p] = {inf, -inf, -inf, inf, -inf}; if (l == r) return; 
    int mid = l + r >> 1; build(ls, l, mid); build(rs, mid + 1, r); update(p); 
}
inline void modify1(int p, int l, int r, int L, int R, int d)
{
    if (l > R || r < L) return; if (l >= L && r <= R) return add(p, d), void(); 
    int mid = l + r >> 1; pushdown(p); modify1(ls, l, mid, L, R, d); modify1(rs, mid + 1, r, L, R, d); update(p); 
}
inline void modify2(int p, int l, int r, int x, int d)
{
    if (l == r) { if (d == 0) { t[p].mnc = inf; t[p].mxc = -inf; } else t[p].mnc = t[p].mxc = d; return; }
    int mid = l + r >> 1; pushdown(p); if (x <= mid) modify2(ls, l, mid, x, d); else modify2(rs, mid + 1, r, x, d); update(p); 
}
inline int query(int p, int l, int r, int L, int R)
{
    if (l > R || r < L) return -inf; if (l >= L && r <= R) return t[p].mxd; 
    int mid = l + r >> 1; pushdown(p); return max(query(ls, l, mid, L, R), query(rs, mid + 1, r, L, R));
}

vector<pii> pos[maxn], q[maxn]; 

int main()
{
    read(n); rep(i, 1, n) read(h[i], a[i], b[i]); 
    rep(i, 1, n)
    {
        if (i + a[i] <= n) pos[i + a[i]].pbk({i, h[i]});
        if (i + b[i] + 1 <= n) pos[i + b[i] + 1].pbk({i, 0}); 
    }
    read(m); rep(i, 1, m) { int l, r; read(l, r); q[r].pbk({l, i}); }
    build(1, 1, n); 
    rep(j, 1, n)
    {
        for (auto [i, hi] : pos[j]) modify2(1, 1, n, i, hi);
        if (j - a[j] >= 1) modify1(1, 1, n, max(1, j - b[j]), j - a[j], h[j]);
        for (auto [l, id] : q[j]) ans[id] = query(1, 1, n, l, j); 
    }
    rep(i, 1, m) write(ans[i] < 0 ? -1 : ans[i]), pc(0xa); 
    return 0; 
}

P14344 [JOISC 2019] 两道料理 / Two Dishes - 洛谷

对于每一个 P_i，如果其计入贡献，则在 S_i 分钟内要完成 \text{IOI} 的第 i 步。完成第 i 步至少需要 \sum_{j=1}^i A_j 的时间，从另一个角度说最多只有 S_i-\sum_{j=1}^{i}A_j 的时间分给 \text{JOI}。

考虑预处理：

• y_i=\max\left\{j|\left(\sum_{k=1}^i a_i+\sum_{k=1}^j b_k\right)\le s_i\right\}
• x_i=\max\left\{j|\left(\sum_{k=1}^ib_i+\sum_{k=1}^j a_k\right)\le t_j\right\}

将原题转化为从 (0,0) 走到 (n,m)，每次只能 x+1\to x 或者 y+1\to y，则

• 当 (i,y_i) 在路径上方或者在路径上时，有 p_i 的贡献（\text{IOI} 完成第 i 步时，\text{JOI} 完成不超过 y_i 步）；
• 当 (x_i,i) 在路径下方或者在路径上时，有 q_i 的贡献（\text{JOI} 完成第 i 步时，\text{IOI} 完成不超过 x_i 步 ）。

一个比较 \text{trival} 的想法是先把所有 p_i 计入贡献，然后把 p_i\leftarrow -p_i，并把 y_i\leftarrow y_i+1，于是可以把两类点都变为第二类计算。

令 f_{i,j} 表示从 (0,0) 走到 (i,j)，所有在路径上或者在路径下方的点的权值和的最大值。

记 \text{sum}_{i,j} 表示第 i 列中所有纵坐标 \le j 的点的权值之和，则有转移：

相当于 f_j\leftarrow f_j+\text{sum}_{i,j} 并进行一次前缀 \max。

考虑维护 f 的差分，每个有值的 \text{sum}_{i-1,j}-\text{sum}_{i-1,j-1} 给 f_{j} 单点加。前缀取 \max 相当于把负的 f' 以及其后一段 \sum\le 0 的都变为 0，用线段树二分容易做到单 \log。

注意每个 i 上点的排序顺序。

const int maxn = 1e6 + 5; const ll inf = 1e15;
int n, m; ll ans = 0; 
ll A[maxn], S[maxn], P[maxn]; 
ll B[maxn], T[maxn], Q[maxn]; 
vector<pil> vec[maxn]; 

#define ls (p << 1)
#define rs (ls | 1)
ll sum[maxn << 2], tag[maxn << 2]; 
inline void update(int p) { sum[p] = sum[ls] + sum[rs]; }
inline void pushdown(int p) { if (tag[p]) { sum[ls] = sum[rs] = 0, tag[ls] = tag[rs] = 1; tag[p] = 0; } }
inline void modify(int p, int l, int r, int x, ll d)
{
    if (l == r) return sum[p]+= d, void(); 
    int mid = l + r >> 1; pushdown(p); if (mid >= x) modify(ls, l, mid, x, d); else modify(rs, mid + 1, r, x, d); update(p); 
}
inline void reset(int p, int l, int r, int L, int R)
{
    if (l > R || r < L) return; if (l >= L && r <= R) { sum[p] = 0; tag[p] = 1; return; }
    int mid = l + r >> 1; pushdown(p); reset(ls, l, mid, L, R); reset(rs, mid + 1, r, L, R); update(p);
}
inline ll query(int p, int l, int r, int L, int R)
{
    if (l > R || r < L) return 0; if (l >= L && r <= R) return sum[p]; 
    int mid = l + r >> 1; return query(ls, l, mid, L, R) + query(rs, mid + 1, r, L, R); 
}
inline int binary(int p, int l, int r, int L, int R, ll pre, ll v)
{
    if (l > R || r < L) return -1; 
    if (l >= L && r <= R) { if (pre + sum[p] < v) return -1; if (l == r) return l; }
    int mid = l + r >> 1; pushdown(p);
    int res = binary(ls, l, mid, L, R, pre, v); 
    if (~res) return res; 
    int L1 = max(L, l), R1 = min(R, mid); 
    ll lsum = 0; 
    if (L1 <= R1) lsum = query(ls, l, mid, L1, R1); 
    return binary(rs, mid + 1, r, L, R, pre + lsum, v); 
}

int main()
{
    read(n, m); 
    rep(i, 1, n) read(A[i], S[i], P[i]), A[i]+= A[i - 1]; 
    rep(i, 1, m) read(B[i], T[i], Q[i]), B[i]+= B[i - 1]; 
    rep(i, 1, n)
    {
        ll t = S[i] - A[i]; if (t < 0) continue; int l = 0, r = m, j = ~0;
        while (l <= r) { int mid = l + r >> 1; if (B[mid] <= t) l = mid + 1, j = mid; else r = mid - 1; }
        ans+= P[i]; if (j + 1 <= m) vec[i - 1].pbk({j + 1, -P[i]});
    }
    rep(i, 1, m) 
    {
        ll t = T[i] - B[i]; if (t < 0) continue; int l = 0, r = n, j = ~0; 
        while (l <= r) { int mid = l + r >> 1; if (A[mid] <= t) l = mid + 1, j = mid; else r = mid - 1; }
        if (~j) vec[j].pbk({i, Q[i]});
    }
    rep(i, 0, n - 1) 
    {
        sort(vec[i].begin(), vec[i].end(), [](const pil& x, const pil& y) 
        { 
            return x.sec == y.sec ? x.fst < y.fst : x.sec > y.sec; 
        });
        for (auto [j, w] : vec[i])
        {
            if (w >= 0) modify(1, 0, m, j, w);
            else
            {
                int r = binary(1, 0, m, j, m, 0, -w);
                // cerr << j << ' ' << r << endl; 
                if (r == -1) reset(1, 0, m, j, m); 
                else { modify(1, 0, m, r, w + query(1, 0, m, j, r - 1)); reset(1, 0, m, j, r - 1); }
            }
        }
    }
    ans+= sum[1]; for (auto [j, w] : vec[n]) ans+= w; write(ans); pc(0xa);  
    return 0; 
}

P14345 [JOISC 2019] 两种交通 / Two Transportations - 洛谷

通信题，不会。

P14346 [JOISC 2019] 指定城市 / Designated Cities - 洛谷

转化一下题意：给定一颗 n 个点的树，每条边为双向边，两个方向权值不同。q 组询问，每组询问给定 k，求任选 k 个点，把以其为根的内向树边权改为 0 后，整棵树的边权和的最小值。

考虑特殊性质。

设 \text{tot}=\sum w。