Q779’s Blog

CF526B Om Nom and Dark Park 题解 题目链接：CF526B Om Nom and Dark Park 题意：给定 \(2^{n+1}-1\) 个结点的满二叉树，求保证根到每一个叶子节点的路径权值和相等的情况下，增加权值的最小值 显然不能从根节点开始修改权值，不然也不知道改成什么才行 因此主要思路是从叶子结点向上修改权值，直到根结点为止 方便起见，用 a[x]表示结点 \(x\) 到它的父结点的那条边的权值 下文中提到的路径长指一个结点到它叶子结点的最终的距离 可以发现，对于一个待修改结点 \(x\) ，假设我们已经知道了它的左右子结点的路径长ls,rs（已经被修改了的路径长，因为是从叶子结点向上修改的） 则结点 \(x\) 到左子结点修改前的路径长为a[2*x]+ls，同理右子结点a[2*x+1]+rs 保证根到叶子节点路径权值和相等，因此要把上面这两个路径长中较小的那个补成较大的那个，这样花费肯定是最小的，又保证了以这个结点为根的子树满足题目要求 于是从下往上传递，过程中统计答案 时间复杂度 \(O(2^n)\) 主要代码很短 #define MA...

洛谷P1108 低价购买 题解 题目链接：P1108 低价购买 题意：“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议:“低价购买；再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价( \(2^{16}\) 范围内的正整数)，你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买；再低价购买”的原则。写一个程序计算最大购买次数。 这里是某支股票的价格清单： 日期 1,2,3,4,5,6,7,8,9,10,11,12 价格 68,69,54,64,68,64,70,67,78,62,98,87 最优秀的投资者可以购买最多4次股票，可行方案中的一种是： 日期 2,5,6,10 价格 69,68,64,62 输入格式 第1行: \(N(1 \le N \le 5000)\) ，股票发行天数 第2行: \(N\)个数，是每天的股票价格。 输出格式 两个数: 最大购买次数和拥有最大购买次...

洛谷P1156 垃圾陷阱 题解&浅谈刷表法与填表法 填表法 ：就是一般的动态规划，当前点的状态，可以直接用状态方程，根据之前点的状态推导出来。 刷表法：由当前点的状态，更新其他点的状态。需要注意：只用当每个状态所依赖的状态对它的影响相互独立。 下面会用一道题目给出两种写法的区别 题目链接：P1156 垃圾陷阱 题意：吃垃圾就完了 卡门――农夫约翰极其珍视的一条Holsteins奶牛――已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为\(D(2 \le D \le 100)\)英尺。 卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。 每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。 假设卡门预先知道了每个垃圾扔下的时间\(t(0< t \le 1000)\)，以及每个垃圾堆放的高度\(h(1 \le h \le 25\))和吃进该垃圾能维持生命的时间\(f(1 \le f \le 30)\)，要求出卡门最早能逃出井外的时间，假设卡门当前体内有足够持续\(10\)小时的能量，如果...

洛谷P1171 售货员的难题 题解 题目链接：P1171 售货员的难题 题意：TSP问题。 某乡有\(n\)个村庄(\(1<n \le 20\))，有一个售货员，他要到各个村庄去售货，各村庄之间的路程\(s(0<s<1000)\)是已知的，且\(A\)村到\(B\)村与\(B\)村到\(A\)村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为\(1\)，他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。 题目应该保证了有解。 经典的状压dp 设 \(dp[i][j]\) 表示目前走过的结点的状态为 \(i\) ，现在在 \(j\) 结点 则有 dp[i][j]=min(dp[i][j],dp[i^(1<<(j-1))][k]+g[k][j]) 代码： #include <bits/stdc++.h> using namespace std; // #define int long long // #define INF 0x3f3f3f3f3f3f3f3f #defin...

洛谷P1282 多米诺骨牌 题解 题目链接：P1282 多米诺骨牌 题意： 多米诺骨牌由上下 \(2\) 个方块组成，每个方块中有 \(1\sim6\) 个点。现有排成行的上方块中点数之和记为 \(S_1\)，下方块中点数之和记为 \(S_2\)，它们的差为 \(\left|S_1-S_2\right|\)。如图，\(S_1=6+1+1+1=9\)，\(S_2=1+5+3+2=11\)，\(\left|S_1-S_2\right|=2\)。每个多米诺骨牌可以旋转 \(180°\)，使得上下两个方块互换位置。请你计算最少旋转多少次才能使多米诺骨牌上下 \(2\) 行点数之差达到最小。 对于图中的例子，只要将最后一个多米诺骨牌旋转 \(180°\)，即可使上下 \(2\) 行点数之差为 \(0\)。 注意到我们其实并不关心 \(S_1,S_2\) 的值，而是关心他们的差值 这个绝对值似乎不好处理，其实只要把正负的情况取个min就可以了 设 \(dp[i][j]\) 表示只考虑前 \(i\) 个骨牌，差值为 \(j\) 时的最小翻转数 这里的 \(j\) 定义为 \(S_1-S_...

洛谷P1284 三角形牧场 题解 题目链接：P1284 三角形牧场 题意：和所有人一样，奶牛喜欢变化。它们正在设想新造型的牧场。奶牛建筑师 Hei 想建造围有漂亮白色栅栏的三角形牧场。她拥有 \(n\) 块木板，每块的长度 \(l_i\) 都是整数，她想用所有的木板围成一个三角形使得牧场面积最大。 请帮助 Hei 小姐构造这样的牧场，并计算出这个最大牧场的面积。 显然我们可以枚举两条边的长度，然后用总和减去这两条边的长度就是第三条边的长度 设 \(dp[k][i][j]\) 表示只考虑前 \(k\) 个木板是否可以形成 \((i,j,S-i-j)\) 的划分 则有 \[ dp[k][i][j]=dp[k-1][i][j]\mid dp[k-1][i-a[k]][j]\mid dp[k-1][i][j-a[k]] \] 其中 \(\mid\) 表示二进制的或 然后滚动数组一下就完了 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f...

洛谷P1640 [SCOI2010]连续攻击游戏 题解 题目链接：P1640 [SCOI2010]连续攻击游戏 题意：lxhgww 最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有 \(2\) 个属性，这些属性的值用 \([1,10000]\) 之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。游戏进行到最后，lxhgww 遇到了终极 boss，这个终极 boss 很奇怪，攻击他的装备所使用的属性值必须从 \(1\) 开始连续递增地攻击，才能对 boss 产生伤害。也就是说一开始的时候，lxhgww 只能使用某个属性值为 \(1\) 的装备攻击 boss，然后只能使用某个属性值为 \(2\) 的装备攻击 boss，然后只能使用某个属性值为 \(3\) 的装备攻击 boss……以此类推。现在 lxhgww 想知道他最多能连续攻击 boss 多少次？ 说实话，这题一眼二分图。 左侧点为属性值，右侧点为装备 然后跑个匈牙利算法就好了 如果匹配某个属性值失败就直接跑路退出循环即可 时间复杂度 \(O(k^2),k=\) 最大属性...

洛谷P1772 [ZJOI2006]物流运输 题解 题目链接：P1772 [ZJOI2006]物流运输 题意：物流公司要把一批货物从码头 A 运到码头 B。由于货物量比较大，需要 \(n\) 天才能运完。货物运输过程中一般要转停好几个码头。 物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。 但是修改路线是一件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个 \(n\) 天的运输计划，使得总成本尽可能地小。 输入格式 第一行是四个整数 \(n,m,k,e\) 。\(n\) 表示货物运输所需天数，\(m\) 表示码头总数，\(k\) 表示每次修改运输路线所需成本，\(e\) 表示航线条数。 接下来 \(e\) 行每行是一条航线描述，包括了三个整数，依次表示航线连接的两个码头编号以及航线长度。其中码头 A 编号为 \(1\) ，码头 B 编号为 \(m\) 。单位长度的运输费用为 \(1\)。航线是双向的。 再接下来一行是一个整数 \(d\...

洛谷P1858 多人背包 题解 题目链接：P1858 多人背包 题意：求01背包前k优解的价值和 建议先去读一读《背包九讲》再来看 注意到朴素的 \(01\) 背包是这样转移的 \[ dp[j]=\max(dp[j],dp[j-w[i]]+v[i]) \] 我们可以将其看作两个长度为 \(1\) 的有序队列合并的结果 则考虑记录 \(k\) 优解 在 \(dp[j]\) 的基础上增加一维 \(k\) ，即 \(dp[j][k]\) ，表示 \(k\) 优解 则每次将 \(dp[j][k_1]\) 与 \(dp[j-w[i]][k_2]+c[i]\) 合并 取最优的 \(k\) 个解记录到 \(dp[j][k_i]\) 即可 显然可以用归并排序来搞定 时间复杂度 \(O(nmk)\) 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(2e2+15) #define M (int)(5e3...

洛谷P1944 最长括号匹配 题解 题意：对一个由(,),[,]括号组成的字符串，求出其中最长的括号匹配子串。具体来说，满足如下条件的字符串成为括号匹配的字符串： 1.(),[]是括号匹配的字符串。 2.若A是括号匹配的串，则(A),[A]是括号匹配的字符串。 3.若A,B是括号匹配的字符串，则AB也是括号匹配的字符串。 例如：(),[],([]),()()都是括号匹配的字符串，而][,[(])则不是。 字符串A的子串是指由A中连续若干个字符组成的字符串。 例如，A,B,C,ABC,CAB,ABCABC都是ABCABC的子串。空串是任何字符串的子串。 似乎可以用栈模拟，但是这个太没劲了，考虑dp 设 \(dp[i]\) 表示以 \(s[i]\) 结尾的最长括号匹配长度 显然当 \(s[i]\) 为左括号时 \(dp[i]=0\) 当 \(s[i]\) 为右括号时，\(dp[i]\) 一定与 \(dp[i-1]\) 有关 容易发现 \(s[i-dp[i-1]]\) 是 \(dp[i-1]\) 的起始字符 则当 \(s[i-dp[i-1]-1]\) 与 \(s[i]\) 合法匹配...

洛谷P2170 选学霸 题解 题目链接：P2170 选学霸 题意：老师想从 \(n\) 名学生中选 \(m\) 人当学霸，但有 \(k\) 人实力相当，如果实力相当的人中，一部分被选上，另一部分没有，同学们就会抗议。所以老师想请你帮他求出他该选多少学霸，才能既不让同学们抗议，又与原来的 \(m\) 尽可能接近。 把所有连通块的大小求出来，统计每个大小各有几个连通块 然后二进制优化的多重背包，不过这道题是可行性问题 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(2e4+15) int n,m,k,w[N],p,dp[N],s[N]; namespace MERGE { int f[N],sz[N]; void init(int n){for(int i=1; i<=n; i++)sz[i]=1,f[i]=i;} int f...

洛谷P2158 [SDOI2008] 仪仗队 题解 题目链接：P2158 [SDOI2008] 仪仗队 题意：作为体育委员，C 君负责这次运动会仪仗队的训练。仪仗队是由学生组成的 \(N \times N\) 的方阵，为了保证队伍在行进中整齐划一，C 君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐（如下图）。 现在，C 君希望你告诉他队伍整齐时能看到的学生人数。 稍微画一画图，可以发现我们只要求对角线以下的个数，然后把答案乘 \(2\) 加 \(1\) 即可 把连线看成直角三角形的斜边 可以发现图中对角线以下一共有 \(9\) 个互不成比例的三角形 （ \((1,1)\) 那个算进去，\((1,0)\) 那个不算） 注：因为把 \((1,0)\) 和 \((1,1)\) 那个交换一下，答案不变（不太好讲，意会一下就行） 考虑怎样的三角形可以对答案有贡献 显然是满足底和高互质的三角形，而我们只要计算底>高的情况 问题就转化为了求 \(\sum\limits_{i=1}^{n-1} \varphi(i)\) ，这里的 \(\varphi(i)\) 表...