UOJ#132 小园丁与老司机
BZOJ2957

POI21填坑计划

HJWJBSR posted @ 2015年12月20日 16:59 in 题解 , 630 阅读

[Upd 12.24]:因为校内集训先坑在这里好了。。感觉剩下的题目好难啃。。

开新坑辣!先口胡一波再写好了。。

现在完成了:

15

[Couriers]:无脑主席树,当然也可以莫队

[Hotel]:无脑DP+乱搞。

[Salad Bar]:O(n log n)的感觉比较无脑。。不知道有没有O(n)的。。

[Around the world]:每次询问任意固定一个起点,然后O(n)求出每个点往左往右走到这个起点的步数和最后一步的距离,最后再看最后一步的距离能否两步缩成一步。O(nm)

[Bricks]:差不多大于1/2就不能放?感觉好想好证好构造。因为固定首尾所以多判几种情况乱搞搞就好了?

[Card]:拿棵线段树随便维护一下就好?反正一段区间只会有四种情况

[FarmCraft]:树形DP+SB贪心?

[Little Bird]:首先一段区间所包含的劳累值肯定是连续的。然后就每个值按高度维护一个单调队列以及维护一下这段区间内的劳累值区间左右端点。然后每次删除一个点就只要在单调队列里面删除。算当前劳累值就只要从最小劳累值和次小劳累值转移就好了。

[Solar Panels]:分成两种情况,第一种答案小于sqrt(1e9),直接枚举判断就好。第二种n/gcd或者m/gcd小于sqrt(1e9),那么设n/gcd=k,则gcd肯定等于[maxn/k],然后按照m范围判断即可。因为不一定是n碰到上界所以m再来一遍即可。(因为两个都没有碰到上界的话gcd是可以加一的)复杂度O(sqrt(1e9)*t)

按照BZOJ上面的AC人数,貌似水题全都写完了。。好虚啊。。

[Solar Lamps]:把一个角度放大CF有一个题也用到过,其它部分直接上个树套树就好了?特判掉范围是一条线的情况就好。

[Rally]:之前想了一个做法发现是在瞎BB。堆+拓扑排序。。主要是一直在怎么找必经点而不是在维护答案上面想所以并不会做,而且答案是维护的一个割集的而不是维护整张图。智商是硬伤。。

[SuperComputer]:还是不会。。听说ans=max(i+[sum[i]/k])= =证明在这里。虽然想过类似结论但是还是没想到这个东西= =太弱= =。然后就可以斜率优化了。

[Criminals]:之前一直看漏了一个条件发现是神题不会做= =后来发现直接扫一遍求出每个点往两个方向的最短可以匹配的序列是在哪个位置就好了。。

[Ant colony]:之前一直没看懂题。。原来是每个叶子节点都会有。。只要处理出每个叶子节点的被除数是多少然后对询问还有这东西排序扫一遍就好了。。

[Freight]:找到一个并没很大用的性质,往那方面想了一个从后往前的贪心,但是明显前面的发车状态会对后面的贪心策略造成影响,于是还没写就弃疗了。后来找到另外一个比较显然的性质就是如果当前在回程的话就应该把所有在T的点全部回到S。因为这样最多会把后面的车推迟s分钟。但是如果这s辆车扣在这里等最后才放的话也要推迟s分钟。于是肯定是如果放车就都放掉比较好。于是可以设t[i]代表第i辆车作为那次回程的最后一辆车回到S的时间是多少。则我们从j<i转移。分两种情况:t[j]+i-j-1<=T[i]或者大于。首先t[j]肯定是单调递增的所以t[j]-j肯定单调不减,并且分界线肯定也是单调不减的。第一种情况t[i]=min(T[i]+s*2+i-j-1),直接取最后一个即可。第二种情况t[i]=min(t[j]+(i-j-1+s)*2),所以维护一棵线段树查询区间最小值即可。至于时间重合的情况直接预处理T[i]=max(T[i],T[i-1]+1)

[Snake]:感觉像是某种神奇的大讨论。。不会啊。。

[Tourism]:跪Claris神脑洞。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter