暑期集訓已經接近尾聲，一年六場的暑期萌新聯賽也已經結束了，進步是比較明顯的，從一開始的七八百名到三四百名，雖然拿不出手，但是這也算對兩個月的集訓的算法初學者的我一個交代。
比賽傳送門：河南萌新聯賽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)
