河南萌新联赛2025第一场-河南工业大学

发布于：2025-07-18 ⋅ 阅读:(21) ⋅ 点赞:(0)

L-Where is zero?

这道题是签到题，随便把一个数变成0即可。

// Problem: Where is zero?
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/113664/L
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define PII pair<int,int>
#define fi first
#define se second
const int N = 1e6+10;
int a[N];

void solve()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	a[2] = 0;
	for(int i=0;i<n;i++) cout<<a[i]<<' ';
}

signed main()
{
	IOS
	int T=1;
//	cin>>T;
	while(T--) solve(); 
	return 0;
}

C-富有的国王

这道题一开始还以为要建图，可是看样例就会发现直接让最大的总数减去现在已经有的数量即可（因为给出的铁路不会重复）。

// Problem: 富有的国王
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/113664/C
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define PII pair<int,int>
#define fi first
#define se second

void solve()
{
	int n,m;
	cin>>n>>m;
	int sum = n*(n-1);
	cout<<sum-m<<endl;
}

signed main()
{
	IOS
	int T=1;
//	cin>>T;
	while(T--) solve(); 
	return 0;
}

H-黑客帝国

这道题是之前寒训的一道蛇形矩阵的题目，这次比赛竟然出来原题那我就不客气了。

只需要用一个变量来控制方向模拟即可，没什么说的，相信看到这篇博客的小伙伴不单单是因为这道题而看的~

// Problem: 黑客帝国
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/113664/H
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define PII pair<int,int>
#define fi first
#define se second
const int N = 1010;
int mp[N][N];
int n;

void solve()
{
	memset(mp,-1,sizeof(mp));
	cin>>n;
	int x,y;
	if(n&1) x=(n+1)/2;
	else x=n/2;
	y=x;
	mp[x][y]=0;
	int sum = n*n;
	int f=1;
	for(int index=1;index<sum;index++)
	{
		if(f==1)
		{
			mp[x][++y]=index;
			if(mp[x+1][y]==-1) f=2;
			continue;
		}
		if(f==2)
		{
			mp[++x][y]=index;
			if(mp[x][y-1]==-1) f=3;
			continue;
		}
		if(f==3)
		{
			mp[x][--y]=index;
			if(mp[x-1][y]==-1) f=4;
			continue;
		}
		if(f==4)
		{
			mp[--x][y]=index;
			if(mp[x][y+1]==-1) f=1;
			continue;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		cout<<mp[i][j]<<' ';
		cout<<endl;
	}
}

signed main()
{
	IOS
	int T=1;
	cin>>T;
	while(T--) solve(); 
	return 0;
}

I-二进制转化

  1. 子串的本质：在二进制字符串中，"01" 和 "10" 子串的数量差异实际上反映了字符串中相邻字符变化的次数。
    • 每次从 '0' 变为 '1' 会增加一个 "01" 子串。
    • 每次从 '1' 变为 '0' 会增加一个 "10" 子串。
  2. 首尾字符的影响：
    • 如果首尾字符相同（例如 s[0] = '0' 且 s[n-1] = '0'），那么整个字符串的变化次数是偶数次。
    • 如果首尾字符不同（例如 s[0] = '0' 且 s[n-1] = '1'），那么整个字符串的变化次数是奇数次。

所以：

  1. 首尾相同的情况：
    • 假设字符串的首尾字符都是 '0'。
    • 由于每次变化都是从 '0' 到 '1' 或从 '1' 到 '0'，首尾相同意味着变化次数是偶数次。
    • 因此，"01" 和 "10" 子串的数量会相等。
    • 无论如何选择区间 ([l, r])，我们都可以通过翻转区间内的字符来调整变化次数，使得 "01" 和 "10" 子串的数量相等。
  1. 首尾不同的情况：
    • 假设字符串的首尾字符分别是 '0' 和 '1'。
    • 首尾不同意味着变化次数是奇数次。
    • 无论如何选择区间 ([l, r])，翻转后的变化次数仍然是奇数次，因此 "01" 和 "10" 子串的数量无法相等。

理清题目意思的本质是很重要的！

// Problem: 二进制转化
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/113664/I
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define PII pair<int,int>
#define fi first
#define se second


void solve()
{
	int n, l, r;
    string s;
    cin>>n>>s>>l>>r;
    if (s[0] == s[s.size()-1])
    {
        cout << "Yes" << endl;
        return;
    } 
    else if (l == 1 || r == n)
    {
        cout << "Yes" << endl;
        return;
    }
    cout << "No" << endl;
    return;
}

signed main()
{
	IOS
	int T=1;
	cin>>T;
	while(T--) solve(); 
	return 0;
}

G-最大子段和，但是两段

这道题我竟然没注意到题目上就说了是最大子段和，用滑动窗口写发现怎么也过不了，后来才发现是把前缀和数组当成后缀和直接用了！！！铭记！

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 10;
const int INF = 1e18;
int a[N], prefix[N], suffix[N];
int left_max[N], right_max[N];

void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        prefix[i] = prefix[i - 1] + a[i];
    }
    
    // 计算后缀和
    for (int i = n; i >= 1; i--) {
        suffix[i] = suffix[i + 1] + a[i];
    }

    // 正向单调队列处理左半部分
    deque<int> q_left;
    q_left.push_back(0);  // 初始放入prefix[0]
    left_max[0] = -INF;
    for (int i = 1; i <= n; i++) {
        // 维护单调递增队列
        while (!q_left.empty() && prefix[q_left.back()] > prefix[i]) {
            q_left.pop_back();
        }
        left_max[i] = max(left_max[i - 1], prefix[i] - prefix[q_left.front()]);
        q_left.push_back(i);
    }

    // 逆向单调队列处理右半部分
    deque<int> q_right;
    q_right.push_back(n + 1);  // 初始放入suffix[n+1]=0
    right_max[n + 1] = -INF;
    for (int i = n; i >= 1; i--) {
        // 维护单调递增队列
        while (!q_right.empty() && suffix[q_right.back()] > suffix[i]) {
            q_right.pop_back();
        }
        right_max[i] = max(right_max[i + 1], suffix[i] - suffix[q_right.front()]);
        q_right.push_back(i);
    }

    // 计算最大两段和
    int ans = -INF;
    for (int i = 1; i < n; i++) {
        ans = max(ans, left_max[i] + right_max[i + 1]);
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

当然用前缀和+单调队列+后缀和+单调队列确实有点麻烦了，下次见到最大子段和可以用动态规划的思想来解决！！！ 

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define PII pair<int,int>
#define fi first
#define se second
const int N = 5e5 + 10;
int a[N], sum[N];
int l[N], r[N];
int n;

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }

    int current_max = a[1];//以当前元素结尾子串的最优解
    l[1] = a[1];//当前元素之前的最优解
    for (int i = 2; i <= n; i++) {
        current_max = max(a[i], current_max + a[i]);
        l[i] = max(l[i - 1], current_max);
    }

    current_max = a[n];
    r[n] = a[n];
    for (int i = n - 1; i >= 1; i--) {
        current_max = max(a[i], current_max + a[i]);
        r[i] = max(r[i + 1], current_max);
    }

    int ans = -1e18;
    for (int i = 1; i < n; i++) {
        ans = max(ans, l[i] + r[i + 1]);
    }

    cout << ans << endl;
}

