首页 > 其他分享 >ARC180 部分简要题解

ARC180 部分简要题解

时间:2024-07-31 12:53:11浏览次数:13  
标签:简要 frac limits ARC180 int 题解 sum right left

C

设 \(f_{i, j}\) 为考虑前 \(i\) 个数,当前选出来的子序列和为 \(j\) 且强制最后一个选出来的数不为 \(j\) 的方案;设 \(g_{i, j}\) 为考虑前 \(i\) 个数,当前选出来的子序列和为 \(j\) 且强制最后一个选出来的数必为 \(j\) 的方案。注意到一个合法方案可以唯一与一个最后一个选出来的数会变的方案对应(不断删掉最后一个选出来但没变的数,结果不变,注意这里包括全部都不选),于是有转移:

\[f_{i, j} = f_{i - 1, j}(j = a_i) \\ f_{i, j} = f_{i - 1, j} + f_{i - 1, j - a_i} + g_{i - 1, j - a_i}(j \ne a_i) \\ g_{i, j} = g_{i - 1, j}(j \ne a_i) \\ g_{i, j} = f_{i - 1, 0}(j = a_i) \]

E

非常漂亮的一道题。首先反过来考虑,求出使用不超过 \(c\) 的代价能得到的最大分数。

不妨先考虑 \(c = 0\),相当于要满足 \(n\) 条关于每个位置上逆序对的条件。考虑 \(\rm dp\),令 \(f_{i, j}\) 为近考虑排列前 \(i\) 个元素的相对顺序,以相对大小第 \(j\) 小的元素作为结尾的最长上升字序列长度,转移考虑第 \(i\) 个位置的排名,排列插入式转移。

\[f_{i, j} = \max \begin{cases} f_{i - 1, j - 1} \\ f_{i - 1, j} (i - j - 1 \ge a_i) \\ \max\limits_{k < j} f_{i - 1, k} + 1 (i - j \ge a_i) \end{cases} \]

注意到去掉 \(f_{i - 1, j}\) 对应方案的最后一个元素,一定是 \(f_{i - 1, k}(k < j)\) 的一个方案,于是转移二包含于转移三。

为了方便转移三,修改 \(\rm dp\) 定义:令 \(f_{i, j}\) 为近考虑排列前 \(i\) 个元素的相对顺序,以相对大小 不大于 第 \(j\) 小的元素作为结尾的最长上升字序列长度。于是转移可以修改为:

\[f_{i, j} = \max(f_{i - 1, j - 1} + [i - j \ge a_i], f_{i, j - 1}) \]

