专栏文章

[JOISC 2019] 做题记录

__MengShang_
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mincmnzs
此快照首次捕获于
2025/12/02 00:13
3 个月前
此快照最后确认于
2025/12/02 00:13
3 个月前
查看原文

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

每个人的信息 (Si,Ti)(S_i,T_i) 视为 (Si,Ti,Si+Ti)(S_i,T_i,S_i+T_i)，直接套三维偏序，排序一维，归并一维，数据结构维护一维。
CPP
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,wu,v,w 聚集的地点一定是 u,v,wu,v,w 两两求 lca\text{lca} 后深度最大的 lca\text{lca}。
设当前递归到的 root\text{root} 为 xx，在 xx 的子树中随机一个点 yy，并对 xx 子树中的所有点 zz 分别询问 (x,y,z)(x,y,z)，以确定 zz 是否在 x→yx\to y 的链上，或者在 x→yx\to y 的链上某个点的子树内。
对于链上的点可以通过一次询问比较两个点的深度，直接排序即可。
CPP
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 - 洛谷

先求出每个人的 nn 等分点。
从左到右分配馕属于谁。对于每个位置 jj，从剩余的还未被分配的人中选择最小的 xjx_j 作为 XjX_j，并把 [Xj−1,Xj][X_{j-1},X_j] 分给他。由于每次都这样分，所以必有 Xj−1≤xj−1X_{j-1}\le x_{j-1}，一定满足要求。
需要注意 xjx_j 计算的方法。
CPP
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)i,j(i<j)，若它们能够互相通信，则需要满足：
  • a[i]≤j−i≤b[i]a[i]\le j-i\le b[i]
  • a[j]≤j−i≤b[j]a[j]\le j-i\le b[j]
即
  • j∈[i+a[i],i+b[i]]j\in[i+a[i],i+b[i]]
  • i∈[j−b[j],j−a[j]]i\in[j-b[j],j-a[j]]
考虑将所有查询离线，并按照右端点 RR 排序。从 11 到 nn 扫描右端点 jj。对于每个 jj，考虑所有左端点 i<ji<j，计算它们与 jj 的通信成本，即 ∣h[i]−h[j]∣|h[i]-h[j]|。
考虑在扫描线时通过线段树维护信息。具体的，需要使它支持：
  • 单点更新：激活/失效天线。
  • 区间更新：用当前天线高度更新历史最大值。
  • 区间查询：查询历史最大值。
容易使用吉司机线段树维护（好像比板子题还水？）。
CPP
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 - 洛谷

对于每一个 PiP_i，如果其计入贡献，则在 SiS_i 分钟内要完成 IOI\text{IOI} 的第 ii 步。完成第 ii 步至少需要 ∑j=1iAj\sum_{j=1}^i A_j 的时间，从另一个角度说最多只有 Si−∑j=1iAjS_i-\sum_{j=1}^{i}A_j 的时间分给 JOI\text{JOI}。
考虑预处理：
  • yi=max⁡{j∣(∑k=1iai+∑k=1jbk)≤si}y_i=\max\left\{j|\left(\sum_{k=1}^i a_i+\sum_{k=1}^j b_k\right)\le s_i\right\}
  • xi=max⁡{j∣(∑k=1ibi+∑k=1jak)≤tj}x_i=\max\left\{j|\left(\sum_{k=1}^ib_i+\sum_{k=1}^j a_k\right)\le t_j\right\}
将原题转化为从 (0,0)(0,0) 走到 (n,m)(n,m)，每次只能 x+1→xx+1\to x 或者 y+1→yy+1\to y，则
  • 当 (i,yi)(i,y_i) 在路径上方或者在路径上时，有 pip_i 的贡献（IOI\text{IOI} 完成第 ii 步时，JOI\text{JOI} 完成不超过 yiy_i 步）；
  • 当 (xi,i)(x_i,i) 在路径下方或者在路径上时，有 qiq_i 的贡献（JOI\text{JOI} 完成第 ii 步时，IOI\text{IOI} 完成不超过 xix_i 步 ）。
