Q779’s Blog

CF19B Checkout Assistant 题解 题目链接：CF19B Checkout Assistant 题意：Bob 来到一家现购自运商店，将 \(n\) 件商品放入了他的手推车，然后到收银台付款。每件商品由它的价格 \(c_i\) 和收银员扫描它的时间 \(t_i\) 秒定义。 当收银员正在扫描某件商品时，Bob 可以从他的手推车中偷走某些其它商品。Bob 需要恰好 \(1\) 秒来偷走一件商品。Bob 需要付给收银员的最少钱数是多少？请记住，收银员扫描商品的顺序由 Bob 决定。 这个题确实有点难想，因为它的背包容量和物品都是与 \(n\) 有关的 观察题目的性质，我们需要带走所有的 \(n\) 件物品 而第 \(i\) 件物品可以花费 \(c_i\) 的价格带走 \(t_i+1\) 件物品 为什么是 \(+1\) ？因为它本身也会被带走 题目要求的是带走这 \(n\) 件物品的最小花费，可以看出这是一个01背包 但是背包的大小并不是很好确定 因为选择的物品它们的 \(\sum (t_i+1)\) 很可能会超过 \(n\) 那么最多会超过多少呢？不难发现背包容...

CF219D Choosing Capital for Treeland 题解 题目链接：CF219D Choosing Capital for Treeland 题意：Treeland国有n个城市，这n个城市连成了一颗树，有n-1条道路连接了所有城市。每条道路只能单向通行。现在政府需要决定选择哪个城市为首都。假如城市i成为了首都，那么为了使首都能到达任意一个城市，不得不将一些道路翻转方向，记翻转道路的条数为k。你的任务是找到所有满足k最小的首都。 随便找一个点 \(rt\) 跑一遍dfs，求出这个 \(dp[rt]\) 的值 然后 \(dp[u] \to dp[v]\) 的转移显然与 \((u,v)\) 有关 判断一下然后转移一下就没了 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(2e5+15) struct Edge { int u,v,next; ...

CF294B Shaass and Bookshelf 题解 题目链接：CF294B Shaass and Bookshelf 题意：Shaass has \(n\) books. He wants to make a bookshelf for all his books. He wants the bookshelf’s dimensions to be as small as possible. The thickness of the \(i\) -th book is \(t_{i}\) and its pages’ width is equal to \(w_{i}\) . The thickness of each book is either \(1\) or \(2\) . All books have the same page heights. Shaass puts the books on the bookshelf in the following way. First he selects some of the books and put th...

CF346B Lucky Common Subsequence 题解 题目链接：CF346B Lucky Common Subsequence 题意： 通过删除一个字符串中的某些元素而不改变其余元素的顺序，可以派生出该字符串的一个子序列。例如，序列 BDF 是 ABCDEF 的子序列。 字符串的子字符串是该字符串的连续子序列。 例如，BCD是ABCDEF的子串。 现在你得到了两个字符串 \(s_1,s_2\) 和另一个名为 virus 的字符串。你的任务是找到 \(s_1\) 和 \(s_2\) 的最长公共子序列，同时不包含 virus 子字符串。 串长均小于等于 \(100\) 。 升级版的最长公共子序列问题（LCS问题） 考虑增加一维，称为「与 \(c\) 串的匹配度」，即： 设 \(f(i,j,k)\) 表示 \(a\) 串匹配到第 \(i\) 位，\(b\) 串匹配到第 \(j\) 位，且最长公共子序列与 \(c\) 串匹配到第 \(k\) 位的某个串。 显然当 \(a_i \ne b_j\) 时，有 \[ f(i,j,k) \uparrow \max\left\{f...

CF374C Inna and Dima 题解 题目链接：CF374C Inna and Dima 题意： Inna和Dima在商店买了一张 n * m 的桌子，桌子的每一个单元格上都有一个字符，字符集为(“D”,“I”,“M”,“A”)。 Inna实在是太爱Dima了，所以她想在桌子上找出一条最长的路线，使得这条路线中包含尽可能多的Dima的名字（有序，即必须是连续的DIMA）。 Inna的路线选取方式会遵循以下原则： 1.一开始，Inna会在桌子上找到所有的”D”，把他们作为起点。 2.Inna会在当前格子的周围四个相邻的格子中选取一个格子，她会从”D”走到”I”，从”I”走到”M”，从”M”走到”A”。这样，她就认为自己走完了一次Dima的名字。 3.Inna每走完一个格子，就会在该格子四周相邻的四个格子中选一个走，即上下左右四个方向，（当然，她不能走出这张桌子）。Inna从不跳过一个字母。因此，从字母”D”开始，她总是走到字母”I”，从字母”I”开始，她总是走到字母”M”，从字母”M”开始，她总是走到字母”A”，从字母”A”开始，她总是走到字母”D”。 因为桌子的不同，...

CF41D Pawn 题解 题目链接：CF41D Pawn 题意：国际象棋棋盘最底行站了一个兵。 它只有两种行动方式： 向上左或向上右走。 它可以选择从最低行哪个节点开始他的旅程。 每个格子上有0-9颗豌豆，而士兵想移动到最上一行并且积累到尽可能多的豌豆。同时，因为这个士兵必须把豌豆平均分给自己和他的k个兄弟，他所收集到的豌豆必须是k+1的倍数。请找到他可以收集到的最多豌豆，并确定他的操作序列。 规定士兵不能手动扔出豌豆，并且他必须捡起所到达的每一个格子的所有豌豆。 输入格式： 第一行三个整数 \(n,m,k(2 \le n,m \le 100, 0 \le k \le 10)\) 行数、列数、士兵的兄弟们。 接下来一个 \(n \times m\) 的矩阵，每个元素均是0-9的整数（不空格），描述该格的豌豆。第一行被认为是最上一行，最后一行被认为是最下一行。 输出格式： 如果不能收集到k+1倍数的豌豆，输出-1. 否则，输出第一行一个整数，为最多豌豆数；第二行一个整数，为士兵开始移动的位置；第三行包括n-1个字母L 或 R，表示士兵的行动序列。 如果有多种收集到相同且是k+1...

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