TopCoder SRM#677(Div2)(2/3)

maksyuki 发表于比赛分类，标签: 比赛-topcoder

25 1月 2016

250 Problem Statement

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.
Definition
Class: PalindromePrime
Method: count
Parameters: int, int
Returns: int
Method signature: int count(int L, int R)
(be sure your method is public)

题目类型：暴力枚举

算法分析：直接循环枚举判断即可

// BEGIN CUT HERE

// END CUT HERE
#line 5 "PalindromePrime.cpp"
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

class PalindromePrime
{
        public:
        int count(int L, int R)
        {
			int res = 0;
			for (int i = L; i <= R; i++)
			{
				if (i == 1) continue;
				bool is_find = true;
				for (int j = 2; j * j <= i; j++)
					if (i % j == 0)
					{
						is_find = false;
						break;
					}
				
				
				if (is_find)
				{
					string s;
					int tt = i;
					do
					{
						s += (char) (tt % 10 + '0');
						tt /= 10;
					} while (tt);
					
					int len = s.size ();
					bool is_have = true;
					for (int i = 0; i < len / 2; i++)
						if (s[i] != s[len-1-i])
						{
							is_have = false;
							break;
						}

					if (is_have) res++;
				}
			}
			return res;
        }
        
// BEGIN CUT HERE
	public:
	void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); }
	private:
	template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
	void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
	void test_case_0() { int Arg0 = 100; int Arg1 = 150; int Arg2 = 2; verify_case(0, Arg2, count(Arg0, Arg1)); }
	void test_case_1() { int Arg0 = 1; int Arg1 = 9; int Arg2 = 4; verify_case(1, Arg2, count(Arg0, Arg1)); }
	void test_case_2() { int Arg0 = 929; int Arg1 = 929; int Arg2 = 1; verify_case(2, Arg2, count(Arg0, Arg1)); }
	void test_case_3() { int Arg0 = 1; int Arg1 = 1; int Arg2 = 0; verify_case(3, Arg2, count(Arg0, Arg1)); }
	void test_case_4() { int Arg0 = 1; int Arg1 = 1000; int Arg2 = 20; verify_case(4, Arg2, count(Arg0, Arg1)); }

// END CUT HERE

};

// BEGIN CUT HERE
int main()
{
        PalindromePrime ___test;
        ___test.run_test(-1);
        return 0;
}
// END CUT HERE

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

// BEGIN CUT HERE

// END CUT HERE

#line 5 "PalindromePrime.cpp"

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

class PalindromePrime

{

public:

int count(int L, int R)

{

int res = 0;

for (int i = L; i <= R; i++)

{

if (i == 1) continue;

bool is_find = true;

for (int j = 2; j * j <= i; j++)

if (i % j == 0)

{

is_find = false;

break;

}

if (is_find)

{

string s;

int tt = i;

{

s += (char) (tt % 10 + '0');

tt /= 10;

} while (tt);

int len = s.size ();

bool is_have = true;

for (int i = 0; i < len / 2; i++)

if (s[i] != s[len-1-i])

{

is_have = false;

break;

}

if (is_have) res++;

}

return res;

}

// BEGIN CUT HERE

public:

void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); }

private:

template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }

void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }

void test_case_0() { int Arg0 = 100; int Arg1 = 150; int Arg2 = 2; verify_case(0, Arg2, count(Arg0, Arg1)); }

void test_case_1() { int Arg0 = 1; int Arg1 = 9; int Arg2 = 4; verify_case(1, Arg2, count(Arg0, Arg1)); }

void test_case_2() { int Arg0 = 929; int Arg1 = 929; int Arg2 = 1; verify_case(2, Arg2, count(Arg0, Arg1)); }

void test_case_3() { int Arg0 = 1; int Arg1 = 1; int Arg2 = 0; verify_case(3, Arg2, count(Arg0, Arg1)); }

void test_case_4() { int Arg0 = 1; int Arg1 = 1000; int Arg2 = 20; verify_case(4, Arg2, count(Arg0, Arg1)); }

// END CUT HERE

};

// BEGIN CUT HERE

int main()

{

PalindromePrime ___test;

___test.run_test(-1);

return 0;

}

// END CUT HERE

550 Problem Statement

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.
Definition
Class: FourStrings
Method: shortestLength
Parameters: string, string, string, string
Returns: int
Method signature: int shortestLength(string a, string b, string c, string d)
(be sure your method is public)

题目类型：暴力枚举+判断

算法分析：由于一共才有4!种排列，所以可以使用next_permutation函数来生成每个排列，然后先判断当前字符串si是否是res的子串，若是则直接判断下一个字符串si+1。否则枚举res后min(res_len, si_len) ~ 0个子串并和si的前len ~ 0个子串比较。将多出来的部分加到res的尾部。最后统计最小值即可

// BEGIN CUT HERE

