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 是否为素数。

class PalindromePrime {
public:
    bool is_prime(int n){
        //if(n == 2 || n == 3) return true;
        for(int i = 2; i <= int(sqrt(n)); ++i)
            if(n % i == 0)
                return false;
        return true;
    }
    bool is_palindromic(int n){
        int on = n; // original n
        int rn = 0;
        while(n){
            rn = 10*rn + n % 10;
            n /= 10;
        }
        return rn == on;
    }
    int count(int L, int R) {
        int res = 0;
        for (int i = L; i <= R; ++i)
            if(is_prime(i) && is_palindromic(i))
                ++res;
        return res;
    }
};

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

    bool is_palindromic2(int n){
        string s = to_string(n);
        string sr = s;
        reverse(sr.begin(), sr.end()); // reverse string
        if (s.compare(sr) == 0)
            return true;
        return false;
    }

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

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

template<class BidirIt>
void reverse(BidirIt first, BidirIt last)
{
    while ((first != last) && (first != --last)) {
        std::iter_swap(first++, last);
    }
}

别人的代码

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

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

class PalindromPrime():
    def count(self, L, R):
        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)

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

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

class FourStrings {
public:
    string merge_two_str(string s1, string s2){
        if(s1.find(s2) != -1)
            return s1;
        size_t l = min(s1.length(), s2.length());
        for(size_t i = l; i > 0; --i){
            string s1_tail = s1.substr(s1.length() - i);
            string s2_head = s2.substr(0, i);
            // cout << s1_tail << endl;
            // cout << s2_head << endl;
            if(s1_tail == s2_head)
                return s1 + s2.substr(i);
        }
        return s1 + s2;
    }
    int shortestLength(string a, string b, string c, string d) {
        int res = 0;
        string s[4];
        s[0] = a, s[1] = b, s[2] = c, s[3] = d;
        for(int i = 0; i < 4; ++i)
            res += int(s[i].length());
        for(int i = 0; i < 4; ++i)
            for(int j = 0; j < 4; ++j){
                if (j == i) continue;
                for(int k = 0; k < 4; ++k){
                    if (k == i || k == j) continue;
                    for(int l = 0; l < 4; ++l){
                        if(l == i || l == j || l == k) continue;
                        string ms = s[0];
                        for(int i = 1; i < 4; ++i)
                            ms = merge_two_str(ms, s[i]);
                        res = min(res, int(ms.length()));
                    }
                }
            }
        return res;
    }
};

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

900

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

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