Rockdu's Blog

题目地址：大家好，我是"题目地址" 想比较不容易偏，但写着细节贼多的题。 首先考虑最优策略，注意到题目给出强化牌的wi>1" role="presentation" style="position: relative;">wi>1wi>1wi>1的条件。 因此，优先打出最大的强化牌一定是最优的，考虑选择了两张最大的攻击牌，仍然与选择最小的强化牌等价。 接下来我们考虑选牌的情况： 设拿到了强化牌c" role="presentation" style="position: relative;">ccc张，攻击牌m−c

题目链接：https://loj.ac/problem/2537 考虑到题目是一颗二叉树，有一个简单的O(N^2)的DP做法。f(i,j)表示i号点取值为数集中第j大数的概率，每一次我们从子树合并上来。j被取到有两种情况：j更大并且当前选择的是最大值 j更小并且当前选择的是最小值分情况讨论，发现要转移需要一个选到比j小的值的概率和(比j大的可以直接用1减比j小的)。那么我们维护两个前缀和(对两边的元素分别计算)，即可完成一次合并。 如何优化这个算法呢？假设两边子树可以产生的j值集合分别为A，B。考虑A值域上这样连续的一段数：满足不存在B[i]使得A[l]<=B[i]<=A

正如大家所见，这是一篇迟到的NOIP2018游记，一篇迟到了两个星期的游记。短短的两天内，所有的事情都是那么的突然。还没有等到我缓过神来，一切都已经结束了。 Day0 　　　　——0，生1？ 　　　　 　　　　NOIP前一天的上午，我们迎来了NOIP前的最后一场考试。然而我的分数不忍直视，T1爆空间了，直接爆零。某毒瘤出题人(是哪个毒瘤自己心里知道QAQ，说的就是你，这个人的名字在下面出现了很多次，大家可以猜猜)告诉我我太菜了，这个辣鸡做法他根本没想到，所以分送都送不给我。然后我就rank10+了(真的泄)。 　　　　心情不太好，下午打了一下午slay.one。还是不敌lp

Problem Description Byteasar has a tree T with n vertices conveniently labeled with 1,2,...,n. Each vertex of the tree has an integer value vi.The value of a non-empty tree T is equal to v1⊕v2⊕...⊕vn, where ⊕ denotes bitwise-xor.Now for every in

题目描述沫沫最近在玩一个二维的射箭游戏，如下图 1 所示，这个游戏中的 x 轴在地面，第一象限中有一些竖直线段作为靶子，任意两个靶子都没有公共部分，也不会接触坐标轴。 沫沫控制一个位于(0,0)的弓箭手，可以朝 0 至 90?中的任意角度（不包括 0度和 90度），以任意大小的力量射出带有穿透能力的光之箭。由于游戏中没有空气阻力，并且光之箭没有箭身，箭的轨迹会是一条标准的抛物线，被轨迹穿过的所有靶子都认为被沫沫射中了，包括那些 只有端点被射中的靶子。 这个游戏有多种模式，其中沫沫最喜欢的是闯关模式。 在闯关模式中，第一关只有一个靶 子，射中这个靶子即可进入第二关，这时在第一关的基础上会出现另外

题目描述这里有一辆赛车比赛正在进行，赛场上一共有N辆车，分别称为个g1，g2......gn。赛道是一条无限长的直线。最初，gi位于距离起跑线前进ki的位置。比赛开始后，车辆gi将会以vi单位每秒的恒定速度行驶。在这个比赛过程中，如果一辆赛车曾经处于领跑位置的话（即没有其他的赛车跑在他的前面），这辆赛车最后就可以得奖，而且比赛过程中不用担心相撞的问题。现在给出所有赛车的起始位置和速度，你的任务就是算出那些赛车将会得奖。 输入输出格式输入格式：   第一行有一个正整数N表示赛车的个数。接下来一行给出N个整数，按顺序给出N辆赛车的起始位置。再接下来一行给出N个整数，按顺序给出N辆赛车的恒

（题目背景）是没有的。 你有一个01" role="presentation" style="position: relative;">010101序列，初始时序列为空。你可以对序列进行两种操作： 在序列末端插入一个0" role="presentation" style="position: relative;">000。 在序列中删去一个子序列，并在序列末端插入一个1" role="presentation" style="position: relative;">111。这里对子序列的选取有一定限制，设子序列中包含x" role="presentation"

1、快速莫比乌斯变换 1.1 什么是莫比乌斯变换 　　　快速莫比乌斯变换，简称(FMT)，也是一种对数列的变换。类似FFT地，FMT也是通过将数列/多项式在两种形式下来回变换达到加速两个数列/多项式卷积的效果。 　　　FFT解决的是这样的卷积： 　　　Cx=&#x2211;i+j=xaibj" role="presentation" style="position: relative;">Cx=∑i+j=xaibjCx=∑i+j=xaibj C_x=\sum_{i+j=x}a_ib_j 　　　其中x,i,j" role="presentation" style=

随着NOIP2018的结束，省选的脚步声又近了一步，2018年也接近尾声了。在这一年最后的日子里，有一些新东西需要学，还有一些老知识需要捡，填坑计划如下： FWT/快速沃尔什变换 (3/3) 半平面交 (2/2) 旋转卡壳 (1/1) Link-Cut-Tree (2/2) 仙人掌 杜教筛 (1/1) 动态DP理论 (1/1) 组合数学(组合数/斯特林数) (2/2) 非旋Treap (1/1) Polya-Burnside 整体二分 (1/1) 带权二分 (1/1) 二进制分组 后缀数组 (2/2) 上下界网络流 (2/2) 二次剩余 (2/2) 回

题目描述Mayan puzzle是最近流行起来的一个游戏。游戏界面是一个7 行 5×5列的棋盘，上面堆放着一些方块，方块不能悬空堆放，即方块必须放在最下面一行，或者放在其他方块之上。游戏通关是指在规定的步数内消除所有的方块，消除方块的规则如下： 1 、每步移动可以且仅可以沿横向（即向左或向右）拖动某一方块一格：当拖动这一方块时，如果拖动后到达的位置（以下称目标位置）也有方块，那么这两个方块将交换位置（参见输入输出样例说明中的图6到图7 ）；如果目标位置上没有方块，那么被拖动的方块将从原来的竖列中抽出，并从目标位置上掉落（直到不悬空，参见下面图1 和图2）； 2