暑期集训已经接近尾声，一年六场的暑期萌新联赛也已经结束了，进步是比较明显的，从一开始的七八百名到三四百名，虽然拿不出手，但是这也算对两个月的集训的算法初学者的我一个交代。
比赛传送门：河南萌新联赛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;
}
 -- 网卡队列)
之加载Mapper)
