河南萌新联赛2025第六场 - 郑州大学

暑期集训已经接近尾声，一年六场的暑期萌新联赛也已经结束了，进步是比较明显的，从一开始的七八百名到三四百名，虽然拿不出手，但是这也算对两个月的集训的算法初学者的我一个交代。

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

整数商店的购物之旅

题目链接：L-整数商店的购物之旅_河南萌新联赛2025第（六）场：郑州大学

这道题是签到题（吧），很容易就能看出来是一道二分答案的题目，需要注意的是由于数据很大，那么我们就要转换为字符串，用字符串的大小来判断位数，不过我用log10一直WA不知道为啥。

// Problem: 整数商店的购物之旅
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/116216/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
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define lbt(x) ((x) & (-x)) const int INF = 0x3f3f3f3f;
const int inf = 1e18; 
int a,b,x;
bool check(int mid)
{int cnt = 0;string s = to_string(mid);int len = s.size();// int len = log10(mid) + 1;int res = a * mid + b * len;return res <= x;
}
void solve()
{cin>>a>>b>>x;if(x < a + b){cout<<"0"<<endl;return ;}int l = 1,r = 1e9;while(l < r){int mid = (l + r + 1) >> 1LL;if(check(mid)) l = mid;else r = mid - 1;}// cout<<min(1000000000LL,l)<<endl;cout<<l<<endl;
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;
//	cin>>T;while(T--) solve(); return 0;
} 

数字支配

题目链接：E-数字支配_河南萌新联赛2025第（六）场：郑州大学

这道题很明显是一道贪心的思维题，能输出9就尽量输出9即可。

// Problem: 数字支配
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/116216/E
// 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;
#define lbt(x) ((x) & (-x)) const int INF = 0x3f3f3f3f;
const int inf = 1e18; void solve()
{string s;cin>>s;int index = 0;for(int i=0;i<s.size();i++){index = i;if(s[i] == '9') cout<<s[i];else break;}// index++;if(index < s.size()-1) for(int i=index;i<s.size() - 1;i++) cout<<'9';else cout<<s[s.size() - 1];
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;
//	cin>>T;while(T--) solve(); return 0;
} 

外卖大战

紧跟时事，题目链接：I-外卖大战_河南萌新联赛2025第（六）场：郑州大学

比较大的一个模拟题，按照题目要求模拟即可，注意在选择当前平台之后后面的平台的未选次数就应该加加，然后每次加之后都进行是否达到三次的判断即可通过。

// Problem: 外卖大战
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/116216/I
// Memory Limit: 1024 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;
#define lbt(x) ((x) & (-x)) const int INF = 0x3f3f3f3f;
const int inf = 1e18; void solve()
{int n;cin>>n;vector<int> a(n+1);int mt = 0,elm = 0,jd = 0;int an1 = 0,an2 = 0,an3 = 0;int cnt1 = 0,cnt2 = 0,cnt3 = 0;for(int i=1;i<=n;i++) cin>>a[i];// sort(a.begin() + 1,a.end(),greater<int> ());// sort(a.begin() + 1,a.end());for(int i=1;i<=n;i++){for(int op=1;op<=3;op++){if(op == 1){// if(cnt1 >= 3) mt += 2,cnt1 -= 3;if(mt < a[i]) cnt1++;else {cnt1 = 0,mt ++,an1 ++;cnt2++,cnt3++;if(cnt2 >= 3) elm += 2,cnt2 -= 3;if(cnt3 >= 3) jd += 2,cnt3 -= 3;break;}if(cnt1 >= 3) mt += 2,cnt1 -= 3;}else if(op == 2){// if(cnt2 >= 3) elm += 2,cnt2 -= 3;if(elm < a[i]) cnt2++;else {cnt2 = 0,elm ++,an2 ++;cnt3++;if(cnt3 >= 3) jd += 2,cnt3 -= 3;break;}if(cnt2 >= 3) elm += 2,cnt2 -= 3;}else if(op == 3){// if(cnt3 >= 3) jd += 2,cnt3 -= 3;if(jd < a[i]) cnt3++;else {cnt3 = 0,jd ++,an3 ++;break;}if(cnt3 >= 3) jd += 2,cnt3 -= 3;}}// cout<<"美团:优惠"<<mt<<" 订单 "<<an1<<"未选"<<cnt1<<endl;// cout<<"饿了么:优惠"<<elm<<" 订单 "<<an2<<"未选"<<cnt2<<endl;// cout<<"京东:优惠"<<jd<<" 订单 "<<an3<<"未选"<<cnt3<<endl;}cout<<an1<<' '<<an2<<' '<<an3<<endl;
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;
//	cin>>T;while(T--) solve(); return 0;
} 

