0829NOIP模拟测试赛后总结
这次发誓不会咕咕咕!
80分rank30完美爆炸。
拿到题目苏轼三连???貌似三篇古诗文我都会背啊hhh。爆零警告
T1没啥思路,打完暴力后想了大约20分钟决定分解个因数,在b次方中每一次方选择一个约数相乘然后累加。
然而发现不太星,发现有重复,只好尝试分解质因数然而仍然不太星。
好吧我放弃了。交了40pts暴力于是与正解完美擦肩而过(<大佬>:其实差好远呢喂!<我>:大哥给留点面子QAQ)
T2想了一会儿发现贪心可过70%,感觉海星然后就打了。结果细节问题(其实是sb问题)炸掉了我60pts。
一是不知道为啥考试的时候突然脑抽把读入的字符串倒着存进了整体中。改了于是10pts->20pts
二是明明是多判而我的ans就是没有清空。改了于是20pts->50pts
三是数组开小了,并没有意识到整体数组的长度应该开2n。改了于是50pts->70pts
然后等我先找个地方哭会儿。。。
T3没啥好说的。只会暴力。30pts封顶滚粗。
失败啊——失败啊——QAQ
于是写题解
T1春思
天皇说这是李煜东上的原题。还有大神说数学一本通上也有。然而不爱看书的我没有见过。
考虑分解质因数,加上等比数列求和公式后柿子就显然了。记得乘逆元~(据说机房某女神犇忘记乘逆元了默哀默哀)
$Sum=(1+p_1+p_1^2+...+p_1^{k_1})*(1+p_2+p_2^2+...+p_2^{k_2})*...(1+p_n+p_n^2+...+p_n^{k_n})$
T2密州盛宴
$70%$贪心($O(n)$比题解的二分可能优秀一些哦hhh)
考虑n分钟内吃完,特判-1显然。
发现合法情况的两个极端:01010101…… 0000……1111
我们预处理出$sum1$和每一个1的位置$a1[i]$
考虑倒序枚举,记录一下1的个数$sum_1$和0的个数$sum_0$。
如果搜到一个$sum_0>sum_1$的位置i,于是考虑将$a1[sum1-sum_1]$上的那个1挪到i-1位置上。
不难发现这是最近的1,也就是最优的情况。
$100%$算法
依旧考虑从后往前扫的过程中。简化记录过程,我们只需要记录一个后缀和,是0减一,是1加一。
gugugu~!
最新文章
- 本地部署arcgis by eclipse
- C# 微信v3退款
- 第5.5次Scrum会议
- iOS开发系列--Objective-C 之 KVC、KVO
- Java多线程编程详解
- careercup-中等难题 17.2
- 数据结构(动态树):COGS 27. [WC 2006] 水管局长
- 解决XCode 4.x SVN无法连接的问题
- codevs 1200 同余方程 (Extend_Eulid)
- 彻底理解浮动float CSS浮动详解 清除浮动的方法
- JavaScript中的execCommand()命令详解及实例展示
- 【Android Developers Training】 10. 序言:支持不同设备
- 关于oracle11g在window10环境下安装不满足最低要求问题:报错NS-13001
- 挖掘频繁项集之FP-Growth算法
- 3.docker基础架构
- 20180429 xlVBA套打单据自适应列宽
- grunt入门讲解1:grunt的基本概念和使用
- (原创)C++11改进我们的程序之简化我们的程序(七)
- ubuntu修改Bash命令行提示符
- Solaris 系统命令使用说明
热门文章
- C++数据类型之实型(浮点型)&;科学计数法
- (一)hello word
- 获取linux性能数据
- 2019牛客暑期多校训练营(第八场)D-Distance 定期重构
- The linux command 之软件包管理
- c++ constructors not allowed a return type错误问题
- 【JZOJ6367】工厂(factory)
- day11 grep正则匹配
- Pycharm中如何加载多个项目同时存在
- HDU-1492-The number of divisors(约数) about Humble Numbers -求因子总数+唯一分解定理的变形