因为有些逗，所以打算水一些这样的题目。囧rz。

POJ3530 - A Modular Arithmetic Challenge

求[tex]L \leq D \cdot x \text{ mod } M \leq R[/tex]的最小非负整数解[tex]x[/tex]，或判断无解。

[tex]L,D,M,R \leq 2\cdot 10^9,100[/tex]组询问。

引入一个[tex]y[/tex],把原式表示成[tex]L \leq D\cdot x-M \cdot y \leq R[/tex],[tex]-R\leq M\cdot y-D \cdot x \leq -L[/tex],[tex]-R \text{ mod }D \leq M \cdot y \text{ mod } D \leq -L \text{ mod } D[/tex]

于是变成子问题了，可以递归了。因为每次两边一直取模，所以复杂度是log级别的？

一些边界问题：L>R无解，L>=M无解，L=0直接返回0，D被M整除而且L>0无解，如果存在L<=Dx<=R直接返回x。其他情况就递归下去。

POJ3968 Jungle Outpost

删除的点一定是连续的一端，而且满足二分性质。

比如当前删k个点，那i和(i-1-k+n)%n连一条直线，然后求半平面交看是否为空集判断k是否可行。

因为点是顺时针告诉你的，求半平面交只需要O(n)扫，总复杂度是O(nlogn)

• 相关文章