IDTagDiffDescriptionSolutionCodeReview
热身赛 C长度为 NN 的隐藏排列 pp 和隐藏颜色。⌈N/2⌉\lceil N/2\rceil 次询问下标 i,ji,j,若颜色为黑,返回 pi+pjp_i+p_j,若颜色为白,返回 pipjp_i p_j。确定颜色。依次询问 (2i−1,2i)(2i-1, 2i),计算结果之和。N=2mN=2m 时,黑色的上界 B=N(N+1)2=m(2m+1)B = \frac{N(N+1)}{2}=m(2m+1),白色的下界(排序不等式,逆序和最小)R=∑i=1mi(2m+1−i)=m(m+1)(2m+1)3R=\sum \limits_{i=1}^{m}i(2m+1-i)=\frac{m(m+1)(2m+1)}{3},R−B=m(2m+1)(m−2)3>0R-B=\frac{m(2m+1)(m-2)}{3}>0,需要 m⩾3m \geqslant 3。N=2m+1N=2m+1,黑色的上界 B=N(N+1)2−1=(m+1)(2m+1)−1B = \frac{N(N+1)}{2}-1=(m+1)(2m+1)-1,白色的下界 R=m(m+1)(2m+1)3R=\frac{m(m+1)(2m+1)}{3},R−B=(m+1)(2m+1)(m−3)3+1>0R-B=\frac{(m+1)(2m+1)(m-3)}{3}+1>0,需要 m⩾3m \geqslant 3。所以对于所有 N≥6N\ge6,均有 R>BR>B。AC
热身赛 Dfirst 根据 NN,输出串集合,字母只能使用一次,jury 打乱集合,打乱每个串,second 根据串集合还原 NN。Bell numbers / Restricted Growth String (RGS)。AC