[寒假集训]2026.2.24

T1《黑白棋》

题目描述

有一个 n×m 的棋盘，棋盘上的每个格子都放着一枚黑棋或白棋。

你可以改变任意格子的棋子颜色（黑变白或白变黑）。现在你需要用最少的改变次数，使得最终棋盘满足：

• 任意两枚相邻棋子（上下左右相邻）的颜色都不相同。

输入格式

第一行两个正整数 n 和 m，表示棋盘的行数和列数。
接下来有 n 行，每行一个长度为 m 的字符串，其中 B 代表黑棋，W 代表白棋。

输出格式

输出一个整数，代表最少需要改变的棋子个数

思路

黑白棋只可能是这两种格式，所以只需将这两种情况分别算一遍再比较，输出最小的那一个。

有一个小技巧，因为，这两种情况是完全不同的，所以，他们两个与原表格不同的个数之和，等于原表格的个数，所以，算一个之后，另一个的个数拿原表格的个数相减；

代码如下

#include<bits/stdc++.h>
using namespace std;
char b[10000][10000];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for(int j = 1;j<=m;j++){
cin >> b[i][j];
}

}
int ans1 = 0;
int ans2 = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if ((i+j) % 2 == 0 && b[i][j] != 'B') ans1++;
if (!((i+j) % 2 == 0) && b[i][j] != 'W') ans1++;
if ((i+j) % 2 == 0 && b[i][j] != 'W') ans2++;
if (!((i+j) % 2 == 0) && b[i][j] != 'B') ans2++;
}
}
cout << min(ans1, ans2);
return 0;
}

T2《闯关游戏》

题目描述

你正在玩一个闯关游戏。角色初始有 X 点血量，每经过一个关卡，血量会发生变化（可能增加也可能减少）。

已知当角色的血量小于等于 0 时会立即死亡。现在你需要计算：初始血量 X 最少是多少，才能保证顺利通过所有关卡。

输入格式

第一行一个正整数 n，表示关卡的数量。

第二行有 n 个整数 a1​,a2​,…,an​，表示每个关卡对血量的影响（正数表示增加，负数表示减少）。

输出格式

输出一个整数，表示初始最少需要多少血量才能通关。

思路

这题只需要找再闯关过程中，血量的最低值绝对值+1，需要运用前缀和；

就可以了

代码如下

#include<bits/stdc++.h>
using namespace std;
int main(){
long long a,b,ans = 0,de = 0,minn = 9999999999;
cin>>a;
for(int i = 1;i<=a;i++){
cin>>b;
if(b<0){
ans += b;
ans += de;
minn = min(ans,minn);
de = 0;
}else{
de += b;
}
}
if(minn>=0){
cout<<1;
}else{
cout<<abs(minn)+1;
}
return 0;
}

拓展

前缀和的概念

前缀和（Prefix Sum）是一种预处理技术，用于快速计算数组或序列中某个区间的和。通过预先计算并存储从起始位置到每个位置的和，可以在常数时间内查询任意区间的和。

前缀和的实现

在C++中，前缀和通常通过一个额外的数组来存储累积和。假设原数组为 arr，前缀和数组为 prefix，则 prefix[i] 表示 arr[0] + arr[1] + … + arr[i-1]。

前缀和数组的构建

vector<int> prefix(n + 1, 0); // 前缀和数组通常比原数组多一个元素
for (int i = 1; i <= n; ++i) {
prefix[i] = prefix[i – 1] + arr[i – 1];
}

区间和查询

通过前缀和数组，区间 [l, r] 的和可以通过以下方式快速计算：

int sum = prefix[r + 1] – prefix[l]; // 注意索引的偏移

前缀和的应用场景

前缀和常用于解决需要频繁查询区间和的问题，例如：

• 子数组和的计算。
• 滑动窗口问题。
• 统计满足条件的区间数量。

T3《偷金币》

题目描述

