By 三石吖 2026.2
- 差\(1\)题
6.课后习题
18931分形
递归好题
首先可以发现，等级为\(n\)的盒子应该有\(3^{n-1}\)行，每一级盒子都由五部分上一级盒子组成，每一部分的占据\(3^n-2\)行，我们可以通过简单计算算出每一部分的起始行位置，然后递归地画出整个盒子
当然，我们发现\(n\)最大只有5，如果你是打表大师的话，完全可以\(O(1)\)通过本题！
#include<bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using pii = std::pair<int,int>;
using pll = std::pair<i64,i64>;
using pli = std::pair<i64,int>;
using pil = std::pair<int,i64>;
constexpr i64 INF = 0x3f3f3f3f3f3f3f3fll;
constexpr int inf = 0x3f3f3f3f;std::vector<std::string>s;void draw(int layer, int d){if(layer == 1){s[d].push_back('X');return;}//最小分级int x = pow(3, layer - 2);//当前等级占据行数draw(layer - 1, d);//画左上角部分for(int i = 0; i < x; i++){for(int j = 0; j < x; j++){s[d + i].push_back(' ');}}//填充左上角和右上角之间的空格draw(layer - 1, d);//画右上角部分for(int i = 0; i < x; i++){for(int j = 0; j < x; j++){s[d + x + i].push_back(' ');}}//填充中间部分左边的空格draw(layer - 1, d + x);//画中间部分for(int i = 0; i < x; i++){for(int j = 0; j < x; j++){s[d + x + i].push_back(' ');}}//填充中间部分右边的空格draw(layer - 1, d + 2 * x);//画左下角部分for(int i = 0; i < x; i++){for(int j = 0; j < x; j++){s[d + 2 * x + i].push_back(' ');}}//填充左下角部分和右下角部分之间的空格draw(layer - 1, d + 2 * x);//画右下角部分
}
int main(){std::ios::sync_with_stdio(false); std::cin.tie(nullptr);#ifdef LOCALfreopen("make.txt", "r", stdin);freopen("a.txt", "w", stdout);
#endifint n;std::cin>>n;int m = pow(3, n - 1);s.resize(m);draw(n, 0);for(int i = 0; i < m; i++){std::cout << s[i] << "\n";}return 0;
}/**/
19180 集合划分问题一
①\(n\)独立作为一个子集，问题变成\(n-1\)个数划分为\(m-1\)个集合
②\(n\)插入别的子集，有\(m\)种方法，先求\(n-1\)个数划分为\(m\)个集合的方法数
递归求解即可
涉及到大量重复计算，可用记忆化搜索优化
- 时间复杂度\(O(n \times m)\)
#include<bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using pii = std::pair<int,int>;
using pll = std::pair<i64,i64>;
using pli = std::pair<i64,int>;
using pil = std::pair<int,i64>;
constexpr i64 INF = 0x3f3f3f3f3f3f3f3fll;
constexpr int inf = 0x3f3f3f3f;void solve(){int n, m;std::cin >> n >> m;std::vector<std::vector<i64>>f(n + 1, std::vector<i64>(m + 1));for(int i = 0; i <= n; i++){f[i][1] = 1;if(i <= m){f[i][i] = 1;}}auto dfs = [&](auto &&self, int x, int y) -> i64 {if(f[x][y]){return f[x][y];}f[x][y] = self(self, x - 1, y - 1) + self(self, x - 1, y) * y;return f[x][y];};std::cout << dfs(dfs, n, m) << "\n";
} int main(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr);#ifdef LOCALfreopen("make.txt", "r", stdin);freopen("a.txt", "w", stdout);
#endifint T = 1;// std::cin >> T;while(T--){solve();}return 0;
}
/* */
19448 集合划分问题二
和上题大差不差，枚举一下子集个数即可
- 时间复杂度\(O(n^2)\)
#include<bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using pii = std::pair<int,int>;
using pll = std::pair<i64,i64>;
using pli = std::pair<i64,int>;
using pil = std::pair<int,i64>;
constexpr i64 INF = 0x3f3f3f3f3f3f3f3fll;
constexpr int inf = 0x3f3f3f3f;void solve(){int n;std::cin >> n;std::vector<std::vector<i64>>f(n + 1, std::vector<i64>(n + 1));for(int i = 0; i <= n; i++){f[i][1] = f[i][i] = 1;}auto dfs = [&](auto &&self, int x, int y) -> i64 {if(f[x][y]){return f[x][y];}f[x][y] = self(self, x - 1, y - 1) + self(self, x - 1, y) * y;return f[x][y];};i64 ans = 0;for(int i = 1; i <= n; i++){ans += dfs(dfs, n, i);}std::cout << ans << "\n";
} int main(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr);#ifdef LOCALfreopen("make.txt", "r", stdin);freopen("a.txt", "w", stdout);
#endifint T = 1;// std::cin >> T;while(T--){solve();}return 0;
}
/* */
19529 照明灯安装
答案具有单调性，于是二分答案
如何检查是否合法呢，假设当前要检查的距离为\(d\)，我们从前往后，每隔\(d\)放一个照明灯，最后看能放的照明灯数是否\(\ge k\)即可
- 时间复杂度\(O(nlogn)\)
#include<bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using pii = std::pair<int,int>;
using pll = std::pair<i64,i64>;
using pli = std::pair<i64,int>;
using pil = std::pair<int,i64>;
constexpr i64 INF = 0x3f3f3f3f3f3f3f3fll;
constexpr int inf = 0x3f3f3f3f;void solve(){int n, k;std::cin >> n >> k;std::vector<int>x(n);for(int i = 0; i < n; i++){std::cin >> x[i];}int lo = 1, hi = x.back() - x.front();auto check = [&](int mid){int cnt = 0;for(int i = 0, j; i < n; i = j){cnt++;j = i + 1;while(j < n && x[j] - x[i] < mid){j++;}}return cnt >= k;};int ans;while(lo <= hi){int mid = lo + hi >> 1;if(check(mid)){ans = mid;lo = mid + 1;}else{hi = mid - 1;}}std::cout << ans << "\n";
} int main(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr);#ifdef LOCALfreopen("make.txt", "r", stdin);freopen("a.txt", "w", stdout);
#endifint T = 1;// std::cin >> T;while(T--){solve();}return 0;
}
/* */
19184 传球游戏
\(dp[i][j]\)表示第\(j\)轮第\(i\)个同学拿到球的方法数
状态转移方程：\(dp[j][i] = dp[(j - 1 + n) \% n][i - 1] + dp[(j + 1) \% n][i - 1]\)
- 时间复杂度\(O(n \times m)\)
#include<bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using pii = std::pair<int,int>;
using pll = std::pair<i64,i64>;
using pli = std::pair<i64,int>;
using pil = std::pair<int,i64>;
constexpr i64 INF = 0x3f3f3f3f3f3f3f3fll;
constexpr int inf = 0x3f3f3f3f;void solve(){int n, m;std::cin >> n >> m;std::vector<std::vector<int>>dp(n, std::vector<int>(m + 1, 0));dp[0][0] = 1;for(int i = 1; i <= m; i++){for(int j = 0; j < n; j++){dp[j][i] += dp[(j - 1 + n) % n][i - 1] + dp[(j + 1) % n][i - 1];}}std::cout << dp[0][m] <<"\n";
} int main(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr);#ifdef LOCALfreopen("make.txt", "r", stdin);freopen("a.txt", "w", stdout);
#endifint T = 1;// std::cin >> T;while(T--){solve();}return 0;
}
/* */
18308 最长公共子序列
\(dp[i][j]\)表示\(a\)串前\(i\)个字符和\(b\)串前\(j\)个字符的最长公共子序列长度
（下面\(a\)和\(b\)串索引均从\(0\)开始，\(dp\)数组索引从\(1\)开始）
讨论：
若\(a[i-1]=b[j-1]\)，找到一个匹配字符，问题转化为\(a\)串前\(i-1\)个字符和\(b\)串前\(j-1\)个字符的最长公共子序列长度，\(dp[i][j]=dp[i-1][j-1]+1\)
否则，考虑\(a\)串前\(i-1\)个字符和\(b\)串前\(j\)个字符的最长公共子序列长度，以及\(a\)串前\(i\)个字符和\(b\)串前\(j-1\)个字符的最长公共子序列长度
\(dp[i][j]=max(dp[i-1][j],dp[i][j-1])+1\)
- 时间复杂度\(O(n \times m)\)
#include<bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using pii = std::pair<int,int>;
using pll = std::pair<i64,i64>;
using pli = std::pair<i64,int>;
using pil = std::pair<int,i64>;
constexpr i64 INF = 0x3f3f3f3f3f3f3f3fll;
constexpr int inf = 0x3f3f3f3f;void solve(){std::string a,b;std::cin >> a >> b;int m = a.size(), n = b.size();int ans = 0;std::vector<std::vector<int>>dp(m + 1, std::vector<int>(n + 1,0));for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){if(a[i - 1] == b[j - 1]){dp[i][j] = dp[i - 1][j - 1] + 1;}else{dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);}ans = std::max(ans, dp[i][j]);}}std::cout << ans << "\n";
} int main(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr);#ifdef LOCALfreopen("make.txt", "r", stdin);freopen("a.txt", "w", stdout);
#endifint T = 1;// std::cin >> T;while(T--){solve();}return 0;
}
/* */