今天考了一场奇怪的考试.
第一题,
大意:给定一个序列,从这个序列中取出一些数,使这些数字的平均数减去中位数最大.
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的,但感觉挺裸的.(逃).