1 Deep_Kevin

尚未进行身份认证

暂无相关描述

等级
博文 292
排名 2w+

商店,2019NOI金牌营9第一题,并查集

正题Portal这题其实很简单。很明显的一个贪心策略就是,优先处理深度较大的节点的答案。因为深度更小的节点会有更多的决策可以决定,所以倒不如把优的决策让给自己的子孙。然后很多人就直接线段树合并/可并堆来做到一个【常数较大的】log。却没发现,这个可以直接把物品的价值排一遍序,然后将物品从大到小插入,每次...

2019-07-13 19:11:23

序列,2019NOI金牌营8第三题,并查集

正题这题其实很容易,做法也很多。可以用单调栈来维护一个点向左走的最小值和向右走的最小值。我们考虑给这些ai取出来从小到大排一个序,这时候我们从前到后一一将ai插进原来的序列里面,那么以当前ai为最小值的区间,就是ai与其前面已经插入的元素组成的区间,那么我们对于一个联通块,维护它的前缀最小最大值,后缀最小最大值。当我们插入一个节点的时...

2019-07-13 18:56:58

Graph,2019NOI金牌营7,bfs序

正题Portal我们很容易就可以发现,如果我们确定了一个点的值,那么它所在的联通块的值就可以确定了。假设这个值为x,那么同一联通块的点的值可以被表示为。而且容易发现以当前点做一遍bfs,奇数层的点都是+x,偶数层的点都是-x。但它是一张图,所以相同层之间可能会有连边,这时,可以直接解出x,然后进行判断。...

2019-07-08 22:22:32

生成树,2019NOI金牌营6,思维好题

