寒假第三周周报

        这一周做了挺多场天题赛的，写题速度变快了，但是错误也更容易犯了，回顾学习了挺多知识。天体赛的模拟题很多，而且题目意思有时候很抽象，这时候就一定不能急着下笔，有大体思路再做，不然后面改太慢了。牛客训练营也结束了，感觉并不是很理想，在23级的同学中排到靠后了。还是需要再努力一点。下周蓝桥杯训练就要开始，这周我也终于把驾照给拿到手了，寒假还有一段时间才结束，继续加油，不要懈怠下来。

题目：Multi-Subject Competition（贪心、前缀和

Problem - C - Codeforces

这题目意思是有m个项目，n个人有会的项目和技术水平，从m个项目中选取任意个项目，选取的项目要满足条件，选取的项目都是相同的参与人数。求怎么样选取技术水平最大。

解析：

这题目的描述我赛时理解的很差，这其实就是一个变换了一点的前缀和加贪心的问题，赛时脑子糊涂想复杂，其实就先把每个人的项目和他的能力记录下来，在项目中按非递减排序。然后再开一个前缀和数组，求如果选i个人参加该项目选法（如果技术值小于0，在大于等于i个人之后都不选该项目）最后排序求出最大的技术水平。

代码： #include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define pdd pair<double,double> #define ull unsigned long long #define endl '\n' const int N=1e5+7; const int M=2e5+7; const int mod=1e9+7; const double pi=3.1415926535; vector<int> a[N]; int d[N]; void solve() { int n,m; cin>>n>>m; for (int i=0;i<n;i++) { int x,y; cin>>x>>y; a[x].push_back(y); } for (int i=1;i<=m;i++) { if (!a[i].empty()) sort(a[i].begin(),a[i].end(),greater<int>());//每个项目从大的开始选。 } vector<int> v(n+1,0);//选i个人的情况下的最优 for (int i=1;i<=m;i++) { int res=0; int len=a[i].size(); for (int j=0;j<len;j++) { res+=a[i][j]; if (res<0) break;//如果该项目选当前的人数小于0就不需要选该项目了 v[j+1]+=res; } } sort(v.begin(),v.end(),greater<int>()); cout<<v[0]<<endl; } signed main(){ ios::sync_with_stdio(false);std::cin.tie(0);cout.tie(0); int T=1; //cin>>T; while(T--){ solve(); } return 0; } 题目：D. Maximum Diameter Graph（构造图

Problem - D - Codeforces

解析：

本题可以先将大于等于2的度的点（假设有k个）相连接（尽量连成一条直线）存边，等于1的点只能做最边上的点，然后再处理等于1的点，连接在度数大于0的点上，存边，如果最后将所有点连完那么就可以构成图，图的直径就是k+p-1，p就是看度大于等于2左右是否还能再加度为1的边；

代码： #include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define pdd pair<double,double> #define ull unsigned long long #define endl '\n' const int N=1e6+7; const int M=2e5+7; const int mod=1e9+7; const double pi=3.1415926535; bool cmp(pii x,pii y) { return x.first>y.first; } void solve() { int n; cin>>n; vector<pii> a; for (int i=1;i<=n;i++) { int x; cin>>x; a.push_back({x,i}); } sort(a.begin(),a.end(),cmp); vector<pii> v; int pr=a[0].second; int len=a.size(); int xb=-1; for (int i=1;i<len;i++) { int x=a[i].first,y=a[i].second; a[i].first--; v.push_back({pr,y}); pr=y; a[i-1].first--; xb=i+1; if (x==1) { break; } } if (xb==-1) { cout<<"NO"<<endl; return; } int l=xb; int lg=0; for (int i=0;i<xb;i++) { int y=a[i].second; while (l<len&&a[i].first>0) { lg=1; a[i].first--; a[l].first--; v.push_back({y,a[l].second}); l++; } } if (l<n) { cout<<"NO"<<endl; } else { cout<<"YES"<<" "<<xb+lg-1<<endl; cout<<v.size()<<endl; for (auto [x,y]: v) { cout<<x<<" "<<y<<endl; } } } signed main(){ ios::sync_with_stdio(false);std::cin.tie(0);cout.tie(0); int T=1; //cin>>T; while(T--){ solve(); } return 0; } 题目：铁刀磨成针

J-铁刀磨成针_2025牛客寒假算法基础集训营6

题意是给你一把攻击力为x,n个回合，并且你还有y个磨刀石每次磨刀增加一点体力，每个回合都可以顺序进行磨刀，和攻击（攻击伤害是刀的攻击力），攻击之后会使刀的攻击力-1。求最大造成伤害。

解析：

这道题可以看出，把刀磨好再砍是最优的，问题是什么时候开始砍，这时候看数据T组y<=1e3,这样复杂度是1e7。开始砍了之后还有两种情况，第一种就是还有磨刀石（每回合边磨边砍），第二种是没有磨刀石了，每次砍完攻击力就会减1.（这是造成了多少攻击就是等差数列了），长度是多少呢？要么到攻击力变为1，要么到回合回合结束，这两种情况下取一个最小值。这道题赛时没写出来，是因为我一直在想分类讨论，没想到挨个枚举开始砍，下次要注意给的数据。

代码： #include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define pdd pair<double,double> #define ull unsigned long long #define endl '\n' const int N=1e5+7; const int M=2e5+7; const int mod=1e9+7; const double pi=3.1415926535; int qh(int a1,int an) { int sum=0; sum=(2*a1-an+1)*an/2; return sum; } void solve() { int n,x,y; cin>>n>>x>>y; int mi=min(y,n);//最多磨mi刀 int ans=0; for (int i=1;i<=mi;i++) {//第i天开始砍 int k=x+i; int res=0; int an=min(k,n-mi+1); res+=(mi-i)*k; res+=qh(k,an);//没有磨刀石伤害每天减1； ans=max(ans,res); } cout<<ans<<endl; } signed main(){ ios::sync_with_stdio(false);std::cin.tie(0);cout.tie(0); int T=1; cin>>T; while(T--){ solve(); } return 0; } 题目：好伙计猜拳(dp)