一个比较 trival\text{trival} 的想法是先把所有 pip_i 计入贡献，然后把 pi←−pip_i\leftarrow -p_i，并把 yi←yi+1y_i\leftarrow y_i+1，于是可以把两类点都变为第二类计算。
令 fi,jf_{i,j} 表示从 (0,0)(0,0) 走到 (i,j)(i,j)，所有在路径上或者在路径下方的点的权值和的最大值。
记 sumi,j\text{sum}_{i,j} 表示第 ii 列中所有纵坐标 ≤j\le j 的点的权值之和，则有转移：
fi,j←max⁡{fi,j−1,fi−1,j+sumi−1,j}f_{i,j}\leftarrow \max\left\{ f_{i,j-1},f_{i-1,j}+\text{sum}_{i-1,j} \right\}
相当于 fj←fj+sumi,jf_j\leftarrow f_j+\text{sum}_{i,j} 并进行一次前缀 max⁡\max。
考虑维护 ff 的差分，每个有值的 sumi−1,j−sumi−1,j−1\text{sum}_{i-1,j}-\text{sum}_{i-1,j-1} 给 fjf_{j} 单点加。前缀取 max⁡\max 相当于把负的 f′f' 以及其后一段 ∑≤0\sum\le 0 的都变为 00，用线段树二分容易做到单 log⁡\log。
注意每个 ii 上点的排序顺序。
CPP
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 - 洛谷

转化一下题意：给定一颗 nn 个点的树，每条边为双向边，两个方向权值不同。qq 组询问，每组询问给定 kk，求任选 kk 个点，把以其为根的内向树边权改为 00 后，整棵树的边权和的最小值。
考虑特殊性质。
设 tot=∑w\text{tot}=\sum w。
k=1k=1 时，对每个点 ii 计算以它为根的内向树的边权和，即为 fif_i，答案为 tot−max⁡fi\text{tot}-\max f_i。容易换根 dp\text{dp} 线性解决。
k=2k=2 时，假设取了 u1,u2u_1,u_2 作为选定点，那么答案为
tot−fu1+fu2+dis(u1,u2)2\text{tot}-\frac{f_{u_1}+f_{u_2}+\text{dis}(u_1,u_2)}{2}
其中 dis(u1,u2)\text{dis}(u_1,u_2) 为树上两点简单路径的正反边权和，用类似求直径的二次扫描换根 dp\text{dp} 可以线性解决。
特殊性质在 k=2k=2 就结束了。猜测 k>2k>2 时的情况满足 kk 时选的点在 k+1k+1 时也选。
考虑在 k=2k=2 的基础上新增一个点，可以直接把 u1↔u2u_1\leftrightarrow u_2 缩成一个点作为根，然后每次从结点中取价值最大的加入，并删去提供贡献的边的贡献。用线段树容易维护，复杂度 O(nlog⁡n)O(n\log n)。
CPP
const int maxn = 2e5 + 5; 
int n, q; struct E{ int to; ll w1, w2; }; vector<E> e[maxn]; 
ll tot, f[maxn], ans[maxn]; // f[u]:Suppose u is root.

