POI18填坑计划
51nod 部分题解

POI20填坑计划

HJWJBSR posted @ 2016年2月03日 13:23 in 题解 , 536 阅读

感觉是至今推过的最神的一届。。而且还有交互题简直厉害。。

惯例先口胡:

[ByteComputer]:一眼DP

[Tower Defense Game]:直接随便删就好。为了保证复杂度标记哪些点是所连的所有点都被删除的

[Polarization]:详见15年论文“启发式思想”。知道了结论之后就直接背包就好。多重背包我用了倍增+bitset。虽然带个log但是跑的飞起。贪心搞法好神啊。

[Take-out]:直接维护一个栈然后如果最后k+1个可以删除就删除。合法性显然。最后也肯定不会有剩余,这个也可以证明。

[Tales of seafaring]:直接每个点为起点BFS一遍就好

[Taxis]:写个式子很容易发现出租车在左边的时候明显先放大的车更优。于是只要分两种情况:要留一个刚好大于等于右边距离的车和不要留取个答案最大值就好。

[Triumphal arch]:一眼二分答案+树形DP

[Multidrink]:很明显一棵子树只能跳进去一次。然后我觉得树形DP+分类讨论就好。但是分类讨论好麻烦的样子不知道还有没有更加优美的姿势啊。

[Inspector]:二分答案显然,然后我觉得应该就差分搞搞,然后贪心一下就好?Tn log n的

[Walk]:只会在每个点搜一下连通块,然后调下阀值什么的能不能过啊?好虚啊。

[Tapestries]:JB几何题直接弃疗了

[Maze]:这题海瑞斯特说他一眼秒!感觉其实也就是拿个栈维护一下哪些东西可以被提出来,比如LR、RL之类的东西。

[Colorful Chain]:水题。。

[Laser]:波兰文不能看

[Watering can]:水题。。每次删除就好。。

[Watering can]:有点意义不明。。不知道那个M(n)到底是干什么的。。


登录 *


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