signed main() {
    IOS
    int T = 1;
    cin >> T;
    while (T--) solve();
    return 0;
}

M-无聊的子序列

暴力枚举长度为 1，2，3，4 的子数组即可。

我们可以通过打表的方式找到一些规律，即：不存在任何一个长度大于等于 5 的子数组满足题目中的限制条件，所以只需要暴力枚举就行了。

注意长度为4的时候，要想不存在非严格递增/减，就要相邻两个为一组同单调性且后面一组的起点更弱。

// Problem: 无聊的子序列
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/113664/M
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define PII pair<int,int>
#define fi first
#define se second
const int N = 1e6+10;
int a[N];
int n;
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (n == 1)
    {
        cout << 1 << endl;
        return;
    }
 	//长度为1的子数组有n个，长度为2的子数组有n-1个这两种所有的都满足条件 所以只需要考虑长度为3和4的即可
    int ans = n * 2 - 1;
    //暴力长度为3的子数组
    for (int i = 1; i <= n - 2; i++)
    {
        if (a[i] <= a[i + 1] && a[i + 1] <= a[i + 2]) continue;
        if (a[i] >= a[i + 1] && a[i + 1] >= a[i + 2]) continue;
        if (a[i] == a[i + 1] || a[i + 1] == a[i + 2]) continue;
        ans++;
    }
    //暴力长度为4的子数组
    for(int i = 1; i <= n-3; i++)
    {
    	//长度为4时只有两个递增或者两个递减
        if (a[i] > a[i + 1] && a[i] < a[i + 2] && a[i + 3] > a[i + 1] && a[i + 3] < a[i + 2]) ans++;
        if (a[i] < a[i + 1] && a[i] > a[i + 2] && a[i + 3] < a[i + 1] && a[i + 3] > a[i + 2]) ans++;
    }
 
    cout << ans << endl;
}

signed main()
{
	IOS
	int T=1;
//	cin>>T;
	while(T--) solve(); 
	return 0;
}

B-代价转移

这个题目可以用优先队列存当前的最小代价，不断的用最小代价的点来搜索，直到达到了这个点

