WorksApplication 机试题求解心得

话说我都不知道该发到哪里，怎么没有编程、算法或者机试题之类的节点，/(ㄒoㄒ)/~~　
　　昨晚看完学校的晚会回实验室，发现几个同学在很激烈的讨论问题，然后听到了什么矩阵、特征向量。数学系出身的我一下子就被吸引住了，本着有好玩的就要凑个热闹的心态问了问，原来他们在讨论一道 WorksApplication （什么公司？没听说，好像很小的样子）的机试题，好像已经讨论了蛮长时间，然后说用什么很高大上的 01 字典树（我打的对的吧？），感觉好牛逼好屌的样子，结果一看题目，嗨，什么嘛。
　　把题目扒下来给你们瞧瞧：
Character Recognition

Description

Character recognition is the conversion of images into text. For now we consider each character in the picture is a N*M matrix with only zeros and ones, and we need to recognize K characters. You are to write a program to find minimal number of pixels so that we can recognize each character.

For example, we have only two characters 'T' and 'L', and the matrix size is 3*3, we can think 'T' and 'L' are

111 　　　 100

010 　　　 100

010 　　　 111

so we can recognize the character with only bottom-left pixel, the answer is 1.

Limits

• Memory limit per test: 256 megabytes

• Time limit per test: The faster the better

• Input

• The first line of input is three integers N, M, K (1 <= N, M <= 10, 2 <= K <= 6). Which represents the size of matrix and number of characters. Then is following K blocks, which represents the matrix. Notice that each block starts with a blank line and we guarantee that characters are different.

• Output

• You should output the minimum number of pixels, which is the answer.

• Sample Test

• input

• 2 3 2

•

• 111

• 010

•

• 100

• 100

• output

• 1

　　说白了就是输入若干个同型 01 矩阵，然后寻找最少的点数来区分这若干个矩阵。我刚开始感觉有点意思，结果越分析越觉着出题目的人是智障，容我慢慢道来。
　　直接正面入手肯定是不行的，一个个组合即使输入矩阵数目不多那么组合起来也是很可怕的数目，穷举法什么的，最不优雅了。正面不行，咱们反其道而行，你不是找能用来区分的点么，我偏偏不找这些点，我找不能区分的点，我们装 B 一下称这种点为无用点（ useless Point ），那么什么样的点是不可用的呢？设想一下集合的交集，两个几个相交的部分一定是不能用来区分两个集合的，因为大家都是一样的嘛，推广一下，也就是说无用点即为所有输入矩阵中值一样的那些个点。剩下就好办了哇，排除掉这些一定不能用的无用点，剩下的点都可以用来当做区别点组的组员，后面 2B 的事情就来了，根据编码规则，要区别 N 个矩阵，那么最少需要 log N （这里 log 以 2 为底，我不知道怎么写下标），那么我们只要判断可用点数目是否大于这个临界值不就行了么，如果大于那么输出 log N 向上取整的整数，如果小于，说明无法有足够的点来区分，咱就输出个 0 吧。关键，最最最 2B 的事情来了，小哥（让我帮忙做题目的同学的绰号）说输入的这些个矩阵一定是可以区分的，那照这样的话我直接输出那个 log N 向上取整的整数不就可以了么， 2333 。
　　关于怎么找出无用点我是这么设计的，设立一个 N\*M 的矩阵（和输入矩阵同型），设该矩阵为 NB （嗯，牛 B 矩阵），然后矩阵中每个元素是一个长度为 2 的 int 数组，设为 a ， a[0]的值表示该矩阵位不同输入矩阵中值为 1 的个数， a[1] 的值表示该矩阵位不同输入矩阵中值为 0 的个数，然后顺序扫描各个输入矩阵，分别判断每一位的值，相应的改变 NB 矩阵中对应的一维数组中的值。随后设立一个值为 N*M 的数，表示初始可用点数，接着遍历统计 NB 矩阵中各个位中的一维数组的两个位，只要有一个位的值和输入矩阵个数是一样的，即表明在这个位所有的输入矩阵的值是一样的（或 0 或 1 ），然后这个点就是无用点，初始可用点数减去 1 。一轮线性扫描后就得出了可用点个数，然后判断一下就 ok 了。
　　我把思路告诉他之后，他说让我帮忙实现（喂喂，有这么厚颜无耻的么，笑），他说他只会 py 交易， c 和 java 都不大会，然后题目只能用 c/c++、 java 来提交，我没理他。然后他说“请你一顿饭，外加两鸡腿，还有饮料！帮不帮？”，我一听，有鸡腿还有饮料，“帮帮帮！”，然后花了一二十分钟编了出来，我很想直接 syso 一个 log N 向上取整的整数啊，可那样有点太二 B 了，还是老老实实写吧。
　　然后代码如下，因为输入较小，所以也没做优化，渣代码，且有注释强迫症，轻喷（提交一次通过， accepted ）：

　　想看代码的可以戳这里： http://www.jerryfu.net/post/worksApplication-character-recognition.html

　　然后今天早上，出于好奇搜了一下，我的妈呀，日本的啊，福利据说不错哇，好像还能免费去日本旅游啊。关键，关键，起薪 600w 啊，日元也不少啊，折算过来 35W 多啊，一年顶我两三年啊！！！
　　他第二题说在网上找到类似的代码了，也过了，这样两道题目全部 accept ，进面试应该妥妥的了吧。
　　我怎么觉得我被他一个鸡腿打发了有点亏啊……
　　我也想去日本玩！我也想去 Works Application ！我也要拿 600w ，哼！