Codeforces Round #382 (Div. 2)

  A题,水题。

  B题,贪心一发。排序一下,从大到小,先拿个数较少的几个,再拿个数较多的几个即可。证明应该是显而易见的。

  C题,本以为log一发即可。但是log的话不能保证深度最深,即不能保证最大分数最大。因此考虑递推,用f[i]表示要得到i分需要的最少的人数,显然要人数最少,最后剩下一个即可。那么要得到f[i],只要分数为i-1和分数为i-2的两个人进行比赛即可,只要i-1胜最后肯定只有最后一个人了。因此得到f[i]=f[i-1]+f[i-2]。所以做法是先做递推的预处理,然后二分查找一下最大的x使得f[x]<=n即可。当然直接暴力查找也是可以的,因为斐波那契数列增长的很快,总共也就没几项。

  D题,哥德巴赫猜想。任意一个大于2的偶数都能被拆分成两个素数的和。同时任意一个大于5的奇数都能被拆分成3个素数的和,一个为3,剩下的是偶数,按照前面的拆分即可。这题,很显然的,将n拆分成最少数目的素数相加即可。因此利用上面的结论就很容易了。如果n是偶数,如果是2,答案是1,否则按照上面的拆分原则,答案是2;n是奇数,如果是素数,答案就是1,如果n-2是素数,那么拆分成2和n-2,答案就是2了,否则,按照哥德巴赫猜想答案就是3了。

  E题,做的人不多,但是看了别人的代码好像是树形DP,代码也不长。下次再补了。

原文地址:https://www.cnblogs.com/zzyDS/p/6361456.html