算法编程小白机试指南(大佬勿进)

常规算法,奇巧淫技,骗分手段

Posted by WeiYang on 2019-07-12

大佬就不用往下看了,这篇文章没有任何逻辑,没有任何进阶的指导意义,纯粹为了应付各种机试(夏令营机试、保研机试、程序设计实践考试等等),对正经编程竞赛没有任何帮助。我就想到哪写到哪了,不定期想到新的在更新。

暴力打表法


错位排列

题目: 给定\(n\)个数字\(1, 2, \ldots, n\),求任意取一个排列,任意第\(i\)个位置上的元素都不等于\(i\)的概率是多少?

如果知道结论的话,这就是一道普通的错位排列题,常规做法是求出递推式
\[f(n) = (n-1)(f(n-1)+f(n-2))\]
然后除以全排列的数量\(n!\)就行了,这里就不讲怎么求的了,百度有很多。这里讲讲如果不会求怎么办?

首先想到的暴力方法就是暴力枚举所有排列,然后看看有多少排列满足题目中的错位的条件。C++中的库函数next_permutation正好可以帮助我们枚举全排列,代码如下:

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a[30] = {0, 0, 1};
int b[30];
int main() {
for (int n = 3; n <= 20; ++n) {
for (int i = 1; i <= n; ++i) {
b[i] = i;
}
int cnt = 0;
do {
int flag = 1;
for (int i = 1; i <= n; ++i) {
if (b[i] == i) {
flag = 0;
break;
}
}
cnt += flag;
} while (next_permutation(b + 1, b + n + 1));
a[n] = cnt;
printf("%d, ", cnt);
}
return 0;
}

然后就可以跑出\(n \le 12\)的结果,但是再大就跑不出来了,因为全排列数量太多了,跑得太慢了。但是不用管,因为题目要求的不是错位排列的数量,而是除以全排列数量之后的概率,巧的是,\(n > 12\)之后概率保留两位小数的结果是完全相同的,所以直接取\(n = 12\)的概率就行了,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL p[30] = {1, 1, 2};
LL a[30] = {0, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841};
int main() {
for (int i = 3; i < 30; ++i) {
p[i] = p[i - 1] * (LL)i;
}
int T;
scanf("%d", &T);
while (T--) {
int n;
scanf("%d", &n);
if (n > 12)
n = 12;
double res = (double)a[n] / p[n] * 100.0;
printf("%.2f%%\n", res);
}
return 0;
}

这样即使你完全不会计算,也可以100分通过这题啦。