Qualification Round 2009 Problem A. Alien Language 逆思维实现

原题：https://code.google.com/codejam/contest/90101/dashboard#s=p0

我原来的想法是为每个用例生成所有可能的外星单词，然后查外星词典判断是否在词典里。最朴素的想法是用一个动态数组存，但是很遗憾在small的时候堆溢出了……（上一道题目是栈溢出）。那就放弃动态数组吧，于是构造了一个简易的多进制混合计数器。每个外星单词构成一位，用例括号里有n个字母这一位就是n进制的，根据这个混合多进制数可以唯一确定一个外星单词，这样我只需要存一个多进制数，而不需要存所有的外星词语了。但是遗憾得很，small的第五个用例一共有天文数组个可能的单词，要遍历完非常费时间，如果是真是比赛我简直不能保证在50min之内算完。我又做了一些优化，包括在构造进制的时候检查这一位是否真的需要所有的字母，包括遍历的时候没必要在达到字典的size之后继续遍历。虽然做了如此多的努力改进它，但是遍历这种算法依然耗时，不得不放弃它。

在构造进制的时候，我检查括号里的字母在字典的对应位置是否出现过，这样可以减少进制的位数。其实这时候就有一点逆向思维的萌芽，既然可能的组合数是天文数字，而字典的大小是有限的，那么不如遍历字典！于是写出如下解法：

#include <iostream>
#include <vector>
#include <string>
using namespace std;
///////////////////////////SubMain//////////////////////////////////
class CAlienDic
{
public:
	vector<string> dic;
	int size;
public:
	bool isWordInDic(const string& word) const
	{
		for (int i = 0; i < size; i++)
		{
			if (dic[i] == word)
			{
				return true;
			}
		}

		return false;
	}
	bool checkCharAt(const char& c, const int& p) const
	{
		for (int i = 0; i < size; i++)
		{
			if (dic[i][p] == c)
			{
				return true;
			}
		}

		return false;
	}
};
class CWord
{
private:
	vector<int> p;
public:
	vector<string> pos_words;
	vector<string> characters;
	CWord(const string& ori_word, const CAlienDic& dic)
	{
		for (int i = 0; i < ori_word.size(); i++)
		{
			if (ori_word[i] == '(')
			{
				i++;
				string temp = ""; 
				while (ori_word[i] != ')')
				{
					if (dic.checkCharAt(ori_word[i], characters.size()))
					{
						temp += ori_word[i];
					}
					i++;
				}
				characters.push_back(temp);
			}
			else
			{
				characters.push_back(string(1, ori_word[i]));
			}
			p.push_back(0);
		}
	}

	int countInDic(const CAlienDic& Dic)
	{
		int n = 0;
		for (int i = 0; i < Dic.size; i++)
		{
			string w = Dic.dic[i];
			int j = 0;
			for (; j < w.size(); j++)
			{
				if (!checkCharAt(w[j], j))
				{
					break;
				}
			}
			if (j == w.size())
			{
				n++;
			}
		}

		return n;
	}

private:
	bool checkCharAt(const char& c, const int& p) const
	{
		string chars = this->characters[p];
		for (int i = 0; i < chars.size(); i++)
		{
			if (chars[i] == c)
			{
				return true;
			}
		}
		return false;
	}
};
int main(int argc, char *argv[])
{
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	CAlienDic Dic;
	int L = 0;
	cin >> L;
	cin >> Dic.size;
	int nCases = 0;
	cin >> nCases;
	cin.get();
	for (int i = 0; i < Dic.size; i++)
	{
		string w = "";
		cin >> w;
		Dic.dic.push_back(w);
	}
	for (int i = 0; i < nCases; i++)
	{
		string temp = "";
		cin >> temp;
		CWord w(temp, Dic);
		cout << "Case #" << i + 1 << ": ";
		cout << w.countInDic(Dic) << endl;
	}
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

其实这里面有很多地方没考虑到效率，字典的动态数组如果直接new的话，在check的时候就可以直接操作指针，会快很多。不过用vector写起来很舒服倒是真的。

 知识共享署名-非商业性使用-相同方式共享：码农场 » Qualification Round 2009 Problem A. Alien Language 逆思维实现