代码如下：

// Problem: 代价转移
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/113664/B
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define PII pair<int,int>
#define fi first
#define se second
const int N = 1e3+10;
int a[N];
int n,m,c1,c2,c3;

void solve()
{
	cin>>n>>m>>c1>>c2>>c3;
	if(n==m)
	{
		cout<<0<<endl;
		return ;
	}
	memset(a,0x3f3f3f,sizeof a);
	priority_queue<PII,vector<PII>,greater<PII>> q;
	//PII中第一个值为目前当前数值的代价 第二个值为当前的数值
	q.push({0,n});
	while(!q.empty())
	{
		PII t = q.top();
		q.pop();
		if(t.se==m)
		{
			cout<<t.fi<<endl;
			return ;
		}
		if(t.fi>a[t.se]) continue;
		if(t.se+1<N && t.fi+c1<a[t.se+1])
		{
			a[t.se+1]=t.fi+c1;
			q.push({a[t.se+1],t.se+1});
		}
		if(t.se-1>0 && t.fi+c2<a[t.se-1])
		{
			a[t.se-1]=t.fi+c2;
			q.push({a[t.se-1],t.se-1});
		}
		if(t.se*2<N && t.fi+c3<a[t.se*2])
		{
			a[t.se*2]=t.fi+c3;
			q.push({a[t.se*2],t.se*2});
		}
	}
}

signed main()
{
	IOS
	int T=1;
	cin>>T;
	while(T--) solve(); 
	return 0;
}

详解见：超详细的代码

A-隔板

这道题算是一个较难的题目了，因为这类问题有好多种，分为好几种问题，需要取花费大量时间取整理。

简单总结一下四种排列组合的递推式：

小球相同盒子相同：

f(n, m) = f(n-1, m-1) + f(n-m, m)

边界条件：

f(n,1) = 1;          

f(n,n) = 1;         

f(n,m)当n<m时等于0：

小球相同盒子不同时：

int qpow(int a, int b) 
{
	a %= mod;
	int ans = 1;
	while(b) 
	{
		if(b%2 == 1)
			ans = (ans*a)%mod;
		a=(a*a)%mod;
		b/=2;
	}
	return ans;
}
// 计算组合数 C(n, m) 对 mod 取模的结果
int zhs(int n, int m) 
{
	int f1[n+1], f2[n+1];
	f1[0] = 1;//特判一下,0的阶乘是1
	for (int i = 1; i <= n; i++)
		f1[i] = (f1[i-1]*i)%mod;  // 计算阶乘数组并取模

	f2[n] = qpow(f1[n], mod-2);  // 计算阶乘的逆元

	for (int i = n-1; i>=0; i--)
		f2[i] = (f2[i+1]*(i+1))%mod;  // 计算逆元数组

	int ans;
	ans = (f1[n]*f2[m]%mod*f2[n-m]) % mod;
	return ans;
}

 

小球不同盒子相同时：

 需要用到 第二类斯特林数

递推公式：f(n, m) =f(n-1, m-1) + m·f(n-1, m)

最终答案就为 ans = dp[n][m] % mod;

dp[0][0]=1; // 边界条件：f(0,0)=1
    for(int i=1; i<N; ++i) 
    {
        for(int m=1; m<=i; ++m) // m最多为i（否则f(i,m)=0）
        	dp[i][m] = (dp[i-1][m-1]+m*dp[i-1][m])%M;
    }

小球不同盒子也不同时： 

利用斯特林数（第二类）和阶乘的组合来解决

斯特林数的预处理：f(n, m) = f(n-1, m-1) + m·f(n-1, m)

边界条件：f(0,0) = 1，n<m 时 f(n,m)=0

 这道题显然属于第四种：

// Problem: ¸ô°å
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/113664/A
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define PII pair<int,int>
#define fi first
#define se second
const int N = 5e3+10;
int n,m;
const int mod = 998244353;
int dp[N][N];//第二类斯特林数
int jie[N];//阶乘

void solve()
{
	cin>>n>>m;
	if(n<m)
	{
		cout<<0<<endl;
		return ;
	}
	jie[0]=1;//阶乘算到盘子即可 因为阶乘是由盘子的不同排列引起的
	for(int i=1;i<=m;i++) jie[i] = i % mod * jie[i-1] % mod;
	dp[0][0]=1;//初始化斯特林数 f(0,0)=1;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=i;j++)
	dp[i][j] = (dp[i-1][j-1] + j*dp[i-1][j]) % mod;
	cout<<dp[n][m] % mod * jie[m] % mod;
}

signed main()
{
	IOS
	int T=1;
//	cin>>T;
	while(T--) solve(); 
	return 0;
}

更多题解：题解

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布