T1《种树》
题目描述
有 n 棵树排在一条直线上,第 i 棵树的位置是一个整数 ai(两两不同)。
你想让这些树从左到右看起来“间距完全一样”,但不能移动已有的树。
你可以在任意位置再种一些新树(位置也必须是整数),使得把所有树的位置从小到大排序后,相邻两棵树的距离都相等。
请你输出最少还需要种多少棵树。
输入格式
第一行一个整数 n,表示树的数量。
第二行 n 个整数 a1,a2,…,an,表示每棵树的位置。
输出格式
输出一个整数,表示最少需要补种的树的数量。
思路
由于题目中的树木位置固定且已按升序排列,我们可以通过以下步骤计算所有相邻树木间距的最大公约数(GCD):
计算相邻间距:首先遍历给定的树木坐标数组,计算每两棵相邻树之间的距离差。例如,对于树木位置[2, 6, 12, 15],相邻间距分别为4(6-2)、6(12-6)和3(15-12)。
初始化GCD值:将第一个计算出的间距作为当前GCD的初始值(如上述例子中的4)。
迭代计算GCD:用欧几里得算法依次计算当前GCD值与后续间距的GCD。例如:
- 计算gcd(4,6)得到2;
- 再用gcd(2,3)得到1。
确定最终结果:当遍历完所有间距后,最终的GCD值即为所求。在这个例子中,所有相邻树木间距的最大公约数是1。
应用场景:这种方法可用于确定绿化带植树的最小间隔单位,或计算路灯等线性排列设施的最优分布间距。算法的时间复杂度为O(n log m),其中n是间距数量,m是间距的最大值。
代码如下
#include<bits/stdc++.h>
using namespace std;
long long n,a[100005],b[100005];
int main(){
long long n;
cin>>n;
for(long long i = 1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
for(long long i = 2;i<=n;i++){
b[i] = a[i]-a[i-1];
}
long long k = __gcd(b[2],b[3]);
for(long long i = 3;i<=n;i++){
k = __gcd(k,b[i]);
}
cout<<((a[n]-a[1])/k+1)-n;
return 0;
}
T2《食人国》
题目描述
食人国国王只吃人。现在他抓了 n 个人,按从左到右排成一排,编号依次为 1,2,…,n。
国王特别喜欢数字 k(保证 k≥2)。他会反复进行如下“报数并吃人”的过程:
- 当前还活着的人保持原来的相对顺序,从左到右依次报数 1,2,3,…;
- 在这一轮中,报出的数字不是 k 的倍数的人会按顺序被吃掉;
- 这一轮结束后,剩下的人再次从 1 开始报数,进入下一轮。
可以证明:不管 n 和 k 取何值(满足 k≥2),国王最终都能把所有人吃掉。
你也是这 n 个人之一。你想知道:最后一个被吃掉的人,最初的编号是多少?
输入格式
一行两个整数 n 和 k。
输出格式
输出一个整数,表示最后一个被吃掉的人的编号。
思路
这是一道纯数学题
代码如下
#include<bits/stdc++.h>
using namespace std;
int main(){
long long n,k;
cin>>n>>k;
long long po = 1;
while(po*k<=n)po *= k;
cout<<n/po*po;
return 0;
}
前情提要
动态规划(Dynamic Programming)简介
动态规划(DP)是一种用于解决具有重叠子问题和最优子结构性质的问题的算法设计方法。它将复杂问题分解为更小的子问题,通过存储子问题的解避免重复计算,从而提高效率。
核心思想
- 最优子结构:问题的最优解包含其子问题的最优解。
- 重叠子问题:子问题在求解过程中被多次重复计算,通过记忆化存储避免重复。
动态规划的两种实现方式
1. 自顶向下(记忆化递归)
- 从原问题出发,递归分解为子问题,通过缓存(如数组或哈希表)存储已计算的子问题结果。
- 适合问题分解直观但递归开销大的场景。
2. 自底向上(迭代填表)
- 从最小子问题开始逐步构建解,通常使用数组(DP表)按顺序填充结果。
- 空间复杂度更优,避免递归栈开销。
动态规划的应用步骤
问题分析
明确问题的状态定义(如dp[i]的含义)、状态转移方程(如何从dp[i-1]推导dp[i])以及初始条件(如dp[0]的值)。
状态转移方程
根据问题逻辑建立数学关系。例如,斐波那契数列的方程为:
[ dp[i] = dp[i-1] + dp[i-2] ]
边界条件
初始化基础情况,如dp[0] = 0,dp[1] = 1。
空间优化
某些问题中,DP表可压缩为有限变量。例如,斐波那契数列只需保存前两个状态:
prev, curr = 0, 1
for _ in range(2, n+1):
prev, curr = curr, prev + curr
经典问题示例
1. 斐波那契数列
- 状态定义:dp[i]表示第i个斐波那契数。
- 转移方程:dp[i] = dp[i-1] + dp[i-2]。
2. 背包问题
- 状态定义:dp[i][j]表示前i个物品在容量j下的最大价值。
- 转移方程:
[ dp[i][j] = \\max(dp[i-1][j], dp[i-1][j-w_i] + v_i) ]
常见优化技巧
- 滚动数组:将二维DP表压缩为一维,减少空间复杂度。
- 状态压缩:用位运算等技巧简化状态表示(如旅行商问题)。
通过理解上述框架和练习经典问题,可以逐步掌握动态规划的核心思想与应用方法。
T3《打BOSS》
题目描述
你正在玩一个关卡游戏。现在你遇到了一个大 Boss,并开始与它战斗。
战斗持续 n 秒。第 i 秒你有两种选择:
- 普攻:造成 k 点伤害;
- 使用技能:造成 ai 点伤害。
需要注意:
- 如果第 i−1 秒你使用了技能,那么第 i 秒再次使用技能时伤害会翻倍,造成 2×ai。
- 你不能连续使用技能超过两次。也就是说,不能出现连续三秒都使用技能的情况。
请你计算:在 n 秒内最多可以造成多少伤害。
输入格式
第一行两个整数 n 和 k。
第二行 n 个整数 a1,a2,…,an。
输出格式
输出一个整数,表示最多造成的伤害值。
思路
这是一道关于攻击策略优化的动态规划问题,具体分析如下:
状态定义详解:
状态转移方程详细说明:
dp[i][0] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2]) + k
- 当前使用普通攻击时,前一次攻击可以是任意类型
- 需要加上当前普通攻击的固定伤害k
dp[i][1] = dp[i-1][0] + a[i]
- 当前使用技能时,前一次攻击必须只能是普通攻击(可能有冷却限制)
- 需要加上当前技能攻击的伤害a[i]
dp[i][2] = dp[i-1][1] + 2*a[i]
- 当前使用强化普通攻击时,前一次攻击必须使用技能(可能是技能触发的强化效果)
- 需要加上当前强化普通攻击的伤害2*a[i]
应用场景示例: 假设有一个游戏角色,其攻击方式有:
- 普通攻击:每次固定造成10点伤害
- 技能攻击:伤害随攻击次数变化,第i次为a[i]
- 强化普通攻击:在技能后可用,造成双倍技能伤害
初始化条件: dp[1][0] = k dp[1][1] = a[1] dp[1][2] = -∞(初始不可用)
最终结果: max(dp[n][0], dp[n][1], dp[n][2]),其中n为总攻击次数
代码如下
#include<bits/stdc++.h>
using namespace std;
long long dp[1000005][3];
long long a[1000005];
int main(){
long long n,k;
cin>>n>>k;
for(int i = 1;i<=n;i++){
cin>>a[i];
}
dp[1][0] = k;
dp[1][1] = a[1];
dp[1][2] = -0x3f3f3f3f;
for(long long i = 2;i<=n;i++){
dp[i][0] = max({dp[i-1][0],dp[i-1][1],dp[i-1][2]})+k;
dp[i][1] = dp[i-1][0]+a[i];
dp[i][2] = dp[i-1][1]+2*a[i];
}
cout<<max({dp[n][0],dp[n][1],dp[n][2]});
return 0;
}
二维DP
二维DP在C++中的实现
二维动态规划(2D DP)是一种解决复杂问题的有效方法,通常用于处理涉及两个变量或维度的问题。在C++中,二维DP通常通过二维数组或向量来实现。
基本概念
二维DP的核心思想是将问题分解为子问题,并将子问题的解存储在一个二维表格中。这种方法常用于解决矩阵路径问题、字符串匹配问题等。关键在于定义状态转移方程,即如何从一个状态推导出下一个状态。
实现步骤
定义DP数组:通常使用vector<vector<int>>或二维数组int dp[m][n]来存储中间结果。数组的大小取决于问题的具体需求。
初始化边界条件:根据问题的具体要求,初始化DP数组的第一行和第一列。这些初始值通常是问题的基本情况。
填充DP数组:通过嵌套循环遍历数组的每个元素,根据状态转移方程更新每个位置的值。状态转移方程定义了当前状态与之前状态之间的关系。
返回结果:最终结果通常存储在DP数组的某个特定位置,如右下角或某个特定坐标。
示例代码
以下是一个典型的二维DP问题示例:计算从矩阵左上角到右下角的最小路径和。
#include <vector>
#include <algorithm>
using namespace std;
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
if (m == 0) return 0;
int n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
dp[0][0] = grid[0][0];
for (int i = 1; i < m; ++i) {
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for (int j = 1; j < n; ++j) {
dp[0][j] = dp[0][j-1] + grid[0][j];
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[m-1][n-1];
}
优化空间复杂度
在某些情况下,二维DP可以优化为一维DP以减少空间复杂度。例如,如果当前行的值仅依赖于上一行或前一列的值,可以只保留一行或一列的数据。
int minPathSumOptimized(vector<vector<int>>& grid) {
int m = grid.size();
if (m == 0) return 0;
int n = grid[0].size();
vector<int> dp(n, 0);
dp[0] = grid[0][0];
for (int j = 1; j < n; ++j) {
dp[j] = dp[j-1] + grid[0][j];
}
for (int i = 1; i < m; ++i) {
dp[0] += grid[i][0];
for (int j = 1; j < n; ++j) {
dp[j] = min(dp[j], dp[j-1]) + grid[i][j];
}
}
return dp[n-1];
}
常见应用场景
二维DP广泛应用于多种问题,如:
- 矩阵中的最长递增路径
- 编辑距离(Levenshtein距离)
- 背包问题的变种
- 字符串匹配问题(如正则表达式匹配)
注意事项
正确性验证:确保状态转移方程的正确性,通常可以通过手动计算小规模案例来验证。
边界条件处理:特别注意数组的边界条件,避免越界访问。
空间优化:在内存受限的情况下,考虑是否可以优化空间复杂度。
时间复杂度分析:二维DP通常具有O(mn)的时间复杂度,其中m和n是问题的两个维度。
T4《逃离迷宫》
题目描述
有一个 n×m 的方格迷宫。第 i 行第 j 列格子里有一个整数 ai,j,表示你进入该格子会受到的伤害。
你从左上角 (1,1) 出发,要走到右下角 (n,m)。每一步只能向右或向下移动。
一条路径的总伤害定义为:路径上经过的所有格子的伤害之和(包含起点与终点)。
由于不同路径的总伤害可能非常多,你只需要关心总伤害对 10007 取模后的结果。请你计算:所有路径的“总伤害 mod 10007”可能取到多少种不同的值。
输入格式
第一行两个整数 n,m。
接下来 n 行,每行 m 个整数,表示矩阵 a。
输出格式
输出一个整数,表示所有路径的总伤害对 10007 取模后,可能得到的不同结果数量。
这道题目同样可以采用动态规划来解决。
定义状态dp[i][j][k]表示到达位置(i,j)时,是否可能受到k点伤害。
状态转移方程为: dp[i+1][j][(k+a[i][j])%10007] = true; dp[i][j+1][(k+a[i][j])%10007] = true;
代码如下
#include<bits/stdc++.h>
using namespace std;
long long a[55][55];
bool dp[55][55][10007];
int main(){
long long n,m;
cin>>n>>m;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
cin>>a[i][j];
a[i][j] %= 10007;
}
}
dp[1][1][a[1][1]] = true;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
for(int k = 0;k<10007;k++){
if(dp[i][j][k]){
dp[i+1][j][(k+a[i][j])%10007] = true;
dp[i][j+1][(k+a[i][j])%10007] = true;
}
}
}
}
int ans = 0;
for(int i = 0;i<10007;i++)ans+=dp[n][m][i];
cout<<ans;
return 0;
}
三维DP
以下是关于三维DPC++(Data Parallel C++)的讲解,涵盖其概念、应用场景及关键实现方法:
三维DPC++的概念
DPC++是Intel开发的异构编程语言,基于SYCL标准,用于在CPU、GPU、FPGA等设备上实现数据并行计算。三维DPC++特指在三维空间数据处理中的应用,如体积渲染、流体模拟或三维网格计算。
三维数据并行化原理
三维数据通常以网格或体素形式存储。在DPC++中,通过三维ND-Range(例如range<3>(width, height, depth))定义工作负载,每个工作项对应一个三维空间点。并行化时需考虑内存访问模式优化,避免跨步访问导致的性能下降。
三维核函数编写示例
以下是一个三维卷积核函数的DPC++实现片段:
void convolution3d(queue& q, float* input, float* output, float* kernel,
int width, int height, int depth) {
q.submit([&](handler& h) {
h.parallel_for(range<3>(width-2, height-2, depth-2), [=](id<3> idx) {
int x = idx[0]+1, y = idx[1]+1, z = idx[2]+1;
float sum = 0.0f;
for (int kz = 0; kz < 3; ++kz)
for (int ky = 0; ky < 3; ++ky)
for (int kx = 0; kx < 3; ++kx)
sum += input[(z+kz-1)*height*width + (y+ky-1)*width + (x+kx-1)]
* kernel[kz*9 + ky*3 + kx];
output[z*height*width + y*width + x] = sum;
});
});
}
内存优化技术
三维数据处理常面临内存带宽压力。可采用以下策略:
- 使用buffer和accessor管理设备内存
- 通过local_accessor实现工作组级数据复用
- 对频繁访问的数据应用constexpr或sycl::property::reuse优化
性能调优要点
- 工作组大小应匹配硬件特性(如GPU的SIMD宽度)
- 三维ND-Range的划分需考虑数据局部性
- 使用sycl::vec类型实现向量化加载/存储
- 通过profiler工具分析内存访问模式
典型应用场景
三维DPC++的实现需平衡算法复杂度和硬件特性,通过迭代优化达到最佳性能。
T5《数字接龙》
题目描述
数字接龙:如果一列数字从左到右排成一行,并且对每一对相邻数字都满足:
- 前一个数字的个位 = 后一个数字的最高位,
那么我们称这列数字为一个“接龙序列”。
现在给你一个长度为 n 的序列 a1,a2,…,an。你可以删除其中一些数字(可以一个也不删),剩下的数字保持原有相对顺序。
请你计算:最少需要删除多少个数字,才能让剩下的数字恰好形成一个接龙序列。
输入格式
第一行一个整数 n。
第二行 n 个正整数 a1,a2,…,an。
输出格式
输出一个整数,表示最少删除的数字个数。
思路
这个问题可以转化为寻找序列中最长的接龙子序列,因为最长的接龙子序列意味着需要删除的数字最少。因此,目标转化为求最长接龙子序列的长度,然后用总长度减去这个长度就是需要删除的数字个数。
动态规划是解决这类问题的有效方法。我们定义 dp[i] 为以第 i 个数字结尾的最长接龙子序列的长度。对于每个数字 a[i],需要遍历之前的所有数字 a[j](j < i),当 a[j] 的个位数等于 a[i] 的最高位时,即可更新 dp[i] 的值。
这是一个典型的一维动态规划问题:
- dp[i] 表示以数字 i 结尾的最长接龙子序列长度
- 状态转移方程为:dp[r[i]] = max(dp[l[i]] + 1, dp[r[i]])
代码如下
#include<bits/stdc++.h>
using namespace std;
int s[1000065],dp[15];
int l[1000065],r[1000065];
int main(){
int n;
cin>>n;
for(int i = 1;i<=n;i++){
cin>>s[i];
r[i] = s[i]%10;
while(s[i]>=10){
s[i]/=10;
}
l[i] = s[i];
}
for(int i= 0;i<=9;i++){
dp[i] = 0;
}
for(int i = 1;i<=n;i++){
dp[r[i]] = max(dp[l[i]]+1,dp[r[i]]);
}
int k = 0;
for(int i = 0;i<=9;i++){
k = max(k,dp[i]);
}
cout<<n-k;
return 0;
}
T6《没有上司》
题目描述
公司正在组织聚餐,但每个人都不想和自己的直接上司同桌吃饭。
作为 HR,你知道每个人的直接上司是谁(只有老板没有上司)。
假设 1 号是老板。现在你想邀请尽可能多的人参加聚餐,但需要满足:
- 如果某人的直接上司也参加,则该人不能参加(反之亦然)。
请你输出最多能邀请多少人。
输入格式
第一行一个整数 n,表示公司人数(编号 1 到 n)。
接下来 n−1 行,每行两个整数 ai 和 bi,表示 ai 的直接上司是 bi。
输出格式
输出一个整数,表示最多有多少人能参加聚餐。
思路
代码实现了一个树形动态规划(DP)算法,用于解决树结构中的最大独立集问题。具体目标是选择树中的节点集合,使得任意两个被选节点不相邻(即没有父子关系),并使得选中的节点数量最大化。
数据结构与初始化
- dp[1000005][2]:二维数组用于存储动态规划状态。dp[u][0]表示不选节点u时的最大独立集大小,dp[u][1]表示选择节点u时的最大独立集大小。
- vector<int> g[1000005]:邻接表存储树结构,g[y]保存节点y的所有子节点。
动态规划状态转移
- 不选当前节点(dp[u][0]):子节点可选或不选,取两者中的较大值累加。
公式:
dp[u][0] = \\sum_{v \\in children(u)} \\max(dp[v][0], dp[v][1]) - 选择当前节点(dp[u][1]):子节点不能被选,因此累加所有子节点不选的状态,并加上当前节点自身(+1)。
公式:
dp[u][1] = 1 + \\sum_{v \\in children(u)} dp[v][0
代码如下
#include<bits/stdc++.h>
using namespace std;
long long dp[1000005][2];
vector<int> g[1000005];
void dfs(int u){
long long s1 = 0,s2 = 0;
for(int i = 0;i<g[u].size();i++){
long long v = g[u][i];
dfs(v);
s1 += max(dp[v][0],dp[v][1]);
s2 += dp[v][0];
}
dp[u][0] = s1;
dp[u][1] = s2+1;
}
int main(){
long long n;
cin>>n;
long long x,y;
for(int i = 1;i<n;i++){
cin>>x>>y;
g[y].push_back(x);
}
dfs(1);
cout<<max(dp[1][1],dp[1][0]);
return 0;
}
树状DP
树状DP(动态规划)是一种利用树形结构进行状态转移的动态规划方法,常用于解决树形结构上的最优化问题。以下是C++实现树状DP的关键要点和示例:
树状DP的核心思路
通过后序遍历或DFS遍历树的结构,从叶子节点向根节点传递信息,每个节点的状态由其子节点的状态转移而来。通常需要定义dp[u][k]表示以节点u为根的子树在状态k下的最优解。
实现步骤
定义状态与转移方程 以二叉树最大路径和为例:
- 状态定义:dp[u]表示以u为根的子树中,从u出发向下延伸的最大路径和
- 转移方程:dp[u] = val[u] + max(dp[left], dp[right], 0)(负数则不选)
DFS递归实现
struct TreeNode {
int val;
TreeNode *left, *right;
};
int maxPathSum(TreeNode* root) {
int max_sum = INT_MIN;
function<int(TreeNode*)> dfs = [&](TreeNode* u) {
if (!u) return 0;
int left = max(dfs(u->left), 0);
int right = max(dfs(u->right), 0);
max_sum = max(max_sum, u->val + left + right);
return u->val + max(left, right);
};
dfs(root);
return max_sum;
}
常见问题类型
树上最大独立集 定义状态:
- dp[u][0]:不选节点u时的最大权值
- dp[u][1]:选择节点u时的最大权值
转移方程:
dp[u][0] += max(dp[v][0], dp[v][1]); // v是子节点
dp[u][1] += dp[v][0];
树上最长路径(直径) 记录每个节点的最大深度,同时更新经过该节点的最长路径:
int diameter = 0;
function<int(TreeNode*)> dfs = [&](TreeNode* u) {
if (!u) return 0;
int left = dfs(u->left);
int right = dfs(u->right);
diameter = max(diameter, left + right);
return 1 + max(left, right);
};
注意事项
- 树状DP通常需要结合递归实现,注意递归深度可能导致栈溢出(可改用非递归DFS)
- 对于多叉树,需要遍历所有子节点进行状态转移
- 初始化叶子节点时,应根据问题需求设置边界条件
复杂度分析
时间复杂度一般为O(N),其中N为节点数,每个节点仅被访问一次。空间复杂度取决于状态维度,通常为O(N)或O(N^2)。
P1352 没有上司的舞会
题目描述
某大学有 n 个职员,编号为 1…n。
他们之间有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。
现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定的快乐指数 ri,但是呢,如果某个职员的直接上司来参加舞会了,那么这个职员就无论如何也不肯来参加舞会了。
所以,请你编程计算,邀请哪些职员可以使快乐指数最大,求最大的快乐指数。
输入格式
输入的第一行是一个整数 n。
第 2 到第 (n+1) 行,每行一个整数,第 (i+1) 行的整数表示 i 号职员的快乐指数 ri。
第 (n+2) 到第 2n 行,每行输入一对整数 l,k,代表 k 是 l 的直接上司。
输出格式
输出一行一个整数代表最大的快乐指数。
思路
这道题目比上一题多了一个要求:需要自行找出没有上司的人。只需修改代码中的赋值语句,将dp[u][1] = s2+1改为dp[u][1] = s2+r[u]即可解决问题。
代码如下
#include<bits/stdc++.h>
using namespace std;
long long dp[1000005][2];
long long s[1000005];
long long r[1000005];
vector<int> g[1000005];
void dfs(int u){
long long s1 = 0,s2 = 0;
for(int i = 0;i<g[u].size();i++){
long long v = g[u][i];
dfs(v);
s1 += max(dp[v][0],dp[v][1]);
s2 += dp[v][0];
}
dp[u][0] = s1;
dp[u][1] = s2+r[u];
}
int main(){
memset(s,0,sizeof(s));
long long n;
cin>>n;
long long x,y;
for(int i = 1;i<=n;i++){
cin>>r[i];
}
for(int i = 1;i<n;i++){
cin>>x>>y;
s[x] = 1;
g[y].push_back(x);
}
int a;
for(int i = 1;i<=n;i++){
if(!s[i]){
a = i;
dfs(i);
break;
}
}
cout<<max(dp[a][1],dp[a][0]);
return 0;
}


![P11246 [GESP202409 六级] 小杨和整数拆分-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108100631-6af049a75855c-220x150.png)
![打卡信奥刷题(3678)用C++实现信奥题 P12274 [蓝桥杯 2024 国 Python B] 设计-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108053830-6af00ad6bdf8d-220x150.png)

