分数：100+100+100+100+0（100）+0（100）+0
T1~T4水题，不讲
T5：
1.观察到形如第一轮（1,2）（2,3），第二轮就会变成（1,3）
2.且答案全为零之后就不会再出现零，满足单调性
二分或倍增都可以，赛时用二分写写挂了（然后以为假了就没打了）
T6
观察到两条性质：
1.一盏灯，要么修到最高，要么不修
2.覆盖区间不会完全包含
根据这两点就可以设计转移方程dp[i]表示选到且选了i的最大面积
写一下DP柿子并化简，发现就是斜率优化板子题
出题人把斜率都给成单调递增了，甚至不用维护斜率的凸包~~~~
当然也可以用李（张）超线段树:
什么，你不会不知道李超线段树是啥吧（
#include
using namespace std;
const long long MAXN=1e5+10;
struct Point {
long long l,r;
long long w;
};
Point P[MAXN];
long long n,s[MAXN],smax[MAXN];
bool cmp(Point a,Point b) {
return a.r<b.r;
}
bool cmp2(Point a,long long b) {
return a.rlch) delete this->lch;
if(this->rch) delete this->rch;
}
Node(long long l,long long r):l(l),r(r),f(0,-1e18),lch(NULL),rch(NULL) {
if(l!=r) {
long long mid=(l+r)>>1;
this->lch=new Node(l,mid);
this->rch=new Node(mid+1,r);
}
}
long long Query(long long x) {
if(this->l==this->r)
return this->f(x);
else {
if(xlch->r)
return std::max(this->lch->Query(x),this->f(x));
else
return std::max(this->rch->Query(x),this->f(x));
}
}
void Insert(Line f) {
long long mid=(this->l+this->r)>>1;
if(f(mid)>this->f(mid)) swap(f,this->f);
long long ld=this->f(this->l)-f(this->l);
long long rd=this->f(this->r)-f(this->r);
if(ld>=0&&rd>=0) return;
else if(rd>=0) this->lch->Insert(f);
else this->rch->Insert(f);
}
};
int main() {
long long T;
scanf("%lld",&T);
while(T--) {
scanf("%lld",&n);
for(long long i=1; i<=n; i++) {
long long x,y,c;
scanf("%lld%lld%lld",&x,&y,&c);
P[i].l=x-y,P[i].r=x+y,s[i]=P[i].l;
P[i].w=4ll*y*y-4ll*c*y;
}
sort(P+1,P+n+1,cmp);
sort(s+1,s+n+1);
long long cnt=unique(s+1,s+n+1)-s-1;
Node* N=new Node(1,cnt);
for(long long i=1; iQuery(h)-1ll*P[i].l*P[i].l+P[i].w;
long long p=lower_bound(P+1,P+n+1,P[i].l,cmp2)-P-1;
dp=max(smax[p]+P[i].w,dp);
N->Insert(Line(2*P[i].r,dp-1ll*P[i].r*P[i].r));
smax[i]=max(smax[i-1],dp);
}
printf("%lld.%02lld\n",smax[n]>>2,(smax[n]&3)*25);
delete N;
}
return 0;
}
赛时推完柿子，发现大家都在摆烂，就没打了
T7
打过原，但事实证明就算打过也不会
但是……