2020-2021:teams:legal_string:jxm2001:contest:arc_127
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:contest:arc_127 [2021/09/26 21:45] jxm2001 |
2020-2021:teams:legal_string:jxm2001:contest:arc_127 [2021/09/27 16:52] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 98: | 行 98: | ||
| c.push_back(make_pair(a[i], b[i])); | c.push_back(make_pair(a[i], b[i])); | ||
| solve(c, MAXD); | solve(c, MAXD); | ||
| + | enter(ans); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== E - Priority Queue ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定一个长度为 $n+m$ 的操作序列，有 $n$ 次 $\text{push}$ 操作和 $m$ 次 $\text{pop}$ 操作。 | ||
| + | |||
| + | 操作过程中维护一个大根堆的优先队列，同时 $\text{push}$ 的所有元素恰好是 $1\sim n$ 的一个排列。问最后优先队列中的元素集合的种数。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 不难构造出令最后优先队列中剩余元素尽可能大的方案：第 $i$ 次 $\text{push}$ 元素 $i$。 | ||
| + | |||
| + | 假定上述方案最后得到的优先队列的元素为 $a_1\lt a_2\lt \cdots a_{n-m}$，被删除的元素为 $b_1\lt b_2\lt \cdots b_m$。 | ||
| + | |||
| + | 对任意一个方案，假定最后得到的优先队列的元素为 $x_1\lt x_2\lt \cdots x_{n-m}$，被删除的元素为 $y_1\lt y_2\lt \cdots y_m$。 | ||
| + | |||
| + | 不难发现，一定有 $x_i\le a_i$。下面证明满足该条件的所有方案均为合法方案。 | ||
| + | |||
| + | 考虑构造，第 $a_i$ 次 $\text{push}$ 元素 $x_i$，第 $b_i$ 次 $\text{push}$ 元素 $y_i$。 | ||
| + | |||
| + | 于是问题等价与找到 $x_i\le a_i$ 的递增序列数，可以 $O(n^2)$ $\text{dp}$ 计算。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=5005,mod=998244353; | ||
| + | int st[MAXN],dp[2][MAXN]; | ||
| + | int main(){ | ||
| + | int n=read_int(),m=read_int(),top=0,pos=0; | ||
| + | _for(i,0,n+m){ | ||
| + | int x=read_int(); | ||
| + | if(x==1) | ||
| + | st[++top]=++pos; | ||
| + | else | ||
| + | top--; | ||
| + | } | ||
| + | pos=0; | ||
| + | dp[0][0]=1; | ||
| + | _rep(i,1,top){ | ||
| + | pos=!pos; | ||
| + | mem(dp[pos],0); | ||
| + | int s=dp[!pos][0]; | ||
| + | _rep(j,1,st[i]){ | ||
| + | dp[pos][j]=s; | ||
| + | s=(s+dp[!pos][j])%mod; | ||
| + | } | ||
| + | } | ||
| + | int ans=0; | ||
| + | _rep(i,1,n) | ||
| + | ans=(ans+dp[pos][i])%mod; | ||
| enter(ans); | enter(ans); | ||
| return 0; | return 0; | ||
2020-2021/teams/legal_string/jxm2001/contest/arc_127.1632663902.txt.gz · 最后更改: 2021/09/26 21:45 由 jxm2001
