[中山市赛 2024] 参数拟合

Luogu

IDLGB4188

Time1000ms

Memory512MB

DifficultyP4

并查集2024广东科创活动小学活动

在《机械设计与制作》课程中，Jimmy 制作了一款机械臂作为期末作业。在测试与改进阶段，immy 通过实验测得了他设计的机械臂的尺寸、硬度、灵活度、最大抓力等 $n$ 个参数 $A_1, A_2\dots A_n$。根据理论计算，机械臂的最佳性能参数为 $B_1, B_2\dots B_n$。为了提高机械臂的性能，拿到更高的分数，Jimmy 决定调整机械参数。由于机械臂各个部件间具有关联性，修改某个参数的同时也会影响到另一个参数。具体来说，只有 m 种调整可以进行：给定 $(x_i, y_i)$，让 $A_{x_i} \gets A_{x_i} + p, A_{y_i} \gets A_{y_i} + p$，其中 $p$ 为任意整数，且调整次数不限。Jimmy 希望通过调整使得 $S =\sum \limits_{i=1}^n(A_i - B_i)^2$ 最小，请你帮他算出调整后 $S$ 的最小值。 ## Input 第一行两个整数 $n, m$，分别表示机械臂参数的个数，以及调整操作的种类数。第二行 $n$ 个整数 $A_i$，表示机械臂当前的参数值。第三行 $n$ 个整数 $B_i$，表示机械臂理论最佳的参数值。接下来 $m$ 行每行两个整数 $x_i, y_i$，表示每种调整操作的两个目标参数。 ## Output 一行一个整数表示答案。 [samples] ## Note ### 数据范围 - 对于 $20\%$ 的数据，$1 \leq n, m \leq 5$，$0 \leq A_i, B_i \leq 5$。 - 另有 $40\%$ 的数据，所有 $B_i = 0$ 且所有 $x_i = 1$ 。 - 对于 $100\%$ 的数据，$1 \leq n \leq 2 \times 10^5$，$1 \leq m \leq 5 \times 10^5$，$0 \leq A_i, B_i \leq 10^5$。注意：$(x_i, y_i)$ 可能出现重复。

Samples

Input #1

6 3
14 9 1 0 4 7
11 11 5 8 7 3
1 2
3 4
5 6

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[中山市赛 2024] 参数拟合",
    "description": {
      "content": "在《机械设计与制作》课程中，Jimmy 制作了一款机械臂作为期末作业。在测试与改进阶段，immy 通过实验测得了他设计的机械臂的尺寸、硬度、灵活度、最大抓力等 $n$ 个参数 $A_1, A_2\\dots A_n$。根据理论计算，机械臂的最佳性能参数为 $B_1, B_2\\dots B_n$。为了提高机械臂的性能，拿到更高的分数，Jimmy 决定调整机械参数。 由于机械臂各个部件间具有关联性，修",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4188"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "在《机械设计与制作》课程中，Jimmy 制作了一款机械臂作为期末作业。在测试与改进阶段，immy 通过实验测得了他设计的机械臂的尺寸、硬度、灵活度、最大抓力等 $n$ 个参数 $A_1, A_2\\dots A_n$。根据理论计算，机械臂的最佳性能参数为 $B_1, B_2\\dots B_n$。为了提高机械臂的性能，拿到更高的分数，Jimmy 决定调整机械参数。\n\n由于机械臂各个部件间具有关联性，修...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments