2 简答题

2.1 整数划分问题

设函数 Q(n,m)：表示整数 $n$ 划分出的被加数都不超过 $m$ 的划分数目。

则有：

Q(n,1) = 1， m = 1

当 $m = 1$ 时只有一种分发，即 $n$ 个 $1$ 相加

Q(1,m) = 1，n = 1

当 $n = 1$ 时只有一种分发，即 $1$ 个 $1$

Q(n,n) = 1 + Q(n,n-1)，m = n

将划分时包含 $n$ 和不包含 $n$ 可分为两种情况，其分别的划分数为 $1$ 和 $Q(n,n-1)$

Q(n,m) = Q(n,n)，n < m

当 $m$ 大于 $n$ 时，其划分方案数与 Q(n,n) 相同

Q(n,m) = Q(n,m-1) + Q(n-m,m)，n > m > 1

当 $n$ 大于 $m$ 时，可以将其分为划分数中包含 $m$ 和不包含 $m$ 两种情况，其分别的方案数为 Q(n-m,m) 和 Q(n,m-1)

所以有公式：

\[Q(n,m) = \begin{cases} 1 & n=1,m=1 \\ \\ Q(n,n) & n < m \\ \\ 1+Q(n,n-1) & n = m \\ \\ Q(n,m-1) + Q(n-m,m) & n > m > 1 \end{cases} \]

2.2 成绩及格问题

在语文中遍历每个几个学生学号，在遍历到每个学号时，去代数中查找及格学生学号中有没有该学号，若有该学号，再去外语中查找是否存在该学号，若存在则该学生是三科全及格的学生，否则该学生至少有一门不及格。若语文中并没有该学生学号，则该学生不可能三科全及格。

2.3 吉普车穿越沙漠问题

问题要求要以最少的耗油量穿越沙漠，即到达终点时，沙漠中的各临时油库和车的装油量均为 $0$，这样只能从终点开始向前倒着推解贮油点和贮油量。

怎样走效率高：

首先不计方向这段应走奇数次（保证最后向前走）。
每次向前行进时吉普车是满载。
要能贮存够下一加油点的贮油量，路上耗油又最少。

第一个加油站：有 $500$ 加仑油，距离终点 $500km$，则正好到达终点油量为 $0$。

第二段加油站：要保证路上耗油的 $500$ 加仑和第一个加油站的 $500$ 加仑，则该加油站要有 $1000$ 加仑。

要给第一个加油站加 $500$ 加仑的油，因为路上会有消耗，所以应该运送两次油，其中最后一次可以直接到第一个加油站，给加油站加完油之后不需要返回。设两加油站的距离为 $x$，则 $500 - 2x + 500 - x = 500$，所以 $x = \frac{500}{3}$

同理后面为 $\frac{500}{5},\frac{500}{7} \cdots $

从倒数第一个加油点，按照上面推导的距离建立加油点，直到即将建立的加油点超过起点终止。

3 编程题

3.1 最长上升子序列

#include <bits/stdc++.h>
#define N 10010

int idx;
int n,maxn;
int pos[N];
int dp[N],a[N];

int main() {
	std::cin >> n;
	for (int i = 1 ; i <= n ; i ++ ) std::cin >> a[i];

	maxn = 1;
	pos[0] = -1;
	for (int i = 1 ; i <= n ; i ++ ) {
		dp[i] = 1;
		for (int j = 1 ; j < i ; j ++ ) {
			if(a[i] > a[j] && dp[j] + 1 > dp[i]) {
				dp[i] = dp[j] + 1;
				pos[i] = j;
				if(dp[i] > maxn) {
					idx = i;
					maxn = dp[i];
				}
			}
		}
	}

	std::stack<int> stk;
	while(pos[idx] != -1) {
		stk.push(a[idx]);
		idx = pos[idx];
	}
	while(!stk.empty()) {
		std::cout << stk.top() << " ";
		stk.pop();
	}
	return 0;
}

3.2 埃及分数

设有分数 $\frac{a}{b}$，令 $\frac{b}{a} = x \cdots y$，则有 $ b = ax + y$，则有如下推导：

\[\begin{align*} \frac{a}{b} = \frac{a}{ax+y} &= \frac{a(x+1)+y-y}{(ax+y)(x+1)} \\ &= \frac{ax+y+1-y}{(ax+y)(x+1)} \\ &= \frac{1}{(x+1)} + \frac{a - y}{(ax+y)(x+1)} \\ &= \frac{1}{x+1} + \frac{a-y}{b(x+1)} \end{align*} \]

所以只需要特判 $b$ 是 $a$ 的倍数的情况，若是则直接输出，不是则利用公式迭代。

#include <bits/stdc++.h>
#define ll long long

int main() {
    ll a,b;
    scanf("%lld/%lld",&a,&b);
    while(a != 1) {
        if(b % a == 0) {
            b = b / a;
            break;
        }
        int x = b / a;
        int y = b % a;
        printf("%lld/%lld+",1,x+1);

        a -= y;
        b *= x + 1;
    }
    printf("%lld/%lld\n",1,b);

    return 0;
}

JZTXT

高级算法