String Minimization

Luogu

IDLGP10244

Time1000ms

Memory512MB

DifficultyP1

字符串洛谷原创洛谷月赛

你有四个长 $n$ 的字符串 $a,b,c,d$。你可以执行任意多次如下操作： - 选择一个 $i$，交换 $a_i,c_i$，然后交换 $b_i,d_i$。求在 $a$ 的字典序尽量小的前提下，$b$ 字典序最小是什么。 --- 如果你不知道什么是字典序，看这里：对于两个字符串 $p,q$，称 $p$ 的字典序小于 $q$（记为 $p<q$），当且仅当存在**自然数** $k$ 使 $p,q$ 的前 $k$ 个字符相同且 $p_{k+1}$ 的 ASCII 码小于 $q_{k+1}$ 的 ASCII 码。例如： - $\texttt{abc}<\texttt{baa}$（当 $k=0$） - $\texttt{bae}<\texttt{bbb}$（当 $k=1$） ## Input 输入的第一行有一个正整数 $n$，表示字符串 $a,b,c,d$ 长度。之后四行，每行一个字符串，分别表示 $a,b,c,d$。 ## Output 输出一行一个字符串，表示题目要求的字符串 $b$。 [samples] ## Note 【样例解释】选择 $i$ 为 $1,3,4$ 可以让 $a$ 取到最小的字典序 $\texttt{weablake}$，此时字符串 $b$ 也得到满足题意最小的字典序 $\texttt{auazyqaq}$。事实上如果 $i=1$ 时不操作 $a$ 的字典序也是最小的，但是此时字符串 $b$ 就是 $\texttt{yuazyqaq}$，不够小。【数据范围】本题共 $10$ 个测试点，每个测试点 $10$ 分。 |测试点编号|$n\le$|特殊性质| |:-:|:-:|:-:| |$1\sim 2$|$15$|| |$3$|$10^5$|$a_i>c_i$| |$4\sim 5$|$10^5$|$a_i\ne c_i$| |$6\sim 7$|$10^5$|$b_i\ge d_i$| |$8\sim 10$|$10^5$|| 对于全体数据，保证 $1\le n\le 10^5$，字符串所有字符都是小写字母。

Samples

Input #1

8
westlake
yummyqaq
weabzzke
azazazaq

Output #1

auazyqaq

API Response (JSON)

{
  "problem": {
    "name": "String Minimization",
    "description": {
      "content": "你有四个长 $n$ 的字符串 $a,b,c,d$。你可以执行任意多次如下操作： - 选择一个 $i$，交换 $a_i,c_i$，然后交换 $b_i,d_i$。 求在 $a$ 的字典序尽量小的前提下，$b$ 字典序最小是什么。 --- 如果你不知道什么是字典序，看这里： 对于两个字符串 $p,q$，称 $p$ 的字典序小于 $q$（记为 $p<q$），当且仅当存在**自然数** $k$ 使",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P1"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10244"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你有四个长 $n$ 的字符串 $a,b,c,d$。你可以执行任意多次如下操作：\n\n- 选择一个 $i$，交换 $a_i,c_i$，然后交换 $b_i,d_i$。\n\n求在 $a$ 的字典序尽量小的前提下，$b$ 字典序最小是什么。\n\n---\n\n如果你不知道什么是字典序，看这里：\n\n对于两个字符串 $p,q$，称 $p$ 的字典序小于 $q$（记为 $p<q$），当且仅当存在**自然数** $k$ 使...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments