BZOJ上的POJ

dzy posted @ 2014年7月15日 19:19 in POJ with tags bzoj , 1334 阅读

因为有些逗,所以打算水一些这样的题目。囧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)


 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter