2020-2021:teams:legal_string:jxm2001:contest:ccpc_wannafly_winter_camp_day1
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:contest:ccpc_wannafly_winter_camp_day1 [2020/09/15 22:43] jxm2001 |
2020-2021:teams:legal_string:jxm2001:contest:ccpc_wannafly_winter_camp_day1 [2020/09/20 21:11] (当前版本) jxm2001 [题解] |
||
|---|---|---|---|
| 行 2: | 行 2: | ||
| [[https://ac.nowcoder.com/acm/contest/3979|比赛链接]] | [[https://ac.nowcoder.com/acm/contest/3979|比赛链接]] | ||
| + | |||
| + | ===== A. 期望逆序对 ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定 $n$ 个随机变量，第 $i$ 个变量的取值为 $[l_i,r_i]$ 中的随机一个数。 | ||
| + | |||
| + | 要求将 $n$ 个随机变量重新排列，使得最终的逆序对的期望值最小。询问该方案下逆序对的期望值。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 假设最终排序为 $p_1p_2\cdots p_n$，考虑相邻两个随机变量 $p_i$ 和 $p_{i+1}$，显然 $p_i$ 大于 $p_{i+1}$ 的概率不超过 $\frac 12$ 时最优。 | ||
| + | |||
| + | 事实上，这等价于 $l_i+r_i\le l_{i+1}r_{i+1}$，发现不等号两边的式子只与自身有关。 | ||
| + | |||
| + | 于是该性质具有传递性，于是对不相邻的随机变量也应该满足该约束，对序列按上述关键字排序即可得到最终序列。 | ||
| + | |||
| + | 考虑暴力计算最终答案，枚举数对 $i\lt j$，该数对的贡献为 $\sum_{k=l_i}^{r_i}\max(0,\min(k-l_j,r_j-l_j+1))$，可以 $O(1)$ 计算。 | ||
| + | |||
| + | 时间复杂度 $O(n^2)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=5e3+5,Mod=998244353; | ||
| + | int Inv[MAXN]; | ||
| + | int inv(int x){ | ||
| + | int k=Mod-2,ans=1; | ||
| + | while(k){ | ||
| + | if(k&1)ans=1LL*ans*x%Mod; | ||
| + | x=1LL*x*x%Mod; | ||
| + | k>>=1; | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | struct Seg{ | ||
| + | int lef,rig; | ||
| + | bool operator < (const Seg &b)const{ | ||
| + | return lef+rig<b.lef+b.rig; | ||
| + | } | ||
| + | }seg[MAXN]; | ||
| + | int cal(int l1,int r1,int l2,int r2){ | ||
| + | if(r1<=l2)return 0; | ||
| + | int s=0,L=max(l1,l2+1),R=min(r1,r2); | ||
| + | if(r1>r2) | ||
| + | s=1LL*(r1-r2)*(r2-l2+1)%Mod; | ||
| + | s=(s+1LL*(R-l2+L-l2)*(R-L+1)/2)%Mod; | ||
| + | return s; | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(); | ||
| + | _for(i,0,n) | ||
| + | seg[i].lef=read_int(),seg[i].rig=read_int(); | ||
| + | sort(seg,seg+n); | ||
| + | int ans=0; | ||
| + | _for(i,0,n) | ||
| + | Inv[i]=inv(seg[i].rig-seg[i].lef+1); | ||
| + | _for(i,0,n) | ||
| + | _for(j,i+1,n) | ||
| + | ans=(ans+1LL*Inv[i]*Inv[j]%Mod*cal(seg[i].lef,seg[i].rig,seg[j].lef,seg[j].rig))%Mod; | ||
| + | enter(ans); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| ===== E. 树与路径 ===== | ===== E. 树与路径 ===== | ||
| 行 132: | 行 197: | ||
| 修改完成后同样打上懒标记，必要时下放标记。 | 修改完成后同样打上懒标记，必要时下放标记。 | ||
| - | 显然每次修改复杂度为 $O(k\log n)$，其中 $k$ 为该次修改删除的权值线段树的叶子数。 | + | 显然每次修改复杂度为 $O(k\log^2 n)$，其中 $k$ 为该次修改删除的权值线段树的叶子数。 |
| - | 由于初始时仅有 $O(n\log n)$ 个权值线段树的叶子结点，于是修改操作的总时间复杂度为 $O(n\log^2 n)$。 | + | 由于初始时仅有 $O(n\log n)$ 个权值线段树的叶子结点，于是修改操作的总时间复杂度为 $O(n\log^3 n)$。 |
| 于是总时间复杂度 $O(n\log^3 n)$，总空间复杂度 $O(n\log^2 n)$。 | 于是总时间复杂度 $O(n\log^3 n)$，总空间复杂度 $O(n\log^2 n)$。 | ||
2020-2021/teams/legal_string/jxm2001/contest/ccpc_wannafly_winter_camp_day1.1600181033.txt.gz · 最后更改: 2020/09/15 22:43 由 jxm2001
