河南萌新联赛2025第（三）场：河南理工大学【补题】
目录
- B-上海保卫战
- E-星际争霸
- G-方案数
- H-连续合规子串
- K-魔法音符
B-上海保卫战
题目来源
好呀这道题一看数据范围这么大给我吓住了，我想着就算欧拉筛标记质数也会超呀，竟然还傻傻打表。。。好了，其实这道题，就是一个规律题，是我思路跑歪了，用ans记录操作数，开始赋值为1，判断n是否为偶数，如果是直接除以2就是还需要的操作数，如果是奇数，就遍历去找它的第一个质因数，不用怕超时。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define endl '\n'
const int N=1e4+4;
int n,ans=1;
int Is(int x)//找x的最小质因数
{if(x<2)return 0;//小于2没有质因数 if(x%2==0)return 2;//如果是偶数 for(int i=3;i<=x/i;i+=2)//从3开始找遍历奇数，找到的第一个数就是x的质因数if(x%i==0)return i; return x;//没有质因数，说明x本身就是质数 }
void solve()
{cin>>n;while(n){int num=Is(n);//找第一个质因数 n-=num;//减去 ans++;//操作数+1 if(n%2==0)//如果n是偶数那么它接下来找到的第一个质因数都会是2，所以剩下的操作数直接是n/2 {ans+=n/2;break;}}cout<<ans;
}
signed main()
{IOS;int _=1;while(_--)solve();return 0;
}E-星际争霸
题目来源
这道题还是比较简单的，主要考查了结构体排序，前缀和以及二分函数。题目意思是让输出每个追猎者一共最多能抢到的晶体矿总数，我们只需要对行星要塞以防御能力从小到大排序。排序后用前缀和记录这个位置的和，也就是大于等于这个防御能力那么在它之前的所有晶体矿都能获得。主要就是用二分查找找到第一个大于等于a[i]的数的位置，如果这个数不等于a[i]就是大于a[i]，这个位置就要前移一位，然后目前为止的前缀和就是能得到的最多的晶体矿数。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define endl '\n'
const int N=2e5+5;
const int mod=1e9+7;
int n,m,a[N],b[N],g[N],s[N],aa[N],q[N];
struct node
{int b,g;
}p[N];
bool cmp(node x,node y)
{return x.b<y.b;
}
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++)cin>>p[i].b>>p[i].g; sort(p+1,p+1+m,cmp);for(int i=1;i<=m;i++){q[i]=p[i].b;s[i]=s[i-1]+p[i].g;}for(int i=1;i<=n;i++){int it=lower_bound(q+1,q+1+m,a[i])-q;if(q[it]!=a[i])it--;aa[i]=s[it];}for(int i=1;i<=n;i++)cout<<aa[i]<<" ";
}
signed main()
{IOS;int _=1;
// cin>>_;while(_--)solve();return 0;
}G-方案数
题目来源
这道题考察的就是组合数以及你对题目的理解。首先在n天中选k天就是组合数问题C(n,k)这里范围不大也不小，可以用递归杨辉三角的做法来求组合数，代码中有对应公式我就不多做赘述了，然后就是要理解可以连续几天去同一个地方，那k天有m个地方可去的方案数就是pow(m,k),由于数据大，大家一定要记得多多%mod.怕少不怕多。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define endl '\n'
const int N=2e5+5;
const int mod=1e9+7;
int dp[1005][1005],n,k,m;
void solve()
{cin>>n>>k>>m;for(int i=0;i<=1000;i++)dp[i][0]=1,dp[i][i]=1;for(int i=1;i<=1000;i++){for(int j=0;j<=i;j++){dp[i][j]=(dp[i-1][j]%mod+dp[i-1][j-1]%mod);}}int sum=1;for(int i=1;i<=k;i++)sum=(sum*m)%mod;cout<<((dp[n][k]%mod)*(sum%mod))%mod;
}
signed main()
{IOS;int _=1;
// cin>>_;while(_--)solve();return 0;
}H-连续合规子串
题目来源
这道题让找出连续的满足这两个条件的最长子串的长度：
- 1.相邻两个数不能相等
- 2.相间隔一个数的两个数也不能相等
为了插入和删除清空操作方便，我是用vector容器写的，用ans记录最长的长度的值。
一开始当v的长度等于0时，将字符f加入。
如果长度为1，判断s是否与它里面的字符相等，若不相等就能加入，否则，更新ans的值，将v清空，并将s加入。
如果v的长度大于等于2的话，就要判断s是否与之末尾的两个字符都不相等，如果是则加入，否则再分两种情况：
如果和倒数第二个相等，但和倒数第一个不相等，则更新ans的值，清空v然后将倒数第一个字符和s加入v。其他的情况就是更新ans,清空v将s加入v.
最后最后还要更新一下ans的值
AC代码
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define endl '\n'
const int N=1e6+6;
int n;
char s;
void solve()
{cin>>n;vector<char>v;int ans=0;for(int i=1;i<=n;i++){cin>>s;if(v.size()==0)v.push_back(s);else if(v.size()==1){if(s!=v[v.size()-1])v.push_back(s);else{if(v.size()>ans)ans=v.size();v.clear();v.push_back(s);}}else{if(s!=v[v.size()-1]&&s!=v[v.size()-2])v.push_back(s);else if(s!=v[v.size()-1]&&s==v[v.size()-2]){char c=v[v.size()-1];if(v.size()>ans)ans=v.size();v.clear();v.push_back(c);v.push_back(s);}else if((s==v[v.size()-1]&&s==v[v.size()-2])||(s==v[v.size()-1]&&s!=v[v.size()-2])) {if(v.size()>ans)ans=v.size();v.clear();v.push_back(s);}}}if(v.size()>ans)ans=v.size();cout<<ans;
}
signed main()
{IOS;int _=1;
// cin>>_;while(_--)solve();return 0;
}这道题我写的有些麻烦但思路正确，我们可以看一种更简便的做法：
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define endl '\n'
int n;
string s;
void solve()
{cin>>n;cin>>s;if(n<=2){if(n==2&&s[0]==s[1]) n--;cout<<n<<endl;return ;}int ans=0,l=0;for(int r=1;r<n;r++){if(s[r]==s[r-2])l=r-1;if(s[r]==s[r-1])l=r;ans=max(ans,r-l+1);}cout<<ans;
}
signed main()
{IOS;int _=1;while(_--)solve();return 0;
}K-魔法音符
题目来源
这道题不会的可以去做力扣的这道：接雨水不能说一模一样只能说完全相同。我认为用单调桟写可能会麻烦一些，所以我是用记录前缀最大值和后缀最大值这样两个数组来找一个位置上的左边的最大值和右边最大值，这样我们取二者最小值，减去当前位置上的高度就是能存储的最大回音能量
AC代码
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define endl '\n'
const int N=2e5+5;
int n,a[N],l[N],r[N],ans;
void solve()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i];l[1]=a[1];for(int i=2;i<=n;i++)l[i]=max(l[i-1],a[i]);//左边的最大值r[n]=a[n];for(int i=n-1;i>=1;i--)r[i]=max(r[i+1],a[i]);//右边的最大值for(int i=1;i<=n;i++)ans+=(min(l[i],r[i])-a[i]);cout<<ans;}
signed main()
{IOS;int _=1;
// cin>>_;while(_--)solve();return 0;
}