博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Codeforces Round #382 (Div. 2)
阅读量:6955 次
发布时间:2019-06-27

本文共 613 字,大约阅读时间需要 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

你可能感兴趣的文章
python 使用函数参数注解
查看>>
Redis五大数据类型以及操作---散列表
查看>>
重载类型转换操作符(overload conversion operator)
查看>>
bootstrap学习(二)页面
查看>>
C++ sizeof操作符的用法和strlen函数的区别
查看>>
文件的续写
查看>>
每天一道算法题(16)——翻转链表
查看>>
点亮LCD1602
查看>>
Windows下SVN备份脚本
查看>>
如何在页面中获取到ModelAndView绑定的值
查看>>
Linux 系统磁盘满处理方法
查看>>
点击按钮弹出窗口
查看>>
以Python为基础的REST(JSON为交换数据)接口的测试框架设计(一)
查看>>
MySQL中是索引
查看>>
Have Fun with Numbers及循环链表(约瑟夫问题)
查看>>
acm常用术语
查看>>
YUV格式&像素
查看>>
Asp.Net Core 快速邮件队列设计与实现
查看>>
归并排序板子
查看>>
oralce入门学习
查看>>