#P12353. 「HCOI-R2」DataErr0r

    ID: 13462 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>动态规划 DP洛谷原创O2优化洛谷月赛

「HCOI-R2」DataErr0r

题目背景

(图片来自 Arcaea 曲绘,如有侵权请联系出题人删除。)

How do you know you are not a Program?

题目描述

小 N 有两个 01\tt01SSTT,其长度分别为 NNN+1N+1。你可以对 TT 进行一些修改。

  • 选定 1iT1\leq i \leq |T|,删除 TiT_i,其余字符下标左移。
  • 选定 1lrT1\leq l\leq r\leq |T|,对于所有 lirl\leq i\leq r(l+i)0(mod2)(l+i)\equiv 0\pmod 2ii 执行 TiTi1T_i\gets T_i\oplus 1

小 N 想使得 T=ST = S,但是她非常懒,所以你需要最小化操作次数。

注意:你只需要输出这个最小化的操作次数即可,而无需给出构造。

输入格式

本题单测试数据内含有多组输入。

第一行一个正整数 KK 表示数据组数。

接下来每组测试数据第一行一个正整数 NN 含义如题面所述。

第二行为 01\tt01TT,由 N+1N+1 个字符(0\tt01\tt1)构成,注意字符之间没有空格。

第二行为 01\tt01SS,由 NN 个字符(0\tt01\tt1)构成,注意字符之间没有空格。

输出格式

KK 行,对于每组测试数据输出一行一个数表示答案。

1
4
10101
1111
2
3
1
11
1
3
1010
010
7
10110110
0001111
1
1
2

提示

样例解释 1

  • 10101111111\textbf 01\textbf 01\to 1\textbf11\textbf11
  • 1111111111\underline{1}\to 111

使用 22 次步骤。

数据规模与约定

本题采用捆绑测试。

  • Subtask 0 (15pts):1N101\leq \sum N\leq 10
  • Subtask 1 (35pts):1N1031\leq \sum N\leq 10^3
  • Subtask 2 (50pts):无特殊限制。

对于所有数据,1K10001\leq K\leq 10001N1061\leq \sum N\leq 10^61N1061\leq N\le 10^6