为了方便令 \(j' = i - j + 1\) 于是:\(f_{i, j'} = \max(f_{i - 1, j'} + [j' \ge a_i + 1], f_{i, j' + 1})\).

由于 \(f_{i, j' + 1} \le f_{i, j'} \le f_{i, j' + 1} + 1\),于是我们可以考虑 \(f_{i, j'} = f_{i, j' + 1} + 1\) 的断点 \(j’\)。于是转移可以看作是添加断点 \(i\),然后删除 \(\le a_i\) 的最大断点。最终答案为断点的个数。

再考虑 \(c \ne 0\) 的情况,这等价于去掉任意 \(c\) 个限制(将对应 \(a_i \leftarrow 0\))之后的相同问题,于是我们来分析上述加删断点的过程。

首先,由于 \(a_i < i\),可以一开始将所有断点 \(\{1, 2, \cdots, n\}\) 添加好,然后按顺序进行删除。

按照 \(a_i\) 从大到小考虑每次删除,设最大和严格次大的 \(a_i\) 分别为 \(v_1, v_2\),所有删除 \(v_1 \le i < v_2\) 断点的行为均可提到最前完成,不影响结果。而接下来从 \(v_2\) 开始删除的断点,\(a_i = v_1\) 的那些位置就完全等同于 \(a_{i'} = v_2\) 的那些位置,递归进行上述操作。于是原本按顺序的删除转化为了上面固定的从大到小的删除,于是原问题 \(a_i\) 给出的顺序就并不重要了。

再考虑将哪些 \(a_i \leftarrow 0\) 能使断点更多:对 \(a_i > a_j\),分别考虑两种方案,一种 \(a_i \leftarrow 0\) 一种 \(a_j \leftarrow 0\);前者将 \(a_j\) 这个删除放到最后,后者将 \(a_i\) 这个删除放到最后;轮到最后一次删除时前者能删的后者一定也能删,故前者不劣。于是一定是选择最大的 \(c\) 个 \(a_i \leftarrow 0\)。

由于删除的顺序不重要,于是可以按照从小到大的顺序依次删,这样就可以求出所有去掉最大 \(c\) 个 \(a_i\) 的结果了,这个过程可以直接线性维护。

F

原代价等价于将连乘拆开,\(\forall i\) 选一个 \(x_j ^ A(i < j \le n + 1, x_{n + 1} = 1)\) 乘起来相加。如果 \(i\) 选择了 \(x_j ^ A\),从 \(i \to j\) 连边构成一颗有根树。

原问题变成随机 \(n\) 个 \([0, 1]\) 中的实数,排序后,对所有合法有根树求所有 \(i \to j\) 这些边 \(x_j ^ A\) 的乘积的和。不妨将顺序倒过来,先确定排序后合法的树结构,再考虑符合树结构的方案。

枚举根节点下子树的集合划分 \(S_1, S_2, \cdots, S_m\),为了使规模减小,枚举这些子树根的权值分别为 \(x_{r_1}, x_{r_2}, \cdots, x_{r_m}\)。

问题转化为了限制随机上界不一定为 \(1\) 的子问题,但这样并不方便直接求。

再转化一下原问题,将权值修改为 \(\prod\limits_{i = 1} ^ n \left(y ^ A + \sum\limits_{j = i + 1} x_j ^ A\right)(x_1 \le x_2 \le \cdots \le x_n \le y)\) 这样的齐次式,接下来的计算就会方便很多。

因为原问题可以转化成钦定生成的随机数递增,根据对称性答案为:

\[\begin{aligned} a_n(y) &= n!\int_0 ^ y \int_{x_1} ^ y \cdots \int_{x_{n - 1}} ^ y \prod\limits_{i = 1} ^ n \left(y ^ A + \sum\limits_{j = i + 1} x_j ^ A\right) \mathrm{d} x_1 \mathrm{d} x_2 \cdots \mathrm{d} x_n \\ &= n!y ^ {n(A + 1)}\int_0 ^ y \int_{x_1} ^ y \cdots \int_{x_{n - 1}} ^ y \prod\limits_{i = 1} ^ n \left(1 + \sum\limits_{j = i + 1} \left(\frac{x_j}{y}\right) ^ A\right) \mathrm{d} \left(\frac{x_1}{y}\right) \mathrm{d} \left(\frac{x_2}{y}\right) \cdots \mathrm{d} \left(\frac{x_n}{y}\right) \\ &= n!y ^ {n(A + 1)}\int_0 ^ 1 \int_{x_1} ^ 1 \cdots \int_{x_{n - 1}} ^ 1 \prod\limits_{i = 1} ^ n \left(y ^ A + \sum\limits_{j = i + 1} x_j ^ A\right) \mathrm{d} x_1 \mathrm{d} x_2 \cdots \mathrm{d} x_n = a_n(1)y ^ {n(A + 1)} \\ \end{aligned} \]

是关于 \(y\) 的单项式!再回到递归求解的部分,为了方便集合划分的枚举,考虑 \(\rm EGF\) 添加集合大小占位符 \(x\),令 \(f(x, y) = \sum\limits_n \frac{a_n(y)}{n!}x^n\)。

对每个集合内部需要先钦定根,然后枚举根随机的实数,故集合内部的 \(\rm EGF\) 为:

\[y ^ A\sum\limits_n \frac{(n + 1)\int_0 ^ y a_n(t) \mathrm{d}t}{(n + 1)!}x ^ {n + 1} = xy ^ A\int_0 ^ y f(x, t) \mathrm{d}t \]

由 \(\exp\) 组合意义,\(f(x, y) = \exp\left(xy ^ A\int_0 ^ y f(x, t) \mathrm{d}t\right)\),故:

\[f(x, y) = \exp\left(xy ^ A \int_0 ^ y \sum\limits_n \frac{a_n(1)t ^ {n(A + 1)}}{n!}x ^ n \mathrm{d}t \right) = \exp\left(\sum\limits_n \frac{a_n(1)}{n!(n(A + 1) + 1)}x ^ {n + 1}y ^ {(n + 1)(A + 1)} \right) \]

注意到 \(f(x, y) = \sum\limits_n \frac{a_n(1)}{n!}(xy ^ {A + 1}) ^ n\),令 \(z = xy ^ {A + 1}, b_n = \frac{a_n(1)}{n!}\),由上式,令:

\[g(z) = \sum\limits_n b_nz ^ n = f(x, y) = \exp\left(\sum\limits_n \frac{b_n}{n(A + 1) + 1}z ^ {n + 1} \right) \]

两边求导得递推式:

\[\begin{aligned} & g'(z) = \sum\limits_n (n + 1)b_{n + 1}z ^ n = \left(\sum\limits_n b_nz ^ n\right)\left(\sum\limits_n \frac{(n + 1)b_n}{n(A + 1) + 1}z ^ n\right) \\ &\Rightarrow b_{n + 1} = \frac{1}{n + 1}\sum\limits_i ^ n \frac{(i + 1)b_ib_{n - i}}{i(A + 1) + 1} \end{aligned} \]

直接暴力即可,复杂度 \(\mathcal{O}(n ^ 2)\),也可以用半在线卷积优化到 \(\mathcal{O}(n \log ^ 2 n)\)。

标签:简要,frac,limits,ARC180,int,题解,sum,right,left
From: https://www.cnblogs.com/Go7338395/p/18334385

相关文章

  • P10814 【模板】离线二维数点 题解
    题目传送门思路一眼主席树板子题,但是一看数据范围\(n,m\le2\times10^6\),似了。在线做法应该是似完了,考虑离线做法。我们知道树状数组是可以做二维偏序的,大家应该都知道一个经典问题:对于一个序列,多次询问下标\(\lea\)且数值\(\leb\)的数的个数。回到这道题,相比上面......
  • P2163 [SHOI2007] 园丁的烦恼 题解
    题目传送门题目大意:在一个平面直角坐标系上,给定\(n\)个点的坐标\((x,y)\),\(m\)次询问,每次询问一个矩形范围内的点的数量,此矩形用\(\{a,b,c,d\}\)来描述,其中\((a,b)\)为左下角,\((c,d)\)为右上角。思路:不难将题目转化为:给定一个长度为\(n\)的序列,序列中的每个元......
  • CF1997(edu168)题解 A-F
    A.StrongPassword注意到最大效果是在两个相同字符之间插入一个不同的,贡献为3。否则在一开始插入一个和首位不同的,贡献为2。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;voidsolve(){strings;cin>>s;boolok=0;for(inti......
  • 【题解】2024牛客多校第5场
    E安https://ac.nowcoder.com/acm/contest/81600/E分析简单博弈/思维题。当ai>bi时,当前骑士一定存活。当ai<bi时,当前骑士一定死亡。为了使得自己存活的骑士尽可能多,若存在ai=bi的情况,一定会选择令该骑士去攻击对方,并且双方均会轮流优先选择此类骑士。......
  • 07-30 题解
    07-30题解A朴素的想法$dp(i,j,k)$表示考虑到第\(i\)位,前\(i\)位的和为\(j\),第\(i\)位的值为\(k\)然后咋转移?重新定义移动小球的方式:从自己右边的邻居拿过来正数个球拿过来负数个球(即往右边的邻居放正数个球)在第2种操作中,我们拿走的球会被后面放过来......
  • Luogu P1983 车站分级 题解 [ 绿 ] [ 拓扑排序 ] [ 图论建模 ] [ 虚点 ]
    车站分级:很好的拓扑排序题,细节有点多。图论建模首先观察对于一条线路,我们可以从中直接得到什么信息:假设这条线路的开头为\(st\),结尾为\(ed\),那么在\([st,ed]\)的车站中,没有被选入线路的点一定比选入线路的点的级数至少少\(1\)。对于这一点条件,我们就可以建模了。......
  • CF538H Summer Dichotomy 题解
    Description有\(T\)名学生,你要从中选出至少\(t\)人,并将选出的人分成两组,可以有某一组是空的。有\(n\)名老师,每名老师要被分配到两个小组之一,对于第\(i\)名老师,要求所在的小组中的学生人数\(\in[l_i,r_i]\)。此外,有\(m\)对老师不能在同一个小组中。你需要判断能否......
  • SP8099 TABLE - Crash´s number table 题解
    题目传送门前置知识一般的积性函数|数论分块|莫比乌斯反演解法令\(n\lem\)。考虑莫比乌斯反演,推式子,有\(\begin{aligned}&\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\operatorname{lcm}(i,j)\\&=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\frac{ij}{\gcd(i,j)......
  • 题解:Pinely Round 4 (Div. 1 + Div. 2) A
    A.MaximizetheLastElementtimelimitpertest:1secondmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputYouaregivenanarray\(a\)of\(n\)integers,where\(n\)isodd.Inoneoperation,youwillremovetwoa......
  • P4449 于神之怒加强版 (题解)
    题目链接P4449于神之怒加强版题目大意:求\[\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)^k\]\(数据范围n,m\leq5e6\)\(二话不说,先开导式子(假定n<m):\)\begin{aligned}ans&=\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)^k\\\end{aligned}\[先套路地枚举d=gcd(i,j)\]\begin{align......