TopCoder Single Round Match 533
这个比赛是在今天凌晨 1:05 开始的，感觉以后做这种还是需要先休息一下。
250 分的题，题意是，皮卡丘只会说三个音节：“pi”、“ka”、“chu”；给出一个只有小写字母的字符串，判断皮卡丘能不能说出这样的话。比如，“pikachu”、“pikapika”之类的要输出“YES”，反之输出“NO”。
我的办法比较笨，都是逐个字母来判断的。但是我感觉这种方法比较快，是 O(n) 的算法。在 Challenge 的时候看到一种方法，每次判断开头几个字母是不是“pi”、“ka”、“chu”，如果不是就直接返回“NO”了，如果是的话，就删除前面几个字母。但是这种方法似乎没法通过系统测试，不过在 Challenge 阶段这样的题解也没人敢动，所以这样错的原因可能是效率比较低。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | #include <string> using namespace std; class PikachuEasy { public: string check(string word) { int i; for (i = 0; i < word.length(); ++i) { if (word[i] == 'p') { if (++i >= word.length()) return "NO"; if (word[i] != 'i') return "NO"; } else if (word[i] == 'k') { if (++i >= word.length()) return "NO"; if (word[i] != 'a') return "NO"; } else if (word[i] == 'c') { if (++i >= word.length()) return "NO"; if (word[i] != 'h') return "NO"; if (++i >= word.length()) return "NO"; if (word[i] != 'u') return "NO"; } else return "NO"; } return "YES"; } }; |
500 分的题目，题意是，有 n 个数字，每次可以删除其中“不是首位的”数字，然后获得那个被删除数字左右两个数字之乘积的能量。这些数字都是正的。数据范围是 3 ≤ n ≤ 10, 那这样的话即使用穷举也是最多 8! = 40320, 这就无压力了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #include <vector> #include <algorithm> using namespace std; class CasketOfStarEasy { public: int maxEnergy(vector<int> weight) { return maxEnergyRecursive(weight); } int maxEnergyRecursive(const vector<int> &weight) { if (weight.size() == 3) return weight[0] * weight[2]; int result, max_result = 0; for (int i = 1; i < weight.size() - 1; ++i) { vector<int> clone = weight; clone.erase(clone.begin() + i); result = maxEnergy(clone) + weight[i - 1] * weight[i + 1]; max_result = max(max_result, result); } return max_result; } }; |
1000 分的题目，不会做。和室友讨论了将近 40 分钟，没有什么结果。
然后 Challenge 阶段，居然意外地搞了两份代码。今天早上起床的时候，发现 Rating 涨了，终于变成了绿人……
沙发发。。。