Q779’s Blog

洛谷P3647 [APIO2014] 连珠线 题解 题目链接：P3647 [APIO2014] 连珠线 题意： 在达芬奇时代，有一个流行的儿童游戏称为连珠线。当然，这个游戏是关于珠子和线的。线是红色或蓝色的，珠子被编号为 \(1\) 到 \(n\)。这个游戏从一个珠子开始，每次会用如下方式添加一个新的珠子： Append(w, v)：一个新的珠子 \(w\) 和一个已经添加的珠子 \(v\) 用红线连接起来。 Insert(w, u, v)：一个新的珠子 \(w\) 插入到用红线连起来的两个珠子 \(u, v\) 之间。具体过程是删去 \(u, v\) 之间红线，分别用蓝线连接 \(u, w\) 和 \(w, v\)。 每条线都有一个长度。游戏结束后，你的最终得分为蓝线长度之和。 给你连珠线游戏结束后的游戏局面，只告诉了你珠子和链的连接方式以及每条线的长度，没有告诉你每条线分别是什么颜色。 你需要写一个程序来找出最大可能得分。即，在所有以给出的最终局面结束的连珠线游戏中找出那个得分最大的，然后输出最大可能得分。 \(1 \leq n \leq 200000\)。 开学前两天准...

洛谷P3047 [USACO12FEB]Nearby Cows G 题解 题目链接：P3047 [USACO12FEB]Nearby Cows G 题意： 给你一棵 \(n\) 个点的树，点带权，对于每个节点求出距离它不超过 \(k\) 的所有节点权值和 \(m_i\)。 「数据范围」 对于 \(100\%\) 的数据：\(1 \le n \le 10^5\)，\(1 \le k \le 20\)，\(0 \le c_i \le 1000\) 换根dp，也叫二次扫描法 这题随便找一个根当做树根，然后扫两遍才能出答案 首先设 \(f[u][j]\) 表示 \(u\) 所在子树，与 \(u\) 相距恰好 \(j\) 的结点个数，则 \[ f[u][j]=\sum_{v \in \text{son}[u]} f[v][j-1] \] 这是第一遍dfs，可以发现我们没有从非 \(u\) 所在子树获取答案 考虑第二遍dfs，设 \(g[u][j]\) 表示在整棵树中与 \(u\) 相距恰好 \(j\) 的结点个数 这个答案一定是从父节点的 \(g\) 转移而来 但是这里会有一个问题，\...

洛谷P4037 [JSOI2008]魔兽地图 题解 题目链接：P4037 [JSOI2008]魔兽地图 题意： DotR (Defense of the Robots) Allstars是一个风靡全球的魔兽地图，他的规则简单与同样流行的地图DotA (Defense of the Ancients) Allstars。 DotR里面的英雄只有一个属性——力量。他们需要购买装备来提升自己的力量值，每件装备都可以使佩戴它的英雄的力量值提高固定的点数，所以英雄的力量值等于它购买的所有装备的力量值之和。装备分为基本装备和高级装备两种。基本装备可以直接从商店里面用金币购买，而高级装备需要用基本装备或者较低级的高级装备来合成，合成不需要附加的金币。装备的合成路线可以用一棵树来表示。 比如，Sange and Yasha的合成需要Sange,Yasha和Sange and Yasha Recipe Scroll三样物品。其中Sange又要用Ogre Axe, Belt of Giant Strength和 Sange Recipe Scroll合成。每件基本装备都有数量限制，这限制了你不能无...

洛谷P1272 重建道路 题解 题目链接：P1272 重建道路 题意： 一场可怕的地震后，人们用 \(N\) 个牲口棚（编号 \(1\sim N\)）重建了农夫 John 的牧场。由于人们没有时间建设多余的道路，所以现在从一个牲口棚到另一个牲口棚的道路是惟一的。因此，牧场运输系统可以被构建成一棵树。 John 想要知道另一次地震会造成多严重的破坏。有些道路一旦被毁坏，就会使一棵含有 \(P\) 个牲口棚的子树和剩余的牲口棚分离，John 想知道这些道路的最小数目。 \(1\le N\le 150\)，\(1\le P\le N\)，保证给出的是一棵树。 题目有点难懂，意思就是说切最少刀切出一个大小为 \(p\) 的块，显然树上背包 设 \(dp[u][j]\) 表示 \(u\) 所在子树切出大小为 \(j\) 的块并强制包含 \(u\) 的最小花费，则 \[ dp[u][j+k]=\min(dp[u][j+k],\text{tmp}[j]+dp[v][k]-1) \] 其中 \(\text{tmp}[j]\) 为上一轮的 \(dp[u][j]\) 。 后面一个柿子比较难懂 考...

洛谷P1734 最大约数和 题解 题目链接：P1734 最大约数和 题意：选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。 设 \(dp[i][j]\) 表示只考虑前 \(i\) 个数总和不超过 \(j\) 的最大价值，则 \[ dp[i][j]= \max(dp[i-1][j],dp[i-1][j-i]+v[i]) \] \(v[i]\) 可以 \(O(n \log n)\) 预处理 时间复杂度 \(O(n^2)\) 代码： #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iomanip> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f...

洛谷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)\) 为什么大于...

POJ2976 Dropping tests 题解 题目链接：POJ2976 Dropping tests 题意： Description In a certain course, you take n tests. If you get ai out of bi questions correct on test i, your cumulative average is defined to be . Given your test scores and a positive integer k, determine how high you can make your cumulative average if you are allowed to drop any k of your test scores. Suppose you take 3 tests with scores of 5/5, 0/1, and 2/6. Without dropping any tests, your cumulative average is . However, if you ...

洛谷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...