NOIP/NOI – Tgotp-Blog

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++代码如下:

 

3670: [Noi2014]动物园

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

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

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

注意卡常

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

Read more

4945: [Noi2017]游戏

观察d的数据范围为8
然后考虑暴力枚举x的取值…
一开始我暴力令x = ‘a’ ,’b’,’c’则为3^n
但是发现其实因为最后每个位置只用一个取值,那么只要保证x能取’A’ ‘B’ ‘C’即可。
也就是x = ‘a’ ,’b’, 复杂度2^n
接下来容易发现是个2-sat问题…
建边以[......]

Read more

1061: [Noi2008]志愿者招募

万年没更新的blog 终于更新一篇了。。。

看完题首先就会想到费用流,

重点是建图,发现可以把第i个位置看成第i天需要的减去第i-1天所需要的,那么如果这个值>=0就从s连过来,否则连向t。

把第i类人从u 连向 v+1即可。

最后跑费用流

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

Read more

1497: [NOI2006]最大获利

差点连网络流都写炸了。

看到这题容易想到最大闭合子权图,考虑建图。

从源点连向i一个流量为p[i]的边,

有一个边的时候,新建一个点,由两个端点连向这个点一个无限流量的边,这个点再连向汇点一个流量为价值的边,搞定。

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

Read more

NOIP2017 题解

终于开始在晚自习的时候填填noip的坑了。

D1T1传送门

D1T2传送门

D1T3传送门

D2T1传送门

D2T2传送门

D2T3传送门

d1t1:math :

推规律(找规律),a*b-a-b;

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

Read more

1064: [Noi2008]假面舞会

对于每个人看到的人,把他看到的连向自己一条-1的边,对看到的人连一条1的边

然后跑dfs,可以发现,会构成链和环两种形式,环的话所有可能性是其的因子,那么多个环最大值就是最大公约数,

链的话直接拼接在一起就搞定了(可以加并查集优化。。。)。

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

Read more