「CROI · R2」01-string

Luogu
IDLGP10766
Time1000ms
Memory512MB
DifficultyP5
动态规划 DPO2优化洛谷月赛
给定两个长度为 $n$ 的 $01$ 串 $S,T$,你可以对串 $S$ 执行无限次操作,每次都可以从以下操作中任选一个执行: - 选择两个正整数 $l,r(1\le l\le r\le n)$,将 $S_l\dots S_r \ 01$ 反转。 - 选择两个正整数 $l,r(1\le l\le r\le n)$,将 $S_l\dots S_r $ 全部改为 $0$。 - 选择两个正整数 $l,r(1\le l\le r\le n)$,将 $S_l\dots S_r $ 全部改为 $1$。 你需要回答最少使用几次操作才能把 $S$ 变成 $T$。 ## Input **本题采用多组数据测试。** 第一行一个正整数 $T$,表示数据组数。 对于每组数据: 第一行一个 $01$ 串,表示串 $S$。 第二行一个 $01$ 串,表示串 $T$。 ## Output 一共 $T$ 行,第 $i$ 行一个整数,表示第 $i$ 组数据的答案。 [samples] ## Note **【样例解释】** 以下提供样例三组数据的合法方案之一: 对于第一组数据,选取 $l=1,r=5$,将 $S_l\dots S_r$ 全部变成 $1$。 对于第二组数据,选取 $l=1,r=5$,将 $S_l\dots S_r \ 01$ 反转。 对于第三组数据,先选取 $l=4,r=8$,将 $S_l\dots S_r$ $01$ 反转,再选取 $l=5,r=8$,将 $S_l\dots S_r$ 全部变成 $0$。 **【数据范围】** **本题采用捆绑测试**。 - Sub 0(10 points):$n\le 5$。 - Sub 1(10 points):$n\le 18$。 - Sub 2(30 points):$n\le 2000$。 - Sub 3(50 points):无特殊限制。 对于所有的数据,$1\le T \le 10$,$1\le n\le 5\times 10^5$。
Samples
Input #1
3
00000
11111
10101
01010
11100101
11110000 
Output #1
1
1
2
API Response (JSON)
{
  "problem": {
    "name": "「CROI · R2」01-string",
    "description": {
      "content": "给定两个长度为 $n$ 的 $01$ 串 $S,T$,你可以对串 $S$ 执行无限次操作,每次都可以从以下操作中任选一个执行: - 选择两个正整数 $l,r(1\\le l\\le r\\le n)$,将 $S_l\\dots S_r \\ 01$ 反转。 - 选择两个正整数 $l,r(1\\le l\\le r\\le n)$,将 $S_l\\dots S_r $ 全部改为 $0$。 - 选择两个正整数 $",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10766"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定两个长度为 $n$ 的 $01$ 串 $S,T$,你可以对串 $S$ 执行无限次操作,每次都可以从以下操作中任选一个执行:\n\n- 选择两个正整数 $l,r(1\\le l\\le r\\le n)$,将 $S_l\\dots S_r \\ 01$ 反转。\n\n- 选择两个正整数 $l,r(1\\le l\\le r\\le n)$,将 $S_l\\dots S_r $ 全部改为 $0$。\n\n- 选择两个正整数 $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments