#PQJ1542x8321. QOJ 1542_8321

    ID: 2631 传统题 500ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:二十一省联合省选2024动态规划

QOJ 1542_8321

NOI2024 联合省选 第一试季风(wind) 季风(wind) 【题目背景】 生活在二维平面的小X 准备拜访小Y,但由于气候的变化,平面上刮起了季风。小 X 想知道季风的影响下,TA 至少要多少天能够到达小Y 的家,但小X 也是第一次遇 见这种怪事,所以请精通算法的你来帮忙。 【题目描述】 给定n, k, x, y 和2n 个整数x0, y0, x1, y1, · · · , xn−1, yn−1。 找到最小的.非.负.整.数m,使得存在2m 个.实.数x′ 0, y′ 0, x′ 1, y′ 1, · · · , x′ m−1, y′ m−1 满足以 下条件,或报告不存在这样的m: • !m−1 i=0 (x′ i + xi mod n) = x; • !m−1 i=0 (y′ i + yi mod n) = y; • ∀0 ≤i ≤m −1,|x′ i| + |y′ i| ≤k。 特别地,m = 0 时,认为 "!m−1 i=0 (x′ i + xi mod n)

和 "!m−1 i=0 (y′ i + yi mod n)

均为0。 【输入格式】 从文件wind.in 中读入数据。 .本.题.有.多.组.测.试.数.据。输入的第一行一个整数T 表示测试数据组数。 对于每组测试数据, • 第一行四个整数n, k, x, y, • 接下来n 行,第i 行两个整数xi−1, yi−1。 【输出格式】 输出到文件wind.out 中。 对于每组测试数据输出一行一个整数,如果存在满足题意的m,输出其最小可能值, 否则输出‐1。 【样例1 输入】 1 4 2 1 2 2 2 3 1 1 4 1 2 ‐2 ‐2 5 1 1 6 1 2 0 0 第2 页 共12 页

NOI2024 联合省选 第一试季风(wind) 7 1 1 8 2 100000000 100000000 100000000 9 ‐99999999 0 10 ‐100000000 0 【样例1 输出】 1 1 2 ‐1 3 0 4 399999999 【样例1 解释】 该组样例共有四组测试数据。 • 对于第一组测试数据,取m = 1,(x′ 0, y′ 0) = (1, 1) 满足条件,可以证明不存在更 小的m 满足条件; • 对于第二组测试数据,可以证明不存在任何非负整数m 满足条件; • 对于第三组测试数据,取m = 0 满足条件,可以证明不存在更小的m 满足条件。 【样例2】 见选手目录下的wind/wind2.in 与wind/wind2.ans。 该组样例共有八十组测试数据,所有测试数据均满足n = 1。其中测试数据1 ∼20 满足特殊性质A,21 ∼40 满足特殊性质B,41 ∼60 满足特殊性质C。 【样例3】 见选手目录下的wind/wind3.in 与wind/wind3.ans。 该组样例共有六十组测试数据,所有测试数据均满足n = 200。其中测试数据1 ∼20 满足特殊性质A,21 ∼40 满足特殊性质B。 【子任务】 设! n 为单个测试点内所有测试数据的n 的和。对于所有测试数据, • 1 ≤T ≤5 × 104; • 1 ≤n ≤105,1 ≤! n ≤106; • 0 ≤|x|, |y|, |xi|, |yi|, k ≤108。 第3 页 共12 页

NOI2024 联合省选 第一试季风(wind) 测试点编号 n ≤ ! n ≤ 特殊性质 1 1 300 A 2 B 3 C 4 无 5 200 5, 000 A 6 B 7 无 8 104 105 A 9 B 10 105 106 无 特殊性质A:∀0 ≤i ≤n −1,|xi| + |yi| ≤k。 特殊性质B:k = 0。 特殊性质C:x0 = y0 = 0。 【提示】 本题输入文件较大,请使用较为快速的输入方式。 第4 页 共12 页