企业官网建设流程全解析

1.最小步数变成 Fib 数

给定数字 x，每次操作可以 \(x\pm1\)，求最少操作步数，使得数字变为斐波那契数。 等价于：找到离 x 最近的斐波那契数，输出差值绝对值。

举例子 \(x=4\) Fib 序列：0,1,1,2,3,5,8… 离 4 最近是 3、5，差值都是 1，答案 = 1

C++ AC 完整代码

cpp

运行

#include <iostream> #include <vector> #include <climits> #include <cmath> using namespace std; typedef long long ll; int main() { vector<ll> fib; fib.push_back(0); fib.push_back(1); // 预先生成足够多斐波那契数 while (true) { ll nxt = fib.back() + fib[fib.size() - 2]; if (nxt > 2e18) break; fib.push_back(nxt); } ll x; cin >> x; ll ans = LLONG_MAX; for (ll v : fib) { ll d = abs(v - x); if (d < ans) ans = d; } cout << ans << endl; return 0; }

思路说明

1. 预先生成全部不超过 \(2\times10^{18}\) 的斐波那契数列（数量很少，不到 90 项）
2. 遍历每一个 fib 数，计算与输入 x 的距离
3. 记录最小距离直接输出

2.单词搜索

题目描述

给定一个m x n二维字符网格board和一个字符串单词word。 在网格中按上下左右四个方向搜索是否存在该单词：

• 每个位置字符只能使用一次（不能重复走）
• 可以从任意格子起点出发

输入样例

plaintext

A B C E S F C S A D E E word = "ABCCED" 输出：true

思路：DFS + 回溯

1. 遍历网格每一个点，作为起点
2. 深度优先搜索：向上下左右走
3. 使用标记（原地修改 /vis 数组）防止重复访问
4. 匹配完所有字符直接返回 true（剪枝）

C++ AC 代码（牛客可直接提交）

cpp

运行

#include <iostream> #include <vector> #include <string> using namespace std; // 四个方向：上、下、左、右 int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; bool dfs(vector<vector<char>>& board, string& word, int x, int y, int idx) { // 当前字符不匹配 if(board[x][y] != word[idx]) return false; // 全部匹配完成 if(idx == word.size() - 1) return true; char tmp = board[x][y]; board[x][y] = '#'; // 原地标记已访问 for(int i = 0; i < 4; i++) { int nx = x + dir[i][0]; int ny = y + dir[i][1]; // 边界判断 if(nx >= 0 && nx < board.size() && ny >=0 && ny < board[0].size()) { if(dfs(board, word, nx, ny, idx + 1)) return true; } } board[x][y] = tmp; // 回溯恢复 return false; } bool exist(vector<vector<char>>& board, string word) { int m = board.size(); int n = board[0].size(); for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(dfs(board, word, i, j, 0)) return true; } } return false; } int main() { int m,n; cin >> m >> n; vector<vector<char>> board(m,vector<char>(n)); for(int i=0;i<m;i++) for(int j=0;j<n;j++) cin >> board[i][j]; string word; cin >> word; if(exist(board,word)) cout << "true"; else cout << "false"; return 0; }

关键要点（笔试易错）

1. 回溯必须恢复现场，否则多条路径互相干扰
2. 优先判断idx == word.size()-1，找到直接 return，大量剪枝
3. 原地修改#节省空间；不允许修改原数组就开vis[][]
4. 只允许上下左右，不能对角线！

3.BC40 杨辉三角

题目描述

输入 n，输出 n 行杨辉三角。

• 第一行一个数字 1
• 每行首尾数字为 1
• 中间数字 = 上一行相邻两个数字之和
• 每个数字输出占 5 个宽度（域宽 5，右对齐）

输入描述

输入一个整数 n（1 ≤ n ≤ 20）

输出描述

输出 n 行杨辉三角，每个数值占 5 字符宽度。

样例输入：

plaintext

4

样例输出：

plaintext

1 1 1 1 2 1 1 3 3 1

#include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int> arr; for (int i = 0; i < n; ++i) { arr.push_back(1); for (int j = i - 1; j > 0; --j) { arr[j] = arr[j] + arr[j - 1]; } for (int x : arr) { printf("%5d", x); } printf("\n"); } return 0; }