2025杭电多校第七场矩形框选伤害冷却比如何优化？

伤害冷却比 数学 题目 思路 令\(a=\frac{K}{N}\)，则有\(f(x)=x\left( \left\lfloor \frac{a}{x} \right\rfloor +1\right)\) 大致画出图像，可得下图 若要求区间\([L,R]\)上的最大值，则需要求出\(f(R)\)与红线蓝线交点值之间的最大值 为了求出交点，联立两个方程： \[\begin{align} x+a&=x\left( \left\lfloor \frac{a}{x} \right\rfloor +1 \right)\\ \\ x+a&=x\left\lfloor \frac{a}{x} \right\rfloor +x\\ \\ \frac{a}{x}&=\left\lfloor \frac{a}{x} \right\rfloor \\ \\ \exists \ n\in& Z\ , \frac{a}{x}=n\\ \\ \therefore x=\frac{a}{n}&,n=1,2,3,\dots \end{align} \] 因此可以找到距离\(R\)最近的\(x_{0}=\frac{a}{n}\)，其中\(n=\left\lceil \frac{a}{R} \right\rceil\) 再将此\(x_{0}\)带入\(y=x+a\)中，即可得到区间\([L,R]\)上交点的最大值啦 随后将\(R\)带入\(f(x)\)中，比较二者大小约分输出即可 代码实现 #include<iostream> #include<cstdio> #include<vector> #include<algorithm> #include<queue> #include<cmath> #include<unordered_map> #include<unordered_set> #include<string.h> using namespace std; using ll = long long; #define rep(i, a, b) for(ll i = (a); i <= (b); i ++) #define per(i, a, b) for(ll i = (a); i >= (b); i --) #define see(stl) for(auto&ele:stl)cout<<ele<<" "; cout<<'\n'; #define mid ((l+r)>>1) #define double long double #define int ll int gcd(int a,int b){ if(b==0)return a; return gcd(b,a%b); } void eachT(){ int K,N,A,B,C,D;cin>>K>>N>>A>>B>>C>>D; int n=ceil(1.0*(K*D)/(N*C)); double x=1.0*K/(N*n); double ans1=x+(1.0*K/N); double L=1.0*A/B; if(L>x)ans1=-1; double ans2=1.0*C/D*(K*D/(N*C)+1); if(ans1>=ans2){ int g=gcd(K*(1+n),N*n); cout<<K*(1+n)/g<<"/"<<N*n/g<<'\n'; }else{ int g=gcd(C*(K*D/(N*C)+1),D); cout<<C*(K*D/(N*C)+1)/g<<"/"<<D/g<<'\n'; } } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); int t=1; cin>>t; while(t--)eachT(); } 矩形框选 线段树 #扫描线 #二维数点 #差分 #区间最值 题目 思路 先讲一讲二维数点的一个常用技巧： 假设红框是当前的矩