每户人家都藏有一些金币，一个小偷正准备偷金币，但是你知道的，如果偷相邻的两家很容易被发现，因此小偷决定偷不相邻人家的金币。

现在已知每户人家各有多少金币，请你计算能偷到的最多的金币数量。

输入格式

第一行一个整数，表示 n 户人家。
第二行 n 个正整数 a1​,a2​,…,an​，分别表示每户人家的金币数量。

输出格式

输出一个整数，表示小偷能偷到的最多的金币数量。

思路

这题是一个标准简单的动态规划（dp）

代码如下

#include<bits/stdc++.h>
using namespace std;
long long s[190009],dp[109283];
int main(){
long long a;
cin>>a;
for(long long i = 1;i<=a;i++){
cin>>s[i];
}
dp[1] = s[1];
for(long long i = 2;i<=a;i++){
dp[i] = max(dp[i-2],dp[i-3])+s[i];
}
cout<<max(dp[a],dp[a-1]);
return 0;
}

拓展

动态规划在C++中的实现

动态规划（Dynamic Programming，简称DP）是一种解决复杂问题的算法思想，通过将问题分解为子问题并存储子问题的解来避免重复计算。在C++中，动态规划的实现通常涉及数组或表格来存储中间结果。

动态规划的基本步骤

确定问题的状态和状态转移方程。状态通常表示问题的子问题，状态转移方程描述如何从一个状态转移到另一个状态。

初始化边界条件。边界条件是动态规划的起点，通常是最小的子问题的解。

通过迭代或递归填充状态表。根据状态转移方程，逐步计算出所有状态的解。

动态规划的常见实现方式

自顶向下（记忆化递归）
使用递归函数解决问题，并通过数组或哈希表存储已计算的子问题结果，避免重复计算。

int memo[MAX_N];
int dp(int n) {
if (n == 0) return 0;
if (memo[n] != -1) return memo[n];
memo[n] = dp(n – 1) + dp(n – 2);
return memo[n];
}

自底向上（迭代法）
从最小的子问题开始，逐步构建更大的子问题的解，通常使用循环结构实现。

int dp[MAX_N];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i – 1] + dp[i – 2];
}

动态规划的优化技巧

空间优化
某些情况下，状态转移只依赖于前几个状态，可以通过滚动数组或变量减少空间复杂度。

int a = 0, b = 1;
for (int i = 2; i <= n; ++i) {
int c = a + b;
a = b;
b = c;
}

状态压缩
对于状态可以用位表示的问题，使用位运算来优化状态存储和转移。

int dp[1 << N];
for (int mask = 0; mask < (1 << N); ++mask) {
for (int i = 0; i < N; ++i) {
if (!(mask & (1 << i))) {
dp[mask | (1 << i)] = dp[mask] + cost[i];
}
}
}

动态规划的注意事项

确保状态转移方程的正确性。错误的状态转移方程会导致整个动态规划算法失效。

注意边界条件的处理。边界条件通常直接影响动态规划的初始状态。

考虑时间和空间复杂度。动态规划的优势在于避免重复计算，但某些情况下可能需要优化空间使用。

T4《乘积最大》

题目描述

给定一个长度为 n 的整数序列 a1​,a2​,…,an​。

你可以把这些数字分成两堆（每个数必须且只能属于其中一堆），设两堆数字的和分别为 X 和 Y。

你需要输出 X×Y 的最大值。

输入格式

第一行一个整数 n 表示序列长度。
第二行 n 个整数，表示 a1​,a2​,…,an​。

输出格式

输出一个整数，表示最大乘积。

思路

这也是一道dp.

代码如下

