[C 语言笔记--Day06] 解题纪录：MAX-MEX Cut

题目：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;
}