namespace Case1
{
ll res;
inline void dfs1(int u, int fa) { f[u] = 0; for (auto o : e[u]) if (o.to != fa) { int v = o.to; ll w2 = o.w2; dfs1(v, u); f[u]+= f[v] + w2; } }
inline void dfs2(int u, int fa) { for (auto o : e[u]) if (o.to != fa) { int v = o.to; ll w1 = o.w1, w2 = o.w2; f[v] = f[u] - w2 + w1; dfs2(v, u); } }
void work() { dfs1(1, 0); dfs2(1, 0); res = 0; rep(i, 1, n) chkmx(res, f[i]); } 
}
namespace Case2
{
int u1, u2; ll res, d[maxn]; 
inline void dfs(int u, int fa) { for (auto o : e[u]) if (o.to != fa) { int v = o.to; ll w1 = o.w1, w2 = o.w2; d[v] = d[u] + w1 + w2; dfs(v, u); } }
void work()
{
	d[1] = 0; dfs(1, 0); u1 = 0; rep(i, 1, n) if (!u1 || f[u1] + d[u1] < f[i] + d[i]) u1 = i;
	d[u1] = 0; dfs(u1, 0); u2 = 0; rep(i, 1, n) if (!u2 || (u1 != u2 && f[u2] + d[u2] < f[i] + d[i])) u2 = i;
	res = (f[u1] + f[u2] + d[u2]) / 2;
}
}
namespace Case3
{
int u1, u2, vis[maxn], dfn[maxn], pos[maxn], siz[maxn], fat[maxn], tim = 0; ll d[maxn], ver[maxn], res; 
inline void dfs1(int u, int fa) { if (u == u2) return vis[u] = 1, void(); for (auto o : e[u]) if (o.to != fa) { int v = o.to; dfs1(v, u); vis[u]|= vis[v]; } }
inline void dfs2(int u, int fa) { fat[u] = fa; siz[u] = 1; dfn[u] = ++tim; pos[tim] = u; for (auto o : e[u]) if (o.to != fa) { int v = o.to; dfs2(v, u); siz[u]+= siz[v]; } }
inline void dfs3(int u, int fa) { if (vis[u]) d[u] = 0; for (auto o : e[u]) if (o.to != fa) { int v = o.to; ll w1 = o.w1; d[v] = d[u] + w1; dfs3(v, u); if (!vis[v]) ver[v] = w1; else ver[v] = 0; } }
#define ls (p << 1)
#define rs (ls | 1)
struct Node{ ll val, tag; int nd; } t[maxn << 2];
Node operator + (const Node& x, const Node& y) { if (x.val > y.val) return {x.val, 0, x.nd}; else return {y.val, 0, y.nd}; }
inline void update(int p) { t[p] = t[ls] + t[rs]; }
inline void add(int p, ll d) { t[p].val-= d; t[p].tag+= d; }
inline void pushdown(int p) { if (t[p].tag) { add(ls, t[p].tag); add(rs, t[p].tag); t[p].tag = 0; } }
inline void build(int p, int l, int r) { if (l == r) return t[p] = {d[pos[l]], 0, pos[l]}, void(); int mid = l + r >> 1; build(ls, l, mid); build(rs, mid + 1, r); update(p); }
inline void modify(int p, int l, int r, int L, int R, ll d)
{
	if (l > R || r < L) return; if (l >= L && r <= R) return add(p, d), void(); 
	int mid = l + r >> 1; pushdown(p); modify(ls, l, mid, L, R, d); modify(rs, mid + 1, r, L, R, d); update(p);
}
void work()
{
	mems(vis, 0); dfs1(u1, 0); dfs2(u1, 0); dfs3(u1, 0); build(1, 1, n); 
	res = ans[2]; 
	for (int k = 3; k <= n; ++k) 
	{ 
		if (res == 0) { ans[k] = 0; continue; }
		Node o = t[1]; int u = o.nd; res-= o.val; ans[k] = res; 
		int x = u; while (x && !vis[x]) { modify(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, ver[x]); vis[x] = 1; x = fat[x]; } 
	}
}
}

int main()
{
	read(n); rep(i, 2, n) { int u, v; ll w1, w2; read(u, v, w1, w2); e[u].pbk({v, w1, w2}); e[v].pbk({u, w2, w1}); tot+= w1 + w2; }
	Case1::work(); ans[1] = tot - Case1::res; 
	Case2::work(); ans[2] = tot - Case2::res; 
	Case3::u1 = Case2::u1; Case3::u2 = Case2::u2; Case3::work();
	read(q); rep(i, 1, q) { int x; read(x); write(ans[x]); pc(0xa); }
	return 0; 
}

P14347 [JOISC 2019] 灯 / Lamps - 洛谷

