文远的笔试是26号早八到晚九之间随便选俩小时笔试就行,用的是牛客oj.

不让泄题,那就透露一下做法...

俩小时笔试,笔者做完还剩半个小时,可还行...

T1

首先有一个很容易想到的O(n^3)区间dp做法,交了过60%.

然后发现这个区间覆盖问题可以转化为图论找最短路,写了一个O(n^2logn)的做法,交了过80%.

然后不会了,尝试玄学优化,限制加边的数量,在WA和TLE之间徘徊几发之后过了.

后续问AI都说是斜率优化,吓哭了(笔者不会斜率优化).

T2

很简单的贪心题,没想到签到居然在T2.

T3

LCA板子题.经典结论: 设树上uv路径上所有点的权值和为 f(u,v) ,那么 f(u,v)=f(u,root)+f(v,root)-2*f(lca(u,v),root)+val(lca(u,v))

PS:牛客OJ的一个小技巧

有缘人,都看到这里了,笔者分享一个可以用在牛客oj上的小技巧...

牛客OJ虽然测试数据是不公开的,但可以使用assert判断数据,从而套取部分数据,比如用于判断边界情况...

似乎有的OJ对assert支持的不是很好,比如牛客会assert(false)后直接告诉你这行假了,隔壁PTA据说已经有通过assert套数据的脚本了www

隔壁阿里笔试更逆天,编程题也是T1最难,而且三个编程做不完上一个不能看下一个...