这一周做了挺多场天题赛的，写题速度变快了，但是错误也更容易犯了，回顾学习了挺多知识。天体赛的模拟题很多，而且题目意思有时候很抽象，这时候就一定不能急着下笔，有大体思路再做，不然后面改太慢了。牛客训练营也结束了，感觉并不是很理想，在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;
}