每个位置不被两个赋值操作覆盖一定不劣。
如果只有翻转操作，则答案即为 a xor ba\text{ xor }b 的极长 11 段的个数。
考虑加了赋值操作后，每个位置的操作可以为：
  • 不操作；
  • 仅翻转；
  • 使用一次赋值 00 并翻转；
  • 使用一次赋值 11 并翻转。
因此定义 f[i][0/1][0/1][0/1]f[i][0/1][0/1][0/1] 表示处理完第 ii 个位置，是否使用了翻转操作，是否使用赋值 00 的操作，是否使用赋值 11 的操作，可以直接转移，复杂度线性。
（直接状压或许会好写一些？）
CPP
const int maxn = 1e6 + 5, inf = 0x3f3f3f3f; 
int n, a[maxn], b[maxn], f[maxn][2][2][2], ans = inf; 

int main()
{
	read(n); char ch = gc();
	while (!isdigit(ch)) ch = gc(); rep(i, 1, n) a[i] = ch ^ 0x30, ch = gc(); 
	while (!isdigit(ch)) ch = gc(); rep(i, 1, n) b[i] = ch ^ 0x30, ch = gc();
	mems(f, 0x3f); f[0][0][0][0] = 0; 
	rep(i, 1, n) rep(j, 0, 1) rep(k, 0, 1) rep(l, 0, 1) if (f[i - 1][j][k][l] < inf)
	{
		int d; 
		d = b[i] == 0; chkmn(f[i][d][1][0], f[i - 1][j][k][l] + (d && j == 0) + (k == 0));
		d = b[i] == 1; chkmn(f[i][d][0][1], f[i - 1][j][k][l] + (d && j == 0) + (l == 0)); 
		d = a[i] ^ b[i]; chkmn(f[i][d][0][0], f[i - 1][j][k][l] + (d && j == 0));
	}
	rep(j, 0, 1) rep(k, 0, 1) rep(l, 0, 1) chkmn(ans, f[n][j][k][l]);
	write(ans); pc(0xa); 
	return 0; 
}

P14348 [JOISC 2019] 穿越时空 Bitaro / Bitaro, who Leaps through Time - 洛谷

瞪了半天发现这不是树而是链。
考虑每次从 AA 到 CC 的最优策略，显然是直接从 AA 向 CC 走，如果走不了就等待或者用技能直到能走。
特判 A=CA=C。
不妨先令 A<CA<C，那么令每条道路的 li←li−i,ri←ri−(i+1)l_i\leftarrow l_i-i,r_i\leftarrow r_i-(i+1)，并相应地改变询问，那么约束就变为一条道路只能在时间 [li,ri][l_i,r_i] 经过，且经过不需要花费。
一个显然的性质是如果一段区间 max⁡{li}>min⁡{ri}\max\{l_i\}>\min\{r_i\}，那么这条路的走法是固定的。
对于每个区间，记录一个四元组 (o,l,r,w)(o,l,r,w)，oo 记录路径是否唯一，如果唯一，那么从 ll 进入，rr 出来的最小代价是 ww；否则只要从 [l,r][l,r] 进入道路就无代价消耗，即 l=max⁡{li},r=min⁡{ri}l=\max\{l_i\},r=\min\{r_i\}。
推一推两个路径的合并，发现有结合律，直接线段树维护，修改是容易的。
注意特判 n=1n=1 的情况。
CPP
const int maxn = 3e5 + 5; const ll inf = 1e18;
int n, q; ll al[maxn], ar[maxn]; 
inline bool chk(ll xl, ll xr, ll yl, ll yr) { return max(xl, yl) <= min(xr, yr); }
inline ll calc(ll x, ll y) { return x > y ? x - y : 0; }
struct Node{ int o; ll il, ir, w; };
inline Node operator + (const Node& x, const Node& y)
{
	Node z;
	if (x.o && y.o) z = {1, x.il, y.ir, x.w + y.w + calc(x.ir, y.il)};
	else if (x.o) 
	{
		if (chk(x.ir, x.ir, y.il, y.ir)) z = {1, x.il, x.ir, x.w};
		else if (x.ir < y.il) z = {1, x.il, y.il, x.w}; 
		else z = {1, x.il, y.ir, x.w + (x.ir - y.ir)};
	}
	else if (y.o)
	{
		if (chk(x.il, x.ir, y.il, y.il)) z = {1, y.il, y.ir, y.w};
		else if (x.ir < y.il) z = {1, x.ir, y.ir, y.w};
		else z = {1, x.il, y.ir, y.w + (x.il - y.il)};
	}
	else 
	{
		if (chk(x.il, x.ir, y.il, y.ir)) z = {0, max(x.il, y.il), min(x.ir, y.ir), 0};
		else if (x.ir < y.il) z = {1, x.ir, y.il, 0};
		else z = {1, x.il, y.ir, (x.il - y.ir)};
	}
	return z;
}

