【20181031T1】一串数字【分解质因数+贪心】
2024-08-26 11:06:44
【错解】
立方就是所有质因子次数都是3的倍数嘛
发现1e5的三次根很小，可以枚举所有和这个数乘起来是完全立方数的(flag*1)
然后……连条边跑最大独立集？
不对啊是NP问题(实际上是个二分图)
那多半要优化连边变成一棵树(flag*2)
推了0.5h没一点结果，就暴搜，希望能剪点枝(那么大的数据剪个*的枝)
然后……搜挂了！0pts
【正解】
既然只和%3有关，那我们可以分解质因数时直接%掉
这样和一个数配对的数是唯一的
由于有重复的数(%了之后)，我们可以把它们合并。如果原来是完全立方，就选一个最大的(不能选多个)；否则把所有的加起来
然后每对数贪心选最大的
最新文章
- Xmemcached的FAQ和性能调整建议
- html5新增及废除属性
- (C#) 反转字符串，反转一个句子中单词。
- mysql与oracle的存储过程有什么区别？
- IOS 杂笔－4（属性与成员变量的区别）
- C#程序开机运行
- bzoj 4423 [AMPPZ2013]Bytehattan（对偶图，并查集）
- Automotive Security的一些资料和心得（7）：AUTOSAR和Security
- 【剑指offer】面试题22：栈的压入、弹出序列
- 【Luogu2711】小行星（网络流，最大流）
- 【Unity3D与23种设计模式】享元模式（Flyweight）
- JavaEE 藏经阁
- java基础知识总结--多线程
- centos每天自动备份mysql数据库
- Ubuntu14.04 安装MySQL 及Can‘t connect to local MYSQL server through socket ’/var/run/mysqld/mysqld.sock‘ (2)
- c++刷题（30/100）
- 6 unit3-文件操作&函数 review
- ASP.Net Core 2.2 MVC入门到基本使用系列 (一)
- request获取当前用户
- [Backbone] First Application!!!!