NOIP/NOI – Tgotp-Blog

4653: [Noi2016]区间

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

c++代码如下:

 

3670: [Noi2014]动物园

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

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

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

注意卡常

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

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-5b0837779f20[......]

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

NOIP2011 P1311 选择客栈

直接dp搞搞,似乎做的麻烦了一点。。

c++代码如下:

更新后的代码如下:

如果符合要求的酒吧位置 >= last[x] ,就可以更新新的值

不然的话对于某个颜色就一直加上之前他有多少个酒店。
[cray[......]

Read more

2017年9月21日 0 / /
Tag:  No Tags

NOIP2012 开车旅行

好难呀。。。

花了一早上来肝这道题,我认为真心不好做。

首先思路是倍增:

令F[I][J]表示以I出发2^J个点所到达的点

令A[I][J]表示以I出发2^J个点a所行驶的距离

令B[I][J]表示以I出发2^J个点b所行驶的距离

首先,你需要找到n个点距离他最近的点与次近的点。

显而[......]

Read more

加分二叉树

洛谷没有spj,有点坑啊,当成最小字典序输出吧...

首先中序遍历代表对于一个数x,其序列左边是它的左子树,右边是它的右子树

f[i][j]代表i - j区间内最大值,node[i][j] 代表i - j 内区间最大值时的根节点...

搞定.

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

Read more