APIO

[APIO 2016] Fireworks

给一棵n个内部结点, m个叶子的有根树, 边带权ci. 修改边权, 使所有叶子到根的距离相等, 求最小代价. 将c修改为c' (c'≥0), 代价为abs(c-c'). (1≤n+m≤3*10^5, 1≤ci≤10^9) Link: WMD 神犇在 APIO 2016 时讲题的课件

Read More

APIO

[APIO 2013] TOLL

N个点M条边的无向连通图, 边带权且权值各不相同, 点也带权. 现有另外K条权值待定的边 (端点已知). 确定它们的权值, 使得: 取该图的某棵最小生成树, 每个点沿树边走向1号点, 点权与途经的新边边权之积的总和 (收益) 最大. 输出这个最大的和. (N≤10^5, M≤3*10^5 且 K≤20)

Read More

APIO

[APIO 2013] ROBOTS

h*w的网格图, 障碍不可通行, 逆/顺时针转向器强制通过者转向, n个机器人. 多个机器人可占同一个格子, 并且不会挡路. 机器人不能自发移动或停止, 可以横向或纵向推它一把, 它会沿直线移动直到碰到边界或障碍物. 机器人的编号是一个区间[l,r], [l,m]和[m+1,r]可以合并成机器人[l,r]; 初始编号[i,i] (1≤i≤n). 静止时, 机器人会自动合并. 给出网格图 (空地, 障碍, 转向器, 机器人), 问最少推多少次, 机器人可合并成[1,n], 或报告无解. (n≤9, w,h≤500)

Read More

APIO

[APIO 2015] Jakarta Skyscrapers

n座摩天楼, n只doge. 每只doge有初始位置B[i]和跳跃能力P[i], 收到消息后, 位于摩天楼b的i号doge可以: - 跳到b-P[i], b+P[i] (如果不越界) - 把消息传递给当前摩天楼上的其他doge

求0号doge将消息传给1号doge所需的最少跳跃总步数. (0≤Bi<n, 1≤n≤30000, 1≤Pi≤30000, 2≤m≤30000)

Read More

APIO

[APIO 2015] Bali Sculptures

一个长度为n的序列Yi, 将其分为不少于A且不多于B组, 求每组元素之和按位取或的最小值. - 子任务 1 （9 分）1≤N≤20, 1≤A≤B≤N, 0≤Yi≤1000000000 - 子任务 2 （16 分）1≤N≤50, 1≤A≤B≤min{20,N}, 0≤Yi≤10 - 子任务 3 （21 分）1≤N≤100, A=1, 1≤B≤N, 0≤Yi≤20 - 子任务 4 （25 分）1≤N≤100, 1≤A≤B≤N, 0≤Yi≤1000000000 - 子任务 5 （29 分）1≤N≤2000, A=1, 1≤B≤N, 0≤Yi≤1000000000

Read More

APIO

[APIO 2014] Beads and wires

n个珠子, 两种操作: - Append(w, v): 将一个新的珠子w和一个已添加的珠子v用红线连起来 - Insert(w, u, v): w是新珠子, u,v是已添加的由红线连接的珠子; 删掉u,v之间的红线, 用两条蓝线分别连接w和u,v

最终得分为蓝线长度之和. 给出结束局面 (珠子的连接方式, 线的长度, 颜色未知), 求最大可能得分. (1≤n≤2*10^5)

Read More