Rockdu's Blog

链接标题 复习最小路径覆盖 最小路径覆盖是指对于给定的DAG，用最少的路径将其所有点覆盖，路径不相交。最小路径覆盖建图如下： 变式1：最小链覆盖 用最少的路径将其所有点覆盖，路径可以相交 做法：使用floyd传递闭包重连边，然后进行最小路径覆盖 变式2：最长反链 指选择最多的点，使得两两之间不能互相到达 做法：对偶问题：最长反链等于最小链覆盖 本题中发现球是依次加入的，如果有两个球和为完全平方数那么小的向大的连接单向边，一个柱子就相当于一条路径。那么可以知道K" role="presentation" style="position: relative;"&

以前一直以为自己写的点分治找对了重心。结果前几天自己写代码的时候，发现重心父亲一端子树的重心有问题。因为代码里传的子树大小是错误的，传的是当前根下父亲的子树大小而不是真正的大小。 当时感性想了一下发现卡不掉，最多也就是常数差别。今天发现原来这个问题已经有严格证明，所以可以放心这么“错误”地写点分啦~ >证明点我<

题目描述 给你一棵n个点的树，每一个点有个颜色ci" role="presentation" style="position: relative;">cicic_i。定义一种颜色的树是：把该颜色的点两两路径上的点和边都拿出来构成的图形。你可以选出k" role="presentation" style="position: relative;">kkk种颜色来，求：有多少种方案可以使每种颜色交集产生的树非空。对k&#x2208;[1,m]" role="presentation" style="position: relative;">k∈[1,m]k∈[1,m]k

题目链接 题解：发现只需要分两段维护就可以了。 上一次排过序的前缀部分用字典树维护，并且对每一位记录nowxor" role="presentation">nowxornowxornow_xor表示按照当前的顺序，第i" role="presentation">iii位是否被翻转。后面的部分用一个前缀和维护。 这样的话，异或的时候维护偏移值，每一次排序我们就把后面的部分全部插入字典树，并且更新now&#x005F;xor" role="presentation">now_xornow_xornow\_xor。 #include<cstdio&g

题目链接：传送门 题解：不难发现，我们有一个优秀的N2N^2的dpdp做法，记录f(i,j,0/1)f(i,j,0/1)表示ii子树内选jj个，当前根选没选。 我们要知道分治NTTNTT的复杂度：对于kk个总度数∑deg=k\sum deg=k的多项式来说，计算它们乘积的复杂度可以做到：O((∑deg)log(∑deg)logk)O((\sum deg)log(\sum deg)logk)。 因此，我们采用重链剖分，先转移所有轻链。 不难发现， g(u,0)=∏v∈son(g(v,0)+g(v,1))g(u,0)=\prod_{v\in son} (g(v,0)+g(v,1))

题目描述 小 L 最近沉迷于塞尔达传说：荒野之息（The Legend of Zelda: Breath of The Wild）无法自拔，他尤其喜欢游戏中的迷你挑战。 游戏中有一个叫做 “LCT” 的挑战，它的规则是这样子的：现在有一个 NN 个点的树（Tree），每条边有一个整数边权 vi" role="presentation">viviv_i，若 vi&#x2265;0" role="presentation">vi≥0vi≥0v_i \ge 0，表示走这条边会获得 vi" role="presentation">viviv_i的收益；若 vi&

题目描述滑雪场坐落在FJ省西北部的若干座山上。 从空中鸟瞰，滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。 你的团队负责每周定时清理雪道。你们拥有一架直升飞机，每次飞行可以从总部带一个人降落到滑雪场的某个地点，然后再飞回总部。从降落的地点出发，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。 由于每次飞行的耗费是固定的，为了最小化耗费，你想知道如何用最少的飞行次数才能完成清理雪道的任务。 输入输出格式输入格式：   输入文件的第一行包含一个整数n (2 <= n <= 100) – 代表滑雪场的地点的数量。 接下来的n行，描述1

题目描述在宽广的非洲荒漠中，生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的Alpaca L. Sotomon是这个家族的领袖，外人也称其为“所驼门王”。所驼门王毕生致力于维护家族的安定与和谐，他曾亲自率军粉碎河蟹帝国主义的野蛮侵略，为族人立下赫赫战功。所驼门王一生财宝无数，但因其生性节俭低调，他将财宝埋藏在自己设计的地下宫殿里，这也是今天Henry Curtis故事的起点。Henry是一个爱财如命的贪婪家伙，而又非常聪明，他费尽心机谋划了这次盗窃行动，破解重重机关后来到这座地下宫殿前。 整座宫殿呈矩阵状，由R×C间矩形宫室组成，其中有N间宫室里埋藏着宝藏，称作藏宝宫室。宫殿里外、相邻宫室

题目描述小 B 最近迷上了华容道，可是他总是要花很长的时间才能完成一次。于是，他想到用编程来完成华容道：给定一种局面， 华容道是否根本就无法完成，如果能完成， 最少需要多少时间。 小 B 玩的华容道与经典的华容道游戏略有不同，游戏规则是这样的： 在一个 n×m 棋盘上有n×m个格子，其中有且只有一个格子是空白的，其余n×m−1个格子上每个格子上有一个棋子，每个棋子的大小都是 1×1 的； 有些棋子是固定的，有些棋子则是可以移动的； 任何与空白的格子相邻（有公共的边）的格子上的棋子都可以移动到空白格子上。 游戏的目的是把某个指定位置可以

题目描述参加jsoi冬令营的同学最近发现，由于南航校内修路截断了原来通向计算中心的路，导致去的路程比原先增加了近一公里。而食堂门前施工虽然也截断了原来通向计算中心的路，却没有使路程增加，因为可以找到同样长度的路作替代。其实，问题的关键在于，路截断的地方是交通要点。 同样的情况也出现在城市间的交通中。某些城市如果出了问题，可能会引起其他很多城市的交通不便。另一些城市则影响不到别的城市的交通。jsoi冬令营的同学发现这是一个有趣的问题，于是决定研究这个问题。 他们认为这样的城市是重要的：如果一个城市c被破坏后，存在两个不同的城市a和b（a, b均不等于c），a到b的最短距离增长了（或不通），则城市