DZY 's BLOG
Hello World!
dzy493941464
Music
BZOJ上的POJ
因为有些逗，所以打算水一些这样的题目。囧rz。
POJ3530 - A Modular Arithmetic Challenge
求的最小非负整数解
，或判断无解。
组询问。
引入一个,把原式表示成
,
,
于是变成子问题了，可以递归了。因为每次两边一直取模，所以复杂度是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)
评论 (0)