NOIP/NOI – Tgotp-Blog

NOIP2017 题解

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

D1T1传送门

D1T2传送门

D1T3传送门

D2T1传送门

D2T2传送门

D2T3传送门

d1t1:math :

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

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

Read more

1064: [Noi2008]假面舞会

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

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

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

c++代码如下:
[crayon-5a[……]

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

P1034 矩形覆盖

被题意坑了,应该是该怎么做就怎么做

主要思路在于:因为分为k份,所以对应每个点一定会被分到某个集合内,所以枚举一下就好了。

然后再判一下交线交点,就搞定了,挺简单。

dfs回溯

c++代码如下:

&nbsp[……]

Read more

NOIP2013D2T1 积木大赛

贪心,比较巧妙。

也就是说,我们搭建一层,一定会将他延伸至他能延长的最长处。

所以,如果当前比前面的高的话,才需要单独去弄,不然一定会在之前的时候弄好。

具体见代码。

c++代码如下:

 

NOIP2014D2T3解方程

这题简单的不像话啊。。。

秦九昭算法一套,取个膜没了。

(其实应该要取多个膜。。。。)

但是洛谷a了,数据好弱啊。。。懒得改了,就这么写写。

至此NOIP2014搞定。。。

分数:

day1:100 + 70 + 45
day2:100 + 90 + 100[……]

Read more

NOIP2014D2T2 P2296 寻找道路

脑残少年理解错了一个地方100-10 = 90;

逆向连边然后稠密图筛一下跑最短路用迪杰斯特拉算法。没了。。。

智障筛的时候没区分。。。浪死了,剩下一道明天再做,今天玩游戏玩的有点晚233

目前分数405,刚刚到sc当年的一等线。。。惊惧

c++代码:
[crayon-5a[……]

Read more

NOIP2014t3P1941 飞扬的小鸟

第一次测 45 ,改了一个地方85。。。

然后满分是加一个完全背包优化。原本很简单,硬是被我一阵乱弄wa了一晚上,然后发现数组开爆了,蜜汁错误。

TAT

目前:NOIP2014 day1自测 100 + 70 + 45= 215

然而明明是可以 100 + 100 +85 =[……]

Read more