Goodbye Bingshen UOJ 282 长度测量鸡

比赛快结束时听说uoj有比赛,抱着娱乐的心态去看了第一题,没什么思路,写了个贪心,就去ow体验无限平局的乱斗模式(ctf夺旗模式)。写了一个平方级别的贪心,尽可能的去满足刻度,不满足就输出-1,后来测了一下发现竟然水到了50分,貌似好像只有3这一个点的值我的贪心和标算算的不一样……然后多case,呵呵掉50分,不过数据满坑的,这么一个O1的题,非要搞n^2的数据范围……诱导无知群众想dp……

暴力贪心是这么写的

然后我们来考虑一下正解。

玩的时候车队的某位神犇说,只要大于3输出-1就行了……(瞬间感到了数据范围的恶意)

我们先来明确一件事,允许刻n-1个刻度,加上收尾自带刻度,一共可以度量出n * (n + 1)/2个刻度。然后他让我们也量出n * (n + 1) / 2个刻度,所以我们可以得出一个结论,如果某一个长度可以被超过1或低于1种方案度量出来,那么这个方案一定是不合法的。

这样子我们来接着考虑,我们可以先手推出1,2,3发现他们都有成功的刻度方式,然后对于>3的情况我们来这样考虑。

设置长度为m,可以刻录n-1次,m = (n + 1) * n / 2(当n>3的情况下m >= 6)

如果我们想如果我们要求出m-1,就必须要在1或m-1处选其一进行刻录。由于这个尺子左右完全相同,因对称性,我们假设在1处进行刻录。然后我们要求出m-2,就必须要在m-1,m-2,2中选择一个点刻录,我们发现m-1,2,都会导致1有多种度量方法,所以我们只能选择m-2,因为此时m-2-1 = m – 3,所以m-3已经可以度量。现在我们已经在1,m-2,我们考虑m-4,我们需要在2,4,m-4,m-3中选择一个位置进行刻录,2会导致1出现多种度量,4会导致3有多种度量,m-4会导致2有多种度量,m-3会导致1有多种度量,所以我们可以发现现在没有一种合法的刻录方式了,所以我们独处结论当n>3 的时候不存在合法的解,这样子我们只需要在n>3的时候输出-1即可。

AC代码:

 

发表评论