#include<bits/stdc++.h>
using namespace std;
int n,a[101],dp[100001];
int main(){
int s=0;
cin>>n;

for(int i=0;i<n;i++){
cin>>a[i];
s+=a[i];
}
int r=s/2;
int t=r;
sort(a+1,a+n+1);
for(int i=0;i<n;i++){
for(int j=s/2;j>=0;j–){
if(j-a[i]>=0){
dp[j]=max(dp[j-a[i]]+a[i],dp[j]);
}
}
for(int i=0;i<=r;i++){
if(r-dp[i]>=0)
t=min(t,r-dp[i]);
}
}

for(int i=0;i<=r;i++){
if(s-dp[i]>=0)
t=min(t,s-dp[i]);
}
long long ans=(r-t)*(s-r+t);
cout<<ans;
return 0;
}

T5《数字金字塔高级版》

题目描述

还记得数字金字塔问题吗？

你需要从塔尖（第 1 行第 1 列）走到最后一排。假设你当前在第 i 行第 j 列，那么下一步只能走到：

• 第 i+1 行第 j 列
• 第 i+1 行第 j+1 列

每走到一个位置，你都会获得该位置上的数字。

但是你现在拥有了魔法手套：它可以把某一个位置的数字变为原来的 2 倍。
很遗憾，这个手套最多只能使用 k 次，也就是说你最多只能对路径上的 k 个位置使用“翻倍”。

现在你需要计算拥有了魔法手套后你能获得的最大数字和。

输入格式

第一行两个正整数 n 和 k，分别表示金字塔的层数与魔法手套最多允许使用的次数。
接下来有 n 行，第 i 行输入 i 个整数，表示第 i 行从左到右的数字。

输出格式

输出一个整数，表示能获得的最大数字和

思路

这是一道三维DP.并且是一道01背包问题；

代码如下

#include<bits/stdc++.h>
using namespace std;
int n,k,s[1003][1003],dp[1003][1008][11];
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
cin>>s[i][j];
for(int i=0;i<=1000;i++)
for(int j=0;j<=1000;j++){
for(int d=0;d<=10;d++){
dp[i][j][d]=-1234567890;
}
}
dp[0][0][0]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
for(int p=0;p<=k;p++){
int t=-0x3f3f3f3f;
t=max(dp[i-1][j-1][p],dp[i-1][j][p])+s[i][j];
if(p)
t=max({t,dp[i-1][j-1][p-1]+s[i][j]*2,dp[i-1][j][p-1]+s[i][j]*2});
dp[i][j][p]=t;
}
int ans=-1234567890;
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++) ans=max(ans,dp[n][i][j]);
}
cout<<ans;
return 0;
}

拓展

01背包问题概述

01背包问题是经典的动态规划问题，要求在给定容量的背包和一组物品（每个物品有重量和价值）的情况下，选择物品装入背包，使得背包中物品的总价值最大。每个物品只能选择装入或不装入（0或1）。

动态规划解法

动态规划的核心是定义状态和状态转移方程。

状态定义

用 dp[i][j] 表示从前 i个物品中选择，背包容量为 j 时的最大价值。

状态转移方程

对于第 i个物品：

• 如果不选第 i个物品，dp[i][j] = dp[i-1][j]
• 如果选第 i 个物品（前提是 j \\geq w_i），dp[i][j] = dp[i-1][j-w_i] + v_i

综合两种情况： dp[i][j] = max(dp[i-1][j], dp[i-1][j-w_i] + v_i) 

初始化

dp[0][j] = 0（前 0 个物品，价值为 0） dp[i][0] = 0（背包容量为 0，价值为 0）

T6《环游世界》

题目描述

你想去环游世界。现在已知从每个城市到另一个城市的路程（有向距离，可能不对称）。

你希望从 1 号城市出发，找到一条最短的路线，使得：

• 每个城市都恰好经过一次；
• 最后回到 1 号城市。

你需要输出最短路程的长度。

输入格式

第一行一个整数 n，表示城市数量。

接下来输入一个 n×n 的矩阵 a，其中 ai,j​ 表示从第 i 个城市到第 j 个城市的距离。
注意：ai,j​ 不一定等于 aj,i​。

