題目：https://codeforces.com/contest/1566/problem/C

題目大意

1. 給定兩個等長的 binary string 使他們成為一個 bi-table ，如：

+          +
| 10101010 |
| 00100110 |
+          +

就是一種 bi-table

2. 把題目給的 bi-table 切成數個 bi-table （也可以不要切）如：

把

+          +
| 10101010 |
| 00100110 |
+          +

切成以下 3 個 bi-table

+     +     +   +   +
| 101 | 010 | 1 | 0 |
| 001 | 001 | 1 | 0 |
+     +     +   +   +

3. 算出每個 bi-table 的 MEX 值，並且把他們加總起來：

像是上面切成了 4 段，就要算出這 4 個 MEX 值，並且加總起來

MEX 值的算法：
在 0, 1, 2 中，不被此 bi-table 包含的字元
挑選出最小的數

+     +
| 101 |
| 001 |
+     +

的 MEX 值為 2 ，因為只有 2 不被此 bi-table 包含

+     +
| 010 |
| 001 |
+     +

的 MEX 值為 2 ，因為只有 2 不被此 bi-table 包含

+   +
| 1 |
| 1 |
+   +

的 MEX 值為 0 ，因為 0, 2 不被此 bi-table 包含，而且 0 < 2

+   +
| 0 |
| 0 |
+   +

的 MEX 值為 1 ，因為 1, 2 不被此 bi-table 包含，而且 1 < 2

算這種切法下出 MEX 的總和 sum of MEX = 2 + 2 + 0 + 1 = 5

4. 題目所求：

sum of MEX 可能的的最大值

觀察

觀察一

如果某個 column 同時包含 0, 1 那麼他一定要獨立切成一個 bi-table，
因為他可以貢獻的 MEX 值為 2
如題目給定：

+            +
| xxxxxx1xxx |
| xxxxxx0xxx |
+            +

那麼不管其他地方怎麼切，10 那個 column 一定會獨立切出來

       +   +    
xxxxxx | 1 | xxx 
xxxxxx | 0 | xxx 
       +   +    

觀察二

1
1  (MEX = 0)

這是最沒用的，除非他旁邊接了 00 ：

10
10  (MEX = 2)

觀察三

+    +
| 00 |
| 00 |
+    +

應該切成

+   +   +
| 0 | 0 |
| 0 | 0 |
+   +   +

但

+    +
| 01 |
| 01 |
+    +

應該切成

+    +
| 01 |
| 01 |
+    +

解題方法

根據以上 3 點觀察，用 greedy 的方式寫出來就可以了

程式碼

// https://codeforces.com/contest/1566/problem/C
#include <stdio.h>
#include <stdlib.h>

#define TYPE(index) (tab[0][(index)] != tab[1][(index)] ? NOT_EQ :           \
                ((tab[0][(index)] == '0' && tab[1][(index)] == '0') ? ZEROS : ONES))    

typedef enum {
    NOT_EQ,
    ZEROS,
    ONES
} type;

int main()
{
    int t, n;

    scanf("%d", &t);

    while (t--) {
        int result = 0, i = 0;

        scanf("%d", &n);
        char tab[2][n+1];
        scanf("%s", tab[0]);
        scanf("%s", tab[1]);

        while (i < n) {
            if (TYPE(i) == NOT_EQ) { 
                result += 2;
                i++;

            } else if ((i < n-1) && TYPE(i) != TYPE(i+1) && TYPE(i+1) != NOT_EQ) { 
                result += 2;
                i += 2;

            } else if (TYPE(i) == ZEROS) { 
                result += 1;
                i++;

            } else if (TYPE(i) == ONES) { 
                i++;

            } else {
                fprintf(stderr, "error\n");
                exit(EXIT_FAILURE);
            }
        }

        printf("%d\n", result);
    }

    return 0;
}