UOJ Round的一些题
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
-----------------------------------------------------------------
想做一下UR
但是因为太弱了只会做一些最简单的题_(:3 」∠)_
所以就把做了的写在这里好了...
-----------------------------------------------------------------
UR1 A:
答案显然就是∑(i=1,n)[a[i]/x]+(a[i] mod x)
= ∑(i=1,n)[a[i]/x]+a[i]-x*[a[i]/x]
= sum - (x-1)∑(i=1,n)[a[i]/x]
= sum - (x-1)∑(i=1,[n/x])∑(j=1,n)[a[j]>=x*i]
= sum - (x-1)∑(i=1,[n/x])s[i*x]
(以上的[]要么表示下标，要么表示取下整，要么表示艾佛森约定)
其中sum表示所有元素的和
s[k]表示a中大于等于k的元素个数
然后就只需要枚举x,然后[n/x]算一下答案了
时间复杂度O(n*log)
-----------------------------------------------------------------
UR3 A:
求每个数和a[1]的次大公约数
而任意一个公约数都是最大公约数的约数（证明：反证法）
因此只需要求gcd的次大约数
只需求出它的最小非平凡约数，然后用这个数来除就可以了
这个数一定是最小素约数（证明：反证法）
想pollard-rho了？
TLE...
然后发现因为每个数都是和a[1]取的gcd
所以gcd的最小素约数一定是a[1]的约数
因此把a[1]素约数分解，然后尝试用a[1]的每个素约数来除就行了
-----------------------------------------------------------------
UR3 B:
考虑二分答案
然后只需要看每个位置框住这么多个盒子最小用时
单调队列搞一搞吧...
诶不对啊这是O(log*∑(ai))的
其实每一次一定框到某一堆的端点
这样每一次都移动到下一个端点处
就是O(n*log)的了
-----------------------------------------------------------------
UR2 A:
每次遇到一个左括号就把他旋到开头去，这样n次之后就全部都是左括号了..
-----------------------------------------------------------------
UR8 A:
发现行和列是独立的，分别求一下答案加起来就好
对于一个向量，只有两种选择，向左走和向右走
-----------------------------------------------------------------
评论 (0)
