分类 题解 下的文章
- 首页
- 题解
UVa11600 Masud Rana
UVaLuogu分析不会做，自闭了 /kk首先把本来就能到达的城市缩成一个点。设 $dp_{i,S}$ 表示当前在第 $i$ 个点，已经打通了 $S$ 中城市的期望天数。设 $num$ 为 $S$ 中城市的数目，$cnt_i$ 为第 $i$ 个点的城市数目，可以写出转移然后 $S$ 很大，un...
UVa12235 Help Bubu
UVaLuogu分析因为书本的高度最多只有 $8$ 种，所以可以考虑状压 DP 。设 $dp_{i,j,S,l}$ 表示前 $i$ 本书，拿掉了 $j$ 本，拿掉的高度集合是 $S$ ，最后拿的高度是 $l$ 的最小混乱度。转移讨论一下当前的拿掉还是不拿掉就好了。然后如果一种高度全部被拿掉了，...
UVa1407 Caves
UVaLuogu分析设 $dp_{i,j,0/1}$ 表示以 $i$ 为根的子树，经过 $j$ 个点，最后不回到 / 回到 $i$ 的最小距离。转移类似于树形背包，边界是 $dp_{i,1,0}=dp_{i,1,1}=0$ 。询问的话就找到最大的使得 $\min\{dp_{1,i,0},dp_...
UVa1437 String painter
UVaLuogu分析比较奇妙的 DP 题...设 $g_{i,j}$ 表示空串刷成 $B_{i..j}$ 的最小次数，转移很简单。然后设 $f_i$ 表示 $A_{1..i}$ 刷成 $B_{1..i}$ 的最小次数。转移也比较简单。然后答案就是 $f_n$ 。感觉这题的难点不在转移而在思想....
UVa12099 The Bookcase
UVaLuogu分析设 $dp_{i,j,k}$ 表示前 $i$ 本书，第一层宽度为 $j$ ，第二层宽度为 $k$ 时，第二三层的高度的最小值。转移直接枚举放在哪一层即可。然而有个问题，我们并不知道某一层原来的高度。所以我们先把所有书按高度从大到小排序。边界就是 $dp_{1,0,0}=0$...
SPOJ GSS 系列简要题解
GSS1线段树上维护以下 $4$ 个东西：区间和区间最大前缀和区间最大后缀和区间最大子段和合并两个区间应该比较简单，这里不再赘述。GSS2这题就很神仙了。把所有询问离线并按右端点排序，然后从左往右扫。对于线段树的每个叶子节点 $[i,i]$，假设当前扫到了 $p$ ，那么该节点存的是 $\di...
SPOJ QTREE 系列简要题解
QTREE1把 $(fa_i,i)$ 的边权作为 $i$ 的点权，然后就是个树剖板子了...但是注意查询时 LCA 是不能查的，需要判一下。而且这题竟然不能交 C++ ，然后我改了半个小时才把 C++ 改成 C QAQQTREE2DIST 操作只需要维护树上前缀和即可求出答案。KTH 操作大力...
Educational Codeforces Round 69 题解
比赛地址我真的什么都不会了嘤嘤嘤DIY Wooden Ladder语文题设次大的 $a$ 为 $x$ 。那么显然答案为 $\min\left\{n-2,x-1\right\}$ 。代码Pillars从大到小考虑所有盘子，如果它到最大的那个盘子中没有比它小的就可以移过去。写一个 ST 表 / 线...
CF743C Vladik and fractions
CodeforcesLuogu分析观察样例可以得到一组合法的解为 $x=n,y=n+1,z=n(n+1)$ 。证明：注意到 $n=1$ 时 $n+1=n(n+1)$ ，所以 $n=1$ 时无解。代码// =================================== // auth...
CF1172D Nauuo and Portals
CodeforcesLuogu分析思想很妙的构造题。考虑把一个 $n\times n$ 的问题削成一个 $(n-1)\times (n-1)$ 的问题。那么我们只要满足掉第一行和第一列即可。如果已经满足了，什么都不要做；如果没有满足，在对应位置放一对传送门让第一行、第一列满足即可。如果懒的话时...