「QFOI R1」摸摸

Luogu
IDLGP9714
Time1000ms
Memory512MB
DifficultyP3
数学洛谷原创Special JudgeO2优化构造洛谷月赛
小 R 是一个可爱的女孩子,她喜欢被摸头。 但是摸头之前,必须答对她提出的一个问题。 她有一个长度为 $n$ 的数列 $a$,初始时所有元素均为 $0$。另有两个长度为 $n$ 的数列 $t,b$。 她可以进行两种操作: 1. 将 $t$ 与 $t$ 的倒序对应元素相加,得到新的 $t$。 - 例如,$t=[1,4,2]$ 变为 $t'=[1+2,4+4,2+1]=[3,8,3]$。 2. 将 $a$ 与 $t$ 对应元素相加,得到新的 $a$。 - 例如,$a=[1,2,3],t=[1,4,2]$ 变为 $a'=[1+1,2+4,3+2]=[2,6,5]$。 是否可能通过若干次以上操作将 $a$ 变为 $b$? 你希望摸她的头 $T$ 次,因此有 $T$ 组数据。 ## Input 第一行一个整数 $T$,表示数据组数。 对于每组数据: - 第一行一个整数 $n$,表示数列长度。 - 第二行 $n$ 个整数,第 $i$ 个整数为 $t_i$。 - 第三行 $n$ 个整数,第 $i$ 个整数为 $b_i$。 ## Output 共 $T$ 行,每行一个为 `Yes` 或 `No` 的字符串,表示每组数据是否可能将 $a$ 变为 $b$。 字符串不区分大小写,如果答案为 `Yes` 的话,`yes`、`YES`、`yEs` 等都将被判为正确。 [samples] ## Note **样例解释** 对于第一组数据: - 初始时:$a=[0,0,0]$,$t=[1,2,2]$,$b=[5,8,7]$。 - 执行操作二:$a=[1,2,2]$,$t=[1,2,2]$,$b=[5,8,7]$。 - 执行操作二:$a=[2,4,4]$,$t=[1,2,2]$,$b=[5,8,7]$。 - 执行操作一:$a=[2,4,4]$,$t=[3,4,3]$,$b=[5,8,7]$。 - 执行操作二:$a=[5,8,7]$,$t=[3,4,3]$,$b=[5,8,7]$。 此时 $a=b$,符合要求。 对于第二组数据,可以证明不存在合法方案。 --- **数据范围** 本题共 $20$ 个测试点,每个测试点 $5$ 分。 记 $\sum n$ 表示每组数据的 $n$ 之和。 对于全部数据,保证 $1\le\sum n\le 2\times 10^3$,$n\ge 1$,$1\le t_i,b_i\le 2\times 10^3$。 - 对于测试点 $1\sim 4$:保证 $n\le 2$。 - 对于测试点 $5\sim 8$:保证所有 $t_i$ 都相等。 - 对于测试点 $9\sim 12$:保证 $b_i=b_{n-i+1}$。 - 对于测试点 $13\sim 16$:保证 $\sum n,t_i,b_i\le 200$。 - 对于测试点 $17\sim 20$:无特殊限制。 --- **Hack 数据** 本题在赛后添加了 Hack 数据,从 $21$ 开始编号。 原有测试点依然计 $5$ 分,Hack 数据计 $0$ 分,但只有通过所有数据才会被判为 Accepted。 为区分原有测试点和 Hack 数据,本题添加了子任务,但子任务的计分方式为“加和”,不会影响正常评测。
Samples
Input #1
2
3
1 2 2
5 8 7
3
1 2 2
2 4 3
Output #1
Yes
No
API Response (JSON)
{
  "problem": {
    "name": "「QFOI R1」摸摸",
    "description": {
      "content": "小 R 是一个可爱的女孩子,她喜欢被摸头。 但是摸头之前,必须答对她提出的一个问题。 她有一个长度为 $n$ 的数列 $a$,初始时所有元素均为 $0$。另有两个长度为 $n$ 的数列 $t,b$。 她可以进行两种操作: 1. 将 $t$ 与 $t$ 的倒序对应元素相加,得到新的 $t$。     - 例如,$t=[1,4,2]$ 变为 $t'=[1+2,4+4,2+1]=[3,8,3]$",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9714"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 R 是一个可爱的女孩子,她喜欢被摸头。\n\n但是摸头之前,必须答对她提出的一个问题。\n\n她有一个长度为 $n$ 的数列 $a$,初始时所有元素均为 $0$。另有两个长度为 $n$ 的数列 $t,b$。\n\n她可以进行两种操作:\n\n1. 将 $t$ 与 $t$ 的倒序对应元素相加,得到新的 $t$。\n    - 例如,$t=[1,4,2]$ 变为 $t'=[1+2,4+4,2+1]=[3,8,3]$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments