题意

洛谷 P1466 集合 Subset Sums

将1到N的整数分成两个和相同的集合,问有多少种分法?

分析

这道题其实是一道标准的经典DP(只要正确建模)。结果我一看数据范围只有39,第一反应是写了一个Meet-in-the-Middle出来。当然也不是不行……

DP的做法是这样的:把原问题换成,用1到N的整数之和表示某个数字,最多有多少种表示方法?然后思路就很简单了,用f[i][j]表示用前i个整数表示j的方法,f[i][j] = f[i-1][j] + f[i-1][j-i]

然后我才意识到对N大小的限制主要是为了动态规划的其中一维不要太大……

代码

DP

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
31
32
33
34
35
36
37
38
39
40
/*
ID: zhanghu15
TASK: subset
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>

using namespace std;
typedef long long int LL;

int N;
LL f[40][8000];

int main() {
ofstream fout("subset.out");
ifstream fin("subset.in");
fin >> N;
int sum = N * (N + 1) / 2;
if (sum % 2 != 0) {
fout << 0 << endl;
return 0;
}
f[0][0] = 1;
for (int i = 1; i <= N; i++) {
for (int j = 0; j < 8000; j++) {
f[i][j] = f[i-1][j];
if (j >= i)
f[i][j] += f[i-1][j-i];
}
}
fout << f[N][sum / 2] / 2 << endl;
return 0;
}

Meet-in-the-Middle

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/*
ID: zhanghu15
TASK: subset
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>

using namespace std;
typedef long long int LL;

int main() {
ofstream fout("subset.out");
ifstream fin("subset.in");
int N;
fin >> N;
int sum = N * (N + 1) / 2;
if (sum % 2 != 0) {
fout << 0 << endl;
return 0;
}
int halfSum = sum / 2;
int halfN = N / 2;
// Meet-in-the-Middle
map<int, int> cntMap;
// gather [1, halfN] sums
for (int i = 0; i < (1 << halfN); i++) {
int sum = 0;
for (int j = 0; j < halfN; j++)
if (i & (1 << j))
sum += j + 1;
// cout << i << ' ' << sum << endl;
cntMap[sum]++;
}
// gather [halfN+1, N] sums
LL ans = 0; // 注意数据范围……
for (int i = 0; i < (1 << (N - halfN)); i++) {
int sum = 0;
for (int j = 0; j < N - halfN; j++)
if (i & (1 << j))
sum += j + halfN + 1;
if (cntMap.find(halfSum - sum) != cntMap.end()) {
ans += cntMap[halfSum - sum];
}
}
fout << ans / 2 << endl;
return 0;
}

题意

洛谷 P1465 序言页码 Preface Numbering

求1到N的罗马数字表示中每个字母出现的次数。

分析

这道题出得有点令人无言以对(的简单)的感觉……总之做就是了。

罗马数字表示法和普通的十进制其实很类似,都是用单个数字来表示某个位,而且各个位的规律是差不多的。比如说,我们可以把一个四位的十进制数字这样分解:

  • 个位:1 -> I, 2 -> II, 3 -> III, 4 -> IV, 5 -> V, 6 -> VI, 7 -> VII, 8 -> VIII, 9 -> IX
  • 十位:1 -> X, 2 -> XX, 3 -> XXX, 4 -> XL, 5 -> L, 6 -> LX, 7 -> LXX, 8 -> LXXX, 9 -> XC
  • 百位:1 -> C, 2 -> CC, 3 -> CCC, 4 -> CD, 5 -> D, 6 -> DC, 7 -> DCC, 8 -> DCCC, 9 -> CM
  • 千位:1 -> M, 2 -> MM, 3 -> MMM(题目里没有更大的数字了)

所以直接按照这个方法去分解就可以啦!

我写得非常暴力,考虑到各个位之间的规律性,可以写得稍微更简单一点。不过因为数组清零时写成了sizeof(0)WA了一次……

题解里有各种花式简化方法。

代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/*
ID: zhanghu15
TASK: preface
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long int LL;

int main() {
ofstream fout("preface.out");
ifstream fin("preface.in");
int N;
fin >> N;
int d[4], n;
int ci = 0, cv = 0, cx = 0, cl = 0, cc = 0, cd = 0, cm = 0;
for (int i = 1; i <= N; i++) {
int x = i;
n = 0;
memset(d, 0, sizeof(d));
while (x > 0) {
d[n++] = x % 10;
x /= 10;
}

cm += d[3];

if (d[2] == 9) // 900 = CM
cc++, cm++;
else if (5 < d[2] && d[2] < 9) // 800 = DCCC
cd++, cc += d[2] - 5;
else if (d[2] == 5) // 500 = D
cd++;
else if (d[2] == 4) // 400 = CD
cc++, cd++;
else // 300 = CCC
cc += d[2];

if (d[1] == 9) // 90 = XC
cx++, cc++;
else if (5 < d[1] && d[1] < 9) // 80 = LXXX
cl++, cx += d[1] - 5;
else if (d[1] == 5) // 50 = L
cl++;
else if (d[1] == 4) // 40 = XL
cx++, cl++;
else // 30 = XXX
cx += d[1];

if (d[0] == 9) // 9 = IX
ci++, cx++;
else if (5 < d[0] && d[0] < 9) // 8 = VIII
cv++, ci += d[0] - 5;
else if (d[0] == 5) // 5 = V
cv++;
else if (d[0] == 4) // 4 = IV
ci++, cv++;
else // 3 = III
ci += d[0];
}

if (ci > 0) fout << "I " << ci << endl;
if (cv > 0) fout << "V " << cv << endl;
if (cx > 0) fout << "X " << cx << endl;
if (cl > 0) fout << "L " << cl << endl;
if (cc > 0) fout << "C " << cc << endl;
if (cd > 0) fout << "D " << cd << endl;
if (cm > 0) fout << "M " << cm << endl;
return 0;
}

题意

P1461 海明码 Hamming Codes

找出N个数字,每个数字的长度均为B位,且每两个数之间的海明距离都至少为D。如果有多个解,则输出排序后值最小的解。

分析

当然,我可以直接写个O(2^(2^B))的枚举加剪枝,而且的确能过。不过这是因为数据太弱了,而且刻意出的这么弱。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
------- test 1 [length 7 bytes] ----
16 7 3
------- test 2 [length 6 bytes] ----
2 7 7
------- test 3 [length 6 bytes] ----
3 6 4
------- test 4 [length 6 bytes] ----
5 5 1
------- test 5 [length 7 bytes] ----
10 8 4
------- test 6 [length 7 bytes] ----
20 6 2
------- test 7 [length 7 bytes] ----
32 5 1
------- test 8 [length 7 bytes] ----
50 8 2
------- test 9 [length 7 bytes] ----
60 7 2
------- test 10 [length 7 bytes] ----
16 8 3
------- test 11 [length 7 bytes] ----
15 8 4

在上述测试数据下,暴力方法的运行时间为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Compiling...
Compile: OK

Executing...
Test 1: TEST OK [0.004 secs, 1388 KB]
Test 2: TEST OK [0.004 secs, 1308 KB]
Test 3: TEST OK [0.004 secs, 1328 KB]
Test 4: TEST OK [0.004 secs, 1392 KB]
Test 5: TEST OK [0.000 secs, 1312 KB]
Test 6: TEST OK [0.000 secs, 1292 KB]
Test 7: TEST OK [0.000 secs, 1304 KB]
Test 8: TEST OK [0.000 secs, 1292 KB]
Test 9: TEST OK [0.000 secs, 1304 KB]
Test 10: TEST OK [0.000 secs, 1392 KB]
Test 11: TEST OK [0.000 secs, 1308 KB]

All tests OK.

来个N=64, B=8, D=4这样的数据,暴力解法得跑到天荒地老。

我的一种想法是,把这2^B个数字当做图的结点,数字之间的海明距离当做边权来建图,然后这个问题就变成了类似于找最大团。但是问题是我们需要找的不只是一个最大团,而是一个排序后数字最小的最大团,好像就不符合一般的问题范畴了。[1]

总之今天也是不想学习最大团算法的一天……

代码

如果把每次的判断__builtin_popcount(code[i] ^ next)都换成查表,常数应该能减少一点,但是并不能改变这个算法复杂度实在太高的事实……

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*
ID: zhanghu15
TASK: hamming
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long int LL;

int N, B, D;
int code[64];
int MAX;
bool found;

void dfs(int n) {
if (n == N) {
found = true;
return;
}
int next;
if (n == 0) next = 0;
else next = code[n - 1] + 1;
for (; next <= MAX; next++) {
if (found) return;
bool ok = true;
for (int i = 0; i < n; i++) {
if (__builtin_popcount(code[i] ^ next) < D) {
ok = false;
break;
}
}
if (!ok) continue;
code[n] = next;
dfs(n + 1);
}
}

int main() {
ofstream fout("hamming.out");
ifstream fin("hamming.in");
fin >> N >> B >> D;
MAX = (1 << B) - 1;
dfs(0);
for (int i = 0; i < N; i++) {
fout << code[i];
if (i % 10 == 9 || i == N - 1)
fout << endl;
else
fout << ' ';
}
return 0;
}

  1. wikipedia - Clique problem

题意

P1460 健康的荷斯坦奶牛 Healthy Holsteins

给定一些稻草(种类数量<=15),每种稻草可以为奶牛提供若干数量的若干种维他命,问最少需要多少种稻草才能为奶牛提供足够的维他命?

分析

我最开始以为这是一道01背包题,然后发现维他命有25种,25维的01背包可还行?最后发现原来稻草最多只有15种,那就直接2^G枚举好了。

代码

这次的枚举是用循环写的(而不是DFS之类)。但仔细想想,这个写法(专指这道题的写法)不怎么样,外面还加了一层处理稻草个数的循环。虽然这道题里可以把这个循环去掉然后手动判断稻草个数,但在其他很多状态DP里不如写成递归的……

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/*
ID: zhanghu15
TASK: holstein
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long int LL;

int V;
int need[25];
int sum[25];
int G;
int scoop[15][25];

int main() {
ofstream fout("holstein.out");
ifstream fin("holstein.in");

fin >> V;
for (int i = 0; i < V; i++)
fin >> need[i];
fin >> G;
for (int i = 0; i < G; i++)
for (int j = 0; j < V; j++)
fin >> scoop[i][j];

for (int num = 1; num <= G; num++) {
for (int x = 0; x < (1 << G); x++) {
if (__builtin_popcount(x) != num) continue;
memset(sum, 0, sizeof(sum));
for (int i = 0; i < G; i++) {
if ((x & (1 << i)) == 0) continue;
for (int j = 0; j < V; j++)
sum[j] += scoop[i][j];
}
bool ok = true;
for (int i = 0; i < V; i++) {
if (sum[i] < need[i]) {
ok = false;
break;
}
}
if (ok) {
fout << num;
for (int i = 0; i < G; i++)
if (x & (1 << i))
fout << ' ' << i + 1;
fout << endl;
return 0;
}
}
}
return 0;
}

题意

洛谷 P1459 三值的排序 Sorting a Three-Valued Sequence

给定一个只包含1,2,3的数组,问将这个数组排序最少需要多少次交换。

分析

这个好像是之前的翻译:贪心算法(USACO)的原题……所以做法也没什么好说的了。首先找出一次交换可以解决的“错位”二元组的数量,然后再找出需要两次交换才能解决的“错位”三元组的数量即可。只要仔细一想就可以发现,每种二元组和三元组的数量是固定的,只跟每个“区域”(排序之后某种元素应该占的位置)内的其他元素的数量相关。

以及我觉得这道题和Codeforces 1102D. Balanced Ternary String有一点点像。(虽然像的程度很有限就是了……)

代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
ID: zhanghu15
TASK: sort3
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long int LL;

int N;
int a[1000];
int num[4];
int cnt[4][4];

int main() {
ofstream fout("sort3.out");
ifstream fin("sort3.in");
fin >> N;
for (int i = 0; i < N; i++) {
fin >> a[i];
num[a[i]]++;
}
int start = 0;
// cnt[i][j]:在i“区域”内j的数量
for (int i = 1; i <= 3; i++) {
for (int j = 0; j < num[i]; j++) {
cnt[i][a[start + j]]++;
}
start += num[i];
}
int swaps = 0;
// 一次交换能解决的数所需交换次数
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
if (i == j) continue;
// 尽可能地将i区域内的j和j区域内的i相交换
int x = min(cnt[i][j], cnt[j][i]);
swaps += x;
cnt[i][j] -= x;
cnt[j][i] -= x;
}
}
// 两次交换能解决的数所需交换次数
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
if (i == j) continue;
int k = 6 - i - j;
// 尽可能地将i区域内的j和j区域内的k交换,然后再和k区域内的i交换
int x = min(min(cnt[i][j], cnt[j][k]), cnt[k][i]);
swaps += x * 2;
cnt[i][j] -= x;
cnt[j][k] -= x;
cnt[k][i] -= x;
}
}
fout << swaps << endl;
return 0;
}

题意

洛谷 P1458 顺序的分数 Ordered Fractions

给定N,求[0, 1]范围内分母小于等于N的所有既约分数,按大小排序。(1 <= N <= 160

分析

作为一道普通的题……可以说它是考察运算符重载之类的花样的(至少对C++选手是这样)。当然也可以写得更简单一些。总之,我就直接枚举了所有这个范围内的分数,把所有既约分数找出来,排了个序,然后输出。

法里数列(Farey sequence)

当然,这道题的题解里还有另一个生成解法:

  • 首先生成列表[0/1, 1/1]
  • 在列表的每两个分数之间插入一个新的分数,其分子和分母各为相邻两个分数分子和分母的和;于是得到:[0/1, 1/2, 1/1]
  • 以此类推:[0/1, 1/3, 1/2, 2/3, 1/1]
  • 继续以此类推:[0/1, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 1/1]
  • 直到新生成的分数的分母都大于N为止

我觉得这个方法很神奇。通过非常简单的数学推导就可以说明,将两个分数的分子和分母分别相加,得到的新分数的值位于这两个分数之间:

已知$\frac{a_1}{b_1} < \frac{a_2}{b_2}$,即$a_1b_2 < a_2b_1$;

两侧都加上$a_1b_1$,化简后得到$\frac{a_1}{b_1} < \frac{a_1 + a_2}{b_1 + b_2}$;

另一侧同理。

当然,这并不能说明很多其他的问题,比如为什么这种生成方法生成的都是既约分数,而且是不重不漏的。这时候就需要使用Farey sequence的一些性质了。n阶的Farey sequence就是我们题目里所求的序列。它的一个性质是这样的:如果$a/b$和$c/d$在某阶的Farey sequence中是相邻的,那么当Farey sequence的阶增加,它们之间出现的第一项就是$(a+c)/(b+d)$,且这一项会第一次出现在$b + d$阶的数列中。这个生成算法就利用了这一性质:它每次生成的并不严格是某一阶的Farey sequence,而可能会多一些项出来;不过这并不重要,因为它们迟早会出现的。

还有一些详细的分析就不写了,总之这个想法很有趣。

代码

普通的代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*
ID: zhanghu15
TASK: frac1
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long int LL;

struct Frac {
// 我着实不想去记分子和分母的英文了……
int up;
int down;

Frac() {
up = down = 0;
}

Frac(int x, int y) {
up = x;
down = y;
}

friend bool operator < (const Frac& f1, const Frac& f2) {
return f1.up * f2.down < f1.down * f2.up;
}
};

int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}

Frac f[160000];
int N;

int main() {
ofstream fout("frac1.out");
ifstream fin("frac1.in");
fin >> N;
int n = 0;
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= i; j++) {
if (gcd(i, j) > 1) continue;
f[n++] = Frac(j, i);
}
}
sort(f, f + n);
for (int i = 0; i < n; i++)
fout << f[i].up << '/' << f[i].down << endl;
return 0;
}

Farey数列生成器

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
31
32
33
34
35
/*
ID: zhanghu15
TASK: frac1
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long int LL;

ofstream fout("frac1.out");
ifstream fin("frac1.in");

int N;

void farey(int a1, int b1, int a2, int b2) {
if (b1 + b2 > N) return;
farey(a1, b1, a1 + a2, b1 + b2);
fout << (a1 + a2) << '/' << (b1 + b2) << endl;
farey(a1 + a2, b1 + b2, a2, b2);
}

int main() {
fin >> N;
fout << "0/1" << endl;
farey(0, 1, 1, 1);
fout << "1/1" << endl;
return 0;
}

题意

洛谷 P1457 城堡 The Castle

有一个M*N的方格图(1 <= M,N <= 50),其中方格外侧有一整圈墙,有些方格线上有墙。问这些墙形成了多少个房间,以及去掉一堵墙能形成的最大房间的面积?

分析

应该可以说是标准的Floodfill算法了。算法流程如下:

  • 对于每一个格子,如果它还没有被访问到,则房间数+1,并从该格子开始DFS
  • 在DFS过程中,将访问到的每一个格子都标为当前房间数(于是立刻可以得到共有多少个房间)
  • 对于每一堵墙,判断它两侧的格子是否属于不同房间,如果是,则拆掉这面墙可以将这两个房间连起来,且新房间的面积是原来两个房间的和

Floodfill的时间复杂度是O(M*N),枚举墙的时间复杂度也是O(M*N),因此总复杂度为O(M*N)

代码

其他部分都没有什么难的,但是在答案去重这部分遇到了一点小问题。题目要求以某个格子北侧或东侧的形式打印需要的墙,且:

  • 选择拆除后得到的房间面积最大的墙
  • 如果面积相同,则选择最靠西的格子
  • 如果同样靠西,则选择最靠北的格子
  • 如果同样靠北,则优先选择格子东侧的墙

这可真是复杂的要求……

所以我也写了一堆复杂的判断条件……

顺带一提,我终于意识到现在USACO题目左边(可能会出现)的数字是你已经通过了多少个样例了……

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/*
ID: zhanghu15
TASK: castle
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long int LL;

int M, N;

// west, north, east, south
int mx[4] = { 0, -1, 0, 1};
int my[4] = {-1, 0, 1, 0};
int module[50][50];
int visited[50][50];
int cnt[2501];
int n;

void dfs(int x, int y) {
for (int i = 0; i < 4; i++) {
if (module[x][y] & (1 << i)) continue;
int nx = x + mx[i], ny = y + my[i];
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
if (visited[nx][ny]) continue;
visited[nx][ny] = n;
cnt[n]++;
dfs(nx, ny);
}
}

int main() {
ofstream fout("castle.out");
ifstream fin("castle.in");

fin >> M >> N;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
fin >> module[i][j];

for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++) {
if (!visited[i][j]) {
n++;
visited[i][j] = n;
cnt[n]++;
dfs(i, j);
}
}
fout << n << endl;
int maxn = -1;
for (int i = 1; i <= n; i++)
maxn = max(maxn, cnt[i]);
fout << maxn << endl;
maxn = -1;
char ch;
int x, y;
// 事实证明光靠顺序去重不太可行
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (j < M - 1 && visited[i][j] != visited[i][j+1]) {
int sum = cnt[visited[i][j]] + cnt[visited[i][j+1]];
if (sum > maxn || (sum == maxn && (j < y || (j == y && i > x)))) {
maxn = sum;
ch = 'E';
x = i + 1;
y = j + 1;
}
}
if (i > 0 && visited[i-1][j] != visited[i][j]) {
int sum = cnt[visited[i][j]] + cnt[visited[i-1][j]];
if (sum > maxn || (sum == maxn && (j < y || (j == y && i > x)))) {
maxn = sum;
ch = 'N';
x = i + 1;
y = j + 1;
}
}
}
}
fout << maxn << endl;
fout << x << ' ' << y << ' ' << ch << endl;
return 0;
}

题意

洛谷 P1218 [USACO1.5]特殊的质数肋骨 Superprime Rib

定义super prime为每个前缀都是质数的数。例:7,73,733,7331都是质数,所以7331是super prime。给定N,问在所有长度为N的数里,有哪些数是super prime?

分析

这其实是一道搜索题。先搜索出长度为N-1的所有super prime,然后在这些数后面分别加上1,3,7,9(去掉2和5的倍数),判断得到的数是否为质数,然后就得到了长度为N的super prime。super prime的总数并不多,所以直接这样搜就可以了,也没有更多需要剪枝的。

题解的方法比我还暴力。我先打了个1-10000的质数表;题解根本没管这个,直接DFS搜索树,然后对每个数暴力枚举2, 3, 5, 7, 9...是否是它的因子……

查了一下,这个数列是有正式定义的(只不过正式定义并不叫super prime,super-prime是别的东西),叫做Right-truncatable primes,在OEIS上的编号为A024770。好像没有什么特别有趣的性质。[1]

代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
ID: zhanghu15
TASK: sprime
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long int LL;

int N;

int prime[10000];
int n;
bool isPrime[10000];
void init() {
memset(isPrime, 1, sizeof(isPrime));
isPrime[1] = false;
for (int i = 2; i < 10000; i++) {
if (isPrime[i]) {
prime[n++] = i;
for (int j = i * i; j < 10000; j += i)
isPrime[j] = false;
}
}
}

bool checkIsPrime(int x) {
if (x < 10000) return isPrime[x];
for (int i = 0; i < n; i++)
if (x % prime[i] == 0)
return false;
return true;
}

int main() {
ofstream fout("sprime.out");
ifstream fin("sprime.in");

fin >> N;
init();

vector<int> sprimes = {2, 3, 5, 7};
for (int i = 2; i <= N; i++) {
vector<int> next;
for (int x: sprimes) {
for (int j = 1; j <= 9; j++) {
int y = x * 10 + j;
if (checkIsPrime(y))
next.push_back(y);
}
}
sprimes = next;
}

for (int x: sprimes) fout << x << endl;

return 0;
}

  1. OEIS - A024770 Right-truncatable primes: every prefix is prime.

题意

P1217 [USACO1.5]回文质数 Prime Palindromes

[a, b]5 <= a < b <= 100,000,000)中所有的质回文数。

分析

上次从Leetcode 906中学到的技巧是,在需要找出具有某种性质的回文数时,先生成回文数,再判断性质。这是因为生成回文数的方法实际上是很简单的,随便拿一个数,把它反过来再接到后面就行。当然,需要注意生成奇数和偶数长度两种回文数的方法。

还有就是,需要判断10^8范围内的数是否为质数时,只需要打10^4范围内的表,这是因为,10^8范围内的合数必然有10^4范围内的因子。

怎么确定上下界是一个问题。我的方法是分别计算出ab的长度,然后只生成在相应长度范围的回文数;生成之后再判断是否在范围内。


题解里更详细地叙述了从小到大生成回文数的过程:

  • 生成长度为1的回文数:用1..9进行翻转,重复中间字符,得到1..9
  • 生成长度为2的回文数:用1..9进行翻转,不重复中间字符,得到11..99
  • 生成长度为3的回文数:用10..99进行翻转,重复中间字符,得到101...999
  • 生成长度为4的回文数:用10..99进行翻转,不重复中间字符,得到1001...9999

由于回文数一共也只有10000个左右,直接全生成出来再判断是否在[a, b]范围内也可以。

另一个观察是,任何长度为偶数的回文数都是11的倍数,所以可以不管除了11之外的所有长度为偶数的回文数。[1]


质回文数也是一个被正式定义了的序列。[2]

代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/*
ID: zhanghu15
TASK: pprime
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long int LL;

int prime[10000];
int n;
bool isPrime[10000];
void init() {
memset(isPrime, 1, sizeof(isPrime));
isPrime[1] = false;
for (int i = 2; i < 10000; i++) {
if (isPrime[i]) {
prime[n++] = i;
for (int j = i * i; j < 10000; j += i)
isPrime[j] = false;
}
}
}

bool checkIsPrime(LL x) {
if (x < 10000) return isPrime[x];
for (int i = 0; i < n; i++) {
if (x % prime[i] == 0) return false;
}
return true;
}

LL getPalindrome(LL x, int isOdd) {
LL l = 0, d[10], y = x;
while (y > 0) {
d[l++] = y % 10;
y /= 10;
}
for (int i = isOdd; i < l; i++)
x = x*10 + d[i];
return x;
}

int getLen(LL x) {
int l = 0;
while (x > 0) {
l++;
x /= 10;
}
return l;
}

int pow10[10] = {1, 10, (int) 1e2, (int) 1e3, (int) 1e4, (int) 1e5, (int) 1e6,
(int) 1e7, (int) 1e8, (int) 1e9};

int main() {
ofstream fout("pprime.out");
ifstream fin("pprime.in");
int a, b;
fin >> a >> b;

// 算出[1, 10000]范围内所有的质数
init();

// 枚举奇数和偶数长度的回文数(注意long long int)
int len1 = getLen(a) / 2, len2 = ceil(getLen(b) / 2.0);
for (int l = len1; l <= len2; l++) {
for (LL i = pow10[l]; i < pow10[l+1]; i++) {
LL x = getPalindrome(i, 1);
if (a <= x && x <= b && checkIsPrime(x))
fout << x << endl;
}
for (LL i = pow10[l]; i < pow10[l+1]; i++) {
LL x = getPalindrome(i, 0);
if (a <= x && x <= b && checkIsPrime(x))
fout << x << endl;
}
}
return 0;
}

  1. stackexchange - Proving a palindromic integer with an even number of digits is divisible by 11

  2. OEIS - A002385 Palindromic primes: prime numbers whose decimal expansion is a palindrome.

题意

P1216 [IOI1999][USACO1.5]数字三角形 Number Triangles

给定一个数字三角形,问从顶到底最大的路径和。

分析

非常简单的DP。对于每个点,判断从上左方走过来还是从上右方走过来和最大即可。上次从Leetcode 931中学到一点,对于这样的题,可以不新开一个数组,直接在输入数组上DP。

自底向上做当然也可以,就是有点怪异……

代码

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
31
/*
ID: zhanghu15
TASK: numtri
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int tri[1001][1001];
int main() {
ofstream fout("numtri.out");
ifstream fin("numtri.in");
int R;
fin >> R;
int ans = -1;
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= i; j++) {
fin >> tri[i][j];
tri[i][j] += max(tri[i-1][j], tri[i-1][j-1]);
if (i == R) ans = max(ans, tri[i][j]);
}
}
fout << ans << endl;
return 0;
}