Codechef 15.10 解题报告

闲来无事补了一下这个月的CHA。

所有的代码都可以参见我的提交记录这里就不贴代码了。

SUBINC

利用单调性扫描一遍。

时间复杂度$O(Tn)$。

WDTBAM

统计回答正确的问题个数并进行贪心。注意全部匹配要特判。

时间复杂度$O(Tn)$。

TIMEASR

数据范围小的可怜，暴力枚举每个分钟算出此时的夹角度数。只要知道时针分针每分钟走的度数就行了。

时间复杂度$O(24\times{60}T)$。

ADTRI

根据一个显然的但是我不会正的数学事实，如果一个数$x$可以作为三条边长度均为整数的直角三角形斜边的长度，则有$x$存在一个质因子$p$满足$p\equiv{1}\pmod{4}$。

于是我们线性筛找出所有的质数，对于每个满足条件的质数向后暴力更新答案。

时间复杂度$O(nlnn+T)$。

KSPHERES

首先预处理出每种大小的球各有多少个。

接下来令$f[i][j]$表示最后一个大小为$i$，长度为$j$的递增序列个数。

显然朴素时间复杂度为$O(C^3)$。

然后用前缀和优化将复杂度优化至$O(C^2)$。

时间复杂度$O(n+m+C^2)$。

PERSHFTS

若$k=n$，那么我们只能得到原串的$n$个循环排列，问题容易解决。

否则先考虑$k$为偶数的情况。

考虑现在有$p_1,p_2,...p_{k+1}$。现在我们考虑能否构造一个方案使得$p_1,p_2$交换位置而其他元素位置不变。

先对区间$[1,k]$进行操作，再对$[2,k+1]$进行操作，这样现在会变成$p_k,p_{k+1},p_1,p_2,...p_{k-1}$。这样就能将最后两个元素移至前两个位置。

这样最终经过$\frac{k}{2}$就能变成$p_2,p_3,...p_{k},p_{k+1},p_1$，此时再对$[2,k+1]$进行操作就能实现$p_1,p_2$对调。

用类似的操作，我们也能交换$p_{k},p_{k+1}$。

这样事实上我们能证明，我们能够得到任意排列。

那么排名也是容易求的，利用树状数组就OK了。

再考虑$k$为奇数的情况。

我们能够发现，进行一次操作这个排列的奇偶性不变。于是显然不能得到全部排列了。

接着用类似刚才的构造策略，我们能够证明能够得到所有奇偶性与原排列相同的排列。

用树状数组求逆序对数判断是否合法。

排名呐？

归纳假设可以发现对于排名为$2i-1,2i$的排列奇偶性不同。

于是令真实排名为$rank$，排名就是$\lfloor\frac{rank+1}{2}\rfloor$。

这个是在模意义下的，怎么求呢？

记录一下$rank$的奇偶性，分类讨论即可。

时间复杂度$O(nlogn)$。

LOTERY

首先你需要以超人的观察力发现$F(n,k)=n\binom{n-1}{k}$。

接着问题就变成了求$lcm(n\binom{n-1}{1},n\binom{n-1}{2},...,n\binom{n-1}{k})$。

不妨再加上一个$n\binom{n-1}{0}$。

然后由神秘定理（CC说It's easy to see）有：

若$n$是正整数，且$0\leq{k}\leq{n}$，满足下面等式：

\[lcm((n+1)\binom{n}{0},(n+1)\binom{n}{1},...,(n+1)\binom{n}{k})=lcm(n-k+1,...,n,n+1)\]

于是问题转化成求$lcm(n-k+1,...,n-1,n)$。

利用JZPLCM的方法水过。

利用可持久化线段树实现在线询问。

时间复杂度$O(mlog^2m+Tlogm)$，空间复杂度$O(mlog^2m)$。

JUMP(没写代码)

无非是经典的斜率优化套上一个距离限制，也就是线段树套Splay就能搞定。

或者用CDQ分治也是OK的。

实在懒得写了。时间复杂度$O(nlog^2n)$。空间复杂度$O(n)$或者$O(nlogn)$。

看着$n$感觉真吓人。

MGCHGYM(没写代码)

一开始想的是单调队列优化的多重背包，结果比不上正解里面的二进制拆分然后bitset优化01背包。

注意到最多只有10种不同的重量，我们用线段树维护区间内的各个重量各有多少个即可。

于是修改复杂度为$O(qlogn)$。

对于每个询问，我们利用上述的方法，复杂度为$pwklogn/32$。

这样看上去复杂度真是日了狗了，好像discuss里面说非常卡时，于是就不写代码了。

Challange:弃