// END CUT HERE
#line 5 "FourStrings.cpp"
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

vector <string> s;
int res;

void SS ()
{
	string ans = s[0];
	for (int i = 1; i < 4; i++)
	{
		if (ans.find (s[i]) != string :: npos) continue;
		int len = min (ans.size (), s[i].size ());
		while (len >= 0 && ans.substr (ans.size () - len).find (s[i].substr (0, len)) == string :: npos) 
			len--;
		ans += s[i].substr (len);
	}
	res = min (res, (int) ans.size ());
}

class FourStrings
{
        public:
        int shortestLength(string a, string b, string c, string d)
        {
			s.clear ();
			s.push_back (a), s.push_back (b), s.push_back (c), s.push_back (d);
			sort (s.begin (), s.end ());
			res = INF;
			do
			{
				SS ();	
			} while (next_permutation (s.begin (), s.end ()));
			return res;
        }
        
// BEGIN CUT HERE
	public:
	void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); }
	private:
	template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
	void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
	void test_case_0() { string Arg0 = "abc"; string Arg1 = "ab"; string Arg2 = "bc"; string Arg3 = "b"; int Arg4 = 3; verify_case(0, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); }
	void test_case_1() { string Arg0 = "a"; string Arg1 = "bc"; string Arg2 = "def"; string Arg3 = "ghij"; int Arg4 = 10; verify_case(1, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); }
	void test_case_2() { string Arg0 = "top"; string Arg1 = "coder"; string Arg2 = "opco"; string Arg3 = "pcode"; int Arg4 = 8; verify_case(2, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); }
	void test_case_3() { string Arg0 = "thereare"; string Arg1 = "arelots"; string Arg2 = "lotsof"; string Arg3 = "ofcases"; int Arg4 = 19; verify_case(3, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); }
	void test_case_4() { string Arg0 = "aba"; string Arg1 = "b"; string Arg2 = "b"; string Arg3 = "b"; int Arg4 = 3; verify_case(4, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); }
	void test_case_5() { string Arg0 = "x"; string Arg1 = "x"; string Arg2 = "x"; string Arg3 = "x"; int Arg4 = 1; verify_case(5, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); }

// END CUT HERE

};

// BEGIN CUT HERE
int main()
{
        FourStrings ___test;
        ___test.run_test(-1);
        return 0;
}
// END CUT HERE

100

101

102

103

104

105

106

107

108

109

110

// BEGIN CUT HERE

// END CUT HERE

#line 5 "FourStrings.cpp"

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

vector <string> s;

int res;

void SS ()

{

string ans = s[0];

for (int i = 1; i < 4; i++)

{

if (ans.find (s[i]) != string :: npos) continue;

int len = min (ans.size (), s[i].size ());

while (len >= 0 && ans.substr (ans.size () - len).find (s[i].substr (0, len)) == string :: npos)

len--;

ans += s[i].substr (len);

}

res = min (res, (int) ans.size ());

}

class FourStrings

{

public:

int shortestLength(string a, string b, string c, string d)

{

s.clear ();

s.push_back (a), s.push_back (b), s.push_back (c), s.push_back (d);

sort (s.begin (), s.end ());

res = INF;

{

SS ();

} while (next_permutation (s.begin (), s.end ()));

return res;

}

// BEGIN CUT HERE

public:

private:

void test_case_0() { string Arg0 = "abc"; string Arg1 = "ab"; string Arg2 = "bc"; string Arg3 = "b"; int Arg4 = 3; verify_case(0, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); }

void test_case_1() { string Arg0 = "a"; string Arg1 = "bc"; string Arg2 = "def"; string Arg3 = "ghij"; int Arg4 = 10; verify_case(1, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); }

void test_case_2() { string Arg0 = "top"; string Arg1 = "coder"; string Arg2 = "opco"; string Arg3 = "pcode"; int Arg4 = 8; verify_case(2, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); }

void test_case_3() { string Arg0 = "thereare"; string Arg1 = "arelots"; string Arg2 = "lotsof"; string Arg3 = "ofcases"; int Arg4 = 19; verify_case(3, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); }

void test_case_4() { string Arg0 = "aba"; string Arg1 = "b"; string Arg2 = "b"; string Arg3 = "b"; int Arg4 = 3; verify_case(4, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); }

void test_case_5() { string Arg0 = "x"; string Arg1 = "x"; string Arg2 = "x"; string Arg3 = "x"; int Arg4 = 1; verify_case(5, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); }

// END CUT HERE

};

// BEGIN CUT HERE

int main()

{

FourStrings ___test;

___test.run_test(-1);

return 0;

}

// END CUT HERE

poj3592

poj3304

超客的水墨烟雨

TopCoder SRM#677(Div2)(2/3)

分类目录

标签云

书签

近期评论

2025年4月
一	二	三	四	五	六	日
« 6月
	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