Q779’s Blog

洛谷P4099 [HEOI2013]SAO 题解 题目链接：P4099 [HEOI2013]SAO 题意： Welcome to SAO ( Strange and Abnormal Online)。这是一个 VR MMORPG， 含有 \(n\) 个关卡。但是，挑战不同关卡的顺序是一个很大的问题。 某款游戏有 \(n-1\) 个对于挑战关卡的限制，诸如第 \(i\) 个关卡必须在第 \(j\) 个关卡前挑战，或者完成了第 \(k\) 个关卡才能挑战第 \(l\) 个关卡。并且，如果不考虑限制的方向性，那么在这 \(n-1\) 个限制的情况下，任何两个关卡都存在某种程度的关联性。即，我们不能把所有关卡分成两个非空且不相交的子集，使得这两个子集之间没有任何限制。 高质量好题👍 做了我一下午+晚上 首先这个题面的意思：给定一棵有方向的树，求拓扑序总数 注意到这个特殊的性质，可以从树形dp的角度去解决这个问题 设 \(dp[u][i]\) 表示结点 \(u\) 在其子树的拓扑序中位于第 \(i\) 位的方案数 对于每个 \(u\) 的儿子 \(v\) ，将 \(v\) 不断合并到...

洛谷P2279 [HNOI2003]消防局的设立 题解 题目链接：P2279 [HNOI2003]消防局的设立 题意： 2020 年，人类在火星上建立了一个庞大的基地群，总共有 \(n\) 个基地。起初为了节约材料，人类只修建了 \(n-1\) 条道路来连接这些基地，并且每两个基地都能够通过道路到达，所以所有的基地形成了一个巨大的树状结构。如果基地 \(A\) 到基地 \(B\) 至少要经过 \(d\) 条道路的话，我们称基地A到基地B的距离为 \(d\)。 由于火星上非常干燥，经常引发火灾，人类决定在火星上修建若干个消防局。消防局只能修建在基地里，每个消防局有能力扑灭与它距离不超过 \(2\) 的基地的火灾。 你的任务是计算至少要修建多少个消防局才能够确保火星上所有的基地在发生火灾时，消防队有能力及时扑灭火灾。 一开始以为是树形dp（确实是），结果发现贪心可做。 树形dp的状态十分恶心，贪心相对简单 注意到距离不大于 \(2\) 的除了爷爷、父亲、儿子、孙子结点，还有它的兄弟结点 对于一个结点，如果我们在它的爷爷放了一个消防站，则可以将其父亲和兄弟全部覆盖 则我们可以每次选...

洛谷P3177 [HAOI2015] 树上染色 题解 题目链接：P3177 [HAOI2015] 树上染色 题意： 有一棵点数为 \(n\) 的树，树边有边权。给你一个在 \(0 \sim n\) 之内的正整数 \(m\) ，你要在这棵树中选择 \(m\) 个点，将其染成黑色，并将其他 的 \(n-m\) 个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的受益。问受益最大值是多少。 upd.20220531 由于本人对树上背包掌握不熟，导致复杂度写假了 其实是题解区普遍写错罢了。 不过原文只是没用刷表法 于是在原文基础上做了修改，不影响观感，请放心食用（逃 显然树上背包 设 \(dp[u][j]\) 表示 \(u\) 所在子树染了 \(j\) 个黑点的最大价值 容易推出一个大概的方程 \[ dp[u][j]=\max(dp[u][j],dp[u][j-k]+dp[v][k]+\text{val}) \] 注：下文会提到这个转移方程是有点问题的 黑点两两距离+白点两两距离 直接去算就是 \(O(n^2)\) 的了 考虑更好的计算方法 一条路径...

洛谷P2015 二叉苹果树 题解 题目链接：P2015 二叉苹果树 题意： 有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点） 这棵树共有 \(N\) 个结点（叶子点或者树枝分叉点），编号为 \(1 \sim N\)，树根编号一定是 \(1\)。 我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 \(4\) 个树枝的树： 2 5 \ / 3 4 \ / 1 现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。 给定需要保留的树枝数量 \(m\) ，求出最多能留住多少苹果。 经典的树形依赖背包（树上背包） 设 \(dp[u][j]\) 表示 \(u\) 结点所在子树保留 \(j\) 条边所能得到的最大苹果树 则有 \[ dp[u][j]=\max(dp[u][j],dp[u][j-k-1]+dp[v][k]+w(u,v)) \] 为什么是 \(j-k-1\) 呢 因为 \(k\) 是 \(v\) 所在子树的分配边数，但是你要花一条边去连上 \(v\) 不然你给了 \(v\) 一共 ...

