UOJ Logo jiry_2的博客

博客

UOJ Test Round #2 题解

2017-01-08 20:13:52 By jiry_2

直播看着看着发现题解还没写,反正题目比较简单,我就随便写一下题解然后就接着去浪吧。

P.S. 写好一句话题解被吕老师叫回来重写了,伤心到变形。

感觉这一套题虽然总体难度不大,但是细节比较多,套上捆绑还是比较恶心的..而且验题的时候感觉样例比较弱(造题的不是我我不背锅)

看了一下榜感觉这个难度挺兹瓷的?以后就按照这个出吧。

题目排列顺序

from jiry_2,数据 from cy

算法一

聪明的你肯定发现了把所有位置按照权值第一关键字升序,下标第二关键字降序排序,依次分配 $1$ 到 $n$ 这 $n$ 个数就直接 work 了。

咦我好像不会排序那怎么办办呢?只好写个冒泡排序了。

时间复杂度 $O(n^2)$,期望得分 $60$ 分。

算法二

哇我好像知道一个叫做 std::sort 的东西耶,赶紧来试一试吧。

时间复杂度 $O(n \log n)$,期望得分 $100$ 分。

题目交流通道

from jiry_2,数据 from SkyDec

算法一

先来考虑 $d_{u,v}>0$ 的情况。

对于边 $(u,v)$,我们先来看是否存在一个点 $k$ 满足 $d_{u,v}=d_{u,k}+d_{k,v}$,如果不存在这样的 $k$,那么这条边的权值就只能是 $d_{u,v}$,否则这条边只要大于等于 $d_{u,v}$ 就可以了,即有 $K-d_{u,v}+1$ 种方案。把所有边的方案乘起来就可以了。

时间复杂度 $O(n^3)$,期望得分 $30$ 分。

算法二

考虑边可以等于 $0$ 的情况,这时 $d_{u,v}=0$ 的边肯定在图中连成了若干个团。我们把每一个团给缩起来。

两个团之间的点对距离一定是相等的,考虑团与团之间的边,此时相当于有重边的 $d_{u,v}>0$ 的情况。假设这是一条 $a$ 重边,如果存在 $k$ 有 $d_{u,v}=d_{u,k}+d_{k,v}$,那么所有边只要大于等于 $d_{u,v}$ 就可以了,即有 $(K-d_{u,v}+1)^a$ 种方案。如果不存在,那么至少要有一条边等于 $d_{u,v}$,其他边都要大于它,即有 $(K-d_{u,v}+1)^a-(K-d_{u,v})^a$ 种方案。

考虑团内部的边,每个团肯定由 $0$ 的边连成了一个联通块,这是一个经典的容斥,令 $f_i$ 为 $n$ 个点的距离为 $0$ 的团的方案数,$g_i$ 为 $n$ 个点的图的方案数。则有 $g_n=(K+1)^{\binom{n}{2}}$,$f_n=g_n-\sum_{i=1}^{n-1} f_i \times g_{n-i} \times \binom{n-1}{i-1} \times K^{i(n-i)}$。

把所有部分的答案乘起来就好了。时间复杂度 $O(n^3)$,期望得分 $100$ 分。

当然最重要的是要判对无解的情况,大致有四种,分别是 $d_{i,j} >K$,$d_{i,i} \neq 0$,$d_{i,j} \neq d_{j,i}$,$d_{i,j} > d_{i,k}+d_{k,j}$,大力 check 一下就可以了。

题目难度提升

from jiry_2,数据 from cy

这道题还是挺简单的,本来是出给 hiho 的 A 题,后来感觉有点难了(其实是最开始想简单了)就出 UR 了,感觉主要难度在于细节稍微多了点。

算法一

按位枚举,判断合法性只需要把后面所有的数升序排序然后检查一下就可以了。

直接裸写时间复杂度 $O(n^4)$ 已经够了,期望得分 $20$ 分。

算法二

考虑没有相同的数的情况。那么这个时候假设中位数是 $m$,新加入的数是 $a$。如果 $a < m$,那么中位数减少;如果 $a > m$,那么中位数增大;否则中位数不变。

