RainAir
My OI Blog
RainAir

RainAir’s Blog

  CSP 2019 Bless All!!!!

「CF860E」Arkady and a Nobody-men

题目描述 给 $n$ 个节点的树。定义 $g(a,b)$ 表示 $a$ 的子树中除 $b$ 之外深度不超过 $b$ 的节点个数,定义 $f(v) = \sum_{x \in anc(v)} g(x,v)$ (其中 $anc(v)$ 是 $v$ 的祖先组成的集合)。 现在要对于每一个点,求出 $f(v)$ $n \leq 10^5$ 题解 如果这题 $n \le…

   62   2019-10-09   62 去吊打作者

「CF908D」New Year and Arbitrary Arrangement

题目大意 一开始序列为空。每次你有 $P_a$ 的概率往序列末尾添加一个a,有 $P_b$ 的概率往序列末尾添加一个b。当子序列ab的出现次数 $\geq K$ 时停止,问子序列ab的期望出现次数。 保证有 $P_a+P_b = 1$(显然) 题解 考虑 dp,设 $f_{i,j,k}$ 表示拿了 $i$ 个 a,$j…

   88   2019-10-09   88 去吊打作者

「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$ 题解 这是个好题(至少我觉得我是想不出来) 首先一个观察是这样的集合一…

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

ZROI1121 小E和小F strikes again

题目 2019 十一权限 题解 每次小 E 肯定会选择获胜概率最大的那个颜色,我们首先考虑如何算出这个概率。 首先题目里的排列形式是没有意义的,可以通过组合数来变成选取一些数。 首先 如果对于颜色 $c$ ,它总共有 $a_c$ 个,这次小 E 手里这个颜色的数的的数量为 $…

   115   2019-10-01   115 去吊打作者

「CF835F」Roads in the Kingdom

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

   158   2019-08-30   158 去吊打作者

「CF76C」Mutation

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

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

「HDU4626」Jinkeloid

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

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

「CF449D」Jzzhu and Numbers

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

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

「CF840C」On the Bench

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

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

「CF803F」Coprime Subsequences

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

   182   2019-08-27   182 去吊打作者
加载更多
标签
近期评论