NOIP/NOI – Tgotp-Blog

3572: [Hnoi2014]世界树

虚树经典题目

对于每次查询建立虚树,然后在树上dfs找出每个点最近的标记点。

然后考虑不在虚树上的点,如果是两点之间的点,看两点的从属,不一样就倍增找分界点

还有一些点和虚树上一个点下面,这种直接从属这个点就好了。

这题说来简单,就是调起来比较麻烦。

c++代码如下:[......]

Read more

1495: [NOI2006]网络收费

观察到层数最多只有10,那么状压层数,
发现对于第i层,若是设为na <nb,那么在子树遍历的时候,以当前层为lca的点为a时能产生价值,反之同理。
令f[i][j]表示第i个点,下面有j个a点,以及记录当前层包含区间[L,R],那么对于na < nb时只能更新[L,mid]反之只能[......]

Read more

1502: [NOI2005]月下柠檬树

容易发现一个平行平面的投影是不会变的,

一个圆柱的投影是两个面的投影+这两个圆的外切线所构成的图形

求出所有外切线再用simpson积分搞搞就行了。

至于求外切线的方法自己推一推,具体见代码。

注意这题是不能删去被包含的圆。

(这代码一开始以为会t,结果竟然过了[......]

Read more

4199: [Noi2015]品酒大会

竟然一遍ac了...万万没想到...

容易想到先求出SA,在hight数组上乱搞即可。。。

那么算某一个r就是区间min>=r的连续一段的组合之和。

考虑算多个r,因为大r肯定包含小r,那么算出了大r最后加到小r即可。

考虑这样怎么算,用单调栈维护一下即可,但是要注意在[......]

Read more

2535: [Noi2010]Plane 航空管制2

第一问一遍拓扑排序就行了,

第二问不塞求得那个即可。

c++代码如下:

 

NOID1T归程

时隔一个月左右更新一下博客...

看到这题很容易想到反向SPFA,然后可持久并查集搞搞啥的。

(离线那分显然是送的。。。

但是该题会卡SPFA(貌似),且可持久化并查集我的时间复杂O(n log^2 n)

所以光荣的只拿了60分滚粗qaq...

上面算法又臭又难[......]

Read more

4653: [Noi2016]区间

水题,离散化一波然后线段树。

c++代码如下:

 

4652: [Noi2016]循环之美

https://www.cnblogs.com/clrs97/p/5731321.html

c++代码如下:

 

3670: [Noi2014]动物园

仔细看完题以后,发现肯定和kmp有关,先搞出 next 数组

然后发现答案就是某一个next <i/2时的值

但是这个样子的话极限情况时n^2,发现瓶颈在于找next,然后考虑倍增一下就出来了.

注意卡常

c++代码如下:
[crayon-5bf096aab04fa9[......]

Read more

2434: [Noi2011]阿狸的打字机

首先容易根据给出的字符串建出trie树

对于查询(x,y),相当于对于y的每一个位置求出他的后缀是否包含x串

那么容易想到建立出ac自动机。

那么就是对于y串的每个位置,其能否通过fail到达x所在节点。

发现其实fail指针会构成一棵树,那么相当于统计在x节点下有多少点属于[......]

Read more