title : HNCPC Multi-university Training Round2
date : 2022-7-29
tags ：ACM,练习记录
author : LINNO
签到题，给定n个区间和k个点，问有多少个区间内有点。
排序然后二分查找所在区间就行了。
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
return 0;
}
比较板的图论缩点。要求输出所有强连通分量中编号最小的点，直接在tarjan过程中记录最小那个数即可。
#include
for(int i=1;i<=n;++i){
if(bel[i]==i&&!deg[i]){
vt.emplace_back(mi[i]);
}
}
sort(vt.begin(),vt.end());
for(int i=0;i<vt.size();++i) cout<<vt[i]<<"\n";
return 0;
}
队友做的，题目大致意思就是给你n*m的字符来表示一棵数作为表达式，然后让你计算结果。直接模拟即可，找下一行相邻两个运算符或数字连边也好做。
#include 你要送n个外卖，每次送完需要回到店里取货。给定每个顾客的外卖从店出发需要的用时t以及不满意系数a，每个顾客对总不满意度的贡献为 s i = a i ∗ ( h i + p i ) s_i=a_i*(h_i+p_i) si=ai∗(hi+pi),其中p为排在他前面送的顾客数，h为从0时刻起到送达的总时间，求一个送货方案使得总不满意度最少。
一眼看就是排序不等式，不过式子是队友推的。
#include 给定S个每个学生的力量a和身高h，规定团队的总战斗力为 ∑ i = 1 N A r i − ∑ i = 1 n − 1 ∣ H r i − H r i − 1 ∣ \sum_{i=1}^NA_{ri}-\sum_{i=1}^{n-1}|H_{ri}-H_{ri-1}| ∑i=1NAri−∑i=1n−1∣Hri−Hri−1∣
要求从S个挑出N个学生使得战斗力最大。
显然对挑出来的n个学生可以从高到低排一下序，那么总战斗力为 ∑ A i − h m a x + h m i n \sum A_i-h_{max}+h_{min} ∑Ai−hmax+hmin，因此对于确定最高和最矮的k个人来说，只用挑中间A最大的即可。那么在枚举过程中，我们确认了最矮的那个（起点），就可以去递推选k个人时的最大战斗力。 d p [ i ] [ j ] 表示前 i 个人选 j 能得到的最大战斗力 , 转移式见代码 dp[i][j]表示前i个人选j能得到的最大战斗力,转移式见代码 dp[i][j]表示前i个人选j能得到的最大战斗力,转移式见代码
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
return 0;
}
给定每个点的初始位置和在x轴,y轴方向的速度分量，问每个人被感染的最短时间。
这道题一样看去就最短路或者最小生成树，但是有点细节，因为我卡精度卡了一个晚上。（应该就是卡精）。我们把两个点能够相互感染的时间求出来，大概是一个一元二次方程，判一下有没有解，有的话可以连一条边，然后跑一下Prim就出来了。
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
}
}
signed main(){
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);0
// freopen("in.cpp","r",stdin);
// freopen("out.cpp","w",stdout);
int T=1;
// cin>>T;
// clock_t start,finish;
// start=clock();
while(T--){
Solve();
}
// finish=clock();
// cerr<<((double)finish-start)/CLOCKS_PER_SEC<
return 0;
}