博客
归档
友链
关于
博客
归档
友链
关于
P2168 [NOI2015]荷马史诗
创建一个哈夫曼树,不同的是一个节点可以有kkk个子节点,并且根节点没有任何编码。 考虑我们构造编码的过程,每次可以选择kkk个子树,将它们合并为一个大的树,并且给子树们的根节点编号钦定为0,1,...k−10,1,...k-10,1,...k−1,此时每个子树深度增加111,这棵树的深度变为max(maxdep(subtreei))+1\max(maxdep(subtree_i))+1m...
2019-11-11
阅读全文
BZOJ 3133 [Baltic2013]ballmachine
传送门 注意到题目条件如果同时有多个点可以走,那么会选择编号最小的节点所在路径的方向。 不妨考虑对树的节点进行一些安排,使得我们按照dfsdfsdfs顺序找到的第一个点就是球落到的点。 不要考虑编号最小的节点在的方向,而是考虑从一个点下落的时候,他会选择哪一条边,使得这条路径可以到达编号最小的点。 没错,假设现在的节点是uuu,它的子节点为vvv,它选择的路径就是子树最小值最小的vvv 于是...
2019-09-15
阅读全文
P1325 雷达安装
传送门 考虑只有一个点,一个雷达的时候,雷达在哪个区间才可以覆盖住这个点, 设dis=d2−y2dis=\sqrt{d^2-y^2}dis=d2−y2,发现只有在区间[x−dis,x+dis][x-dis,x+dis][x−dis,x+dis]才能覆盖住点(x,y)(x,y)(x,y),也就是说在[x−dis,x+dis][x-dis,x+dis][x−dis,x+dis]要至少有一个雷...
2019-07-31
阅读全文
P2507 [SCOI2008]配对
传送门 假设没有不允许两个相同的数配对的条件,那么直接将ABABAB数组排序一遍,每一位每一位配对即可。 现在不允许两个相同的数配对,还是考虑贪心,如果出现如图的匹配情况,即a[i]a[i]a[i]和b[i−alb]b[i-alb]b[i−alb]匹配,其中alb>2alb>2alb>2。 发现这种情况肯定不是最优的,因为我们发现一定存在一个a[j](j≤i−1)a[j]...
2019-07-21
阅读全文
P2114 [NOI2014]起床困难综合症
传送门 首先,我们发现位运算和十进制的加减乘除不一样,位运算对于每一位都是独立的,而加减乘除会产生进位,在一位上的操作会影响另一位。 我们可以这样理解,对于一大堆不知道是蜃么奇奇怪怪的AndAndAnd,OrOrOr,XorXorXor ,我们可以算出来一个函数f(x,pos)f(x,pos)f(x,pos)(其中x=0,1x=0,1x=0,1且f(x,pos)=0,1f(x,pos)=0,...
2019-07-20
阅读全文
CF280D k-Maximum Subsequence Sum 线段树
传送门 题面大意: 长度为nnn的数列,支持两种操作: 1.1.1.修改某个位置的值 2.2.2.询问区间[l,r][l,r][l,r]里选出至多kkk个不相交的子段和的最大值。 一共有mmm个操作 解法: 暴力 dpdpdp+滚动数组(在本地卡进2s2s2s) 模拟赛的时候有人用这个方法AAA了 dp[i][j][p]dp[i][j][p]dp[i][j][p]表示进行到a[i]a[...
2019-07-13
阅读全文