NOIP自闭赛2

• T1

• 把行和列看成一个点，把每个点看成所在行和所在列的连边，那么机器人捡金币的实质就是在新建的二分图中遍历，由于每条边只能经过一次（金币只能捡一次）且每条边都要遍历到（所有金币都要捡），判断是否存在欧拉路即可

• T2

• orz syk

• 整一个priority_queue，按题意模拟来重载小于号，然后一个个加进去就好了，suctask3 注意只要push前后100个就好了（利用了单调性）,然后就有 70pts

• T3

• orzqy

• 只考虑k=2,推个式子

  [E(a_n^2) ]
  [= frac{sum_{i=0}^{n-1} sum_{r=0}^{n-1}E((a_i+a_r)^2)}{n^2} ]
  [=frac{2sum_{i=0}^{n-1}E(a_i^2)}{n}+frac{2sum_{i=0}^{n-1}sum_{r=0}^{n-1}E(a_ia_r)}{n^2} ]
  [sum_{i=0}^nsum_{r=0}^nE(a_ia_r) ]
  [=sum_{i=0}^{n-1}sum_{r=0}^{n-1}E(a_ia_r)+2sum_{i=0}^{n-1}E(a_ia_n)+E(a_n^2) ]
  [=sum_{i=0}^{n-1}sum_{r=0}^{n-1}E(a_ia_r) +2sum_{i=0}^{n-1}E(a_ifrac{2sum_{i=0}^{n-1}a_i}{n}+E(a_n^2)) ]
  [=sum_{i=0}^{n-1}sum_{r=0}^{n-1}E(a_ia_r) +frac{4E(sum_{i=0}^{n-1}sum_{r=0}^{n-1}a_ia_r)}{n}+E(a_n^2) ]
  [=frac{n+4}{n}E(sum_{i=0}^{n-1}sum_{r=0}^{n-1}a_ia_r)+E(a_n^2) ]

• 设 $$dp1_n=E(a_n^2) $$ $$dp2_n=sum_{i=0}^nsum_{r=0}nE(a_ia_r)$$

• 有$$dp1_n=frac{2sum_{i=0}^{{n-1}dp1_i}{n}+frac{2dp2_{n-1}}{n}2}$$ $$dp2_n=frac{n+4}{n}dp2_{n-1}+dp1_n$$

  然后递推80pts