| 热身赛 C | | | 长度为 N 的隐藏排列 p 和隐藏颜色。⌈N/2⌉ 次询问下标 i,j,若颜色为黑,返回 pi+pj,若颜色为白,返回 pipj。确定颜色。 | 依次询问 (2i−1,2i),计算结果之和。N=2m 时,黑色的上界 B=2N(N+1)=m(2m+1),白色的下界(排序不等式,逆序和最小)R=i=1∑mi(2m+1−i)=3m(m+1)(2m+1),R−B=3m(2m+1)(m−2)>0,需要 m⩾3。N=2m+1,黑色的上界 B=2N(N+1)−1=(m+1)(2m+1)−1,白色的下界 R=3m(m+1)(2m+1),R−B=3(m+1)(2m+1)(m−3)+1>0,需要 m⩾3。所以对于所有 N≥6,均有 R>B。 | AC | |