RainAir
My OI Blog
RainAir

动态规划
文章归档

「CF599E」Sandy and Nuts

题意 给你若干限制,限制为 $lca(u,v) = c$ 和 $(u,v)$ 有连边,数一下以一为根的满足限制的树的个数。 $n \leq 13$,限制总数 $\leq 100$ 题解 这个题目太神仙了。。远古 CF 场的题目还是好。 考虑设 $f_{v,S}$ 表示 $v$ 节点子树内的点是 $S$ 的树的个数。答案是 …

   213   2019-10-11   213 去吊打作者

「CF388D」Fox and Perfect Sets

题意 定义一个集合 $S$ 是好的,当且仅当: 1. $\forall x\in S,y \in S $ 有 $x \oplus y \in S$,这里 $\oplus$ 是异或操作。 2. 集合最大值 $\leq n$ 求这样的集合的个数,模 $10 ^9+7$ 题解 这是个好题(至少我觉得我是想不出来) 首先一个观察是这样的集合一…

   176   2019-10-08   176 去吊打作者

「CF840C」On the Bench

题目大意 给你一个长度为 $n$ 的序列,问你有多少种置换,使得置换后的序列相邻两项的乘积都不是平方数。 题解 这个题目好像比较厉害的样子。。首先把这些数按照是否能组成平方数分组,同一组里都是两两相乘能凑成平方数的,可以证明存在这样的分配方案。 然后我们…

   204   2019-08-28   204 去吊打作者

轮廓线 dp 学习笔记

轮廓线 dp 也是一种状压,适用于一维特别大而另一维特别小的情况。 我们来从一道经典例题入手:求 $1 \times 2$ 的骨牌填满 $n \times m $ 的矩形的方案数。 如果 $n,m \leq 11$ 那么当然可以轻松状压了,但是如果 $n = 10^5$ ,我们就要考虑使用轮廓线 dp 了。 设 $f_…

   271   2019-08-26   271 去吊打作者

「CF833B」The Bakery

题目大意 把 $n$ 个数分成 $k$ 个区间,每个区间的价值为区间内不同数字的个数,问价值和最大为多少。 题解 简单 dp:设 $f_{i,j}$ 表示前 $i$ 个数 分了 $j$ 段的价值和最大是多少。我们记 $cnt_{l,r}$ 表示 $[l,r]$ 的不同的数的数量,那么有转移 $$f_{i,j} = …

   346   2019-08-26   346 去吊打作者

DDP 学习笔记

DDP(动态 dp),是通过将状态改写成矩阵,然后定义具有结合律的与转移等价的运算,用数据结构快速维护的一种方法。在 NOIP2018 时作为 Day2 T3 出现。 NOIP2018 Day2T3 - 保卫王国 考场上根本不会...那个时候我是连暴力 dp 都不会的菜鸡,现在回来学一学。 我们来找一…

   398   2019-07-11   398 去吊打作者

ZROI466小 G 的数

最近从某个地方看到了这个题。。。所以回来补一下题解。 题目描述 题解 直接求期望不太好求,我们可以考虑求出每一种条件下的概率,最后乘上直径长度就可以了。 我们设 $f_{i,j,k}$ 表示在以 $i$ 为根的子树里,目前不跨过 $i$ 节点的最长链是 $j$,子树的直径是…

   327   2019-07-08   327 去吊打作者

「NOI2005」瑰丽华尔兹

题目链接 题目大意 现在有一个 $n\times m$ 的矩阵,给定的起始点上有个钢琴,矩阵上有些方格是障碍物,用连续的区间 $[l,r]$ 和一个参数 $d$ 表示在时间 $[l,r]$ 时会向 $d$ 方向滑动(上下左右),当然每个时间点可以选择让钢琴不动,不允许钢琴超出边界或者碰到障…

   280   2019-07-07   280 去吊打作者

HDU 3480 Division

题目链接 题意 有长度为 n 的序列,定义一个集合的代价是$(MAX-MIN)^2$,要求你找出 m 个集合,在满足下面图片的限制的情况下,使得总代价最小。 多组数据,每组数据 $n \leq 10^4,m \leq 5 \times 10^3$,保证答案在 int 范围内。 题解 观察题目 发现让你选取 M …

   242   2019-07-06   242 去吊打作者

「BZOJ2553」「BJOI2011」禁忌

题目链接 题目描述 题目大意:给你前 $alphabet$ 个小写字母组成的字符集,以及 $n$ 个单词,定义一个串 s 的禁忌值为 $\sum_{i} [s[i] == Taboo[i]]$,其中 $Taboo[i]$ 是第 $i$ 个单词(禁忌值也就是找到一种分割字符串的方法 使得出现这N个字符串的次数最多的次数…

   385   2019-05-01   385 去吊打作者
加载更多
标签
近期评论