静水流深,浮躁者难有成
Ta,线段树上二分
P4422 [COCI2017-2018#1] Deda
这道题有个非常精妙的思考点:正常思路应该是以站台为下标维护,但是这道题你观察一下发现他可以根据年龄维护的!!!
如果按照站台下标维护,你就需要在节点上快速二分,就要套set,log方了
类似的思路回顾:背包dp的时候观察数据范围不以体积为限制,以价值为限制,优化时空复杂度!
Tb,结论题
https://www.luogu.com.cn/problem/P8365
考试的时候根本没意识到
为什么?只能是思考不彻底。
对于一道题,大胆定义,列式,遇式化简看转移,巧妙构造模型,大胆发现简化的性质,都是必不可少的
譬如此题
ai==1显然必吃,剩下情况至多吃一个,why?
思考的时候:对于每两个食物进行考察
b1,b2,a1,a2
设b1>=b2
那么b1+b2<=a2*b1,每一个都是如此
接下来考虑吃哪一个,还是列式
记S=Σ,K=π
若吃i:(S-b[i])K/a[i]
若不吃:SK
一个对比完成,球最大的就行
思维题、推式题一定大胆啊!!!!!!
Tc:大分块,心细,不浮躁再想着去开
Td:思维题,但是你代码实现炸了!!!
特别常识:double很大,比longlong还大,不用开longlong!!!
对撞问题经典trick
观察数据范围直接得到要用Nk算法
从题解区获得了更为简单的实现
for(int i=1;i<=n;i++){
scanf("%d%d%s",&a,&b,op);
if(*op=='L'){//如果这个点向左
ans[b]+=(a-lst)/2.0;//它会代表他们颜色向左走,和最后一个向右走的做相遇
ans[md(b+fp)]+=a/2.0;//跟他走的那个向右的也要加
for(int j=0;j<k;j++) ans[md(j+b)]+=col[j];//它左侧的向右走的这种颜色的都会跟他变化成其他颜色,要加
}else{
ans[b]+=L-a;//向右走,直接走到底
rotate(col,col+k-b,col+k);//rotate学会了,旋转数组,第一个位置置为中间那个,他前面的那个位置是最后一个,这里旋转是因为后面的往前走都要加上这个数,类似后缀和,直接数组旋转就好了
col[b]+=(a-lst)/2.0;//跟他擦肩而过的会带着这种颜色走那么远,记录下
fp=md(fp+b);//更新第一个位置
lst=a;//更新上一个往右走的变色龙
}
}
over。敬祝goodluck。