wc2007疯狂赛车&wc2010重建计划

两道比较水的……题……
明天就要期末考了……
真的要裸考期末考了……真是感动啊……

疯狂赛车……这题很像bzoj另一道水题……scoi2010传送带
然后找一些显然的性质……就可以做了……
首先在沙地上走的路线一定是直线……
然后从一个赛道离开走到沙地然后走到另一条赛道这个路线……我们考虑两个在赛道上的端点……
可以调整得出可以有一个最优解满足一个点是赛道转折点
有了这个性质就好做了……
也就是转折的地方是有限的……然后我们对于一条线段和一个点,求出在这条线段的转折点就好了……
其实是可以O(1)求的……
但是我懒就写了三分……

然后三分姿势不对就tle了……

居然还有人写这种三分——fotile

原来的三分写法:

for(int cnt=1;cnt<=40;cnt++){
        double m1=l+(r-l)/3.0,m2=l+2.0*(r-l)/3.0;
        if(calc(m1)>calc(m2))
            l=m1;
        else r=m2;
}

新的姿势:

 for(int cnt=1;cnt<=25;cnt++){
        double m1=l+(r-l)*0.45,m2=l+(r-l)*0.55;
        if(calc(m1)>calc(m2))
            l=m1;
        else r=m2;
}

这样可以把三分次数减少……(虽然理论复杂度上界一样……)

就这样玩了一下常数之后就在bzoj上通过了……

然后bzoj评测姬速度略diao……我的代码自测总时间100s(开了O2)……在它上面只有22s……居然过了……
时间居然不是垫底……

然后重建计划就是道傻×点分治……套个二分就可以变成树上最长路了……
都没有啥写题解的必要(那你还写)

Comments

comments powered by Disqus