[USACO23DEC] Cycle Correspondence S

Luogu

IDLGP9978

Time1000ms

Memory256MB

DifficultyP3

USACO2023O2优化枚举分类讨论

Farmer John 有 $N$（$3 \le N \le 5\cdot 10^5$）座谷仓，其中 $K$ 对不同的谷仓连接在一起。一开始，Annabelle 为每座谷仓分配了一个 $[1,N]$ 范围内的整数编号，并发现编号为 $a_1,\dots,a_K$ 的谷仓按照顺序形成了一个环形连接。换句话说，对于所有的 $1 \le i < K$，谷仓 $a_i$ 和 $a_{i+1}$ 相连，谷仓 $a_K$ 与 $a_1$ 亦相连。所有的 $a_i$ 不相同。然后，Bessie 也为每个谷仓分配了一个 $[1,N]$ 范围内的整数编号，并发现编号为 $b_1,\dots,b_K$ 也按照顺序形成了一个环形链接。所有的 $b_i$ 不相同。一些（可能没有或全部）谷仓被 Annabelle 和 Bessie 分配了相同的编号。计算最多有多少个这样的谷仓。 ## Input 第一行包含 $N$ 和 $K$。接下来一行包含 $a_1,\dots,a_K$。接下来一行包含 $b_1,\dots,b_K$。 ## Output 分配了相同编号谷仓的最大数量。 [samples] ## Note ### 样例解释 1 Annabelle 和 Bessie 可以为每个谷仓分配相同的编号。 ### 样例解释 2 Annabelle 和 Bessie 无法为任何谷仓分配相同的编号。 ### 样例解释 3 Annabelle 和 Bessie 可以分配编号 $2,3,4,6$ 给相同的谷仓。 ### 测试点性质 - 测试点 $4-5$ 满足 $N \le 8$。 - 测试点 $6-8$ 满足 $N \le 5000$。 - 测试点 $9-15$ 没有额外限制。

Samples

Input #1

6 3
1 2 3
2 3 1

Output #1

Input #2

6 3
1 2 3
4 5 6

Output #2

Input #3

6 4
1 2 3 4
4 3 2 5

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[USACO23DEC] Cycle Correspondence S",
    "description": {
      "content": "Farmer John 有 $N$（$3 \\le N \\le 5\\cdot 10^5$）座谷仓，其中 $K$ 对不同的谷仓连接在一起。 一开始，Annabelle 为每座谷仓分配了一个 $[1,N]$ 范围内的整数编号，并发现编号为 $a_1,\\dots,a_K$ 的谷仓按照顺序形成了一个环形连接。换句话说，对于所有的 $1 \\le i < K$，谷仓 $a_i$ 和 $a_{i+1}$ 相连，",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9978"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Farmer John 有 $N$（$3 \\le N \\le 5\\cdot 10^5$）座谷仓，其中 $K$ 对不同的谷仓连接在一起。\n\n一开始，Annabelle 为每座谷仓分配了一个 $[1,N]$ 范围内的整数编号，并发现编号为 $a_1,\\dots,a_K$ 的谷仓按照顺序形成了一个环形连接。换句话说，对于所有的 $1 \\le i < K$，谷仓 $a_i$ 和 $a_{i+1}$ 相连，...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments