@cleardusk 2016-05-23T05:56:57.000000Z 字数 3210 阅读 1131

# SRM677 Div2

topcoder

# 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.

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;    }};

    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 支持可选参数多多了。

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

## 别人的代码

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))

# 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.

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

review 了别人的代码，但是不懂。

• 私有
• 公开
• 删除