[UOJ282]长度测量鸡

思路：

数学归纳。

设最少所需刻度数为$s$，则$n和s$的关系为：

$n=1,s=0;$

$n=2,s=1;$

$n=3,s=3;$

...

观察发现$s=n(n-1)/2$，得到$sn$时，满足条件。

然而只有50分。。

因为我手算错了，$n=3,s=2$。

然而人不能没有信仰，就把$<$改成$\leq$，A了。。

正解：

当$n>3$时，一定不能满足条件。

附官方题解：

from nneztlk

算法一

直接枚举刻度, 时间复杂度为 O((n(n+1)/2&＃x2212;1n&＃x2212;1))">O((n(n+1)/2−1n−1))O((n(n+1)/2−1n−1)). n=5">n=5n=5 时这个数是 (144)=1001">(144)=1001(144)=1001, n=8">n=8n=8 时这个数是 (357)=6724520">(357)=6724520(357)=6724520. 期望得分 10&＃x223C;20">10∼2010∼20 分.

算法二

我们需要题目描述中的 sj&＃x2212;si&＃xA0;(0&＃x2264;i<j&＃x2264;n)">sj−si (0≤i<j≤n)sj−si (0≤in(n+1)2">n(n+1)2n(n+1)2 个数取到 1&＃x223C;n(n+1)2">1∼n(n+1)21∼n(n+1)2 的所有整数, 所以每个整数只能取一次, 即每种长度只能被一种方法量出. 特别地, si&＃x2212;si&＃x2212;1(1&＃x2264;i&＃x2264;n)">si−si−1(1≤i≤n)si−si−1(1≤i≤n) 这 n">nn 段长度两两不同, 故只能是 1,2,&＃x2026;,n">1,2,…,n1,2,…,n 的一种排列.

枚举排列, 时间复杂度为 O(n!)">O(n!)O(n!). n=8">n=8n=8 时这个数是 40320">4032040320. 期望得分 20">2020 分.

算法三

事实上, n=1,2,3">n=1,2,3n=1,2,3 时可以直接试出刻度方案, 分别为 &＃x2205;,{1},{1,4}">∅,{1},{1,4}∅,{1},{1,4}, 而对所有 n>3">n>3n>3 都不存在满足要求的刻度. 证明如下:

记 M=n(n+1)2">M=n(n+1)2M=n(n+1)2, 则对 n>3">n>3n>3, M&＃x2265;10">M≥10M≥10. 现假设存在满足要求的刻度方案. 由于需要量出 M&＃x2212;1">M−1M−1 的长度, 所以 1">11 或 M&＃x2212;1">M−1M−1 处必须有刻度, 由对称性不妨设 1">11 处有. 要量出 M&＃x2212;2">M−2M−2 的长度, 2,M&＃x2212;2,M&＃x2212;1">2,M−2,M−12,M−2,M−1 中需要有一处有刻度, 而如果 2">22 或 M&＃x2212;1">M−1M−1 处有刻度, 则可以用两种方法量出长度 1">11, 矛盾! 所以 M&＃x2212;2">M−2M−2 处必须有刻度. 此时由 (M&＃x2212;2)&＃x2212;1=M&＃x2212;3">(M−2)−1=M−3(M−2)−1=M−3, M&＃x2212;3">M−3M−3 的长度已经可以被量出. 要量出 M&＃x2212;4">M−4M−4 的长度, 2,4,M&＃x2212;3,M&＃x2212;4">2,4,M−3,M−42,4,M−3,M−4 四处必有一处有刻度. 容易发现只有 4">44 处的刻度不会引起重复.

现在已经知道 1,4,M&＃x2212;2">1,4,M−21,4,M−2 处都需要有刻度, 而长度 M&＃x2212;5">M−5M−5 尚未被量出. 欲量出 M&＃x2212;5">M−5M−5, 需要 3,5,M&＃x2212;5,M&＃x2212;4,M&＃x2212;1">3,5,M−5,M−4,M−13,5,M−5,M−4,M−1 中的一处有刻度. 然而它们都会导致 1,2,3">1,2,31,2,3 中的某个长度能被两种方法量出, 矛盾! 故不存在满足要求的刻度.

所以只需判断 n">nn 是否大于 3">33. 时间复杂度 O(1)">O(1)O(1), 期望得分 100">100100 分.

我的AC代码：

 1 #include
 2 int main() {
 3     int t;
 4     scanf("%d",&t);
 5     while(t--) {
 6         int n;
 7         scanf("%d",&n);
 8         printf("%d\n",((n*(n+1)>>2)<=n)?1:-1);
 9     }
10     return 0;
11 }

附最短代码（Python2.7）：

1 print'\n'.join(['-1'if input()>3 else'1'for i in range(input())])