B-好伙计猜拳_2025牛客寒假算法基础集训营6

解析：

一个合法序列需要满足的要求其实就是 ai≥ai−1,bi≥bi−1，因此这很像最长上升子序列，最长上升子序列的状态定义是 dp[x] 表示以 x 处的数字结尾的最长上升子序列的长度.这里不同的就是有个交换操作。具体见代码。

代码： #include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define pdd pair<double,double> #define ull unsigned long long #define endl '\n' const int N=1e3+7; const int M=2e5+7; const int mod=1e9+7; const double pi=3.1415926535; void solve() { int n, c1, c2; cin >> n >> c1 >> c2; vector<vector<int>> dp(n + 1, vector<int>(2, 1e14)); dp[0][0] = 0; vector<pair<int, int>> a(n + 1); for(int i=1;i<=n;i++) cin >> a[i].first >> a[i].second; int ans = 1e14; for(int i=1;i<=n;i++) { for(int j=i-1;j>=0;j--) { if(a[i].first >= a[j].first && a[i].second >= a[j].second) { dp[i][0] = min(dp[i][0], dp[j][0] + (i - j - 1) * c1); } if(a[i].first >= a[j].second && a[i].second >= a[j].first) { dp[i][0] = min(dp[i][0], dp[j][1] +(i - j - 1) * c1); } if(a[i].second >= a[j].first && a[i].first >= a[j].second) { dp[i][1] = min(dp[i][1], c2 + dp[j][0] + (i - j - 1) * c1); } if(a[i].second >= a[j].second && a[i].first >= a[j].first) { dp[i][1] = min(dp[i][1], c2 + dp[j][1] + (i - j - 1) * c1); } } ans = min(ans, min(dp[i][0], dp[i][1]) + (n - i) * c1); } cout << ans << '\n'; } signed main(){ ios::sync_with_stdio(false);std::cin.tie(0);cout.tie(0); int T=1; cin>>T; while(T--){ solve(); } return 0; } 题目：L2-2 病毒溯源

解析：

Edge[i]中保存第i种病毒可能产生的变异病毒编号，in[i]中保存编号i的入度，入度为零的病毒为源头病毒，pa[i]中保存病毒由哪种病毒变异而来（上级病毒）。为了保证序列最小，在输入Edge[i]后可对其进行一次排序～然后通过BFS找到变异次数，过程中由Long和ans标记最多变异次数量以及对应的病毒编号，最后通过pa找回完整变异链

代码： #include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define pdd pair<double,double> #define ull unsigned long long #define endl '\n' const int N=1e4+7; const int M=1e4+7; const int mod=1e9+7; const double pi=3.1415926535; int n, k, t, S, Long = 0, ans, in[10005], pa[10005]; vector<int> F, Edge[10005]; queue<pii> Q; void solve() { cin >> n; for (int i = 0; i < n; i++) { cin >> k; for (int j = 0; j < k; j++) { cin >> t; in[t]++; pa[t] = i; Edge[i].push_back(t); } sort(Edge[i].begin(), Edge[i].end()); } for (int i = 0; i < n; i++) if (in[i] == 0) S = i; while(!Q.empty()) Q.pop(); Q.push({S, 1}); while (!Q.empty()) { int now = Q.front().first, D = Q.front().second; Q.pop(); if (D > Long) { Long = D; ans = now; } for (auto nex : Edge[now]) Q.push({nex, D + 1}); } cout << Long << '\n'; while (ans != S) { F.push_back(ans); ans = pa[ans]; } F.push_back(S); for (int i = F.size() - 1; ~i; --i) { cout << F[i]; if (i != 0) cout << ' '; } } signed main(){ ios::sync_with_stdio(false);std::cin.tie(0);cout.tie(0); int T=1; //cin>>T; while(T--){ solve(); } return 0; } 题目：C. Li Hua and Chess（交互题

Problem - C - Codeforces

解析：

我们发现，每次询问（1，1）一般情况下会得到列坐标或者横坐标为p=d+1，这时就需要判断是列还是横，这时我们再查询（1，p）和（p，1），如果相等就既是列，又是横。如果该点到（1，p）等于d，那么横坐标就是p，纵坐标就为该点到（p，1）的位置。反之一样。注意交互题需要的一些语句，不然会报错。

代码： #include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define pdd pair<double,double> #define ull unsigned long long #define endl '\n' const int N=1e6+7; const int M=2e5+7; const int mod=1e9+7; const double pi=3.1415926535; int ask(int x,int y) { cout<<"? "<<x<<" "<<y<<endl; cout.flush(); int d; cin>>d; return d; } void get(int x,int y) { cout<<"! "<<x<<" "<<y<<endl; cout.flush(); } void solve() { int n,m; cin>>n>>m; int d=ask(1,1); int p=d+1; if (d>=n) { int x=ask(1,p)+1; get(x,p); } else if (d>=m) {//超过了列，p就是横 int y=ask(p,1)+1; get(p,y); } else { int a,b; a=ask(p,1); b=ask(1,p); if (a==b&&a==d) { get(p,p); } else if (b==d) { get(p,a+1); } else { get(b+1,p); } } } signed main(){ ios::sync_with_stdio(false);std::cin.tie(0);cout.tie(0); int T=1; cin>>T; while(T--){ solve(); } return 0; }