首页 > 代码库 > 20170303
20170303
今天考了一场奇怪的考试.
第一题,
大意:给定一个序列,从这个序列中取出一些数,使这些数字的平均数减去中位数最大.
n<=200000.
题解:
这种题一看就是sort一下,枚举一维,二分或数据结构一维.复杂度O(nlogn).
实际这道题也就是这样了,枚举中位数,三分两端的数数量,然后就没了.
第二题:
大意:求存在多少排列任意两相邻数字差绝对值不为1.n<=1000
题解:比赛是没想出来,实际dp,至于怎么dp自己脑补.
第三题:
大意:求存在多少由1,2,3,5,7组成的数符合它不是2,3,5,7,11,47的倍数.n<=1e9
题解:f[i][j]表示i位的数字对T=3*7*11*47取模的结果是j的方案数.
2和5只需要在取第n位的时候不进行2,5的转移即可.
然后用上优化技巧,FFT+倍增......
这题听说是用来防AK的,但感觉挺裸的.(逃).
20170303
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。