【寒假集训】2026.2.25

前言：

这是第四天了，所有题目中，有许多高质量的题目，很多人想看，但我发现链接对很多人不行，所以从这次开始，换成图片。

之前的文章链接：

day1：https://blog.csdn.net/Matthew_zhu_/article/details/158290602?spm=1001.2014.3001.5501

day2：https://blog.csdn.net/Matthew_zhu_/article/details/158320728?spm=1001.2014.3001.5501

day3：https://blog.csdn.net/Matthew_zhu_/article/details/158355986?spm=1001.2014.3001.5501

那么为了弥补之前的空缺，我把day1-3的题目放入文章里，代码自行点进链接查看。

day1：

T1：

T2：

T3：

T4：

T5：

T6：

day2：

T1：

T2：

T3：

T4：

T5：

T6：

day3：

T1：

T2：

T3：

T4：

T5：

T6：

正文：

T1：

本题AC代码：

#include<bits/stdc++.h>
using namespace std;
int a[100005],space[100005];
int main(){
int n,minn,sum=0;
cin>>n;
space[1]=0;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)if(i>=2)space[i]=a[i]-a[i-1];
minn=__gcd(space[2],space[3]);
for(int i=1;i<=n;i++){
minn=__gcd(minn,space[i]);
}
for(int i=2;i<=n;i++){
sum+=(space[i]/minn)-1;
}
cout<<sum;
return 0;
}

本题思路：

        要形成等间距的序列，需要满足所有相邻树的间距相同。这意味着所有原始树的位置必须构成一个等差数列。因此，关键在于找到原始树位置的最大公约数（GCD）作为等差数列的公差。

T2：

本题AC代码：

#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;
}

本题思路：

        该问题类似于经典的约瑟夫问题变种，但规则有所不同。在每一轮中，所有报数不是k的倍数的人会被吃掉，剩下的继续下一轮。目标是找到最后一个被吃掉的人的初始编号。

T3：

本题AC代：码：

#include<bits/stdc++.h>
using namespace std;
long long dp[100005][3];
long long a[100005];
int main(){
long long n,k;
cin>>n>>k;
for(long long i=1;i<=n;i++){
cin>>a[i];
}
dp[0][0]=0;
dp[0][1]=-0x3f3f3f3f3f3f3f3f;
dp[0][2]=-0x3f3f3f3f3f3f3f3f;
for(int i=1;i<=n;i++){
dp[i][0]=max(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]+a[i]*2;
}
cout<<max(max(dp[n][0],dp[n][1]),dp[n][2]);
return 0;
}

本题思路：

        这道题目可以通过动态规划来解决。需要记录每一秒的状态，即前几秒的技能使用情况。具体来说，可以定义状态为：

• dp[i][0]：第 i 秒选择普攻时的最大伤害。
• dp[i][1]：第 i 秒第一次使用技能时的最大伤害。
• dp[i][2]：第 i 秒连续第二次使用技能时的最大伤害。

T4：

本题AC代码：

#include<bits/stdc++.h>
using namespace std;
bool dp[55][55][10007];
int a[55][55];
int main() {
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
dp[1][1][a[1][1] % 10007] = 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][j+1][(k+a[i][j+1])%10007]=true;
dp[i+1][j][(k+a[i+1][j])%10007]=true;
}
}
}
}
int cnt=0;
for(int i=0;i<10007;i++){
cnt+=dp[n][m][i];
}
cout<<cnt;

return 0;
}

本题思路：

        这道题目要求计算从迷宫左上角到右下角的所有可能路径的总伤害对10007取模后的不同结果数量。由于每一步只能向右或向下移动，可以使用动态规划的方法来记录到达每个位置时的所有可能模值。

T5：

本题AC代码：

#include<bits/stdc++.h>
using namespace std;
long long ans=0,d,dp[100005],n,l[100005],r[100005];
char a[100005][10];
int main() {
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
l[i]=a[i][0]-'0';
r[i]=a[i][strlen(a[i])-1]-'0';
}
for(int i=1;i<=n;i++){
dp[r[i]]=max(dp[r[i]],dp[l[i]]+1);
}
for(int i=0;i<10;i++){
ans=max(ans,dp[i]);
}
cout<<n-ans;
return 0;
}

本题思路：

        数字接龙问题要求找到最长的子序列，使得相邻数字满足前一个数字的个位数等于后一个数字的最高位。最少删除数字的数量等于原序列长度减去最长接龙子序列的长度。

T6：

本题AC代码：

#include<bits/stdc++.h>
using namespace std;
vector<int> g[100005];
int dp[100005][2];

void dfs(int u) {
int s1 = 0, s2 = 0;
for (int i = 0; i<g[u].size(); i++) {
int 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(){
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
g[b].push_back(a);
}
dfs(1);
cout << max(dp[1][1], dp[1][0]) <<'\\n';
return 0;
}

本题思路：

        这道题目可以抽象为树形动态规划问题。每个人可以看作树中的一个节点，其直接上司是父节点。题目要求选择尽可能多的节点，使得没有父子节点同时被选中。