正题因为这次比赛撞题了,我就凭借着我曾经的记忆慢慢的写出来了这一题。(现场做出来的是真的强Portal我们考虑先把1到n的边先建出来,如果已经有n-1条黑边或者白边,那么就直接输出。否则就存在一个点使得它的两边一边是黑边都是白边。可以直接问一下连接两边的点的边,直接把这条边建出来,那么无论外面是白树还是黑树,...

2019-07-07 21:28:19

猫,2019NOI金牌营6第一题,斜率优化决策单调性

正题Portal这题很简单啊。把每只猫的时间变为要求饲养员出发的时间,然后排个序,那么一个饲养员出发就会收回一个区间的猫。那么就变成了一个Dp,我们设表示派出i个饲养员把前j只猫收回来的最小等待时间之和。转移就很明显是。其中。to就是t的前缀和。那么把它带进去就是。...

2019-07-07 21:13:50

神树和多边形,2019NOI金牌营5,”简单的计算几何“

正题这题其实想想很简单。(据说是老师找我们试水的首先枚举一个关键点,因为我们知道分割这个多边形的最优方案一定是经过关键点的。把顶点和关键点按照极角排序,做这个极角排序的方法,就是如果一个y<0,那么让x=-x,y=-y;那么所在的直线是不会变的,然后再用叉积排序就好了。然后我们得到了从x正半轴到x负半轴的一堆直线,每次对于两条...

2019-07-06 23:06:11

神树和物品,2019NOI金牌营5第一题,Dp决策单调性

正题Portal这题我一开始写了一个决策单调性,但是最后改题了就没有去细想,打了个暴力,就交了上去,所以就只有暴力的分,很惨。这题其实是很好证明决策单调性的。因为把考虑i,i+1两个决策,假设存在一个k使得k的决策为i+1,那么k+1的决策很明显不可能是i。因为这东西是三次方,很容易就可以发现,所以我们就知道了差值越大...

2019-07-06 22:49:13

神树的矩阵,2019NOI金牌营4,思维好题+构造

正题Portal蒙蔽了很久。首先我们可以找一下的情况,发现肯定是1的连续段个数。的规律也是很好找的,直接特判一下输出就好了。否则我们把它竖着放。第一次,我们强制给红色区域加上一个1,然后再除了最后一行的空白部分标上我们想要的。+第二次,我们强制个蓝色区域加上一个1,然后除了第一行的空...

2019-07-06 22:34:28

神树和排列,2019NOI金牌营4第一题,困难的Dp

正题Portal我们考虑一个排列P,他经过一次操作之后变为F。很明显一个P可以得到一个F,但是F可能对应着多个P,我们考虑怎么算出一个F对应多少个P,然后我们就可以对F进行Dp,而得出P的数量。有一个结论就是:F中的前缀最大值变化次数为k,那么一个F对应个P证明为什么?我们考虑一个不为前缀最大值的位置,它不可...

2019-07-06 22:18:20

神树的路径,2019NOI金牌营3第二题,高维前缀和+分块

正题题目传送门我们考虑分块,第一块先做一遍暴力,转移好的Dp数组后,直接做一遍高维前缀和,具体高维前缀和的实现就是枚举每一个质数,再枚举每一个m的约数,再枚举这个质数的几次方,使得这个约数乘上质数的几次方仍然是m的约数,那么就转移一下,因为是每个质数依次转移,所以相当于。相当于算了这一个块向后走一步的贡献,然后直接将这个东西赋值到下一个块。...

2019-07-03 22:21:13

神树的权值,2019NOI金牌营3第一题,思维好题

正题题目传送门很容易就可以想到对si排序,那么每加入一个点就可以走到附近的联通块。走到的点就是那些可以被算进权值的点。所以我们可以用队列维护每一个块,然后对于每一个新加入的点,把它周围的联通块合并起来,那么用启发式合并就可以nlogn完成这个问题。#include<cstdio>#include&...

2019-07-03 22:00:54

2019NOI金牌营第二天~贪心

引子贪心只是一种思想,小部分题目可能直接贪心后就能完成,大部分题目都需要贪心之后再进一步推导,或是用某些算法维护。正题想出来贪心的时候可以运用对拍来进行验证,但是证明自己的贪心并不是那么容易。所以我们通常直接“一激灵”地就想到解法,否则就要先打暴力。由于真的没什么可说的,也没有什么套路可言,在这里直接放要补题。(留个坑...

2019-07-03 08:00:12

神树和蒟蒻,2019NOI金牌营2第一题,困难的Dp

正题这两天第一题都考Dp我也是醉。题目portal我们考虑一个点被算进答案,当且仅当中有东西移到这个点而且不走,假设这个点是最后移到这个点中的第一个。那么我们考虑中的数必须先移走,我们设为第i步,x点在j,x-1点在k的方案数。当然先枚举x。初始状态就是接着就是一个转移的问题。...

2019-07-02 21:50:13

2019NOI金牌营第一天~网络流

正题首先,看这篇文章之前,你需要先搞懂最大流,最小费用最大流,无源汇有上下界最大流,有源汇有上下界最大流。接着我们来了解几个有趣的东西(例题太多后面有空慢慢补最小割建图我们可以这样想,假如有一堆东西,权值有正有负,有几组东西要连带选择,现在问你最大总权值是多少。我们考虑与S连点边就是选中的,与T连边的就是不被选中的,那么我们不管选...

2019-07-01 23:00:42

函数,2019NOI金牌营1第二题,数论求和

正题题目传送门我们需要先知道一个东西这个指的是所有质因子的幂次都不低于2的数。通过简单积分可以证明1到n的powerfulnumber的总数是级别的。然后我们就知道,如果我们可以构造出两个函数。使得G在的值为0.H的前缀和很好计算,且(狄利克雷卷积。这样就可以用乘常数的时间算出来F的前缀和了。...

2019-07-01 22:00:52

分组游戏,2019NOI金牌营1第一题,困难的Dp

正题题目传送门对我来说太困难了,居然是签到题。很容易我们可以先排个序,但是很容易想偏成从前往后做Dp。不妨从后往前,我们考虑表示后面i种ai分组后剩下j个人的方案数。那么答案就是。转移考虑新加入的有多少个人,加上前面剩余的j个人,总共就有个人。接着我们枚举一下有k个人现在开始组成一队,就...

2019-07-01 21:17:39

第K大区间,51nod1686,二分答案+two-pointers

正题首先这个答案是可以二分的。判断的时候我们直接用two-pointers算一算答案就可以了。(鄂然回首发现这是道简单题。#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#include<ios...

2019-06-28 23:45:59

球与切换器,51nod1293,思维好题+递推

正题通过观察我们会发现,一个1的点从右边出去的必定比从下面出去的多一或者等于,一个-1的点从下面出去的必定比从右边出去的多一或者等于,所以说顺序并不影响一个球到达一个点之后的走向,我们可以根据奇偶判断到达一个点的多个球有多少个球往下走或者往右走。0的情况就很简单了。所以就直接表示第i,j这个点向下走或者向右走的有多少个。递推一下,就做完了。#i...

2019-06-28 23:43:17

分则能成,51nod2386,树结构+思维好题

正题首先我们需要知道一个结论,只有最后叶子节点的值才会影响答案,而分的方式不会影响。因为这个题相当于叶子节点的值两两乘求最大值。仔细分析一下过程就可以发现这个东西(虽然我太菜了分析不出来然后问题就变成了把一个数n分成k+1份,求两两相乘总和的最大值。我们设第一份是以此类推,那么答案就是。把他们写出来就会...

2019-06-28 23:38:53

[HAOI2008]木棍分割,bzoj1044,二分+简单的Dp

正题这题应该很容易就可以看出来二分求第一个答案ans1。二分出来直接贪心判断正误就可以了。第二个答案考虑Dp:用表示前i根木棍切j刀且每块大小不超过ans1的方案数。初始值可以把都设为1.因为前面的任意一块不用切都有一种方案数,但是在这里需要注意的是。接着就可以枚举当前块的最大长度,用前缀和加速一下就可...

2019-06-28 23:29:22
奖章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周上午根据用户上周的博文发布情况由系统自动颁发。