算法竞赛入门

背景

网址：https://oj.neupioneer.team/
账号密码均为学号，登陆后请修改密码，发现密码不正确或任何有关网站本身或题目问题的，请在群里私聊负责oj的管理员解决
在AI时代，算法能力也逐渐沦为计算机领域非物质文化遗产，但是与此同时，掌握算法思想的含金量却是在不断地提高。在大学阶段，无论是在学业成绩，各类面试机试中得到理想的成绩，还是在XCPC等竞赛领域赢得奖牌，学习算法思想提升算法能力仍然是很关键的。
以下的题目可能对于刚入门的同学比较难，希望同学可以努力尝试攻克，建议在完成编程基础部分后再来尝试以下内容。
注意：解决算法问题在于思考的过程而不是通过的结果，没有思考的算法题毫无价值，哪怕没有做出但是努力地去尝试理解和学习也是值得的。
我们不排斥使用AI去辅助理解和学习算法内容，但是不可以完全依赖AI，比如直接提交AI生成的代码。我们鼓励多尝试提交，但是同时我们会对提交内容中可能存在的AI成分进行审核，不要把自己的思想完全交给AI，百害而无一利

题目一：活泼的纯情小姑娘

• 时间限制：1.5 秒
• 内存限制：256 MB

题目描述

去年，冰精琪露诺在上课时偷偷使用了符卡冻符「Perfect Freeze」，结果被老师狠狠教训了一顿。但她不长记性，还是想再玩一次。
这一次，琪露诺冻结了 N 个弹幕（1 ≤ N ≤ 10000），并把它们排成一列，从第一个开始按周期报数。现在她忘记了到底冻结了多少个弹幕，只记得四种不同的报数周期下，最后一个弹幕（第 N 个）报到数分别是多少。请你根据这些信息，帮她算出冻结的弹幕总数。
设最后一个弹幕报到的数为 N 对周期取模的余数。具体地：
• 以 Ax 为报数周期，最后一个弹幕报到的数为 Ay，即 N mod Ax = Ay；
• 以 Bx 为报数周期，最后一个弹幕报到的数为 By，即 N mod Bx = By；
• 以 Cx 为报数周期，最后一个弹幕报到的数为 Cy，即 N mod Cx = Cy；
• 以 Dx 为报数周期，最后一个弹幕报到的数为 Dy，即 N mod Dx = Dy。
题目保证存在一个满足上述全部四个条件的正整数 N（1 ≤ N ≤ 10000）。如果存在多个满足条件的 N，请输出最小的那一个。

输入格式

输入共四行，每行两个整数，分别对应一组（周期，余数）：
Ax Ay
Bx By
Cx Cy
Dx Dy
数据范围：
• 1 ≤ Ax, Bx, Cx, Dx < 20
• 0 ≤ Ay < Ax，0 ≤ By < Bx，0 ≤ Cy < Cx，0 ≤ Dy < Dx

输出格式

输出一行一个整数：满足条件的弹幕总数 N。若存在多个，输出最小的一个。

样例

输入：

1
2
3
4

2 1  
6 3  
5 1  
4 1

输出：

1

21

样例解释

取 N = 21：
• 21 mod 2 = 1
• 21 mod 6 = 3
• 21 mod 5 = 1
• 21 mod 4 = 1
四个条件全部满足，且不存在比 21 更小的可行答案。

题目二：飞翔在宇宙的不可思议的巫女

• 时间限制：2 秒
• 内存限制：512 MB

题目描述

乐园的巫女博丽灵梦正在梦境世界中穿梭，寻找梦境的管理者哆来咪。众所周知，哆来咪所在的梦境世界，地面上布满了网格，因此可以把梦境世界看作一张带网格的二维地图。博丽灵梦最初位于点 (0, 0)，而她想要找到的哆来咪位于点 (x, y)。
灵梦每次移动的位移由一个向量 (a, b) 描述：一次移动中，她沿第一坐标移动 a 个单位，同时沿第二坐标移动 b 个单位。初始时灵梦处于静止状态，即 (a, b) = (0, 0)。
灵梦连续地进行移动。每一次移动执行以下两个操作：

