Destiny
多随几次就好了,然而 \(O(\log n)\) 的复杂度不能保证正确性,所以用莫队,对于每一次随机 \(O(1)\) 求答案。
Ghd
因为有至少一半的数符合条件,所以随机选一个数分解因数,求出是和 \(a_i\) 的 \(\gcd\) 是 \(x\) 的数有多少个,然后分解质因数,从高到低转移,因为每次转移的质因数不同,所以保证了正确性,最后看有没有出现次数大于一半的因子即可。
Xor Permutations
首先两个排列异或和一定是 \(0\),所以可以判断无解。
考虑随机两个排列。找到一个不合法的位置,随机调整 \(a\) 或 \(b\),直到合法。
如果调整太多次还不对,就重新随机排列。
卡时判无解,虽然无解情况只有上面的一种。
Choosing Ads
其实这题已经没有保证正确性的随机化算法了,考虑广义的摩尔投票法,记录出现次数最多的 \(k\) 个数,用线段树更新,复杂度是 \(O(nk^2\log n)\)。
标签:问题,log,复杂度,随机化,正确性,随机,质因数 From: https://www.cnblogs.com/mikefeng/p/17475563.html