namespace Case1 // A < C, i->i+1
{
#define ls (p << 1)
#define rs (ls | 1)
Node t[maxn << 2];
inline void update(int p) { t[p] = t[ls] + t[rs]; }
inline void build(int p, int l, int r) { if (l == r) return t[p] = {0, al[l] - l, ar[l] - l - 1, 0}, void(); int mid = l + r >> 1; build(ls, l, mid); build(rs, mid + 1, r); update(p); }
inline void modify(int p, int l, int r, int x, ll dl, ll dr) 
{ 
	if (l == r) return t[p] = {0, dl, dr, 0}, void();
	int mid = l + r >> 1; if (mid >= x) modify(ls, l, mid, x, dl, dr); else modify(rs, mid + 1, r, x, dl, dr); update(p);
}
inline Node query(int p, int l, int r, int L, int R)
{
	if (l > R || r < L) return {0, -inf, inf, 0ll}; if (l >= L && r <= R) return t[p]; 
	int mid = l + r >> 1; return query(ls, l, mid, L, R) + query(rs, mid + 1, r, L, R);  
}
void init() { build(1, 1, n - 1); } 
}
namespace Case2 // A > C, i+1->i
{
#define ls (p << 1)
#define rs (ls | 1)
Node t[maxn << 2];
inline void update(int p) { t[p] = t[rs] + t[ls]; }
inline void build(int p, int l, int r) { if (l == r) return t[p] = {0, al[l] - (n - l - 1), ar[l] - (n - l), 0}, void(); int mid = l + r >> 1; build(ls, l, mid); build(rs, mid + 1, r); update(p); }
inline void modify(int p, int l, int r, int x, ll dl, ll dr) 
{ 
	if (l == r) return t[p] = {0, dl, dr, 0}, void();
	int mid = l + r >> 1; if (mid >= x) modify(ls, l, mid, x, dl, dr); else modify(rs, mid + 1, r, x, dl, dr); update(p);
}
inline Node query(int p, int l, int r, int L, int R)
{
	if (l > R || r < L) return {0, -inf, inf, 0ll}; if (l >= L && r <= R) return t[p]; 
	int mid = l + r >> 1; return query(rs, mid + 1, r, L, R) + query(ls, l, mid, L, R);  
}
void init() { build(1, 1, n - 1); }
}

inline ll merge(const ll &x, const Node& y, const ll& z)
{
	if (y.o == 0)
	{
		if (x > y.ir && z > y.ir) return x - y.ir;
		if (x < y.il && z < y.il) return y.il - z;
		return calc(x, z);
	}
	else
	{
		return y.w + calc(x, y.il) + calc(y.ir, z);
	}
}