按位枚举,一个前缀有解当且仅当前缀的中位数 $m$ 小于等于所有还没有放的数。

最开始先放最小的数,每一阶段放两个数进去。阶段开始时因为有奇数个数,所以中位数一定落在某个数上。

假设开始时中位数是 $m$,大于 $m$ 的第一个还没有放的数是 $K$,如果 $(m,K)$ 中已经有数放了,那么这个数不管放什么都可以,直接放最大的数就可以了。否则新放入的数 $a$ 一定要满足 $a+m \leq 2K$,即 $a \leq 2K-m$,令 $R=2K-m$。如果 $(m,R]$ 中已经有数放了,直接放最大的数就可以了,否则找到 $(m,R]$ 中最大的数放进去即可。

假设此时中位数是 $M$,大于等于 $M$ 的第一个还没有放的数是 $L$,如果 $(m,L)$ 中已经有数放了,那么直接放最大的数,否则就只能放 $L$ 了。

可通过第 4 个子任务,结合算法一可获得 $50$ 分。

算法三

有相同的数其实也不难。令所有数的中位数是 $m$,如果小于等于中位数的数中没有重复出现的数字,那么算法一仍然适用,否则令 $R$ 为第一个小于等于 $m$ 的重复出现的数字。

那最开始两个数最大字典序的情况一定是两个 $R$。因为如果更大的话中位数就没机会落在重复数上了,这时就满足算法一的性质,然而最大的数还没有放,所以无解。

放了两个 $R$ 后接下来就可以贪心了,每次放一个最大的数和一个小于等于 $R$ 最大的数,这个时候中位数在两个 $R$ 中左右横跳,一直没有变化,直到小于等于 $R$ 的数都用完了。这时就回到了算法一的情况,接着用算法一就可以了。

如果暴力实现的时间复杂度 $O(n^2)$,期望得分 $40$ 分。

可以发现所有的操作都是可以用 set 方便的做到。时间复杂度 $O(n \log n)$,期望得分 $100$ 分。

后半部分直接按位枚举也是可以的,稍微优化一下可以做到 $O(n \log^2 n)$ 或者 $O(n \log n)$,细节会稍微少一点。因为要降难度,所以也没去卡 $O(n log^2 n)$ 的做法,感觉还是比较良心的。

评论

LCF
前排zici!
150137
前排膜拜Orz
PbTfcLx
前排资瓷
whzzt
orz jiry_2
bogo
以后比赛能不能尽量捡一些节假日啊……不然没法打
WuHongxun
『套上捆绑还是比较恶心的..』 『看了一下榜感觉这个难度挺兹瓷的?以后就按照这个出吧』 这我妹子都找我诉苦说jsj不良心了啊。。。私以为出题人考虑选手和选手的妹子的感受也是很重要的吧。
Drench
只有我收到了一堆“无可奉告”吗......
freeloop
第一题有O(n)的算法呀
liu_runda
第一题我一开始的想法是依次添加数字,确定第i个数字在前i个数字中的相对大小位置。然后发现对每个位置的答案有贡献的是前方fi小于它的数和后方fi小于等于它的数,算了算发现总的贡献数目加上每个数字初始值1正好是n(n+1)/2就愉快地写了一发树状数组统计每个数前方fi小于它的数字个数和后方fi小于等于它的数字个数。应该和题解写法是等价的吧。
immortalCO2
“把后面所有的数升序排序然后检查一下” 我一开始想这样,每次枚举一位看后面是否有合法序列,O(N^4)做,但是不知道怎么检查QAQ 只看升序排序是否有解不对啊QAQ
stealthassassin
T1暴力拓扑没毛病
i
这题根本不敢看啊,说好的降低难度呢,反正我个辣鸡看同机房的人点开了题,瞄了一眼便不敢继续做了...UOJ的难度都是不可信的!哼...
i
啊啊啊啊啊神难的UOJ我要和你离婚!
JeremyGuo
orz jiry_2

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。