复旦大学2021年计算机学院机试题解
写在前面
更新说明
2021年真题
第一题
例子
输入 ：
3, 1, 4, 3, null, 1, 5
plaintext输出 ：4（图中蓝色节点是关键节点）
解题思路
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> data;
int count = 0;
bool charIsDigit(char a){
return a <= '9' and a >= '0';
}
int charToInt(char a){
return a - '0';
}
int getParentIndex(int childIndex){
return (childIndex - 1) / 2;
}
void judgeKeyNode(int index){
int pivot = data[index];
int flag = true;
while (index != 0){
index = getParentIndex(index);
if (data[index] > pivot){
flag = false;
break;
}
}
if (flag){
count++;
}
}
int main(){
string input;
getline(cin, input);
int nodeValue = 0;
bool remain = false; // 前面是否还有连续的值
for (int i=0; i<input.length(); i++){
char tmp = input[i];
if (charIsDigit(tmp)){
nodeValue = nodeValue * 10 + charToInt(tmp);
}else{
if (nodeValue != 0){
data.push_back(nodeValue);
nodeValue = 0;
}else if(tmp == 'n'){
data.push_back(-1);
}
}
}
data.push_back(nodeValue);
// 构建树
for (int i=0; i<data.size(); i++){
if (data[i] != -1){
judgeKeyNode(i);
}
}
cout << count << endl;
return 0;
}
cpp
第二题
题目描述
解题思路
示例代码
#include <cstdio>
int main(){
int n;
scanf("%d", &n);
int dp[n+1];
// 初始化dp
dp[0] = 1;
dp[1] = 1;
for (int i=2; i<=n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
printf("%d\n", dp[n]);
}
cpp
后续改进与说明
第三题
设有非负整数序列{x₁, x₂, …, xₙ}。对于每一个x_i可以选择其相反数或保持原值，请计算满足∑(±x_i) = E的不同组合数目，并阐述解决这一问题的具体方法及其对应的算法实现。
1, 1, 1, 1, 1, 3
plaintext例子输出 ：
5
plaintext样例解释 ：5 种取法分别为：
-1+1+1+1+1 = 3
1-1+1+1+1 = 3
1+1-1+1+1 = 3
1+1+1-1+1 = 3
1+1+1+1-1 = 3
plaintext解题思路 ：设dp[i][v]表示从前i个数中选择若干个数使得它们的期望值为v时的最大组合数目。
状态转移方程定义如下：对于每个i>0和v, 有
dp[i][v] = dp[i-1][v - data_{i-1}] + dp_{i-1}[v + data_i]
其中data是一个存储原始数据序列的数据结构，默认从索引0开始计算。
此外，在状态转移过程中需要满足以下约束条件：
-\sum_{k=0}^{n} |data_k| \leq v - data_{i} \leq \sum_{k=0}^{n} |data_k|
-\sum_{k=0}^{n} |data_k| \leq v \pm data_i \leq \sum_{k=0}^{n} |data_k|
这里\sum_{k=0}^{n}|data_k|代表原始数据序列所有元素绝对值之和。边界条件设定为：当i=0, j=0, 初始状态满足d[0][j]=\delta_{j, 0}（即当j=0, 组合数目d[0][j]=1, 否则$d[0][j]= ）.
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
vector<int> data;
int expect = 0; // 期望值
int result = 0; // 有多少种取法
bool charIsDigit(char a) {
return a <= '9' and a >= '0';
}
int charToInt(char a) {
return a - '0';
}
int main() {
string input;
getline(cin, input);
int nodeValue = 0;
for (int i = 0; i < input.length(); i++) {
char tmp = input[i];
if (charIsDigit(tmp)) {
nodeValue = nodeValue * 10 + charToInt(tmp);
} else {
if (nodeValue != 0) {
data.push_back(nodeValue);
nodeValue = 0;
}
}
}
// 最后一个值为期望值
expect = nodeValue;
int sum = 0;
for (int i = 0; i < data.size(); i++) {
sum += data[i];
}
vector<map<int, int>> dp(data.size() + 1);
// 初始化
for (int j = 0; j <= data.size(); j++) {
for (int i = -sum; i <= sum; i++) {
if (i == 0 and j==0) {
dp[j][i] = 1;
} else {
dp[j][i] = 0;
}
}
}
// DP的主过程
for (int i = 1; i<=data.size(); i++){
for (int v=-sum; v<=sum; v++){
int tmp1 = 0, tmp2 = 0, currentNum = data[i-1];
if (-sum <= v - currentNum and v-currentNum <= sum){
tmp1 = dp[i-1][v - currentNum];
}
if (-sum <= currentNum + v and currentNum + v <= sum){
tmp2 = dp[i-1][v+currentNum];
}
dp[i][v] = tmp1 + tmp2;
}
}
cout << dp[data.size()][expect] << endl;
return 0;
}
cpp
历年真题（2011-2020）专题总结
历年真题精选了本人当时准备机试时重点练习的真题。对于其中一些题目而言，由于其复杂性较高或趣味性不足而被排除在练习之外。
动态规划
动态规划可视为复旦历年机试的核心内容之一。
在这一部分中通常会涉及多个常见考点。
该部分的题目往往具有较高的难度集中度。
2011 最长公共子序列
问题描述 ：给定三个连续子序列，请计算这三个连续子序列的最大公共连续子序列
输入：
abcd acb abc
输出：
ab
示例代码 ：
#include <iostream>
#include <string>
using namespace std;
/** * 明显的LCS问题
* 设dp[i][j][k]是指字符串1第i个字符串2第j个字符串3第k个字符之前的最长公共子序列
* 状态方程：
* dp[i][j][k] = dp[i-1][j-1][k-1] + str1[i]; if str1[i] == str2[j] == str3[k]
* dp[i][j][k] = max{dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1]}
* 边界条件:
* dp[][][] = 0;
*/
int main(){
string str1, str2, str3, tmp, ans;
cin >> str1 >> str2 >> str3;
string dp[str1.length() + 1][str2.length() + 1][str3.length() + 1];
for (int i=1; i<=str1.length(); i++){
for (int j=1; j<=str2.length(); j++){
for (int k=1; k<str3.length(); k++){
if (str1[i-1] == str2[j-1] and str1[i-1] == str3[k-1]){ // 相等
tmp = dp[i-1][j-1][k-1];
tmp.push_back(str1[i-1]);
dp[i][j][k] = tmp;
}else{ // 不想等
int len1 = dp[i-1][j][k].length(), len2 = dp[i][j-1][k].length(), len3 = dp[i][j][k-1].length();
if (len1 > len2 and len1 > len3){
dp[i][j][k] = dp[i-1][j][k];
} else if(len2 > len1 and len2 > len3){
dp[i][j][k] = dp[i][j-1][k];
} else{
dp[i][j][k] = dp[i][j][k-1];
}
}
}
}
}
// 输出结果
for (int i=1; i<=str1.length(); i++){
for (int j=1; j<=str2.length(); j++){
for (int k=1; k<=str3.length(); k++){
if (dp[i][j][k].length() > ans.length()){
ans = dp[i][j][k];
}
}
}
}
cout << ans << endl;
}
cpp
2014 字符串的编辑距离
这个题存在的问题是将该问题误认为是LCS的问题进行处理。
当被当作LCS问题进行处理时无法应对该特定情况。
具体来说，在这种情况下算法只能识别出最长的共同子序列长度为1而无法捕捉到更长的潜在匹配。
题目描述 ：
把两个字符串变成相同的三个基本操作定义如下：
1.修改一个字符（如把a变成b）
2.增加一个字符(如abed 变成abedd)
3.删除一个字符（如jackbllog 变成jackblog）
针对于jackbllog到jackblog只需要删除一个或增加一个l 就可以把两个字符串变为相同。
把这种操作需要的最小次数定义为两个字符串的编辑距离L。
编写程序计算指定文件中字符串的距离。输入两个长度不超过512字节的ASCII字符串，在屏幕上输出字符串的编辑距离。
输入：
Hello world!
Hello word!输出：
1
#include <iostream>
#include <string>
using namespace std;
/** * 设dp[i][j]是指当字符串1第i个位置和字符串2第j个位置的最小编辑距离
* 状态转移方程为： dp[i][j] = dp[i-1][j-1] if str1[i] == str2[j]
* dp[i][j] = min{dp[i-1][j], dp[i][j-1]} + 1; else
* 边界条件为：
* dp[i][0] = i
* dp[0][j] = j
*/
int main(){
string input1, input2;
getline(cin, input1);
getline(cin, input2);
int length1 = input1.length(), length2 = input2.length();
int dp[length1][length2];
// 处理dp边界
for (int i=0; i<=length1; i++){
dp[i][0] = i;
}
for (int j=0; j<=length2; j++){
dp[0][j] = j;
}
// dp过程
for (int i=1; i<=length1; i++){
for (int j=1; j<=length2; j++){
if (input2[j-1] == input1[i-1]){
dp[i][j] = dp[i-1][j-1];
}else{
if (dp[i-1][j] < dp[i][j-1]){
dp[i][j] = dp[i-1][j] + 1;
}else{
dp[i][j] = dp[i][j-1] + 1;
}
}
}
}
cout << dp[length1][length2] << endl;
return 0;
}
cpp
2016 求最大连续公共字串长度
题目描述 ：给定两个字符串，求最大公共字串的长度，长度小于1000
输入 ：
1111hello2222
1133hello444输出 ：
5 #include <iostream>
#include <string>
using namespace std;
/*** * 是一道很明显DP的问题
* 设dp[i][j]是字符串1第i个位置与字符串2第j个位置之前的最大连续字符串的长度
* 状态转移方程： if (input[i] == input[j]) dp[i][j] = dp[i-1][j-1]
* else dp[i][j] = 0;
* 边界条件： 0
*/
int main(){
string input1, input2;
getline(cin, input1);
getline(cin, input2);
int length1 = input1.length(), length2 = input2.length(), ans;
int dp[length1 + 1][length2 + 1];
// 初始化
for (int i=0; i<=length1; i++){
for (int j=0; j<=length2; j++){
dp[i][j] = 0;
}
}
// DP
for (int i=1; i<=length1; i++){
for (int j=1; j<=length2; j++){
if (input1[i-1] == input2[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
}
}
}
// 找最大值
for (int i=0; i<=length1; i++){
for (int j=0; j<=length2; j++){
if (dp[i][j] > ans){
ans = dp[i][j];
}
}
}
cout << ans << endl;
}
cpp
2019 最大连续子序列
#include <cstdio>
#include <vector>
using namespace std;
vector<int> data, dp;
// 最大连续子序列 复旦2019年真题
/** * 这里很明显是一个动态规划的题
* 设dp[i]是以第i个结尾的序列的最大值
* 1. 状态转移方程
* dp[i] = { dp[i-1] + data[i], dp[i-1] + data[i] >= 0
* 0 , dp[i-1] + data[i] < 0
* 2. 边界条件
* dp[0] = 0;
*/
int main(){
int n, tmp, max=0;
scanf("%d", &n);
for (int i=0; i<n; i++){
scanf("%d", &tmp);
data.push_back(tmp);
}
// 初始化
for (int i=0; i<=n; i++){
dp.push_back(0);
}
for (int i=1; i<=n; i++){
int pivot = dp[i-1] + data[i-1];
if (pivot >= 0){
dp[i] = pivot;
}else{
dp[i] = 0;
}
}
for (int i=0; i<=n; i++){
if (dp[i] > max){
max = dp[i];
}
}
printf("%d\n", max);
return 0;
}
cpp
2020 序列
题目描述 ：给定⼀个⻓为n的序列 A，其中序列中的元素都是0~9之间的整数，对于⼀个⻓度同样为n整数序列B，定义其权值为|A_i-B_i| (1\le i\le n) 之和加上(B_j-B_{j+1})^2 (1\le j
输⼊格式 ：第⼀⾏⼀个整数n (1\le n\le 10^5)，表⽰序列A的⻓度。 第⼆⾏n个整数a_1, a_2, …, a_n (0\le a_i\le 9, 1\le i\le n)，表⽰序列A中的元素。
输出格式 ：仅⼀⾏⼀个整数，表⽰答案。
样例输⼊ ：
6
1 4 2 8 5 7样例输出 ：
11解释：
A 数组是 [1 4 2 8 5 7]
B 数组可以是 [3 4 4 5 5 6]。
权值为|A_i - B_i| (1 \le i \le n)之和加上(B_j - B_{j+1})^2 (1 \le j
权值第⼀部分|A_i - B_i| (1 \le i \le n)之和为：
|1 - 3| + |4 - 4| + |2 - 4| + |8 - 5| + |5 - 5| + |7 - 6| = 2 + 0 + 2 + 3 + 0 + 1 = 8
权值第⼆部分(B_j - B_{j+1})^2 (1\le j
(3 - 4)^2 + (4 - 4)^2 + (4 - 5)^2 + (5 - 5)^2 + (5 - 6)^2 = 1 + 0 + 1 + 0 + 1 = 3
所以总权值为 8 + 3 = 11。
示例代码 ：
#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;
int calculateAWeight(int a_value, int b_value){
return abs(a_value - b_value);
}
int calculateBWeight(int b_value_i, int b_value_i2){
return (b_value_i - b_value_i2) * (b_value_i - b_value_i2);
}
int main(){
int n;
scanf("%d", &n);
int dataA[n], dp[n][10], ans = INT_MAX;
for (int i=0; i<n; i++){
scanf("%d", &dataA[i]);
}
// 初始化
for (int i=0; i<=9; i++){
dp[0][i] = calculateAWeight(dataA[0], i);
}
// DP Main
for (int i=1; i<n; i++){
for (int j=0; j<10; j++){
int minWeight = INT_MAX;
int weightA = calculateAWeight(dataA[i], j);
for (int k=0; k<10; k++){
int weightB = calculateBWeight(k, j);
int total = dp[i-1][k] + weightB;
if (total < minWeight){
minWeight = total;
}
}
dp[i][j] = weightA + minWeight;
}
}
for (int i=0; i<=9; i++){
if (dp[n-1][i] < ans){
ans = dp[n-1][i];
}
}
printf("%d\n", ans);
return 0;
}
cpp
递归
搞清楚递归只要搞清两点：
- 结束条件
- 把问题规模缩小
2014 Hanoi塔
若仅考虑移动次数，则可直接得出：f(n)=2f(n-1)+1。进而基于此式子编写相应的程序代码。
Hanoi塔问题是一个源自印度古老传说的问题。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒子，在第一根棒上套着64个圆环形金片。
众僧们则不断地将这些金片从一根柱子移动到另一根柱子上。
请完成一个程序设计，在满足以下条件的前提下实现Hanoi塔问题：
将A柱上的n个金片通过B柱辅助全部移动至C柱上，
并使移动操作总次数最少。
输入为n值（范围在1至64之间），输出包括：
操作步数以及最终所有操作记录。
若操作步数少于等于100次，则全部输出；
否则只输出前100次的操作记录。
每次操作占一行，
格式为："第X次操作: 操作内容"（X为当前操作序号）。
例如：
输入：2
输出：
第1次操作: 将A柱第1号金片移到B柱
第2次操作: 将A柱第2号金片移到C柱
第3次操作: 将B柱第1号金片移到C柱
3
1:A->B
2:A->C
3:B->C #include <cstdio>
int current = 0, total = 1;
void print(char from, char to);
void hanoi(char from, char to, char helper, int n){
if (n==1){
current++;
print(from, to);
}else{
hanoi(from, helper, to, n-1);
// single move
current ++;
print(from , to);
// reverse
hanoi(helper, to, from, n-1);
}
}
void print(char from, char to){
if (total - current < 100){ // 倒序100以内才进行打印
printf("%d:%c->%c\n", current, from, to);
}
}
int main(){
int n;
scanf("%d", &n);
// 根据通项公式计算总的移动次数
for (int i=0; i<n; i++){
total *= 2;
}
total -= 1;
hanoi('A', 'C', 'B', n);
return 0;
}
cpp
栈与队列
2016 后缀序列求值
该后缀表达式的运算子位于操作数之后，在处理该后缀表达式时已考虑到各运算子的优先级。
题目描述 ：
给定一个后缀序列，要求求值，只有加减
输入 ：
123++4-输出 ：
2示例代码 ：
#include <iostream>
#include <string>
#include <stack>
#include <vector>
using namespace std;
stack<int> numbers;
int charToInt(char target){
return target - '0';
}
bool charIsNumber(char target){
if (target >= '0' and target <= '9'){
return true;
}else{
return false;
}
}
int main(){
int ans = 0, first, second;
char tmp;
string input;
getline(cin, input);
for (int i=0; i<input.length(); i++){
tmp = input[i];
if (charIsNumber(tmp)){ // 为数字的话
numbers.push(charToInt(tmp));
}else{
second = numbers.top();
numbers.pop();
first = numbers.top();
numbers.pop();
if (tmp == '+'){
ans = first + second;
}else{
ans = first - second;
}
numbers.push(ans);
}
}
cout << ans << endl;
return 0;
}
cpp
树与二叉树
2016 字符串的哈夫曼编码的最短长度
存在一个问题是：当输入完全相同的字符串时（即每个字符都与前一个字符相同），算法将返回值为0；然而，在实际情况中，并没有出现这种特殊的情况。
题目描述 ：给定一个字符串（长度不超过100），求哈夫曼编码的最短长度。
输入1：
abbcccdddd输出1：
19输入2：
we will we will r u输出2：
50示例代码 ：
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <map>
using namespace std;
typedef struct Node{
char data;
int weight;
bool leaf;
struct Node *left;
struct Node *right;
Node(char _data, int _weight, bool isLeaf, struct Node * _left = nullptr, struct Node * _right = nullptr){
data = _data;
weight = _weight;
leaf = isLeaf;
left = _left;
right = _right;
}
}*tree, Node;
struct cmp{
bool operator () (tree n1, tree n2){
return n1->weight > n2->weight;
}
};
priority_queue<tree, vector<tree>, cmp> q;
map<char, int> charCount;
map<char, int> charLength;
void calculateHuffmanCodeLength(tree root, int length=0){
if (root != nullptr){
if (root->leaf){
charLength[root->data] = length;
}else{
length++;
calculateHuffmanCodeLength(root->left, length);
calculateHuffmanCodeLength(root->right, length);
}
}
}
int main(){
string input;
tree first, second, head;
int sum=0;
getline(cin, input);
for (int i=0; i<input.length(); i++){
char tmp = input[i];
if (charCount.find(tmp) != charCount.end()){ // 找到了
charCount[tmp] += 1;
}else{
charCount[tmp] = 1;
}
}
// 构建初始的优先队列
for (auto it=charCount.begin(); it!=charCount.end(); it++){
q.push(new Node(it->first, it->second, true));
}
// 构建Huffman Tree
while (q.size() != 1){
first = q.top();
q.pop();
second = q.top();
q.pop();
// 构建一个新的节点，然后放进去
q.push(new Node(' ', first->weight + second->weight, false, first, second));
}
head = q.top();
calculateHuffmanCodeLength(head);
for (auto it=charCount.begin(); it!=charCount.end(); it++){
sum += it->second * charLength[it->first];
}
cout << sum << endl;
return 0;
}
cpp
2019 有向树形态
需要用该系统进行编程练习时，请注意以下事项：在处理整数运算时，请确保所有计算结果都未超出整数范围（即不超过INT_MAX），否则可能会导致溢出错误
在处理整数运算时，请确保所有计算结果都未超出整数范围（即不超过INT_MAX），否则可能会导致溢出错误
#include <cstdio>
// 2019年真题 有向树形态
int main(){
int n;
scanf("%d", &n);
long long data[n+1];
data[0] = 1;
data[1] = 1;
for (int i=2; i<=n; i++){
long long sum = 0, left;
for (int j=0; j<= i-1; j++){
left = i - j - 1;
if (left==j){
sum += data[j]*data[j];
}else{
sum += data[j]*data[left];
}
data[i] = sum;
}
}
printf("%lld\n", data[n]);
return 0;
}
cpp
2020 二叉搜索树
题目描述 ：
给定⼀个 1~n 的排列 P，即⻓度为 n，且 1~n 中所有数字都恰好出现⼀次的序列。现在按顺序将排列中的元素⼀⼀插⼊到初始为空的⼆叉搜索树中（左⼩右⼤），问最后每个节点的⽗亲节点的元素是什么。特别地，根节点的⽗亲节点元素视为 0。
输入格式 ：
第⼀⾏⼀个整数 n (1\le n \le 10^5)，表⽰排列 P 中的元素个数。
第⼆⾏ n 个整数p1, p2, ..., pn (1\le pi\le n, 1\le i\le n)，表⽰给定的排列。
输出格式 ：
⼀⾏ n 个整数，其中第 i 个整数 ai 表⽰元素 i 对应节点的⽗亲节点的元素。特别地，根节点的⽗亲节点元素视为 0。
样例输入 ：
5
2 3 5 1 4样例输出：
2 0 2 5 3样例解释 ：
最后建出来的⼆叉搜索树如下：
1的父节点是2；其中2作为根结点；其子节点无（即其父节点编号为0）；3的父节点同样是2；4和5的父节点分别是5和3。
解答 ：答案：一种计算量较大的算法，在处理大量数据时可能会导致内存不足问题。
#include <cstdio>
#include <vector>
using namespace std;
typedef struct Node{
int data;
struct Node * left;
struct Node * right;
Node(int _data){
data = _data;
left = nullptr;
right = nullptr;
}
}*tree, Node;
vector<int> result;
tree root = nullptr;
void insert(tree &head, int target){
if (head == nullptr){
head = new Node(target);
}else{
if (target < head->data){
insert(head->left, target);
}else{
insert(head->right, target);
}
}
}
void inorderTraverse(tree head, int parentData){
if (head != nullptr){
inorderTraverse(head->left, head->data);
result.push_back(parentData);
inorderTraverse(head->right, head->data);
}
}
int main(){
int n, tmp;
scanf("%d", &n);
for (int i=0; i<n; i++){
scanf("%d", &tmp);
insert(root, tmp);
}
inorderTraverse(root, 0);
for (int i=0; i<result.size(); i++){
printf("%d", result[i]);
if (i != result.size() - 1){
printf(" ");
}else{
printf("\n");
}
}
return 0;
}
cpp
某大佬解法 ：
对于数据量达到1e5的情况而言,必须选用时间复杂度至少为O(n\log n)的算法.相比之下,二叉排序树在最坏情况下其时间复杂度可达到O(n^2),因此不宜直接使用其作为数据结构.
探讨二叉排序树的性质：
- 新加入的结点大于树中的所有结点，则该结点的父亲结点为值小于自己且最接近自身的结点
- 新加入的结点小于树中的所有结点，则该结点的父亲结点为值大于自己且最接近自身的结点
- 更一般的，树中的结点既有比新加入的结点大的也有比新加入的结点小的。
此时新节点的父亲结点也一定是最接近自身的大于自己或者小于自己的结点，设大于自己的结点为m,小于自己的结点为n,判断是新结点的父亲结点是m和n哪个结点的依据是：如果大于的结点m先于小于的结点n插入，由于n<m,根据插入排序的规律，n可能在m的左子树上，或者是m的父亲结点，但是由于m先于n插入，n不可能是m的父亲结点，所有n在m的左子树上；同理小于的结点n先于大于的结点m插入，m在n的右子树上由于新结点的大小介于m和n之间，所有新结点的父亲结点，必定为后插入的结点。
当前问题归结为寻找已插入元素中大小最接近新结点的两个大小值，并根据这两个值来判断其插入顺序。传统的单个查找操作在最坏情况下的时间复杂度是O(n)，而连续进行n次这样的操作会导致时间复杂度达到O(n²)。因此为了将问题的时间复杂度降低到O(log n)，我们需要采用一种高效的查询方法：即通过将数据组织成一种能够在对数时间内完成查询的数据结构来进行查询处理。对于二分查找而言，在每次查询前都需要对数据进行排序以保持有序状态。然而这种做法并不能有效降低时间复杂度因为每次排序都会使整体的时间开销增加到最低限度的情况下依然无法避免线性增长的问题进而导致总的时间复杂度过高无法满足需求
简单模拟
2015 长方形中的正方形
#include <cstdio>
int sum = 0;
void cutRectangle(int height, int width){
if(height > width){
cutRectangle(width, height - width);
}else if(width > height){
cutRectangle(height, width - height);
}
sum++;
}
int main(){
int width, height;
scanf("%d%d", &height, &width);
cutRectangle(height, width);
printf("%d\n", sum);
return 0;
}
cpp
2015 a与b得到c
#include <cstdio>
int main(){
int a, b, c;
bool flag = false;
scanf("%d%d%d", &a, &b, &c);
if (a * b == c){
flag = true;
}
if (a + b == c){
flag = true;
}
if (a - b == c){
flag = true;
}
if (b - a == c){
flag = true;
}
if (double(b) / double (a) == double (c)){
flag = true;
}
if (double(a) / double (b) == double (c)){
flag = true;
}
if (flag){
printf("YES\n");
}else{
printf("NO\n");
}
return 0;
}
cpp
2018 求众数
OJ题目链接
这个题虽然使用下面的解题方法复杂度也就是O(n\log{n})，复杂度可以接受，但也可以使用map进行处理的，处理过程感觉只会更加简单。
#include <cstdio>
#include <algorithm>
#define MAX 100000
// 2018年真题
int data[MAX];
bool cmp(int a, int b){
return a < b;
}
int main(){
int n;
int max=0, max_count=0, current=0, current_count=0;
scanf("%d", &n);
for (int i=0; i<n; i++){
scanf("%d", &data[i]);
}
// 排序
std::sort(data, data+n, cmp);
// 统计
for (int i=0; i<n; i++){
if (data[i] == current){
current_count++;
}else{
// 统计之前的频率
if (current_count > max_count){
max = current;
max_count = current_count;
}
current = data[i];
current_count = 1;
}
}
// 对最后一个元素进行统计
if (current_count > max_count){
max = current;
max_count = current_count;
}
// 输出结果
printf("%d\n", max);
return 0;
}
cpp
2018 解一元一次方程
OJ题目链接
感觉这种写法有几个问题：
- 没有考虑乘除法
- 没有考虑小数的情况
#include <iostream>
#include <string>
using namespace std;
// 复旦2018年真题，求解一元一次方程组
/** * 1. 有无穷个解，x的系数为0， 剩余等式成立
* 2. 无解，x的系数为0， 剩余等式不成立
* 3. 有唯一解，x的系数不为0
*/
bool charIsNumber(char target){
if (target >= '0' and target <= '9'){
return true;
}
return false;
}
int charToInt(char target){
return target - '0';
}
int main(){
int tmp = 0, last = 0;
// 分别表示数字和未知数
int coefficient=0, number=0;
// 分别表示当前的数是否为正数，1为正数，-1为复试，后面那个reverse为1表示不用反过来，如果为-1表示需要反过来
int positive=1, reverse=1;
string input;
getline(cin, input);
// 遍历
for (int i=0; i<input.length(); i++){
if (charIsNumber(input[i])){
tmp = charToInt(input[i]);
if (last == 0){ // 之前没有值
last = tmp;
}else{ // 之前有值
last = last * 10 + tmp;
}
}else if(input[i] == 'x'){
if (last == 0){
last = 1;
}
coefficient += last * positive * reverse;
last = 0;
}else if(input[i] == '+'){
number += last * positive * reverse;
positive = 1;
last = 0;
}else if(input[i] == '-'){
number += last * positive * reverse;
positive = -1;
last = 0;
}else if(input[i] == '='){
number += last * positive * reverse;
last = 0;
reverse = -1;
positive = 1;
}
}
// 如果最后还有值
number += last * positive * reverse;
if (coefficient == 0 and number == 0){
cout << "infinite solutions" << endl;
}else if(coefficient == 0 and number != 0){
cout << "no solution" << endl;
}else{
cout << "x=" << -number/coefficient << endl;
}
return 0;
}
cpp
2018 骨牌
当时出现了一个测试用例未通过的情况：当n等于10,000时。由于数值超出整数类型所能表示的最大值导致计算结果溢出，在动态规划的过程中必须先对数值取模。
#include <cstdio>
// 2018年复旦真题 骨牌 非常明显是一个dp的问题
/** * DP问题两个关键的地方
* 1. 边界
* dp[1] = 1 dp[2] = 2
* 2. 状态转移方程
* dp[n] = dp[n-1] + dp[n-2]
*/
int main(){
int n;
scanf("%d", &n);
int dp[n+2];
dp[0] = 0;
dp[1] = 1;
for (int i=2; i<=n+1; i++){
dp[i] = (dp[i-1] + dp[i-2])% 999983;
}
printf("%d\n", dp[n+1]);
return 0;
}
cpp
2018 集合交并
#include <cstdio>
#include <vector>
using namespace std;
// 2018年复旦真题 集合交并
vector<int > outer, inner, tmp_vec;
bool inVector(int target, vector<int> data){
for (int i=0; i<data.size(); i++){
if (target == data[i]){
return true;
}
}
return false;
}
int main(){
int first, second, tmp;
scanf("%d%d", &first, &second);
while (first-- >0){
scanf("%d", &tmp);
if (!inVector(tmp, outer)){
outer.push_back(tmp);
}
}
while (second-- >0){
scanf("%d", &tmp);
if (!inVector(tmp, tmp_vec)){
tmp_vec.push_back(tmp);
}
}
for (int i=0; i<tmp_vec.size(); i++){
if (inVector(tmp_vec[i], outer)){
inner.push_back(tmp_vec[i]);
}else{
outer.push_back(tmp_vec[i]);
}
}
printf("%d %d\n", inner.size(), outer.size());
return 0;
}
cpp
2018 约数求和
OJ题目链接
常规方法枚举是会超时的，这样子减少重复运算才能够满足时间复杂度。
#include <cstdio>
int main(){
int n;
long long sum=0;
scanf("%d", &n);
for (int i=1; i<=n; i++){
sum += i*(n/i);
}
printf("%lld\n", sum);
}
cpp
2018 求交点
#include <cstdio>
// 2018年真题 求两直线 交点
int main() {
double x0, x1, x2, x3, y0, y1, y2, y3;
scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &x0, &y0, &x1, &y1, &x2, &y2, &x3, &y3);
double k1 = (y1 - y0) / (x1 - x0);
double b1 = y1 - x1 * k1;
double k2 = (y3 - y2) / (x3 - x2);
double b2 = y3 - x3 * k2;
if (k1 == k2) {
printf("Parallel or coincident\n");
return 0;
}
double ansx = (b1 - b2) / (k2 - k1);
double ansy = k1 * ansx + b1;
printf("%.2f %.2f\n", ansx, ansy);
return 0;
}
cpp
2019 相隔天数
这里还要注意判断闰年的方式。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
//month[2][0]平年， month[2][1]闰年
int month[13][2] = {{0,0}, {31, 31}, {28,29}, {31,31}, {30,30}, {31, 31}, {30,30},{31, 31}, {31, 31}, {30,30}, {31, 31},{30,30},{31, 31}} ;
bool isLeapYear(int year){
if(year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)){
return true;
}
return false;
}
int main(){
int time1, time2 = 20190205;
scanf("%d", &time1);
if(time1 > time2){
swap(time1, time2);
}
int y1, m1, d1, y2, m2, d2;
y1 = time1 / 10000, m1 = time1 % 10000 / 100, d1 = time1 % 100;
y2 = time2 / 10000, m2 = time2 % 10000 / 100, d2 = time2 % 100;
int num = 0;
while(y1 < y2 || m1 < m2 || d1 < d2){
d1++;
num++;
if(d1 == month[m1][isLeapYear(y1)] + 1){
m1++;
d1 = 1;
}
if(m1 == 13){
y1++;
m1 = 1;
}
}
cout << num << endl;
return 0;
}
cpp
2020 斗牛
设有五个a_1至a_5均为[0,9]范围内的整数值。
若存在三个这样的变量其和恰能被10整除（含零），则计算剩余两个变量之和并对10取余的结果作为这五个变量的整体权值。
不言而喻的是无论满足条件的情形有多少种结果始终一致；若无任何三元组满足条件则整体权值赋值为-\-{1}。
对于数据处理的具体要求如下：
第一行为一个正整数量纲符符\text{'}T\text{'}(满足\text{'}1\leq T\leq 1\text{e}3\text{'}) 表示数据组的数量。
随后有\text{'}T\text{'}行 每一行均包含恰好\text{'}5\text{'}个区间在\text{'}[0,9]\text{'}\$范围内的数字表示一组待处理的数据集。
对应输出部分：
第一行为一个正整数量纲符符\text{'}T\text{'}$ 表示待处理数据集的数量。
随后有$\text{'}T\text{'}$ 行 每一行均给出一个非负或负一的形式表示对应待处理数据集的整体权值结果。
以下为此算法测试的具体案例：
4
1 0 0 1 0
1 0 0 8 6
3 4 5 6 7
4 5 6 7 8样例输出 ：
2
-1
-1
0在第一组（1, 2, 3, 4, 5）中，在位置（i=3,j=4,k=5）处形成一个三维数组A[3][4][5]。该数组的最大值位于位置（i=5,j=3,k=4），其值为99.9998；最小值则位于位置（i=2,j=2,k=2），其值为-99.9986。这两个极值之间的差值即为空间中的最大间距Δs = max(A) - min(A) = (99.9998) - (-99.9986) = (Δs)=1. (单位：m)
在第二维空间中投影时，在x轴方向上的投影长度Lx = max(A[..][..][k]) - min(A[..][..][k]) = (max_x - min_x) = ... m；而在y轴方向上的投影长度Ly = max(A[i..][..]) - min(A[i..][..]) = (max_y - min_y) = ... m.
其中，在z轴方向上的投影长度Lz = max(A[..][j..]) - min(A[..][j..]) = (max_z - min_z) = ... m. 这样一来，在三维空间中的最大间距Δs就可以表示为√(Lx² + Ly² + Lz²).
#include <cstdio>
int calculate(int* data){
for (int i=0; i<5; i++){
for(int j=i+1; j<5; j++){
// 看看剩下三张牌是否能为10的倍数
int total = 0;
for (int k=0; k<5; k++){
if (k != i and k != j){
total += data[k];
}
}
if (total % 10 == 0){
return (data[i] + data[j]) % 10;
}
}
}
return -1;
}
int main(){
int n, data[5];
scanf("%d", &n);
int result[n], index=0;
while (n-- > 0){
for (int i=0; i<5; i++){
scanf("%d", &data[i]);
}
result[index++] = calculate(data);
}
for (int i=0; i<index; i++){
printf("%d\n", result[i]);
}
return 0;
}
cpp
2020 打地鼠
题目描述 ：
给定 n 个整数a_1, a_2, ..., a_n和⼀个d，你需要选出若⼲个整数，使得将这些整数从⼩到⼤排好序之后，任意两个相邻的数之差都不⼩于给定的 d，问最多能选多少个数出来。
输⼊格式 ：
第⼀⾏两个整数n,d (1<=n<=10^5, 0<=d<=10^9)，分别表⽰整数个数和相邻整数差的下界。
第⼆⾏n个整数 a_1, a_2, ..., a_n (1<=a_i<=10^9, 1<=i<=n)，表⽰给定的 n 个整数。
输出格式 :
仅⼀⾏⼀个整数，表⽰答案。
样例输⼊ ：
6 2
1 4 2 8 5 7样例输出 ：
3特别注意
#include <cstdio>
#include <algorithm>
int main(){
int n, d, ans=1;
scanf("%d%d", &n, &d);
int data[n];
for (int i=0; i<n; i++){
scanf("%d", &data[i]);
}
// 排序
std::sort(data, data+n); // 默认升序
// Main Part
int cmpBase = data[0];
for (int i=1; i<n; i++){
if (data[i] - cmpBase >= d){
ans += 1;
cmpBase = data[i];
}
}
printf("%d\n", ans);
return 0;
}
cpp
2020 排队打饭
题目描述 ：
下课了，有 n 位同学陆续赶到⻝堂进⾏排队打饭，其中第 i 位同学的到达时间为 ai，打饭耗时为 ti， 等待时间上限为 bi，即如果其在第 ai+bi 秒的时刻仍然没有轮到他开始打饭，那么他将离开打饭队列，另寻吃饭的地⽅。问每位同学的开始打饭时间，或者指出其提前离开了队伍（如果这样则输出 -1）。
输入格式 ：
第⼀⾏⼀个整数n (1\le n\le10^5)，表⽰来打饭的同学数量。
接下来 n ⾏，每⾏三个整数ai,ti,bi (1\le ai,ti,bi\le 10^9, 1\le i\le n)，分别表⽰每位同学的到达时间、打饭耗时、等待时间上限。 保证 a1<a2<…<an
输出格式 ：
⼀⾏ n 个整数，表⽰每位同学的开始打饭时间或者 -1（如果该同学提前离开了队伍）。
样例输入 ：
4
1 3 3
2 2 2
3 9 1
4 3 2样例输出 ：
1 4 -1 6在此示例中
#include <cstdio>
int main(){
int n, arriveTime, dafanTime, waitTime, lastFinishTime=0;
scanf("%d", &n);
int result[n];
for (int i=0; i<n; i++){
scanf("%d%d%d", &arriveTime, &dafanTime, &waitTime);
if (lastFinishTime > arriveTime + waitTime){ // 到了忍受上限，离开
result[i] = -1;
}else{
result[i] = arriveTime > lastFinishTime ? arriveTime : lastFinishTime;
lastFinishTime = result[i] + dafanTime;
}
}
// 输出结果
for (int i=0; i<n; i++){
printf("%d", result[i]);
if (i != n-1){
printf(" ");
}else{
printf("\n");
}
}
return 0;
}
cpp
