【codechef】March Challenge 2015

2015年3月17日1,3690

只做了前6题弃疗了

感觉codechef写题解也没啥人看……

【codechefCNOTE】Chef and Notebooks

纯模拟

【codechefSIGNWAVE】 Sign Wave

听说此题打表可以找规律。。

引用zld神犇的话吧。。。

就是若干个余弦函数的零点均不同。。
然后sin函数的分布就十分奇怪了。。
比如s=3的时候就是312131213,忽略两端的情况。。
就变成非常规则的1213121
然后我们再考虑余弦函数当c=2的时候分布就是011101110
k=1的时候那么我们就求总共有多少个交点就行了。。
否则,k>s的时候一定无解。。
否则我们枚举i,表示有i个sin函数交在同一点。。
考虑一下它加上余弦函数的交点之后能不能>=k
如果能的话就把i这一类加入答案。。

【codechefDEVCLASS】Devu and his Class

type为0易得。。

否则将男女编号求逆序对啥的。。。略

【codechefSTRSUB】Count Substrings

预处理每个位置向左不超过k的最左点。。。

求其前缀和,每次询问分段统计一下

【codechefSEAPROAR】Sereja and Random Array

x和x+130172在1中生成的序列相同

种子同余于是直接暴力

【codechefMTRWY】Matrix

离线+并查集水过