洛谷P3174 [HAOI2009] 毛毛虫 题解 题目链接：P3174 [HAOI2009] 毛毛虫 题意： 对于一棵树，我们可以将某条链和与该链相连的边抽出来，看上去就象成一个毛毛虫，点数越多，毛毛虫就越大。例如下图左边的树（图 \(1\)）抽出一部分就变成了右边的一个毛毛虫了（图 \(2\)）。 这道题是可以树形dp的，具体看这里 link，不是本文重点。 设 \(f[u]\) 为 \(u\) 结点所在子树的最大毛毛虫🐛大小 则有 \[ f[u]=\max(f[v])+1+\max(\text{cnt}[u]-1,0) \] 然后还要维护个次大值啥的，挺麻烦的 其实这道题就是树的直径。两遍dfs就能搞定的问题 为什么树的直径对呢 考虑两条路径，长度相等，则答案一定相等，这个很显然 然后么找个最长的，也就是直径，统计一下答案就好了 代码： #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #incl...

洛谷P3621 [APIO2007] 风铃 题解 题目链接：P3621 [APIO2007] 风铃 题意： 你准备给弟弟 Ike 买一件礼物，但是，Ike 挑选礼物的方式很特别：他只喜欢那些能被他排成有序形状的东西。 你准备给 Ike 买一个风铃。风铃是一种多层的装饰品，一般挂在天花板上。 每个风铃都包含一些由竖直线连起来的水平杆。每根杆的两头都有线连接，下面或者挂着另一根水平杆，或者挂着一个玩具。下面是一个风铃的例子： 为了满足弟弟，你需要选一个满足下面两个条件的风铃： 所有的玩具都在同一层(也就是说，每个玩具到天花板之间的杆的个数是一样的)或至多相差一层。 对于两个相差一层的玩具，左边的玩具比右边的玩具要更靠下一点。 风铃可以按照下面的规则重新排列：任选一根杆，将杆两头的线“交换”。也就是解开一根杆左右两头的线，然后将它们绑到杆的另一头。这个操作不会改变更下面的杆上线的排列顺序。 正在训练信息学奥林匹克的你，决定设计一个算法，判断能否通过重新排列，将一个给定的风铃变为 Ike 喜欢的样子。 考虑上面的例子，上图中的风铃满足条件 \(1\)，却不满足条件 \(2\) ——...

洛谷P2458 [SDOI2006]保安站岗 题解 题目链接：P2458 [SDOI2006]保安站岗 题意： 五一来临，某地下超市为了便于疏通和指挥密集的人员和车辆，以免造成超市内的混乱和拥挤，准备临时从外单位调用部分保安来维持交通秩序。 已知整个地下超市的所有通道呈一棵树的形状；某些通道之间可以互相望见。总经理要求所有通道的每个端点（树的顶点）都要有人全天候看守，在不同的通道端点安排保安所需的费用不同。 一个保安一旦站在某个通道的其中一个端点，那么他除了能看守住他所站的那个端点，也能看到这个通道的另一个端点，所以一个保安可能同时能看守住多个端点（树的结点），因此没有必要在每个通道的端点都安排保安。 请你帮助超市经理策划安排，在能看守全部通道端点的前提下，使得花费的经费最少。 注意到这道题目可能会有相邻两个都不放保安的情况 首先想到记录一个结点是否放，以及其儿子、儿子的儿子是否放 但是这样比较麻烦 考虑设 \(dp[u][0/1/2]\) 表示 \(u\) 结点： \(0\) 表示被自己覆盖（自己放保安） \(1\) 表示被儿子覆盖（某个（或某些）儿子放保安） \(2\)...

洛谷P2016 战略游戏 题解 题目链接：P2016 战略游戏 题意： Bob 要建立一个古城堡，城堡中的路形成一棵无根树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能了望到所有的路。 注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。 请你编一程序，给定一树，帮 Bob 计算出他需要放置最少的士兵。 注意这里是相邻的边，不是相邻的结点 显然我们需要记录与子结点所连的边是否被监视 于是有 \[ dp[u][0]=\sum dp[v][1]\\ dp[u][1]=\sum \min(dp[v][0],dp[v][1]) \] 然后就没了 代码： #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> using namespace std; #define int...

