ICPC WF 题目翻译
快乐的大童
·
·
个人记录
WF 题目编排疑似按照题名字典序升序排序
A. Billboards
有 n 个人和一个长度为 l 的线段，每个人对这条线段的每一部分的喜好程度可以用一个分段一次函数来表示，输入中给出 m_i 个 (a_j,b_j)，表示第 i 个人的喜好程度被分为了 m_i-1 段，第 j 段一次函数的两个端点是 (a_j,b_j) 和 (a_{j+1},b_{j+1})。
你现在需要将线段分成 n 部分并分给这 n 个人，使得每个人对 分得的那部分线段的喜好值 和 整个线段的喜好值之和 的比值至少是 \frac{1}{n}。求出一种可能的构造，无解输出 impossible。
-
1\le n\le 5000,1\le l\le 10^6,2\le m\le 5000,\sum m\le 5\times10^5
-
0=a_1<a_2<\cdots<a_{m_i-1}<a_{m_i}=l,0\le b_i\le 100$，保证对于每个人，其必定存在一个 $>0$ 的 $b_i
B. Bingo for the Win!
有 n 个人参加一场比赛，每个人手里有 k 个数 a_{i,j}。
一个回合中，主持人会随机在场上所有还没有被抹除的数中均匀随机选择一个整数，那么编号最小的且手里有这个数的人会响应，并把手里的对应的那个数抹掉。若一个人手里的数都被抹掉了，那么这个人就胜利了，游戏直到所有人都胜利时结束。
求每个人最后一个胜利的概率。
1\le n\le 100,1\le k\le 1000,1\le a_{i,j}\le 10^9
C. Citizenship
你想要成为一个国家的公民，而成为这个国家的公民需要在该国居住至少 y 年（从申请日期开始倒推），且每一年至少在该国居住至少 d 天。
你在这期间进行了 n 次旅行，每次旅行给出起始日期和终止日期（左闭右闭），旅行期间不算在该国居住。
求最早什么时候你能成为该国公民，此日期必须要晚于最后一次旅游结束的日期。
该国的日历是没有闰年的公历，即每年固定 365 天，2 月固定 28 天。
- 所有日期均用
YYYY-MM-DD 形式表述。
-
1\le n\le 500,1\le y\le 1000,1\le d\le 365
-
D. Doubles Horseback Wrestling
有 n 个点和一个固定参数 s，每个点有一个点权区间 [l_i,u_i]，定义两个点 i,j 能匹配当且仅当 \exists \ l_i\le x\le u_i,l_j\le y\le u_j,x+y=s。求最大匹配。
2\le n\le 2\times10^5,1\le s\le 10^9,1\le l_i\le u_i\le 10^9
E. Flipping Container
你有一个集装箱，长宽高分别为 a,b,c，你可以把集装箱沿其底部的四条边中的一条翻滚 90 度。你现在想要将集装箱往 x 轴正方向和 y 轴正方形分别平移 x,y 个单位长度，求最小步数，无解输出 impossible。
-
1\le a,b,c\le 1000
-
-
|x|,|y|\le 10^{18}
F. Friendly Rivalry
给定 2n 个点 (x_i,y_i)，你现在想要把这 2n 个点划分成两个集合 A,B，使得：
输出该最大值并构造方案。
1\le n\le 500,|x_i|,|y_i|\le 10^9
G. Kindergarten
现在有 n 个人，每个人有一个他讨厌的人 j_i 和一个他喜欢的人 l_i，你现在要把这 n 个人按一个顺序排起来，如果存在一个 i 使得 j_i 排在 i 的后面且 l_i 不排在 i 后面，那么就会发生混乱。
你需要构造一个不会发生混乱的排列方案，无解输出 impossible。
### H. Maxwell’s Demon
_前言：解决这个问题不需要热力学知识。_
现在有一个长为 $h$ 宽为 $2w$ 的矩形，在宽为 $w$ 的地方有一堵墙，不难发现这堵墙将矩形分成了 $h\times w$ 的两部分
形式化的，在平面直角坐标系上有一个 $h\times 2w$ 的矩形，左上角在 $(-w,h)$，右下角在 $(w,0)$，在矩形边界（$y=-w,w$ 和 $x=n,0$）和 $y$ 轴处有一堵墙。
现在有 $r$ 个红球和 $b$ 个蓝球，每个球有起点 $(p_x,p_y)$ 和速度 $(v_x,v_y)$。一般情况下，一个球碰到墙壁会被反弹回去，但是如果有若干个球在 $(0,d)$ 处，你可以选择把所有在此处的球从此处透过去，或者选择把所有在此处的球按一般情况反弹回去。
你现在想要让所有红球都在左矩形里，所有蓝球都在右矩阵里，问最早时间，无解输出 `impossible`。
- $2\le w,h\le 200,0\le d\le h,1\le r+b\le 200,r,b\ge 0
-
0<|p_x|<w,0<p_y<h,|v_x|<w,|v_y|<h,(v_x,v_y)\not =0
I. Steppe on It
https://www.luogu.com.cn/problem/P8314
J. The Silk Road ... with Robots!
给定一条无限长的数轴，数轴上会有一些机器人和一些商店。商店会有权值 w_i。一个机器人移动一单位距离有 1 的花费。若存在至少一个机器人和商店在同一位置，则获得 w_i 的利润，同时商店的权值被重置为 0（即只能被取一次），你需要算出最终你能获得的利润减去花费的最大值是多少。
- `1 x`：在 $x$ 处出现了一个机器人。保证初始没有两个机器人在同一位置，但是可以出现中途中多个机器人在同一位置的情况。
- `2 x c`：在 $x$ 处出现了一个商店，其权值为 $c$。
- 每次操作后查询前文所述的问题的答案。
- 询问之间独立。
$q\le 2\times10^5,0\le x,c\le 10^8
K. Tower of noiHa
假设有一个 n 个圆盘的汉诺塔问题。
你先做了 k 步最优解（众所周知汉诺塔最优解为 2^n-1 且唯一），然后，你一次性的将所有在第一根柱子上的所有圆盘都放在了第三根柱子上（即使原来第一根柱子上最底下的圆盘比第三根柱子的最上面的圆盘更大）。你现在想要求出完成汉诺塔问题（把所有柱子按照大小顺序放在第三根柱子上）的最小步数。
$1\le n\le2\times10^5,0\le k\le 2^n-1
L. Where Am I Now?
这是一道交互题。
有一张 r\times c 的地图，有一些格子是空地，有一些格子是墙。你初始知道这张地图的形态。
你初始在某一个位置，面朝某一个方向，你不知道你的位置和方向。你可以操纵你自己做出如下操作：
left：向左旋转 90 度。right：向右旋转 90 度。step：向当前方向前进一格。yes x y：表示你知道你当前所在位置是 (x,y)。no：表示你无论如何都不可能知道你在哪里。
每次操作过后（回答操作除外）交互库返回当前方向上距离你最近的墙壁的距离是多少（约定若面前就是墙壁则距离为 0）。
你不能使用 step 操作走到墙里，且操作次数不能超过 10^5（回答操作算进操作次数）。
1\le r,c\le 100