int main()
{
	read(n, q); rep(i, 1, n - 1) read(al[i], ar[i]);
	if (n > 1) Case1::init(), Case2::init(); 
	rep(i, 1, q)
	{
		int opt; read(opt); 
		if (opt == 1) 
		{ 
			int x; ll y, z; read(x, y, z); 
			Case1::modify(1, 1, n - 1, x, y - x, z - x - 1); 
			Case2::modify(1, 1, n - 1, x, y - (n - x - 1), z - (n - x)); 
		}
		else 
		{
			int a, c; ll b, d; read(a, b, c, d);
			if (a == c) { write(b > d ? b - d : 0); pc(0xa); }
			else if (a < c)
			{
				b = b - a; d = d - c; Node tmp = Case1::query(1, 1, n - 1, a, c - 1);
				ll res = merge(b, tmp, d); write(res); pc(0xa); 
			}
			else 
			{
				b = b - (n - a); d = d - (n - c); Node tmp = Case2::query(1, 1, n - 1, c, a - 1);
				ll res = merge(b, tmp, d); write(res); pc(0xa); 
			}
		}
	}
	return 0; 
}

P14349 [JOISC 2019] 蛋糕 3 / Cake 3 - 洛谷

对于一组选定的 {ki}\{k_i\}，交换两个 kk 的位置不会影响 ∑V\sum V，只会影响 ∑∣Ckj−Ckj+1∣\sum|C_{k_j}-C_{k_{j+1}}|。
考虑 {ki}\{k_i\} 的 CC 具有单调性。考虑先把 nn 块蛋糕按 CiC_i 升序排序，记选中的序列为 {ki}\{k_i\}，最终答案为 ans\text{ans}，有:
ans=(∑Vki)−(∑∣Cki−Cki+1∣)=(∑Vki)+(∑Cki−Cki+1)=(∑Vki)+2×(Ck1−Ckm)\begin{split} \text{ans}=&\left(\sum V_{k_i}\right)-\left(\sum |C_{k_i}-C_{k_{i+1}}|\right)\\ =&\left(\sum V_{k_i}\right)+\left(\sum C_{k_i}-C_{k_{i+1}}\right)\\ =&\left(\sum V_{k_i}\right)+2\times (C_{k_1}-C_{k_m}) \end{split}
记 w(l,r)w(l,r) 为强制选择 ll 作为左端点，rr 作为右端点，在 (l,r)(l,r) 中选 m−2m-2 个 VV 的最大价值，即 (∑Vki)+2×(Ck1−Ckm)\left(\sum V_{k_i}\right)+2\times (C_{k_1}-C_{k_m})，答案即为 max⁡w\max w。
考虑如果区间 [l,r][l,r] 是答案区间，那么 (l,r)(l,r) 中的第 m−1m-1 大的 VV 应该小于 VlV_l 和 VrV_r，否则就能剔除 ll 或 rr 使极差减小，且 ∑V\sum V 不降，更优。
因此修改 w(l,r)w(l,r) 的定义，为选取 [l,r][l,r] 中前 mm 大的 VV，其位置集合 SS，w(l,r)=∑i∈SVi−2×(Cr−Cl)w(l,r)=\sum_{i\in S}V_i-2\times (C_r-C_l)。
显然该式满足四边形不等式，w(l,r)+w(l+1,r−1)≤w(l+1,r)+w(l,r−1)w(l,r)+w(l+1,r-1)\le w(l+1,r)+w(l,r-1)，因为左右式 CC 项抵消，分类讨论 VlV_l 和 VrV_r 与 (l,r)(l,r) 中 VV 的大小关系易得该式的 ∑V\sum V 左式不大于右式。
因此，随着右端点 rr 的增加，使答案最优的左端点 ll 不会下降，直接分治即可，时间复杂度 O(nlog⁡2n)O(n\log^2n)。
CPP
const int maxn = 2e5 + 5; const ll inf = 1e18;
int n, m; struct Node{ ll v, c; } a[maxn];
ll ans = -inf, sum = 0;
multiset<ll> st1, st2; // used / re
int curl = 1, curr = 0; 
inline void add(ll x)
{
	st1.insert(x); sum+= x; if ((int)st1.size() <= m) return; 
	auto it = st1.begin(); sum-= *it; st2.insert(*it); st1.erase(it);
} 
inline void del(ll x)
{
	auto it = st1.find(x); 
	if (it != st1.end())
	{
		sum-= *it; st1.erase(it); 
		if (st2.size()) { auto it2 = st2.end(); --it2; sum+= *it2; st1.insert(*it2); st2.erase(it2); }
	}
	else 
	{
		it = st2.find(x); if (it != st2.end()) st2.erase(it);
	}
}
inline ll w(int l, int r)
{
	while (curl > l) add(a[--curl].v);
	while (curr < r) add(a[++curr].v);
	while (curr > r) del(a[curr--].v);
	while (curl < l) del(a[curl++].v);
	if ((int)st1.size() < m) return -inf; 
	return sum - 2ll * (a[r].c - a[l].c);
}