1. 在当前位移向量 (a, b) 的基础上，必须将 a、b 中恰好一个的值增加 1；
2. 然后灵梦从点 (p, q) 飞到点 (p + a, q + b)。
   a 和 b 的值只能增加，不能减少。
   由于梦境世界的范围有限，它由矩形 [0, x] × [0, y] 表示。如果灵梦在某次移动后离开了这个矩形区域，她就会进入不稳定的空间区域并被摧毁。
   灵梦可以在任意多次移动之后结束旅程。由于不一定能准确到达哆来咪所在的位置，她希望停在一个有效点上（有效点指落在矩形 [0, x] × [0, y] 内的点，包含边界），并且该点离目标点 (x, y) 尽可能近。具体地，她希望 (p − x)² + (q − y)² 的值尽可能小。
   请你帮助灵梦选择移动的次数，并决定每次移动是增加 a 还是增加 b，使她的终点是一个使 (p − x)² + (q − y)² 最小的有效点。

输入格式

每个测试包含多个测试用例。第一行包含一个整数 t（1 ≤ t ≤ 100），表示测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的一行包含两个整数 x 和 y（1 ≤ x, y ≤ 10^8）——哆来咪所在位置（目标点）的坐标。

输出格式

对每个测试用例，输出一行由字符 X 和 Y 组成的字符串 s，描述灵梦的最佳行程。
字符串 s 的长度必须等于移动次数。字符 s_i 描述灵梦在第 i 次移动中的行动：
• 若 s_i = X，则灵梦将 a 增加 1，然后用得到的向量进行移动；
• 若 s_i = Y，则灵梦将 b 增加 1，然后用得到的向量进行移动。
字符串描述的行程必须满足题目中的全部条件，并且终点到目标点 (x, y) 的欧氏距离平方尽可能小。可以证明，在题目限制下，任意最优答案包含的移动次数都不超过 20000。如果存在多个最优答案，输出其中任意一个。

样例

输入：

1
2
3
4
5
6
7
8

7  
1 1  
2 1  
4 2  
5 4  
3 7  
1 100  
231 157

输出：

1
2
3
4
5
6
7

X  
XY  
XYX  
XYY  
YXYY  
YYYYYYYYYYYYY  
XXXXXXXXXXYYYYYYYYYYYYYYYYX

样例解释

测试用例 1： 字符串 X 描述一次移动。灵梦将 a 增加 1，然后从 (0, 0) 移动到 (1, 0)。到目标点 (1, 1) 的距离平方为 (1−1)² + (0−1)² = 1。
测试用例 2： 字符串 XY 把灵梦准确带到了目标点：
(0, 0) → (1, 0) → (2, 1)
测试用例 3： 字符串 XYX 描述的移动序列为：
(0, 0) → (1, 0) → (2, 1) → (4, 2)
灵梦准确到达了目标点 (4, 2)。
测试用例 4： 字符串 XYY 把灵梦带到了点 (3, 3)。到目标点 (5, 4) 的距离平方为 (3−5)² + (3−4)² = 5。另一个最优答案，例如 XYX，可以把灵梦带到点 (4, 2)。

题目三：芥川龙之介的河童

• 时间限制：2 秒
• 内存限制：512 MB

题目描述

为了增加守矢神社的信仰，八坂神奈子邀请河城荷取为神社修建御柱。一根御柱由若干楼层组成。
荷取的初始资金是 个黄瓜（对河童来说是一种非常宝贵的货币）。共有 根可供建造的御柱，编号为 到 。每根御柱的建造相互独立、互不影响；目前还没有任何御柱开始建造。
为了建造第 根御柱的第 层，需要花费 个黄瓜；建造完成后，荷取会立即收到 个黄瓜，并加入她的预算中，可用于建造任何御柱的楼层。注意，同一根御柱的楼层必须按编号从小到大依次建造：必须先建好第 1 层，才能建造第 2 层，依此类推。
由于神奈子非常狡诈，并非所有合同都一定有利可图，甚至可能存在 的情况（即建造该层反而会亏损）。
荷取可以自由安排建造顺序：她可以在不同御柱之间任意切换，也可以在建造过程中穿插任意数量的其他合同。她不需要建造所有楼层，甚至可以完全不建造任何楼层。
荷取的目标是让其中一根御柱建得尽可能高。请你帮助荷取规划建造方案，求出她能让御柱达到的最大层数，以及能达到该层数的御柱中最小的编号。

输入格式