还在分糖果！

题目链接：K-还在分糖果！_河南萌新联赛2025第（六）场：郑州大学

这道题是几个月前的ICPC训练赛的原题（原题是求的9，这道题求的是7），因为那时候太懒了没有补题，导致今天被这道题卡了好久，幸好在比赛结束前通过了这道题。

打表之后不难发现规律：

• 第9个数为 10
• 第81个数为100
• 第729个数为1000
• .........
• 也就是说：第9 ^ i个数为10 ^ i ！

那么我们就可以用两个数组讲所对应的映射存起来，然后从大到小遍历，不断累加ans即可。

注意遍历到这一位如果这一位上大于等于7的话就需要++。

// Problem: 还在分糖果！
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/116216/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;
#define lbt(x) ((x) & (-x)) const int INF = 0x3f3f3f3f;
const int inf = 1e18; void solve()
{int f[14],s[14];int x = 1,y = 1;for(int i=1;i<=13;i++){x *= 9;y *= 10;f[i] = x;s[i] = y;}int n;cin>>n;int m = n;int ans = 0;for(int i=13;i>=0;i--){int x = f[i];int y = s[i];if(n >= x){if(n / x >= 7) {ans += pow(10,i);}ans += (n / x) * y;n %= x;}}if(n > 0){if(n >= 7) ans ++;ans += n;}cout<<ans<<endl;
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;cin>>T;while(T--) solve(); return 0;
} 

由于上一道题卡了好久，通过之后就没再开其他的题了，接下来就是：

穿过哈气之门

这道题的题目有点难读懂，实际上就是遍历整个给定的数组，判断有多少个子区间中包含了m种的物品，所以很明显这道题可以用滑动窗口来写，如果当前物品的种类数量小于m的话就一直不断地移动右指针，知道当前窗口中的物品种类数量等于了m，这时候以当前窗口为基础，包含这个窗口的后面的所有窗口都符合条件，所以直接让ans += (n - r + 1)，然后我们就可以滑动左指针，不断地用这个思想来更新累加ans即可。