洛谷P4084 [USACO17DEC]Barn Painting G 题解 题目链接：P4084 [USACO17DEC]Barn Painting G 题意：题意：给定一颗N个节点组成的树，3种颜色，其中K个节点已染色，要求任意两相邻节点颜色不同，求合法染色方案数。 这个题太水了 设 \(dp[u][1/2/3]\) 表示 \(u\) 结点涂 \(1/2/3\) 颜色的方案数 根据加法原理， 如果 \(u\) 已经有颜色了，那么 \[ dp[u][j] = \sum dp[v][k]\times [k\ne j]\times [j=\text{val[u]}] \] 否则 \[ dp[u][j] = \sum dp[v][k]\times [k\ne j] \] 时间复杂度 \(O(n)\) 代码： #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #inclu...

洛谷P1122 最大子树和 题解 题目链接：P1122 最大子树和 题意： 小明对数学饱有兴趣，并且是个勤奋好学的学生，总是在课后留在教室向老师请教一些问题。一天他早晨骑车去上课，路上见到一个老伯正在修剪花花草草，顿时想到了一个有关修剪花卉的问题。于是当日课后，小明就向老师提出了这个问题： 一株奇怪的花卉，上面共连有 \(N\) 朵花，共有 \(N-1\) 条枝干将花儿连在一起，并且未修剪时每朵花都不是孤立的。每朵花都有一个“美丽指数”，该数越大说明这朵花越漂亮，也有“美丽指数”为负数的，说明这朵花看着都让人恶心。所谓“修剪”，意为：去掉其中的一条枝条，这样一株花就成了两株，扔掉其中一株。经过一系列“修剪“之后，还剩下最后一株花（也可能是一朵）。老师的任务就是：通过一系列“修剪”（也可以什么“修剪”都不进行），使剩下的那株（那朵）花卉上所有花朵的“美丽指数”之和最大。 老师想了一会儿，给出了正解。小明见问题被轻易攻破，相当不爽，于是又拿来问你。 一眼树形dp 这道题就是要在树上找一个极大权值连通块 显然我们不知道连通块是什么样的，但是不急 树形dp的核心是从子树转移状态 \[...

洛谷P3205 [HNOI2010]合唱队 题解 题目链接：P3205 [HNOI2010]合唱队 题意： 为了在即将到来的晚会上有更好的演出效果，作为 AAA 合唱队负责人的小 A 需要将合唱队的人根据他们的身高排出一个队形。假定合唱队一共 \(n\) 个人，第 \(i\) 个人的身高为 \(h_i\) 米（\(1000 \le h_i \le 2000\)），并已知任何两个人的身高都不同。假定最终排出的队形是 \(A\) 个人站成一排，为了简化问题，小 A 想出了如下排队的方式：他让所有的人先按任意顺序站成一个初始队形，然后从左到右按以下原则依次将每个人插入最终棑排出的队形中： 第一个人直接插入空的当前队形中。 对从第二个人开始的每个人，如果他比前面那个人高（\(h\) 较大），那么将他插入当前队形的最右边。如果他比前面那个人矮（\(h\) 较小），那么将他插入当前队形的最左边。 当 \(n\) 个人全部插入当前队形后便获得最终排出的队形。 例如，有 \(6\) 个人站成一个初始队形，身高依次为 \(1850, 1900, 1700, 1650, 1800, 1750\...

UVA1629 切蛋糕 Cake slicing 题解 题目链接：UVA1629 切蛋糕 Cake slicing 题意：这个翻译够烂的，直接看pdf 翻译：有一个n行m列(1<=n,m<=20)的网络蛋糕上有k个樱桃。每次可以用一刀沿着网络线把蛋糕切成两块，并且只能够直切不能拐弯。要求最后每一块蛋糕上恰好有一个樱桃，且切割线总长度最小。 输入输出格式 输入格式:每次输入有若干组数据。每组数据第一行有三个正整数n m k(行，列，樱桃个数)，之后的k行每行两个正整数(樱桃的坐标) 输出格式:输出有若干行，对应每组数据。每行输出两个正整数(id,最小的切割长度) 输入输出样例 输入样例: 3 4 3 1 2 2 3 3 2 输出样例: Case 1: 5 首先普通的二维枚举好像不行 数据范围这么小，于是考虑从小的矩形向大的矩形更新 设 \(dp[x_1][y_1][x_2][y_2]\) 表示矩形的左下角为 \((x_1,y_1)\) ，右上角为 \((x_2,y_2)\) 时的最小花费 方便起见，下面转移方程中的 \(dp[x_1][y_1][x_2][y_2]\...