每个测试包含多个测试用例。第一行包含一个整数 （），表示测试用例的数量。
每个测试用例的格式如下：
• 第一行包含两个整数 和 （，）——御柱的数量和初始资金；
• 接下来是 n 根御柱的描述，第 i 根御柱的描述为：
◦ 第一行包含一个整数 （）——该御柱最多可建造的层数；
◦ 第二行包含 个整数 ——建造各层需要的花费；
◦ 第三行包含 个整数 ——建造各层后立即收到的黄瓜数。
其中 。保证所有测试用例的 之和不超过 。

输出格式

对每个测试用例，输出一行两个整数：荷取能让御柱达到的最大层数 ，以及能达到层数 的御柱中最小的编号。

样例

输入：

1
2
3
4
5
6
7
8
9
10
11
12

2  
1 6  
4  
4 4 2 1  
2 4 1 1  
2 3  
2  
4 4  
5 5  
2  
2 20  
4 0

输出：

1
2

4 1  
2 1

样例解释

测试用例 1： 资金足够依次建造唯一一根御柱的全部 4 层，所以答案是 4 1。
测试用例 2： 可以先建造第 2 根御柱的第 1 层（花费 2，得到 4，净赚 2 个黄瓜），此时资金变为 5；再依次建造第 1 根御柱的两层（共花费 8，共得到 10，净赚 2），第 1 根御柱因此达到 2 层；第 2 根御柱最多只有 1 层，所以答案是 2 1。

题目四：只有地藏知晓的哀叹

• 时间限制：1.5 秒
• 内存限制：256 MB

题目描述

戎璎花正在玩垒石头的游戏。她把 堆石子摆成一排，其中第 堆里有 颗石子。魂魄妖梦给了她一个严格递增的序列 ，并希望她让 堆石子的数量序列恰好变成 ，即最终第 堆的石子数必须等于 。
戎璎花分以下两个阶段完成这个过程：
阶段一（加石子）： 她可以在任意一堆石子中添加任意数量的石子。形式上，对每一堆 ，她选择一个非负整数 ，将 替换为 。
阶段二（交换）： 她可以重复交换相邻的两堆石子。形式上，她可以执行任意多次（可能为零次）如下操作：选择一个满足 的索引 ，交换 与 的值。
如果在两个有效过程中，阶段二所需操作次数的最小值。如果不存在有效过程，则输出 −1。

输入格式

每个测试包含多个测试用例。第一行包含一个整数 （），表示测试用例的数量。
每个测试用例的格式如下：
• 第一行包含一个整数 （）——石子的堆数；
• 第二行包含 个整数 （）——每堆石子的初始数量；
• 第三行包含 个整数 （）——每堆石子的目标数量。
保证所有测试用例的 之和不超过 。

输出格式

对每个测试用例，输出一行一个整数——在所有有效过程中，阶段二可能执行的最小操作次数；如果不存在有效过程，则输出 −1。

样例

输入：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

10  
3  
1 2 2  
1 3 5  
3  
2 2 1  
1 2 3  
2  
5 1  
2 4  
6  
6 5 4 3 2 1  
1 2 3 4 5 6  
7  
4 7 1 6 2 5 3  
1 2 3 4 5 6 7  
2  
2 1  
2 3  
4  
3 2 2 1  
1 2 3 4  
4  
4 3 2 1  
1 3 4 5  
5  
1 5 4 3 2  
2 3 4 5 6  
5  
10 3 8 6 9  
3 6 8 9 10

输出：

1
2
3
4
5
6
7
8
9
10

0  
2  
-1  
15  
12  
0  
4  
4  
3  
5

样例解释

测试用例 1： 只需要阶段一。取 ，石子堆变成 。不需要交换，所以答案是 0。
测试用例 2： 两个阶段都需要。取 ，石子堆变成 ；然后进行两次交换：[2,3,1] → [2,1,3] → [1,2,3]。带 1 颗石子的那堆必须从第 3 个位置移到第 1 个位置，至少需要两次交换，因此答案是 2。
测试用例 3： 无解。第 1 堆最初有 5 颗石子，而目标序列中的每个数都不超过 4；由于只能加石子不能减，这堆石子不可能等于目标序列中的任何数。因此答案为 −1。
测试用例 4： 不需要加石子，只要把石子堆重新排成递增顺序。相邻交换的最少次数为 15。
测试用例 5： 同样不需要加石子，只要把石子堆重新排序。相邻交换的最少次数为 12。