// Problem: 穿过哈气之门
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/116216/D
// 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;
#define lbt(x) ((x) & (-x)) const int INF = 0x3f3f3f3f;
const int inf = 1e18; void solve()
{int n,m;cin>>n>>m;vector<int> a(n+1);for(int i=1;i<=n;i++) cin>>a[i];map<int,int> mp;int ans = 0;int l = 1,r = 0;while(r < n){while(mp.size() < m && r < n){r ++;mp[a[r]] ++;}if(mp.size() == m)ans += (n - r + 1);while(l < r && mp.size() == m){mp[a[l]] --;if(mp[a[l]] == 0) mp.erase(a[l]);l ++;if(mp.size() == m)ans += (n - r + 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;
} 

凹包

这是今天的重点！之前打的XCPC训练赛的时候出现过凸包类的题目，那时候感觉这个算法有点冷门就没有去学，今天就吃了懒的亏！所以今天就好好整理一下这道题。

首先和凸包相关的知识就是叉积：

我们用叉积来计算两个向量所组成的内角，对凸包来说，叉积为负数的点为凸顶点，即：

我们对输入的点进行排序，（当然这道题给出的点是有序）然后就是构建这个凸包，分为先构建下凸包再构建上凸包，然后判断凸包中的凸节点的数量是否等于n+1来进行判断是否是凸包，而这道题判断的是凹包，那么我们就只判断凸节点的数量是否小于等于n即可。

// Problem: 凹包
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/116216/J
// 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;
#define lbt(x) ((x) & (-x)) const int INF = 0x3f3f3f3f;
const int inf = 1e18; 
const int N = 2e5 + 10;
pii a[N];
bool cmp(pii x,pii y)
{return (x.fi != y.fi ? x.fi < y.fi : x.se < y.se);
}
double dis(pii a,pii b,pii c)
{return (b.fi - a.fi) * (c.se - a.se) - (b.se - a.se) * (c.fi - a.fi);
}
pii tu[N];
int top = 0;
void solve()
{int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i].fi>>a[i].se;if(n == 3){NOreturn ;}sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++){while(top > 1 && dis(tu[top],tu[top-1],a[i]) <= 0) top --;tu[++top] = a[i];}int t = top;for(int i=n-1;i>=1;i--){while(top > t && dis(tu[top],tu[top-1],a[i]) <= 0) top --;tu[++top] = a[i];}if(top <= n) YESelse		 NO
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;
//	cin>>T;while(T--) solve(); return 0;
} 

下面整理了一些有关凸包的模板，ICPCer可用：

#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);const double eps = 1e-8;  // 浮点数精度误差// 点结构体 - 简单版本，无运算符重载
struct Point {double x, y;
};// 比较函数：按x坐标排序，x相同按y排序
bool point_compare(Point a, Point b) {if (fabs(a.x - b.x) < eps)return a.y < b.y;return a.x < b.x;
}// 计算两点之间的距离
double point_dist(Point a, Point b) {double dx = a.x - b.x;double dy = a.y - b.y;return sqrt(dx * dx + dy * dy);
}// 计算向量叉积 (ab × ac)
// 返回值 > 0: c在ab左侧
// 返回值 < 0: c在ab右侧  
// 返回值 = 0: 三点共线
double point_cross(Point a, Point b, Point c) {return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}// Andrew算法求凸包
// 返回凸包上的点（逆时针顺序）
vector<Point> get_convex_hull(vector<Point> points) {int n = points.size();if (n <= 2) return points;  // 点太少直接返回// 按x坐标排序sort(points.begin(), points.end(), point_compare);vector<Point> hull(2 * n);  // 存储凸包点int top = 0;  // 凸包栈顶指针// 构建下凸壳for (int i = 0; i < n; i++) {// 当栈中至少有两个点，且新点使凸性不满足时，弹出栈顶点while (top >= 2 && point_cross(hull[top - 2], hull[top - 1], points[i]) <= 0) {top--;}hull[top++] = points[i];}// 构建上凸壳int lower_size = top;  // 下凸壳的大小for (int i = n - 2; i >= 0; i--) {while (top > lower_size && point_cross(hull[top - 2], hull[top - 1], points[i]) <= 0) {top--;}hull[top++] = points[i];}// 调整大小（去掉重复的起点）if (top > 1) {top--;  // 去掉重复的起点}hull.resize(top);return hull;
}// 计算多边形面积（凸包或任意多边形）
// 要求点按顺序给出（顺时针或逆时针）
double get_polygon_area(vector<Point> poly) {double area = 0;int n = poly.size();for (int i = 0; i < n; i++) {int j = (i + 1) % n;area += poly[i].x * poly[j].y - poly[j].x * poly[i].y;}return fabs(area) / 2.0;
}// 判断点是否在凸多边形内部或边界上
bool is_point_in_convex(Point p, vector<Point> convex) {int n = convex.size();// 检查点是否在凸包的每条边的左侧（或线上）for (int i = 0; i < n; i++) {int j = (i + 1) % n;if (point_cross(convex[i], convex[j], p) < -eps) {return false;  // 点在边的右侧，不在凸包内}}return true;
}// 旋转卡壳求凸包直径（最远点对距离）
double get_convex_diameter(vector<Point> convex) {int n = convex.size();if (n == 1) return 0;if (n == 2) return point_dist(convex[0], convex[1]);double max_dist = 0;int j = 1;  // 对跖点指针for (int i = 0; i < n; i++) {int next_i = (i + 1) % n;// 寻找对跖点：使得三角形面积最大的点while (point_cross(convex[i], convex[next_i], convex[(j + 1) % n]) > point_cross(convex[i], convex[next_i], convex[j])) {j = (j + 1) % n;}// 更新最大距离double dist1 = point_dist(convex[i], convex[j]);double dist2 = point_dist(convex[next_i], convex[j]);max_dist = max(max_dist, max(dist1, dist2));}return max_dist;
}// 计算凸包周长
double get_convex_perimeter(vector<Point> convex) {double perimeter = 0;int n = convex.size();for (int i = 0; i < n; i++) {int j = (i + 1) % n;perimeter += point_dist(convex[i], convex[j]);}return perimeter;
}void solve() {int n;cin >> n;vector<Point> points(n);for (int i = 0; i < n; i++) {cin >> points[i].x >> points[i].y;}// 求凸包vector<Point> convex = get_convex_hull(points);// 输出凸包信息cout << "凸包点数: " << convex.size() << endl;cout << "凸包面积: " << fixed << setprecision(2) << get_polygon_area(convex) << endl;cout << "凸包周长: " << fixed << setprecision(2) << get_convex_perimeter(convex) << endl;cout << "凸包直径: " << fixed << setprecision(2) << get_convex_diameter(convex) << endl;
}signed main() {IOSint T = 1;// cin >> T;while (T--) {solve();}return 0;
}

迷宫穿越

题目链接：F-迷宫穿越_河南萌新联赛2025第（六）场：郑州大学

这道题第一眼能看出来是BFS，但是难在有一个附加条件，那么我们可以用三维的标记数组来实现，狠狠学到了！用三维的标记数组来表示当前位置穿过了k个障碍的状态是否达到过。

// Problem: 迷宫穿越
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/116216/F
// Memory Limit: 1024 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;
#define lbt(x) ((x) & (-x)) 
const int N = 1005;
const int INF = 0x3f3f3f3f;
const int inf = 1e18; 
int n,m,K;
string mp[N];
struct node
{int dis,x,y,k;
};
int d[4][2] = {{-1, 0},{0, 1},{1, 0},{0, -1}};
void solve()
{cin>>n>>m>>K;string t;for(int i=1;i<=n;i++) cin>>t,mp[i] = "*" + t;bool v[n+1][m+1][15];memset(v,0,sizeof(v));int ans = inf;if(n == 1 && m == 1) ans = 0;// priority_queue<node,vector<node>,greater<npde>> q;queue<node> q;int startx = 1,starty = 1,endx = n,endy = m;v[startx][starty][0] = 1;q.push({0,1,1,0});while(q.size()){// node cur = q.top();q.pop();node cur = q.front();q.pop();int x = cur.x,y = cur.y,k = cur.k,dis = cur.dis;for(int i=0;i<4;i++){int tx = x + d[i][0],ty = y + d[i][1];if(tx < 1 || ty < 1 || tx > n || ty > m) continue;int tk = (mp[tx][ty] == '#' ? k + 1 : k);if(v[tx][ty][tk] || tk > K) continue; q.push({dis+1,tx,ty,tk});v[tx][ty][tk] = 1;if(tx == n && ty == m) ans = min(ans,dis + 1);}}if(ans == inf) cout<<"-1"<<endl;else 		   cout<<ans<<endl;
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;
//	cin>>T;while(T--) solve(); return 0;
} 

下面是关于在网格图中使用Dijkstra求最短路问题的时候途中可以使用k次魔法等等有限制类问题的情况模板：

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;// 状态结构体：表示当前位置、已使用的特殊次数、到起点的距离
struct State {int x;          // 当前x坐标（从1开始）int y;          // 当前y坐标（从1开始）int use;        // 已使用特殊操作的次数（如破墙、使用道具等）int dist;       // 从起点到当前位置的距离// 重载小于号，使优先队列成为小根堆（距离小的优先出队）bool operator<(const State& other) const {return dist > other.dist;}
};// 全局常量定义
const int MAX_N = 1005;          // 最大行数
const int MAX_M = 1005;          // 最大列数
const int MAX_USE = 15;          // 最大特殊操作次数（根据题目调整）
const int INF = 0x3f3f3f3f;      // 表示无穷大距离// 全局变量（根据题目需求调整）
int n, m, max_use;               // 网格大小、最大允许的特殊操作次数
string grid[MAX_N];              // 存储网格地图
int dir[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};  // 四个方向（上、下、左、右）
int dist[MAX_N][MAX_M][MAX_USE]; // 距离数组：dist[x][y][k]表示用k次特殊操作到(x,y)的最短距离/*** Dijkstra算法求解最短路径* @param start_x 起点x坐标（从1开始）* @param start_y 起点y坐标（从1开始）* @param end_x 终点x坐标（从1开始）* @param end_y 终点y坐标（从1开始）* @return 最短距离，无法到达返回-1*/
int dijkstra(int start_x, int start_y, int end_x, int end_y) {// 1. 初始化距离数组为无穷大memset(dist, 0x3f, sizeof(dist));// 起点初始状态：距离0，使用0次特殊操作dist[start_x][start_y][0] = 0;// 2. 优先队列（小根堆），存储状态priority_queue<State> pq;pq.push({start_x, start_y, 0, 0});// 3. 算法主循环while (!pq.empty()) {// 取出当前距离最短的状态State cur = pq.top();pq.pop();// 若到达终点，直接返回当前距离（Dijkstra保证此时为最短距离）if (cur.x == end_x && cur.y == end_y) {return cur.dist;}// 若当前状态的距离大于已知最短距离，说明已被处理过，直接跳过if (cur.dist > dist[cur.x][cur.y][cur.use]) {continue;}// 探索四个方向的移动for (int i = 0; i < 4; i++) {// 计算新坐标int nx = cur.x + dir[i][0];int ny = cur.y + dir[i][1];// 边界检查：确保新坐标在网格范围内if (nx < 1 || nx > n || ny < 1 || ny > m) {continue;}// 4. 判断是否需要使用特殊操作（根据题目调整条件）// 这里以"网格中的障碍物需要使用特殊操作"为例int new_use = cur.use;if (grid[nx-1][ny-1] == '#') {  // 注意：网格存储是0-basednew_use++;  // 遇到障碍物，特殊操作次数+1}// 检查特殊操作次数是否超过限制if (new_use > max_use) {continue;}// 计算新距离（每次移动距离+1，可根据题目调整）int new_dist = cur.dist + 1;// 若新路径更优，则更新距离并加入队列if (new_dist < dist[nx][ny][new_use]) {dist[nx][ny][new_use] = new_dist;pq.push({nx, ny, new_use, new_dist});}}}// 若队列空了仍未到达终点，说明无法到达return -1;
}int main() {// 输入优化ios::sync_with_stdio(false);cin.tie(0);// 读取输入（根据题目调整）cin >> n >> m >> max_use;for (int i = 0; i < n; i++) {cin >> grid[i];  // 读取网格，0-based存储}// 特殊情况：起点即终点if (n == 1 && m == 1) {cout << 0 << endl;return 0;}// 调用Dijkstra算法，起点(1,1)，终点(n,m)int result = dijkstra(1, 1, n, m);cout << result << endl;return 0;
}