题意

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

题意

洛谷 P1214 [USACO1.4]等差数列 Arithmetic Progressions

在双平方数集合(p^2 + q^2, 0 <= p, q <= M)中寻找长度为N的等差数列。3 <= N <= 251 <= M <= 250

分析

我的做法是这样的。

首先枚举得到所有双平方数并去重和排序,复杂度为O(M^2);并且用数组ind记录每个数是否是双平方数,以及如果是,它排序后的index。

枚举公差长度b1 <= b <= 2*M^2 / (N-1)):对每个双平方数,用数组maxlen维护以它为结尾的公差为b的等差数列的最大长度。从小到大枚举所有双平方数x

  • 如果x - b不存在,则记maxlen[x] = 1(即数列中只有它一个数)
  • 如果maxlen[x] >= N,则输出首项为x - (N-1)*b的等差数列(也即输出末项为x的等差数列,这样可以做到不重不漏)
  • 如果x + b也是双平方数,则将maxlen[ind[x + b]]更新为maxlen[x] + 1

这种做法的时间复杂度约为O(M^4 / (N-1)),时间最长的测试点需要2.558s才能通过。

题解里的第一种算法剪枝的方法有些不同。首先也是预处理出所有的双平方数并排序;然后对于任意两个双平方数,判断它们是否有可能成为一个长度为N的等差数列的前两项(判断方法是期望的末项和倒数第二项是否存在),如果有可能,则将这两个数的差记录下来,作为有可能的公差;最后对于每个有可能的公差,列举每个双平方数,判断将这个数作为首项是否存在长度为N的等差数列,如果有则输出。

第二种算法也没剪枝,就直接枚举公差和首项,然后判断是否存在长度为N的等差数列。

代码

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

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

using namespace std;

int a[62500];
int maxlen[62500];
bool isBisquare[125001];
int ind[125001];

int main() {
ofstream fout("ariprog.out");
ifstream fin("ariprog.in");
int N, M;
fin >> N >> M;
int n = 0;
for (int i = 0; i <= M; i++)
for (int j = i; j <= M; j++) {
isBisquare[i*i + j*j] = true;
}
int m = 2*M*M;
memset(ind, -1, sizeof(ind));
for (int i = 0; i <= m; i++) {
if (isBisquare[i]) {
a[n] = i;
ind[i] = n;
n++;
}
}
bool found = false;
for (int b = 1; b <= m/(N-1); b++) {
memset(maxlen, 0, sizeof(maxlen));
for (int i = 0; i < n; i++) {
if (maxlen[i] == 0) maxlen[i] = 1;
if (maxlen[i] >= N) {
fout << a[i] - (N-1)*b << ' ' << b << endl;
found = true;
}
if (a[i]+b <= m && ind[a[i]+b] >= 0) {
maxlen[ind[a[i]+b]] = maxlen[i] + 1;
}
}
}
if (!found) fout << "NONE" << endl;
fin.close();
fout.close();
return 0;
}

题意

洛谷 P3650

N座山,每座山有一个高度([0, 100]范围内)。现在需要修改这些山的高度(每座山只修改一次),使得最高的山和最低的山之间的高度差不大于17;修改高度的代价是高度变化值的平方。问如何修改才能使总代价最小。N<=1000

分析

还是暴力。这次题解里给的方法是,枚举所有的长度为17的区间,然后对于每个区间,计算把所有山的高度修改到这个区间内的代价。算法复杂度为O(N*M),其中M是区间总数(也就是大约100个,实际84个),已经足够了。

