河南萌新联赛2025第五场 - 信息工程大学

信息工程大学的出题依旧对待小白友好~在这里感谢出题方，但是你自己看看A题阴不阴😭

这次的题目没有很深奥的算法知识，大多都是一些模拟和常见的基础算法以及数论中的内容，所以我会认真对待这次的题目，补题会持续更新~

本场比赛传送门：河南萌新联赛2025第（五）场：信息工程大学”_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

首当其冲的就是签到题了：

A - 宇宙终极能量调和与多维时空稳定性验证下的基础算术可行性研究

看到题目的我小脑都萎缩了，怀着反常的心思断定这道题就是签到题，点进去之后...哇，小脑变成大脑了！出题人你自己看看阴不阴😄：

这道题把我的思绪拉回到了高考做语文阅读理解的时候，读完一遍题发现读了一遍题，😄，但是看到别人一顿酷酷过，我第一眼就锁定了异或符号，直接将1 ^ 1的结果交了上去，没错！WA了，后来就放弃这一题了，谁爱写谁写，再之后看到更多的人过了，我还是咬咬牙又读了一遍题，终于发现了一些端倪：666经典线性叠加，我怀着幼儿园都会的1 + 1交了上去，过了...过的很窝囊

后来看题解，我想着出题人会给我一些说法，知道我看到了：

？我请问呢，全剧终。代码就不粘贴了，直接 cout << “ 2 ” << endl; 即可

接下来看B题：

B - 中位数

题目传送门：B-中位数_河南萌新联赛2025第（五）场：信息工程大学”

这道题还是朴实无华的简单思维题，只需要稍微动动脑就能发现，每次删除的是中位数，也就是说，不管对哪个长度为3的序列操作，最终都会剩下一个最小值和一个最大值，所以我们只需要对原数组进行排序，然后求最大值和最小值的中位数即可，不管了，直接交：

怎么错了？看一眼数据范围，哦哦哦哦哦！还有1的时候的特判！加上特判：

赛时代码如下：

// Problem: 中位数
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/115567/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
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
const int INF = 0x3f3f3f3f;
const int inf = 1e18; void solve()
{int n;cin>>n;vector<int> a(n+1);if(n == 1){cout<<n<<endl;return ;}for(int i=1;i<=n;i++) cin>>a[i];sort(a.begin() + 1,a.end());int ans = a[1] + a[n];ans /= 2;cout<<ans<<endl;//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;
//	cin>>T;while(T--) solve(); return 0;
} 

C - 中位数 + 1

题目链接：C-中位数+1_河南萌新联赛2025第（五）场：信息工程大学”

这道题是很熟悉的一道题，通过每次加进来的一个数，然后计算出该数组中的中位数，说白了就是求动态中位数，直接套模版，用一个名为对顶堆的数据结构，对奇数和偶数情况进行判断，过过过

// Problem: 中位数+1
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/115567/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
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
const int INF = 0x3f3f3f3f;
const int inf = 1e18; void solve()
{priority_queue<int> da;//dapriority_queue<int,vector<int>,greater<int>> xiao;//xiaoint n;cin>>n;for(int i=1;i<=n;i++){int x;cin>>x;da.push(x);if(da.size() == xiao.size() + 2){int t = da.top();da.pop();xiao.push(t);}while(xiao.size() && da.top() > xiao.top()){int t = da.top();da.pop();int tt = xiao.top();xiao.pop();da.push(tt);xiao.push(t);}if(i & 1) cout<<da.top()<<' ';else if(da.size() && xiao.size()) cout<<(da.top() + xiao.top())/2<<' ';}
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;
//	cin>>T;while(T--) solve(); return 0;
} 

F - 中位数 + 4

题目链接：F-中位数+4_河南萌新联赛2025第（五）场：信息工程大学”

这道题就是将给定的数转化为k进制，然后判断有几个后导零即可，直接用字符串模拟即可。

// Problem: 中位数+4
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/115567/F
// 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
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
const int INF = 0x3f3f3f3f;
const int inf = 1e18; 
string to(int n,int k)
{string ans;int t = k;while(n){string t = to_string(n%k);n /= k;ans += t;}reverse(ans.begin(),ans.end());return ans;
}
void solve()
{int n,k;cin>>n>>k;string s = to(n,k);int cnt = 0;for(int i=s.size()-1;i>0;i--){if(s[i] == '0') cnt ++;else break;}cout<<cnt<<endl;
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;
//	cin>>T;while(T--) solve(); return 0;
} 

G - 简单题

