NOIP/NOI – 第4页 – Tgotp-Blog

聪明的质监员 NOIP2011

二分答案,sum[i]表示前i个中符合>=x的个数,num[i]表示前i个中这些符合的v之和;剩下的直接二分搞搞就好了。原谅sum与num的英语意义乱用2333.

 

NOIP T4 跳石头 P2678

应zny的要求,写一篇二分的入门教程。

所谓二分答案,通俗的理解(我也只会通俗的理解)就是说,我们假定已经找出一个答案 ans,然后对这个假设进行判定,看他是否满足条件,

比如这道题,我们假设最大值为ans,那么任意两个石子间的距离均 >= ans ,所以当我们查询到两个石子间的距[......]

Read more

运输计划BZOJ4326 && P2680 && noip2015T6

算法:tarjan + 二分

思路:先找lca,可以在dfs的时候就用tarjan直接算出,然后找出s -> t的路程,即 q[i].dis = deep[q[i].from] + deep[q[i].to] - 2* deep[q[i].lca];

继续进行二分,对于路程大于假定[......]

Read more

NOIP2015 P2679 子串

动态规划,原谅我学的渣,只能边看题解边做。

用 f[j][p] 数组表示到 s2 的分割了p次的情况(上一次到当前没分,所以匹配到s [i]!=s[j]时,要清零)。

用dp[j][p]数组表示到s2的分割了p次的情况(这次结尾断开)。

小细节,j 从后往前匹配,为了避免冲突(免去[......]

Read more

[NOI2005]维护数列

Splay

NOI2009植物大战僵尸

最大闭合子全图。

注意判环就好了。

NOIP2016T2

号称noip2016最难的题。搜索+lca。

具体实践看代码。

NOIP2016T4

会点组合数知识就可以过了,记忆化搜索。

NOIP2016T1

纯暴力模拟,没啥说的。

NOIP2016T5