Q779’s Blog

洛谷P4322 [JSOI2016]最佳团体 题解 题目链接：P4322 [JSOI2016]最佳团体 题意： JSOI 信息学代表队一共有 \(N\) 名候选人，这些候选人从 \(1\) 到 \(N\) 编号。方便起见，JYY 的编号是 \(0\) 号。每个候选人都由一位编号比他小的候选人\(R_i\) 推荐。如果 \(R_i = 0\)，则说明这个候选人是 JYY 自己看上的。 为了保证团队的和谐，JYY 需要保证，如果招募了候选人 \(i\)，那么候选人 \(R_i\) 也一定需要在团队中。当然了，JYY 自己总是在团队里的。每一个候选人都有一个战斗值 \(P_i\) ，也有一个招募费用 \(S_i\) 。JYY 希望招募 \(K\) 个候选人（JYY 自己不算），组成一个性价比最高的团队。也就是，这 \(K\) 个被 JYY 选择的候选人的总战斗值与总招募费用的比值最大。 对于100%的数据满足\(1≤K≤N≤2500\),\(0<S_i,P_i≤10^4\) , \(0\) \(≤\) \(R_i\) \(<\) \(i\) 下面的讲述用 \(m\) 代替...

洛谷P2868 [USACO07DEC]Sightseeing Cows G 题解 题目链接：P2868 [USACO07DEC]Sightseeing Cows G 题意： 给定有向图，有点权 \(F_i\) 和边权 \(T_i\) ，找一条回路（不一定是简单回路），使得 \[ \dfrac{\sum F_i}{\sum T_i} \] 尽可能的大，求出这个值 若回路的结点序列中含相同结点，只计算一次点权 \(2 \le n \le 10^3,1\le m \le 5 \times 10^3,1 \le F_i,T_i \le 10^3\) 比较经典的01分数规划问题 设 \[ \sum F_i \times \dfrac{1}{\sum T_i} > x \] 移项可得 \[ \sum (F_i - x T_i) > 0 \] 取个反可得 \[ \sum (xT_i - F_i) < 0 \] 然后就变成了判负环的问题。 二分一个 \(x\) ，然后每次跑个spfa检验一下 时间复杂度 \(O(\log_2 10^7 \times nm)\) 为什么大于...

洛谷P1270 “访问”美术馆 题解 题目链接：P1270 “访问”美术馆 题意： 经过数月的精心准备，Peer Brelstet，一个出了名的盗画者，准备开始他的下一个行动。艺术馆的结构，每条走廊要么分叉为两条走廊，要么通向一个展览室。Peer知道每个展室里藏画的数量，并且他精确测量了通过每条走廊的时间。由于经验老到，他拿下一幅画需要5秒的时间。你的任务是编一个程序，计算在警察赶来之前，他最多能偷到多少幅画。 显然的树上背包题，还是个二叉树 读入可以用dfs，然后走廊耗时肯定要变原来两倍 设 \(dp[u][j]\) 表示 \(u\) 所在子树花不超过 \(j\) 秒能获得的最大价值，则 \[ dp[u][j] = \max(dp[u][j],dp[\text{ls}][j-k-\text{w}[u]]+dp[\text{rs}][k]) \] 如果 \(u\) 是叶子结点的话，可以枚举它的耗时然后算能拿几幅画 for(int i=0; i/5<=val[u]&&w[u]+i<=m; i++) dp[u][w[u]+i]=i/5; 时间...

洛谷P3354 [IOI2005]Riv 河流 题解 题目链接：P3354 [IOI2005]Riv 河流 题意： 几乎整个 Byteland 王国都被森林和河流所覆盖。小点的河汇聚到一起，形成了稍大点的河。就这样，所有的河水都汇聚并流进了一条大河，最后这条大河流进了大海。这条大河的入海口处有一个村庄——名叫 Bytetown。 在 Byteland 国，有 \(n\) 个伐木的村庄，这些村庄都座落在河边。目前在 Bytetown，有一个巨大的伐木场，它处理着全国砍下的所有木料。木料被砍下后，顺着河流而被运到 Bytetown 的伐木场。Byteland 的国王决定，为了减少运输木料的费用，再额外地建造 \(k\) 个伐木场。这 \(k\) 个伐木场将被建在其他村庄里。这些伐木场建造后，木料就不用都被送到 Bytetown 了，它们可以在运输过程中第一个碰到的新伐木场被处理。显然，如果伐木场座落的那个村子就不用再付运送木料的费用了。它们可以直接被本村的伐木场处理。 注：所有的河流都不会分叉，形成一棵树，根结点是 Bytetown。 国王的大臣计算出了每个村子每年要产多少木料，你...

洛谷P3237 [HNOI2014]米特运输 题解 题目链接：P3237 [HNOI2014]米特运输 题意： 米特是D星球上一种非常神秘的物质，蕴含着巨大的能量。在以米特为主要能源的D星上，这种米特能源的运输和储存一直是一个大问题。 D星上有N个城市，我们将其顺序编号为1到N，1号城市为首都。这N个城市由N-1条单向高速通道连接起来，构成一棵以1号城市（首部）为根的树，高速通道的方向由树中的儿子指向父亲。树按深度分层：根结点深度为0，属于第1层；根结点的子节点深度为1，属于第2层；依此类推，深度为i的结点属于第i+l层。 建好高速通道之后，D星人开始考虑如何具体地储存和传输米特资源。由于发展程度不同，每个城市储存米特的能力不尽相同，其中第i个城市建有一个容量为A[i]的米特储存器。这个米特储存器除了具有储存的功能，还具有自动收集米特的能力。 如果到了晚上六点，有某个储存器处于未满的状态，它就会自动收集大气中蕴含的米特能源，在早上六点之前就能收集满；但是，只有在储存器完全空的状态下启动自动收集程序才是安全的，未满而又非空时启动可能有安全隐患。 早上六点到七点间，根节点城市（1号...

洛谷P1273 有线电视网 题解 题目链接：P1273 有线电视网 题意： 某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。 从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。 现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。 写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。 如果直接去想怎么保证不超过边权和什么的不太好搞 考虑把每个用户数是否能够承担都算出来即可 也就是 设 \(dp[i][u][j]\) 表示以 \(u\) 为根的子树，仅用前 \(i\) 个儿子，满足 \(j\) 个客户能获得的最大价值 事实上我们并不是非常关心是否能获得的最大价值，我们只要不亏本的情况下尽可能多让人看罢了（好良心有没有） 则有转移方程 \[ dp[i][u][j]=\max(dp[i][u][j],dp[i-1][u...

洛谷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\) ——...