时光怎不经一生
浮浮沉沉已半生
一壶浊酒欲随风
一步一瞥似惊鸿
情字要如何追问
一指兰花为谁挽留
\(\text{[ARC147D]Sets Scores}\)
\(\color{green}{\text{[EASY]}}\)
考虑一种令集合之间相差的数的数列为 \(x\) , 若确定一个 \(x\) 和 \(S_1\) 则确定整个集合序列, 对于一个确定的 \(x\) , 有 \(2^m\) 个可能的 \(S_1\) .
令 \(A_x\) 为 \(S_1\) 中有 \(x\) 这个数时的集合数量, \(B_x\) 则为没有 \(x\) 的集合数量, 则数列 \(x\) 所能构造出的集合序列分数和为 \((A_1+B_1)(A_2+B_2)\cdots(A_m+B_m)=n^m\) .
数列 \(x\) 总共有 \(m^{n-1}\) 种, 则答案为 \(n^m\times m^{n-1}\) .
\(\text{[ARC111E]Simple Math 3}\)
\(\color{green}{\text{[EASY]}}\)
大概是求个这种东西 \(\sum\limits_{i=1}^{lim}{\frac{Ci+A}{D}-\frac{Bi+A-1}{D}}\) , 类欧几里得即可.
\(\text{[ARC101D]Robots and Exits}\)
\(\color{green}{\text{[EASY]}}\)
不用管只有一个出口的, 把一个机器人的两个可能的出口看作 \((a,b)\) , 机器人移动左右的最远距离看成 \((x,y)\) , 每次可能变成 \((x+1,y)\) 或者 \((x,y+1)\) , 变成二维偏序问题了, 设 \(f_i\) 表示第 \(i\) 个机器人出去的方案数, \(f_i=\sum\limits_{a_j<a_i,b_j<b_i}{f_j+1}\) .
时间复杂度 \(\mathcal{O}(n\log{n})\) .
\(\text{[ARC071D]Infinite Sequence}\)
\(\color{green}{\text{[EASY]}}\)
正着 \(dp\) 有后效性, 倒着就没了, 设 \(f_i\) 表示考虑了 \(i\sim n\) 的填法的方案数.
注意到只有填了 \(1\) 才有拓展的空间, 如果两个连续位置都不是 \(1\) , 那只能是 \(xyyyyyy\dots\) , 转移分别是第 \(i\) 位为 \(1\) , 第 \(i\) 为不唯一但第 \(i+1\) 位为 \(1\) 和第 \(i\) 位和第 \(i+1\) 位都不为 \(1\) , 后缀和优化, 时间复杂度 \(\mathcal{O}(n)\) .
\(\text{[ARC073D]Many Moves}\)
\(\color{green}{\text{[EASY]}}\)
貌似很套路, 但还是想了蛮久.
注意到我们不需要知道到底是哪个棋子在询问位置上, 所以设 \(f_{i,j}\) 表示做完前 \(i\) 个询问, 一个棋子在 \(x_i\) , 另一个在 \(j\) 的最小值.
\[f_{i,j}=f_{i-1,j}+|x_i-x_{i-1}|\\ f_{i,x_{i-1}}=\min\{f_{i-1,j}+|j-x_i|\} \]放在线段树上, 第一个操作是全局加, 另一个把绝对值拆开, 维护 \(f_{j}+j\) 和 \(f_{j}-j\) 即可.
时间复杂度 \(\mathcal{O}(n+q\log{n})\) .
\(\text{[AGC009D]Uninity}\)
\(\color{red}{\text{[HARD]}}\)
不可多得的贪心好题啊.
最优解一定是最优的点分数的最大深度.
考虑这棵树形成的过程, 初始点的 \(tag\) 均为 \(0\) , 每次合并时变为 \(k\) , 对于一对点, 若 \(tag_u=tag_v\) , 则 \(u\) 到 \(v\) 的路径上一定存在一个点的 \(tag\) 大于它们.
考虑贪心的从叶子往根选, 每个选可行的最小值即可保证正确, 记集合 \(s_x\) 为在 \(x\) 子树中已经存在且到 \(x\) 还没有比它大的集合.
首先 \(tag_x\) 要满足两点,
- \(y\in son_x\) , 则 \(tag_x\not \in s_x\) .
- \(y_1,y_2 \in son_x\) , 则 \(tag_x > \max\{s_{y_1}\cap s_{y_2}\}\) .
若不满足 \(1\) , 则其子树到 \(x\) 不满足; 若不满足 \(2\) , 则两个子树通过 \(x\) 连通不满足.
此时我们已经知道了 \(tag_x\) , 可以根据子树信息推出 \(s_x\) , 时间复杂度 \(\mathcal{O}(n)\) .
\(\text{[ARC120E]1D Party}\)
\(\color{blue}{\text{[NORMAL]}}\)
注意到还是不难的, 首先不可能停下, 一定是朝一个方向见到一个人再变向, 进一步不变向继续走也是一样的.
注意到放到坐标轴上是形成三角形, 所以要最小化高度, 不难列出一个 \(\mathcal{O}(n^2)\) 的 \(dp\) , 设 \(f_i\) 表示以 \(i\) 结尾的最低高度.
只有常数项有用, 所以复杂度 \(\mathcal{O}(n)\) .
\(\text{[ARC111F]Do you like query problems?}\)
\(\color{blue}{\text{[NORMAL]}}\)
受教了, 先转期望乘上方案数做题.
\[ans=\sum_{j=1}^{q}{\frac{1}{2m+1}{E}}=\sum_{j=1}^{q}{\frac{1}{2m+1}\sum_{i=1}^{n}{\frac{i(n-i+1)}{\frac{ n(n+1)}{2}}E(a_{i,j})}}\\ =\sum_{j=1}^{q}{\frac{1}{2m+1}\sum_{i=1}^{n}{\frac{i(n-i+1)}{\frac{ n(n+1)}{2}}\sum_{k=1}^{m-1}{P(a_{i,j}\geqslant k)}}} \]对于一个点有效的操作概率是 \(P_i=\frac{m}{2m+1}\times \frac{i(n-i+1)}{\frac{n(n+1)}{2}}\) , 所以 \(P(a_{i,j}\geqslant k)=(1-(1-P_i)^{j-1})\frac{m-k}{m}\) .
\[ans=\frac{m-1}{(2m+1)n(n+1)}\sum_{i=1}^{n}{i(n-i+1)\sum_{j=1}^{q}{(1-(1-P_i)^{j-1})}} \]后面是等比数列求和, 时间复杂度线性对数.
\(\text{[ARC112E]Cigar Box}\)
\(\color{green}{\text{[EASY]}}\)
好像也不是很难, 为什么我想不出呢, orzxy.
注意到只有最后一个操作是有用的, 同时注意到, 最终的序列一定是这样的形式, 可以分成三部分, 左边一部分放是最终操作移动到左边的数, 右边一部分是最终操作移动到右边的数, 中间是从来没有被移动过的数, 并且中间部分是单调递增的.
这时我们可以 \(\mathcal{O}(n^2)\) 的枚举左边和右边的个数 \(L\) , \(R\) , 并且期望快速计算这种情况下移动的方案数.
这相当于我们给 \(m\) 个元素上颜色, 颜色为 \(1\sim L+R\) , 并且每种颜色都要有, 相当于我们把 \(m\) 个球放进 \(L+R\) 个无标号的盒子中, 并令盒子的编号为盒子中的序号最大的球的序号, 并给盒子排序, 这样即可一一对应一种移动方案, 同时我们需要钦定这 \(L+R\) 个颜色哪些左移哪些右移, 并且我们只需要最后一个操作是我们钦定的方向即可, 之前的颜色相同的可以任意方向, 所以一个局面的移动方案即为
\[\begin{Bmatrix}m\\L+R\end{Bmatrix}\binom{L+R}{L}2^{m-L-R} \]时间复杂度 \(\mathcal{O}(n^2)\) .
\(\text{[ARC087F]Squirrel Migration}\)
\(\color{red}{\text{[HARD]}}\)
这为什么想的出来啊.
对于一条边, 它把树分成两个部分 \(s_1\) 和 \(s_2\) , 不妨设 \(|s_1|\leqslant |s_2|\) , 那么这条边最多被经过 \(2|s_1|\) 次.
最大值即等价于, 将重心 \(G\) 拉出来, \(\forall u\in son_G,v\in subtree_u,p_v\not \in subtree_u\) .
所以可以容斥求答案, 设 \(f_i\) 表示钦定 \(i\) 个点不满足条件的方案数, 则答案即为 \(\sum{(-1)^if_i(n-i)!}\) , \(f_{i}=\binom{x}{i}^2i!\) , 其中 \(x\) 为该子树的大小.
求 \(f\) 树上背包即可, 时间复杂度 \(\mathcal{O}(n^2)\) .
青山常伴绿水
燕雀已是南飞
美人画卷残留一丝青灰叹余美
回忆斑驳微醉
叹相思未随
几春几秋几段轮回
标签：Atcoder,frac,试题,color,text,sum,Part4,mathcal,复杂度 From： https://www.cnblogs.com/Lonely923/p/16732584.html