输出格式

输出一个整数，表示最短的路程。

思路

这是一道状态压缩DP;

代码如下

#include<bits/stdc++.h>
using namespace std;
int dp[(1<<20)][20],a[(1<<20)][20];
int main(){
memset(dp,0x3f,sizeof(dp));
dp[1][0] = 0;
int n;
cin>>n;
if(n == 1){
cout<<0;
return 0;
}
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
cin>>a[i][j];
}
}
for(int i = 0;i<(1<<n);i++){
for(int j = 0;j<n;j++){
if(i&(1<<j)){
int s = i – (1<<j);
for(int k = 0;k<n;k++){
if(s&(1<<k)){
dp[i][j] = min(dp[i][j],dp[s][k]+a[k][j]);
}
}
}

}
}
int ans = 0x3f3f3f3f;
for(int i = 1;i<n;i++)ans = min(ans,dp[(1<<n)-1][i] + a[i][0]);
cout<<ans;
return 0;
}

拓展

状态压缩动态规划（Dynamic Programming with State Compression）是一种优化技术，用于处理状态空间较大的动态规划问题，通过压缩状态表示来减少内存或计算复杂度。以下是关于状态压缩DP在C++中的关键点：

状态压缩DP的核心思想

状态压缩通常利用位运算（如按位与、或、移位）将多维状态或复杂状态转化为一个整数（通常是二进制形式）。例如，用二进制数的每一位表示某个物品是否被选中，或某个位置是否被访问过。

常见应用场景

• 旅行商问题（TSP）：用二进制数表示已访问的城市集合。
• 棋盘覆盖问题：用位掩码表示棋盘的摆放状态。
• 子集问题：枚举所有子集时直接使用二进制数的每一位作为标志。

C++实现要点

// 示例：检查第i位是否为1
bool isSet(int mask, int i) {
return mask & (1 << i);
}

状态转移设计
状态转移方程通常涉及从当前状态（掩码）生成新状态。例如在TSP中：

dp[mask][u] = min(dp[mask][u], dp[mask ^ (1 << u)][v] + dist[v][u]);

初始化与边界条件
初始状态（如空集合或起点）需单独处理：

// 初始化：从城市0出发
dp[1 << 0][0] = 0;

遍历顺序
通常外层循环遍历所有可能的掩码状态，内层循环处理具体子问题：

for (int mask = 0; mask < (1 << n); ++mask) {
for (int u = 0; u < n; ++u) {
if (!(mask & (1 << u))) continue;
// 状态转移逻辑
}
}

优化技巧

• 预处理合法状态：提前生成所有可能的合法掩码，减少无效计算。
• 滚动数组：对于某些问题，只需保存前一个状态的空间。
• 剪枝：在状态转移中跳过不可能达到最优解的分支。

完整示例（TSP问题片段）

const int INF = 1e9;
int dist[20][20];
int dp[1 << 16][20];

int tsp(int n) {
memset(dp, INF, sizeof(dp));
dp[1 << 0][0] = 0; // 从城市0出发

for (int mask = 0; mask < (1 << n); ++mask) {
for (int u = 0; u < n; ++u) {
if (!(mask & (1 << u))) continue;
for (int v = 0; v < n; ++v) {
if (mask & (1 << v)) continue;
dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v],
dp[mask][u] + dist[u][v]);
}
}
}

// 返回最终状态：所有城市访问过并回到起点
int final_mask = (1 << n) – 1;
int res = INF;
for (int u = 1; u < n; ++u) {
res = min(res, dp[final_mask][u] + dist[u][0]);
}
return res;
}

注意事项

• 复杂度分析：状态数为(O(2^n \\cdot n))，适用于(n \\leq 20)左右的问题。
• 调试技巧：打印中间状态（掩码的二进制形式）辅助验证逻辑。

通过合理设计状态表示和转移方程，状态压缩DP能显著提升某些动态规划问题的求解效率。