inline void divide(int l, int r, int pl, int pr)
{
	if (l > r || pl > pr) return; 
	int mid = l + r >> 1, p = pl; ll res = -inf;
	for (int i = pl; i <= min(pr, mid); ++i)
	{
		ll cur = w(i, mid); if (cur > res) p = i, res = cur;
	}
	chkmx(ans, res); 
	divide(l, mid - 1, pl, p);
	divide(mid + 1, r, p, pr);
}

int main()
{
	read(n, m); rep(i, 1, n) read(a[i].v, a[i].c); 
	sort(a + 1, a + n + 1, [](const Node& x, const Node& y) { return x.c < y.c; });
	divide(1, n, 1, n); 
	write(ans); pc(0xa); 
	return 0; 
}

P14350 [JOISC 2019] 合并 / Mergers - 洛谷

把同一个组的城市缩成一个点，再跑 tarjan\text{tarjan} 边双缩点。此时把树变得不可分即在新树上连边使得整张图边双连通。
最优操作显然是把度数为 11 的点两两连边，答案显然。
CPP
const int maxn = 5e5 + 5; 
int n, K, lst[maxn]; 
struct E{ int to, nxt; };
E e1[maxn << 2]; int hd1[maxn], ct1 = 1; inline void add1(int u, int v) { e1[++ct1] = {v, hd1[u]}; hd1[u] = ct1; } 
E e2[maxn << 1]; int hd2[maxn], ct2 = 1; inline void add2(int u, int v) { e2[++ct2] = {v, hd2[u]}; hd2[u] = ct2; }

int dfn[maxn], low[maxn], tim, bok[maxn << 2], pos[maxn], tot; 
inline void tarjan(int u, int fa)
{
	dfn[u] = low[u] = ++tim; 
	for (int o = hd1[u]; o; o = e1[o].nxt) if (e1[o].to != fa)
	{
		int v = e1[o].to;
		if (!dfn[v])
		{
			tarjan(v, u); chkmn(low[u], low[v]);
			// cerr << u << ' ' << v << ' ' << low[v] << ' ' << dfn[u] << endl;
			if (low[v] > dfn[u]) bok[o] = bok[o ^ 1] = 1;
		}
		else chkmn(low[u], dfn[v]);
	}
}
inline void dfs(int u)
{
	pos[u] = tot;
	for (int o = hd1[u]; o; o = e1[o].nxt) if (!bok[o]) { int v = e1[o].to; if (!pos[v]) dfs(v); } 
}

int main()
{
	read(n, K); 
	rep(i, 2, n) { int u, v; read(u, v); add1(u, v); add1(v, u);  }
	rep(i, 1, n) { int x; read(x); if (lst[x]) add1(i, lst[x]), add1(lst[x], i); lst[x] = i; }
	tarjan(1, 0); rep(i, 1, n) if (!pos[i]) ++tot, dfs(i);
	rep(u, 1, n) for (int o = hd1[u]; o; o = e1[o].nxt) { int v = e1[o].to; if (pos[u] != pos[v]) add2(pos[u], pos[v]); }
	int ans = 0; rep(u, 1, tot) { int cnt = 0; for (int o = hd2[u]; o; o = e2[o].nxt) ++cnt; if (cnt == 1) ans++; }
	write((ans + 1) / 2); pc(0xa); 
	return 0; 
}

P14351 [JOISC 2019] 矿物 / Minerals - 洛谷

交互题。咕咕咕~

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...