蓝红蓝/绿红绿
by lingfunny @ 2022-05-23 21:43:06
蓝红蓝
by MaLX @ 2022-05-23 21:49:52
尽管我到目前为止不知道第三题说的什么
by MaLX @ 2022-05-23 21:50:39
个人觉得 蓝红？（T3 还没看）
by I_am_Accepted @ 2022-05-23 21:53:44
@[I_am_Accepted](/user/101868)
问下dalao，模拟赛是1：1还原吗？题目是去年题还是纯原创呢？必须挤出5h参加吗
by ningago @ 2022-05-23 22:00:00
~~T2红过分了啊 人家至少是个《交 互 题》（雾~~
by Stinger @ 2022-05-23 22:04:42
@[ningago](/user/371968) bzd，感觉就是练手的（？）熟悉操作和文件的吧……
by I_am_Accepted @ 2022-05-23 22:06:12
@[MaLX](/user/685127) @[lingfunny](/user/280800)
求 treasure 题解 qwq
本蒟蒻不会压位 awa
我的想法是存 $p_i$ 使得 $X,Y$ 分别排序后 $(X_i,Y_{p_i})$ 为一对，但是咋 $n$ 个数存 $\{p\}$ 啊 qwq。
by I_am_Accepted @ 2022-05-25 22:23:22
@[I_am_Accepted](/user/101868)
提供一个做法。
用 $2n$ 个数存 $x_i$ 和 $y_i$，排序然后离散化，考虑用剩下的 $n$ 个数来 decode。
如果记 $(i,j)$ 表示 $(x_i, y_j)$，那么值域是 $n^2=1.6\times10^9$，但由于你存 $x,y$ 花掉了 $10^9$，这样行不通。
考虑到第一维和第二位都是一个排列，改记 $p_i$ 为 $i$ 对应的 $j$，即 $(x_i,y_{p_i})\to (i, p_i)$。
$p_i$ 显然不能做，考虑记 $v_i=\sum_{j=1}^{i-1}[p_j>p_i]$，即逆序对个数。如果能记下来所有 $v_i$，显然通过逆序对可以还原一个排列。
注意到 $v_i\le i$，所以实际上你只需要用 $\frac{i(i-1)}{2}+v_i$ 表示即可。此时最大值是 $\frac{n(n-1)}{2}+v_n\le9\times 10^8$，可以记。
by lingfunny @ 2022-05-26 02:08:21
1. 相信您会通过逆序对还原排列（
2. 实际上最大值是 $8\times10^8$ 左右的，上面那个等号取不到。
by lingfunny @ 2022-05-26 02:12:37