[转] Facebook杯2013年编程挑战赛——预选赛题目及答案
[译] Facebook杯2013年编程挑战赛——预选赛题目及答案
今年的预选赛已经在1月29日结束了，总共有10169名选手成功解决了至少一道问题。来自密歇根大学的Ryan在50分钟内解决了全部三道问题，预选赛排名第一。 预赛 排名 中 的 前500名选手 获得了 进入下一轮比赛 的 资格 。
第一题 美丽的字符串 （20分）
对于一个字符串，定义这个字符串的“美丽程度”是其所有字母“美丽程度”的 总和 ( s u m ) 。
每个字母都有一个“美丽程度”，范围在1到26之间。 没有任何两个字母拥有相同的“美丽程度”。字母忽略大小写。
给出一个字符串，计算它最大可能的“美丽程度”。
官方答案：
这是本轮比赛最简单的题目。一共有10697名参赛者尝试解决此题，其中9865名参赛者成功解决。解法的核心思想是：计算每个字母出现的频率，给频率最多的字母赋予“美丽程度值”26，以此类推。如果两个字母频率相等，可以任意挑一个赋予稍高的值，因为不影响字符串总和。
from collections import Counter
def get_beauty(string):
string = string.lower()
# Remove all characters other than letters
string = '' .join(x for x in string if ' a ' <= x <= ' z ' )
# Make a dictionary where the keys are letters and the values are counts
freq = Counter(string)
# Get the values (letter counts) and sort them in descending order
arr = freq.values()
arr.sort()
arr.reverse()
# 26 * (count of most common letter) + (25 * next most common) + ...
values_and_counts = zip(range(26, 0, -1 ), arr)
return sum(value * count for value, count in values_and_counts)
第二题 平衡的笑脸符号 （35分）
有时候我们把笑脸符号 :) 放在了括号中间，这时就比较难分辨到底是笑脸符号还是括号的一部分。
一段文本被视为“括号平衡” 需要满足以下中的一个条件：
这段文本为空 有超过一个的英文字母，空格或者冒号 一个左括号，然后是一段“括号平衡”文本，接着一个右括号 一段“括号平衡”文本，接着又是一段“括号平衡”文本 一个笑脸符号 :) 或者哭脸符号 :(给出一段文本，判断它是不是“括号平衡”的。
官方答案：
一共有7096名参赛者尝试解决这道题，其中只有2086名参赛者成功解决。 对于这道题，有很多种方法。你可以用“暴力搜索”，动态规划+缓存，或者本文介绍的O(N)的算法。我们决定让每位参赛者只要答案正确就算成功解决此题，因此上面的任何做法都可以。 下面介绍O(N)的算法。
核心思想是跟踪“开括号”（指缺相应的右括号）数的范围。
我们使用两个变量，minOpen和maxOpen，都初始化为0。
逐个字符遍历整段文本。
当遇见左括号时，maxOpen加一。如果这个左括号不是 哭脸符号 的一部分，minOpen也要加一。
当遇见右括号时，minOpen减一。如果这个右括号不是 笑脸符号 的一部分，maxOpen也要减一。 如果minOpen被减成负数了，重新令它为0。
最后，如果maxOpen被减成负数了，或者minOpen不为0，此时这段文本不可能是“括号平衡的”；反之，则是“括号平衡的”。
def isBalanced(message):
minOpen = 0
maxOpen = 0
for i in xrange(len(message)):
if message[i] == ' ( ' :
maxOpen += 1
if i != 0 and message[i-1] != ' : ' :
minOpen += 1
elif message[i] == ' ) ' :
minOpen = max(0, minOpen-1 )
if i != 0 and message[i-1] != ' : ' :
maxOpen -= 1
if maxOpen < 0:
break
if maxOpen >= 0 and minOpen == 0:
return " YES "
else :
return " NO "
第三题 找最小 （45分）
有一个下标从0开始的数组M，里面有N个非负数。只有前K个数已知。
我们只知道，对于下标i的数，当 K <= i < N时，M[i]是前K个数中没有包含的最小的非负数。
例如，如果K=3, N=4, 前K个数是[2, 3, 0]，我们就能推出 M[3] = 1。
给出一个数组M中的前K个数，你的任务是推出这个数组中最后一个数M[N-1]。
另外，我们使用下列公式产生前K个数：
M[0] = A
M[i] = (B * M[i - 1] + C) % r, 0 < i < K
你应该在你的程序中根据输入数据提供的A,B,C和r，自行生成前K个数。
官方答案：
总共有2555名参赛者尝试解决这道题，总共有1929名参赛者成功解决。 这道题的难点在于测试数据中 N 的值会非常大。 不管这样，你应该需要推断出这两点：
（1） M[i] (i >=k) 的最大值不可能大于 k+1。所以即使前面K个数的值最大可以到10^9，最终答案也不可能大于k+1。
（ 2 ） 根据上一点，M的后半段的值将在每k+1个数后重复。所以即使N很大，我们也只需要计算k+1个数，
现在我们把问题缩小到了找 m[k], m[k+1] ... m[2k+1]这些数。“暴力搜索”依然很慢，复杂度是O(K^2)。所以我们考虑使用一个BST（c++中用set/map）维持那些没有在前K个数中出现的数。这样复杂度就降低到了O(k log k)，可以通过测试数据了。
下面是本次比赛第一名的这道题的代码：
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include < set >
#include <queue>
using namespace std;
int M[ 200020 ];
int main() {
int N; cin >> N;
for ( int t = 0 ; t < N; t++ ) {
int n, k; cin >> n >> k; n-- ;
int a, b, c, r; cin >> a >> b >> c >> r;
M[ 0 ] = a;
for ( int i = 1 ; i < k; i++ ) {
M[i] = (1ll * b * M[i - 1 ] + c) % r;
}
set < int > st;
for ( int i = 0 ; i <= k; i++ ) st.insert(i);
for ( int i = 0 ; i < k; i++ ) st.erase(M[i]);
multiset < int > dupst;
for ( int i = 0 ; i < k; i++ ) dupst.insert(M[i]);
for ( int i = k; i <= 2 * k; i++ ) {
M[i] = * st.begin();
st.erase(st.begin());
if (i < 2 * k) {
dupst.erase(dupst.find(M[i - k]));
if (M[i - k] <= k && dupst.find(M[i - k]) == dupst.end()) {
st.insert(M[i - k]);
}
}
}
cout << " Case # " << (t + 1 ) << " : " ;
if (n <= 2 * k) {
cout << M[n] << endl;
} else {
cout << M[k + (n - 2 * k - 1 ) % (k + 1 )] << endl;
}
}
return 0 ;
}
如果你喜欢这篇文章，请点击右下方的“推荐”按钮，谢谢 :)
作者： Leo_wl
出处： http://HdhCmsTestcnblogs测试数据/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息查看更多关于Facebook杯2013年编程挑战赛——预选赛题目及答案的详细内容...