当然事实上可以把复杂度减到更低,用计数排序的方法来统计山的高度,然后对于每个区间,计算把每种高度(可能对应几座山)修改到区间内的代价。复杂度是O(M^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
/*
ID: zhanghu15
TASK: skidesign
LANG: C++14
*/

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

using namespace std;

int cnt[101];

int main() {
ofstream fout("skidesign.out");
ifstream fin("skidesign.in");
int N;
fin >> N;
for (int i = 0; i < N; i++) {
int x;
fin >> x;
cnt[x]++;
}
int ans = -1;
// take i as the base
for (int i = 0; i <= 83; i++) {
int low = i, high = i + 17, cur = 0;
for (int j = 0; j <= 100; j++) {
if (cnt[j] == 0) continue;
if (j < low) cur += (low - j) * (low - j) * cnt[j];
else if (j > high) cur += (j - high) * (j - high) * cnt[j];
}
ans = ans == -1 ? cur : min(ans, cur);
}
fout << ans << endl;
return 0;
}

非暴力

TBD

题意

USACO 2013 December Contest, Bronze Problem 3. Wormholes

原来USACO是会新加题的吗!!因为是新题所以好像洛谷没有……

在一个平面上有最多12个虫洞(偶数个),虫洞两两相连,可以互相传送;Bessie在平面上只会向+x方向移动。问有多少种虫洞连接方式会让Bessie困在循环中,

分析

这道题我做了好久,设计得相当不错,真是相当不错,我本来以为是暴力水题的来着……

需要注意的一点是,Bessie是向+x方向走,所以能够相互走到的是相邻且y坐标相等的虫洞,不是x坐标相等的虫洞……我最开始就写错了,后来就直接把x和y换了一下。

遍历虫洞两两相连的方法可以直接用回溯法解决。问题显然在于得到一个连接顺序之后,怎么判定有环。最开始我直接把这个问题建模成了“判断一张图上是否有环”,图上的边就是相连的虫洞和能相互走到的虫洞。然后我就挂了。问题在于,“连接虫洞的边”和“走路能到的边”不是一种边,在实际判定有环的时候,必须交替着走,而且判定有环的时候,不止要看虫洞是否重复,也要看上一条边是否重复,因为显然,走路到达一个虫洞(然后传送)和传送到达一个虫洞(然后开始走路)是两种不同的情况。

这些问题我搞了一晚上……然后错了三次,我注意到USACO左侧开始有一个类似于"3/10"的标签了,这是否意味着交10次就不能再交了(还是交满10次自动出题解)?

题解里又有一个视频(大概因为是新题吧),里面的解法很巧妙:既然必须交替走两种边,那我一次就走两条边,传送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
66
67
68
69
70
71
72
73
74
75
76
77
78
/*
ID: zhanghu15
TASK: wormhole
LANG: C++14
*/

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

using namespace std;

int N;
pair<int, int> wormholes[12];
int walkPairing[12];
int wormholePairing[12];
bool visited[12][2]; // 记录走/跳是必要的
int ans;

// 两类边交替走,找环
bool dfs(bool isWalking, int x) {
if (visited[x][isWalking]) return true;
visited[x][isWalking] = true;
if (isWalking && walkPairing[x] != -1)
return dfs(!isWalking, walkPairing[x]);
else if (!isWalking)
return dfs(!isWalking, wormholePairing[x]);
return false;
}

void backtrack(int cur) {
// 找到了一组合法的配对
if (cur == N) {
// 尝试DFS找环
for (int i = 0; i < N; i++) {
memset(visited, 0, sizeof(visited));
if (dfs(true, i)) {
ans++;
break;
}
}
return;
}
if (wormholePairing[cur] != -1)
backtrack(cur + 1);
else {
for (int i = cur + 1; i < N; i++) {
if (wormholePairing[i] != -1) continue;
wormholePairing[cur] = i;
wormholePairing[i] = cur;
backtrack(cur + 1);
wormholePairing[cur] = wormholePairing[i] = -1;
}
}
}

int main() {
ofstream fout("wormhole.out");
ifstream fin("wormhole.in");
fin >> N;
// x和y坐标搞反了……
for (int i = 0; i < N; i++)
fin >> wormholes[i].second >> wormholes[i].first;
// 找能走到的虫洞
sort(wormholes, wormholes+N);
memset(walkPairing, -1, sizeof(walkPairing));
for (int i = 1; i < N; i++)
if (wormholes[i-1].first == wormholes[i].first)
walkPairing[i-1] = i;
// 寻找所有可能的虫洞配对方法
memset(wormholePairing, -1, sizeof(wormholePairing));
backtrack(0);

fout << ans << endl;
return 0;
}

题意

洛谷 P2963

有一些密码锁组合(形如[1, 2, 3],每个数的范围是[1, N]),定义两个组合每个位置上的数相差两个位置以内时是接近的(密码锁是一个圈,所以1和N是相邻的)。给定两个已知组合,问所有组合里和这两个组合中的至少一个接近的有多少。

分析

暴力方法和上一道题如出一辙。可能需要注意的两点:

  • 要求是和至少一个组合接近,而不是每个位置上的数和至少一个组合在这个位置上的数相近。不过这一点仍然可以用来剪枝。
  • 如何判断接近。题解里的方法是abs(a-b) <= 2 || abs(a-b) >= N-2;我写的是(a-b+N) % N <= 2 || (b-a+N) % N <= 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
/*
ID: zhanghu15
TASK: combo
LANG: C++14
*/

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

using namespace std;

bool isNear(int a, int b, int N) {
return (a-b+N) % N <= 2 || (b-a+N) % N <= 2;
}

int main() {
ofstream fout("combo.out");
ifstream fin("combo.in");
int N;
int combo1[3];
int combo2[3];
fin >> N;
fin >> combo1[0] >> combo1[1] >> combo1[2];
fin >> combo2[0] >> combo2[1] >> combo2[2];
int ans = 0;
for (int c1 = 1; c1 <= N; c1++) {
if (!isNear(combo1[0], c1, N) && !isNear(combo2[0], c1, N)) continue;
for (int c2 = 1; c2 <= N; c2++) {
if (!isNear(combo1[1], c2, N) && !isNear(combo2[1], c2, N)) continue;
for (int c3 = 1; c3 <= N; c3++) {
if (isNear(combo1[0], c1, N) && isNear(combo1[1], c2, N) && isNear(combo1[2], c3, N) ||
isNear(combo2[0], c1, N) && isNear(combo2[1], c2, N) && isNear(combo2[2], c3, N))
ans++;
}
}
}
fout << ans << endl;
return 0;
}

题意

洛谷 P1211

分析

是个水题。开始时我还觉得会很难写,结果发现,与其正经地去按位搜索,不如直接枚举所有的两位数和三位数,判断它们和它们的乘积的中间结果是否满足题目要求。这样就非常好写了。

对于难(时间复杂度高的)题来说,当然还是得正经搜索,但对于简单题,改成这样简单的搜索反而更好。这是我从Leetcode 401. Binary Watch里学到的。题解也是这个做法。

代码

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

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

using namespace std;

bool digits[10];

bool isOk(int number, int length = -1) {
int i = 0;
while (number > 0) {
if (!digits[number % 10]) return false;
number /= 10;
i++;
}
if (length != -1 && i != length) return false;
return true;
}

int main() {
ofstream fout("crypt1.out");
ifstream fin("crypt1.in");
int N;
fin >> N;
for (int i = 0; i < N; i++) {
int x;
fin >> x;
digits[x] = true;
}
int ans = 0;
for (int mul1 = 111; mul1 <= 999; mul1++) {
if (!isOk(mul1)) continue;
for (int mul2 = 11; mul2 <= 99; mul2++) {
if (!isOk(mul2)) continue;
int part1 = (mul2 % 10) * mul1;
if (!isOk(part1, 3)) continue;
int part2 = (mul2 / 10) * mul1;
if (!isOk(part2, 3)) continue;
int res = mul1 * mul2;
if (!isOk(res, 4)) continue;
ans++;
}
}
fout << ans << endl;
return 0;
}

题目来源:https://leetcode.com/problems/largest-time-for-given-digits/description/

标记难度:Easy

提交次数:1/2

代码效率:4ms

题意

给定4个数字,求出能用这些数字排列成的最大时间(24小时制)。

分析

这次我没参加正式比赛,因为我参加internal contest去了。很有趣,而且有很多感受,我可以再写一篇文章出来了……internal contest虽然人少,也是有计时和排名的,我看了一下,我在正式比赛中大概能排在50-100名左右吧。


这道题看起来很简单,因为“时间”这个属性限制了解的数量,这使得暴力方法非常适用;这一点让我想起之前做的Leetcode 401. Binary Watch,也是暴力方法优于搜索方法的例子。反正就是枚举这4个数字的排列,然后从中选出合法且最大的时间。

但是这道题的通过率相当低(虽然通过的人数显然不低)。(我猜)这是因为很多人都没有处理时间数字前面带0的情况,于是在[0, 0, 0, 0]这样的样例中就挂了。我很难想到什么保证自己能想到这样的corner case的例子,也许只能多练吧。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
string largestTimeFromDigits(vector<int>& A) {
sort(A.begin(), A.end());
int maxtime = -1;
string time;
do {
int hour = A[0] * 10 + A[1];
if (hour >= 24) continue;
int minute = A[2] * 10 + A[3];
if (minute >= 60) continue;
if (hour * 100 + minute > maxtime) {
maxtime = hour * 100 + minute;
time = to_string(A[0]) + to_string(A[1]) + ":" + to_string(A[2]) + to_string(A[3]);
}
} while (next_permutation(A.begin(), A.end()));
return time;
}
};

