[CERC2019] Ponk Warshall

Luogu
IDLGP9614
Time1000ms
Memory128MB
DifficultyP5
2019图论建模ICPCCERC
听摇滚乐会改变你的核心 DNA。这一令人震惊和难以置信的事实最近发表在地球上顶级科学期刊之一的《摇滚自然周刊》上。研究的一部分是在摇滚音乐会季前后从志愿者身上采集 DNA 样本。对样品进行处理,并从样品中分离出各种基因。对于每个人,每个基因被分离两次:摇滚季之前的变体和摇滚季之后的变体。这两个变体是配对的,在许多情况下,发现一个变体是该对中另一个变体的某种排列。 研究的下一步是确定排列是如何发生的。普遍的假说认为,排列是由一系列转座组成的,即所谓的交换。交换是指基因中正好有两个核碱基在基因中交换位置的事件(其化学性质尚不完全清楚)。该基因中没有其他核碱基受到交换的影响。两个交换的核碱基的位置可能是完全任意的。 为了预测和观察分子在排列过程中的运动,研究人员需要知道能够在基因中产生特定核碱基排列的理论最小交换次数。我们提醒你,核 DNA 基因是一个由胞嘧啶、鸟嘌呤、腺嘌呤和胸腺嘧啶组成的碱基序列,它们分别编码为 C、G、A 和 T。 ### 简要题意 给定两个字符串(字符集只含 `A`、`C`、`G` 或 `T`),求把第一个字符串通过交换两个字母变为第二个字符串的最少交换次数。 ## Input 输入包含两行。每行包含一个由 $N\ (1\le N\le 10^6)$ 个大写字母“A”、“C”、“G”或“T”组成的字符串。这两个字符串代表一对特定的基因版本。第一行代表摇滚季之前的基因,第二行代表来自摇滚季之后同一个人的相同基因。在两个字符串中,每个核碱基的出现次数是相同的。 ## Output 输出一个整数,代表将第一个基因版本转换为第二个基因版本交换的最小数量。 [samples] ## Background **题目译自 [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) 「[Ponk Warshall](https://contest.felk.cvut.cz/19cerc/solved/ponk.pdf)」**
Samples
Input #1
CGATA
ATAGC
Output #1
2
Input #2
CTAGAGTCTA
TACCGTATAG
Output #2
7
API Response (JSON)
{
  "problem": {
    "name": "[CERC2019] Ponk Warshall",
    "description": {
      "content": "听摇滚乐会改变你的核心 DNA。这一令人震惊和难以置信的事实最近发表在地球上顶级科学期刊之一的《摇滚自然周刊》上。研究的一部分是在摇滚音乐会季前后从志愿者身上采集 DNA 样本。对样品进行处理,并从样品中分离出各种基因。对于每个人,每个基因被分离两次:摇滚季之前的变体和摇滚季之后的变体。这两个变体是配对的,在许多情况下,发现一个变体是该对中另一个变体的某种排列。 研究的下一步是确定排列是如何发生",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9614"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "听摇滚乐会改变你的核心 DNA。这一令人震惊和难以置信的事实最近发表在地球上顶级科学期刊之一的《摇滚自然周刊》上。研究的一部分是在摇滚音乐会季前后从志愿者身上采集 DNA 样本。对样品进行处理,并从样品中分离出各种基因。对于每个人,每个基因被分离两次:摇滚季之前的变体和摇滚季之后的变体。这两个变体是配对的,在许多情况下,发现一个变体是该对中另一个变体的某种排列。\n\n研究的下一步是确定排列是如何发生...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments