[关闭]
@cleardusk 2016-05-23T05:56:57.000000Z 字数 3210 阅读 1215

SRM677 Div2

topcoder


做这个是为了熟悉 topcoder 的 SRM 规则以及练练手,目前貌似没有写程序的感觉了。

250

自己的实现

这道题很简单:

A positive integer is called a prime if it has exactly two distinct positive integer divisors: 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, ...

A positive integer is called a palindrome if its base-10 representation reads the same forwards and backwards. Some palindromes: 2, 77, 101, 33333, 12344321.

A positive integer is called a palindromic prime if it is both a palindrome and a prime.

You are given two ints: L and R. Compute and return the number of palindromic primes between L and R, inclusive.

就是判断 [L, R] 中有多少数,既是素数又是回文数。我的解法很传统,判断是否为回文数,我没有用字符串来判断,而是直接计算出反转的数值再判断是否相等。值得注意的细节是,第四行的代码是可以注释掉的,该函数依然能正确的判断 n 是否为素数。

  1. class PalindromePrime {
  2. public:
  3. bool is_prime(int n){
  4. //if(n == 2 || n == 3) return true;
  5. for(int i = 2; i <= int(sqrt(n)); ++i)
  6. if(n % i == 0)
  7. return false;
  8. return true;
  9. }
  10. bool is_palindromic(int n){
  11. int on = n; // original n
  12. int rn = 0;
  13. while(n){
  14. rn = 10*rn + n % 10;
  15. n /= 10;
  16. }
  17. return rn == on;
  18. }
  19. int count(int L, int R) {
  20. int res = 0;
  21. for (int i = L; i <= R; ++i)
  22. if(is_prime(i) && is_palindromic(i))
  23. ++res;
  24. return res;
  25. }
  26. };

接下来,我用反转字符串的思路实现一下,用到 c++ 中的 std::reverse。受限,int -> string 用 std::to_string,这个能将 int, double 等类型转化为 string。OK,代码如下:

  1. bool is_palindromic2(int n){
  2. string s = to_string(n);
  3. string sr = s;
  4. reverse(sr.begin(), sr.end()); // reverse string
  5. if (s.compare(sr) == 0)
  6. return true;
  7. return false;
  8. }

reverse 只能 reverse 参数中的 string 对象。to_string 必须使用 -std=c++0x flag 编译,经测试,topcoder 默认开启了 c++0x。比较字符串我使用了 compare 函数,其实使用 == 运算符也行,不过 compare 支持可选参数多多了。

拓展一下,reverse 的可能实现如下,相当精炼。更多的参考 reverse_copy,并行版本的 reverse 等。

  1. template<class BidirIt>
  2. void reverse(BidirIt first, BidirIt last)
  3. {
  4. while ((first != last) && (first != --last)) {
  5. std::iter_swap(first++, last);
  6. }
  7. }

别人的代码

他人的代码是只读不可复制的,quora 的一个讨论,这样能避免在 challenge 阶段暴力测试别人的 bug。

比赛排位第一的代码,一行搞定。注意生成式的结果是 bool 型的,注意一下 str(x) == str(x)[::-1] 这句代码。

  1. class PalindromPrime():
  2. def count(self, L, R):
  3. return sum(str(x) == str(x)[::-1] and not any (x % i == 0 for i in range(2, x)) for x in range(L, R+1))

关于是否回文数,有人写的代码是 c 风格的,就是逐个字符的判断,str[i] == str[l-i] 类似这样的。

550

这道题花了我一晚上,还是在跑步的时候彻底想清楚的。

We have four strings: a, b, c, and d.

A superstring of our four strings is any string S such that each of the four strings occurs somewhere in S as a contiguous substring.
Note that some superstrings of our four strings always exist.
For example, the string S = a+b+c+d is obviously a superstring of a, b, c, and d.

Find and return the length of the shortest superstring of a, b, c, and d.

暴力解法/朴素解法就是排列 (a, b, c, d),对每一个排列,进行字符串的融合,过程如下,其中 merge 是针对两个字符串,大致过程是对第一个字符串的尾部和第二个字符串的头部进行判断,若有重叠的就融合掉。
s <- a
s <- merge(s, b)
s <- merge(s, c)
s <- merge(s, d)

其实这道题目的难点是,如何证明该算法是正确的?我也大底是凭感觉的,排列出所有排列,然后对每一种排列融合,覆盖所有情况。这是一个好方法麽?

我的实现相当的搓,排列的生成简直。。

  1. class FourStrings {
  2. public:
  3. string merge_two_str(string s1, string s2){
  4. if(s1.find(s2) != -1)
  5. return s1;
  6. size_t l = min(s1.length(), s2.length());
  7. for(size_t i = l; i > 0; --i){
  8. string s1_tail = s1.substr(s1.length() - i);
  9. string s2_head = s2.substr(0, i);
  10. // cout << s1_tail << endl;
  11. // cout << s2_head << endl;
  12. if(s1_tail == s2_head)
  13. return s1 + s2.substr(i);
  14. }
  15. return s1 + s2;
  16. }
  17. int shortestLength(string a, string b, string c, string d) {
  18. int res = 0;
  19. string s[4];
  20. s[0] = a, s[1] = b, s[2] = c, s[3] = d;
  21. for(int i = 0; i < 4; ++i)
  22. res += int(s[i].length());
  23. for(int i = 0; i < 4; ++i)
  24. for(int j = 0; j < 4; ++j){
  25. if (j == i) continue;
  26. for(int k = 0; k < 4; ++k){
  27. if (k == i || k == j) continue;
  28. for(int l = 0; l < 4; ++l){
  29. if(l == i || l == j || l == k) continue;
  30. string ms = s[0];
  31. for(int i = 1; i < 4; ++i)
  32. ms = merge_two_str(ms, s[i]);
  33. res = min(res, int(ms.length()));
  34. }
  35. }
  36. }
  37. return res;
  38. }
  39. };

需要学习的地方有排列的生成,看离散数学的书。

900

关于图的,赶紧去看离散数学补补相关知识。

参考:http://kmjp.hatenablog.jp/entry/2015/12/27/0930
review 了别人的代码,但是不懂。


添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注