RainAir
My OI Blog
RainAir

RainAir’s Blog

  NOIP 2019 Bless All!!!!

密码保护:CF 题解汇集

这篇文章受密码保护,输入密码才能看哦

   320   2019-07-13 去围观

「CF835F」Roads in the Kingdom

题目大意 有一棵基环树,现在你需要从基环树上选择一条边被删除,满足: 1. 删除后形成的是一棵树(不是森林) 2. 删除后的直径尽量小 并且求出最小可能的直径 题解 首先基环树求直径大家都会。。。Island 岛屿(虽然由于我太菜至今还没卡常成功) 然后这个题我们…

   51   2019-08-30 去围观

「CF76C」Mutation

题目大意 给出一个由前 $k$ 个大写字母组成的字符串,每次可以花费 $t_i$ 代价删去该字符串中所有的第 $i$ 个大写字母,一个字符串的代价为该字符串每对相邻字符的代价,给出 $k\times k$ 的矩阵表示两个相邻的大写字母的代价矩阵,问有多少种删除方案使得删除的代价…

   54   2019-08-28 去围观

「HDU4626」Jinkeloid

题目大意 多组数据:每组数据给你由前 $20$ 个小写字母组成的长度为 $n$ 的字符串,询问 $m$ 次,每次询问给出不超过 $5$ 个字母,询问满足这些字母的出现次数为偶数的子区间的个数。 $n \leq 10^5,m \leq 3\times 10^4$ 题解 题目英文名字是。。金坷垃?(大雾 首…

   55   2019-08-28 去围观

「CF449D」Jzzhu and Numbers

题目大意 有 $n$ 个元素,求有多少个子集满足它们的按位或的答案是 $0$。 $n,a_i \leq 10^6$ 题解 其实这篇是来水的因为题目比较简单 答案是 $0$ 也就是每一位都是 $0$,发现 $log_2(10^6) \approx 19.9315685693 \leq 20$ ,所以我们可以对于每一位分别容斥。我们…

   65   2019-08-28 去围观

「CF840C」On the Bench

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

   64   2019-08-28 去围观

「CF803F」Coprime Subsequences

题目大意 给长度为 $n$ 的序列,询问有多少个子序列满足它们的 gcd 为 $1$。 题解 其实这篇博客是用来 水 的 (强行刷文章量) 我们设 $f(x)$ 表示 $gcd = x$ 的子序列的数量,那么可以立马启发我们设 $F(x)$ 表示 gcd 是 $x$ 的倍数的子序列数量,如果我们统计出 $…

   64   2019-08-27 去围观

「Gym100548F」Color

题目大意 题意:现在有 $n$ 个格子和 $m$ 种颜色,问你恰好将这些花盆染成 $k$ 种颜色,且同种颜色不相邻的方案数。答案对 $10^9+7$ 取模, $n,m, \leq 10^9,k \leq 10^6$ 心路历程 首先比较 sb 的交了个 $\binom m k k(k-1)^{n-1}$,WA on 2(其实就 $2$ 组数据).…

   87   2019-08-27 去围观

轮廓线 dp 学习笔记

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

   84   2019-08-26 去围观

「BZOJ 4788」[CERC2016]Bipartite Blanket

题目大意 二分图点有点权,定义点集的权值为点权和,统计二分图中有多少个点集,满足被至少一个匹配覆盖。 $n,m \leq 20$ 题解 首先你要知道一个叫做霍尔定理的东西:设 $G$ 中有一组匹配,一端恰好为组成 $X$ 的点的充分必要条件是: $X$ 中的任意 $k$ 个点至少与…

   143   2019-08-26 去围观

「CF833B」The Bakery

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

   152   2019-08-26 去围观
加载更多
标签
近期评论