题目链接：G-简单题_河南萌新联赛2025第（五）场：信息工程大学”

幸亏我会三阶行列式，将三阶行列式算出来之后就是1 1 2 3，相信一直刷算法的小伙伴对这个序列都不陌生吧，这不就是斐波那契数列吗？？！，然后通过打表找出斐波那契数列的和的奇偶性的变化是奇偶偶奇偶偶奇偶偶奇...所以我们只需要对n--，然后对3取模就行了。

// Problem: 简单题
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/115567/G
// Memory Limit: 2048 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
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
const int INF = 0x3f3f3f3f;
const int inf = 1e18; void solve()
{// int n;cin>>n;// int sum;n--;// sum = (1 + n) * n / 2;// sum ++;// cout<<sum % 2<<endl;// vector<int> a(20,0);// a[1] = 1;// a[2] = 1;// a[3] = 2;// for(int i=4;i<=17;i++) a[i] = a[i-1] + a[i-2];// for(int i=1;i<=17;i++) a[i] = a[i] + a[i-1];// for(int i=1;i<=17;i++) cout<<a[i] % 2<<endl;int n;cin>>n;if(n == 1){cout<<1<<endl;}else{n--;if(n % 3 == 0) cout<<1<<endl;else cout<<0<<endl;}//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;
//	cin>>T;while(T--) solve(); return 0;
} 

K - 狂飙追击

题目链接：K-狂飙追击_河南萌新联赛2025第（五）场：信息工程大学”

这道题唯一需要注意的就是题目中说的m是动态变化的，不是根据初始的位置而确定的（就是因为这个导致错了好几次），明白这里之后就很好想了，我们只需要用一个搜索都能出来，这里用BFS和DFS都可以，我下面就以DFS来举例子吧：

// Problem: 狂飙追击
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/115567/K
// 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
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
const int INF = 0x3f3f3f3f;
const int inf = 1e18; 
int endx,endy,dis = inf;
bool f = 0;
void dfs(int x,int y,int st)
{if(x > endx || y > endy) return ;if(x == endx && y == endy){f = 1;dis = min(dis,st);return ;}int m = max(x,y);int tx = x + m;int ty = y + m;dfs(tx,y,st + 1);dfs(x,ty,st + 1);
}
void solve()
{int a,b;cin>>a>>b>>endx>>endy;dfs(a,b,0);if(f) cout<<dis<<endl;else cout<<"-1"<<endl;
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;
//	cin>>T;while(T--) solve(); return 0;
} 

I - Re:从零开始的近世代数复习（easy）

题目链接：I-Re:从零开始的近世代数复习（easy）_河南萌新联赛2025第（五）场：信息工程大学”

这道题一开始看到节点之间有这依赖的顺序关系，以为这个是用拓扑排序写的，后来读完题之后发现是一个树形结构，所以这道题可以用倍增优化LCA来写！但是赛时改了好几次都错了，没办法只能在赛后补题了。

// Problem: Re:从零开始的近世代数复习（easy）
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/115567/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
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
const int INF = 0x3f3f3f3f;
const int inf = 1e18; 
const int N = 1e5 + 10;
vector<int> e[N],p[N];
int n,ans = 0;
vector<int> deep(N,0);
int fu[N][35],g[N][35];
void dfs(int x,int fa)
{deep[x] = deep[fa] + 1;fu[x][0] = fa;for(int i=1;i<=25;i++){fu[x][i] = fu[fu[x][i-1]][i-1];g[x][i] = g[fu[x][i-1]][i-1] + g[x][i-1];}for(auto &i : e[x]) dfs(i,x);
}
int LCA(int x,int y)
{if(deep[x] < deep[y]) swap(x,y);for(int i=25;i>=0;i--){if(deep[fu[x][i]] >= deep[y])ans += g[x][i],x = fu[x][i];}if(x == y) return x;for(int i=25;i>=0;i--){if(fu[x][i] != fu[y][i]){ans += g[x][i] + g[y][i];x = fu[x][i];y = fu[y][i];}}ans += g[x][0] + g[y][0];return fu[x][0];
}
void solve()
{int n;cin>>n;for(int i=1;i<=n;i++) cin>>g[i][0];for(int i=1;i<n;i++) {int u,v;cin>>u>>v;e[u].push_back(v);}dfs(1,0);int q;cin>>q;while(q--){int k;cin>>k;int x,y;cin>>x>>y;ans = g[1][0];int lca = LCA(x,y);if(lca != 1)LCA(lca,1);cout<<ans<<endl;}
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;
//	cin>>T;while(T--) solve(); return 0;
}