题意

洛谷 P1202

分析

比较简单的模拟题(或者说是暴力),但是思路有点绕。在做题的时候,我好好考虑了一下,这个月的13号和下个月的13号之间到底应该差多少天,结论是天数取决于这个月的天数,而和下个月的天数无关:因为我们可以把下个月的13天挪到这个月前面来,这样就凑齐了这个月的所有天数。这好像是一个很简单的结论,但是在日常生活中我从来没有仔细思考过这个问题,总有种“应该是个平均值吧”的错觉。

代码

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

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

int daysInMonth[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int thirteens[7];

int main() {
ofstream fout("friday.out");
ifstream fin("friday.in");
int N;
fin >> N;

int dayOfWeek = 5; // 1900.1.13是周六
int year = 1900;
for (int i = 0; i < N; i++) {
for (int month = 0; month < 12; month++) {
thirteens[dayOfWeek]++;
dayOfWeek += daysInMonth[month];
if (month == 1 && ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0))
dayOfWeek++;
dayOfWeek %= 7;
}
year++;
}

// 输出顺序是周六,周日,周一,周二……有趣
// 好吧!USACO不接受行尾空格!
fout << thirteens[5];
for (int i = 6; i < 12; i++)
fout << ' ' << thirteens[i % 7];
fout << endl;

return 0;
}