河南萌新联赛2025第（七）场：郑州轻工业大学

做事情要有始有终，补题也是，怎么能少了这最后一场呢。今天终于有时间将最后一场的萌新赛补下题。

比赛来源：河南萌新联赛2025第（七）场：郑州轻工业大学

M-奥数班

解题思路

按照题目模拟即可

AC代码

void solve()
{int a,b;cin>>a>>b;if(a>=b*10)cout<<">>";if(a>b&&a<b*10)cout<<">";if(a==b)cout<<"=";if(b>a&&b<a*10)cout<<"<";if(b>=a*10)cout<<"<<"; 
}

J-掷骰子

解题思路

通过观察可以发现,最小能构成的数是45最大能构成的数是495，所以如果这个数小于45或者大于495就是一定不能构成的，再观察这些数，发现只要在45的基础上加上5的倍数且不超过495就是一定能构成的，因此只需要判断这个数-45后能否整除5.

AC代码

void solve()
{int n,x,ans=0;cin>>n;for(int i=1;i<=n;i++){cin>>x;if(x<45||(x-45)%5!=0||x>495)ans++;}cout<<ans;}

C-灯光是我在异世界的呼喊’

解题思路

这道题给了所有S的长度不会超过2e5，那么我们是可以用map来存每个可能的前缀的个数，然后再遍历这n条密文，看哪个数量最多。

AC代码

void solve()
{cin>>n;vector<string>s(n);for(int i=0;i<n;i++){cin>>s[i];string s1;for(auto c:s[i]){s1+=c;mp[s1]++;}}int ans=0;for(auto x:s)ans=max(ans,mp[x]);cout<<ans;	
}

K-好奇的小夏

解题思路

利用双指针和滑动窗口的思想，先对数字进行排序，然后依次判断每个数所能构成的最多数量，利用双指针，通过加过之后的和减去原来的和得到需要的操作次数，利用前缀和可以大大节省时间，如果大于k就不满足需要缩短长度，最后更新最优即可。

AC代码

void solve()
{cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];int mx=-1e18,ans=1e18,l=1;for(int r=1;r<=n;r++){while((a[r]*(r-l+1))-(s[r]-s[l-1])>k)l++;//判断这个数所能构成的最大数量int len=r-l+1;if(len>mx){mx=len;ans=a[r];}}cout<<mx<<" "<<ans<<endl;
}

D-灯泡

解题思路

打表找规律。

AC代码

void solve()
{cin >> n;cout << (int)(sqrt(n))+(int)(sqrt(n/2));
}

L-打游戏 or 写程序

解题思路

定义dp[i]为前 i 个中，第 i 个是打游戏的所有可能性数目,对于每个位置 i，如果第 i 个事件是打游戏，那么前一个打游戏事件的位置最多只能是i - k - 1（因为中间至少有 k 个写程序事件）。因此dp[i]是前 i - k - 1个位置中所有打游戏可能性的和。然后使用前缀和数组S，其中s[i]表示前 i 个位置的 dp 值的和。这样可以将状态转移的时间复杂度优化到 (O(1))

AC代码

void solve()
{int n,k;cin>>n>>k;vector<int>s(n+2,0);s[0]=1;for(int i=1;i<=n;i++){int l=0;if(i-k-1>0)l=i-k-1;s[i]=s[l];s[i]=(s[i]+s[i-1])%mod; }cout<<s[n]<<endl;	
}