比较神奇的dp题.其实也不能算dp辣ovo 有一个神奇的事情是,塔的高度与底层的宽度是负相关的. 所以就变成了问塔底最窄的时候塔有多高. 用f[i]来表示用从第i个砖块到第n个砖块搭起来的塔的最窄底层宽度.用s[i]来表示宽度的前缀和,然后得到一个式子: f[i] = min(s[j-1]) - s[i - 1] (f[j] ≤ s[j - 1] - s[i - 1], j > i) s是单调的.看上去很像是dp呢. 然后就变成了求s[j - 1] - f[j] ≥ s[i - 1]时的最大的s[j - 1].于是开单调队列搞吧ovo
idy居然会开1d-1d这个坑ovo之前听讲的时候也只是觉得很神奇,没有真正手写过,所以不明觉厉. 这个东西需要实际问题实际分析.总的思路就是利用决策的单调性. 对于这题,设f(x)=sqrt(x-j)+a[j].那么显然它是凸的.然后若干个它还可以拼成一个奇怪的凸壳状的分段函数.然后我们要取每段的极值.怎么有种半平面交的变形的感觉. 然后发现每次插入的函数的j单增,既x单增.于是只需要开一个双端出的队列就好了.然后每次二分一下两个函数的交的x坐标.其它时候可以完全单调性搞定. 然后算的时候用double会方便很多. 似乎很有意思啊hhh
似乎是去年省选集训的时候见过啊ovo还记得当年因为把背包写错了所以被唱歌了ovo 比较有意思的题.这个题询问数是骗人的ovo其实是预处理然后O(1)询问. 把如果强行预处理的话时间是O(n3)的.于是考虑一些奇怪的黑暗.把物品强行分块.对于每一个块,可以知道它左边的总答案,右边的总答案.这个是可以O(n2)的.(二进制背包的log就忽略了)然后把左边和右边合并一下,这个是平方的.然后对于块内的每个物品,把其它的物品拿来强行跑一遍背包,这个对于一个物品的复杂度是O(n1.5)的.于是就奇妙地少了O(n0.5)的复杂度.然后就可过了ovo 我当年是怎么想到的ovo还是我当年黑暗过去了ovo
继续填idy的坑ovo 这个题就是比sdoi那个题要麻烦一些.于是我决定把虚树建成真正的树来跑dp.然后这个树形dp似乎没啥麻烦的东西.就是给你一棵有关键点的树求所有点对的距离和,距离min和max. 常数又被吊打ovo无语喽.
idy又开坑辣.居然开的是虚树. 然后发现我好像还是不会ovo我太弱了ovo而且idy自带常数优化+代码长度优化根本打不过ovo 这个题算是相对比较容易的虚树吧.强行模拟一遍缩掉所有没有用的边之后的dfs就好了.中间要讨论一下几个点的祖先关系.yy起来还比较清晰. 然后似乎就没有啥要说的了ovo Upd:早上起来脑洞一开发现似乎不需要讨论当前的点已经在栈里的情况啊ovo
考试的时候do big die去刷bzoj.大概下午会hug zero. sam的第二题.其实这个玩意是应该用sa做的,不过现在我觉得sa没有sam简单.虽然sam的构造和性质还是一团大雾. 这个题可以做出原串的后缀树,然后在上面dp一下.每个点对答案的贡献为任意两个不在同一子树的终态对数*深度. 然后倒过来建sam,它的parent树就是原串的后缀树.虽然我还没有成功理解这个东西. 然后坑了一会的一件事情是新建的nq节点的right集合为空.因为它只是一个扩展点,但是不是一个接受态ovo 我还是太弱啊怎么办.
比较基础的dp。不过因为权限的原因好像做的人不多。 首先肯定先泡便宜的茶再泡贵的茶。 然后记一下上一种茶是啥，连续泡了几次。 于是用f[i][j][k][l]表示泡了i个红茶，j个绿茶，上一种茶是k，连续泡了l次的最小花费。转移是O(1)的。然后后两个反正都要手拆开，所以干脆压下来了。 似乎很水的样子。
<div class="post_brief"><p> 题目名字好长。</p> 当年在考场上只会分块打表的题。 前几天有人讲之后觉得大概可做。而且好像那个方法很优秀。 于是我难得地去写了一回不用记搜且不记上界的数位dp。感觉这个玩意写出来很短，但是思考和调试的复杂度变高了。我觉得是状态定义变得不明确的原因。也许再补一些题就好了。 考虑先让所有都合并到最低位，一个基础数位dp。（然后写丑了好久） 然后考虑如果把一个数字的集合位置从p移动到p+1，设这个数字从低位到高位是a[0]..a[n-1]，那么贡献就是∑a[0..p]-∑a[p+1..n-1]。显然当p从右往左移动的时候它是会先负后正的。如果它负的话就减，否则就不玩了。可以发现它们互相不影响。于是对于每一个p单独计算一遍贡献就行了。 然后还是没有原版跑得快。OTL。 #define PROC "shop" #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int) const int maxn = 53; const int maxm = 509; const int mb = 253; dint l, r; int n, m, bs, a[maxn];...
<div class="post_brief"><p> 插头dp的练手题么。虽然之前还没写过哈密顿回路的题。</p> 学习了一下广义括号法。发现状态数比之前记连通性的方法要少。仔细想想发现，两个连通的插头的顺序有关。不能存在1212这种东西。所以连通性的方法记了很多废状态。那把连通性方法改进一下会不会变得更快呢？可以研究一下。我觉得应该是等效了吧。 今天的debug时间明显缩短了。虽然还是debug了老半天。然后怎么代码还是那么长。想起我每次都觉得把东西挤到一起看起来很不雅观，于是去写一堆找转移的函数。晕。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int) const int maxn = 15; const int maxst = 50009; #define mbit(x,y) ((x)<<((y)<<1)) #define gbit(x,y) (((x)>>((y)<<1))&3) #define cbit(x,y) ((x)&(~(3<<((y)<<1)))) int n, m, tots, slst[maxst]; bool mp[maxn][maxn]; dint f[2][maxst]; void dfsState(int l, int c, int z) { if (l == m + 1) { if (!...
<div class="post_brief"><p> 居然网上都没有找到程序来和我拍。好吧其实它是一道权限题而且过的人也不多。</p> 其实就是裸的插头DP。本来想学一下广义括号的然后被状态数吓到了于是只好还是写最小表示。连通性。 然后我发现最小表示连通性很容易写挂。而在findstate的时候检查一下是个不错的办法。至少这道题靠这个就可以直接debug出来问题了。 比上次写插头要好许多了。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long dint; #define _l (long long int) #define mbit(x,y) ((_l x)<<((y)<<2)) #define gbit(x,y) (((x)>>((y)<<2))&0xf) const int maxn = 13; const int maxst = 570009; dint slst[maxst]; int n, m, v[maxn][maxn], tots, f[2][maxst], cnt[17]; bool av[2][maxst]; void dfsState(int l, int tot, dint z) { if (l == m) { for (int i = 1; i <= tot; ++ i) if (cnt[i] !...