目录
《随机算法在信息学竞赛中的应用》做题记录
MSTONES
Problem
\(T\) 组数据，给出 \(n\) 个点的坐标，求一条直线最多能覆盖多少个点。
\(T \le 30\)，\(n\le 10^4\)。
Solution
朴素算法：枚举两个点，数有多少个点在两点确定的直线上，取最大值。时间复杂度 \(O(Tn^3)\)。
向朴素算法中加入随机，改造为 Monte Carlo 算法。
由于存在不超过 \(7\) 条直线覆盖完了所有点，所以：
\(ans \ge \lfloor \frac{n}{7} \rfloor\)
从而有：
从 \(n\) 个点中随机选择两个点，过两点的直线与覆盖了最多点的直线重合的概率最小为 \(\frac{1}{49}\)。
即一个点在覆盖了最多点的直线上的概率至少为 \(\frac{1}{7}\)，两个点乘法原理即可。
所以如果随 \(k\) 次，正确率为：\(1 - (1 - \frac{1}{49})^{k}\)。
取 \(k = 1000\)，正确率约为 \(1.1 \times 10^{-9}\)，运行次数为 \(1000nT\)。可以接受。
#include<bits/stdc++.h>
using namespace std;
template<typename T> void chkmx(T &a, const T &b)
{
(a < b) && (a = b);
}
const int N = 1e4 + 5;
int T, n, ans;
struct node
{
int x, y;
}a[N];
int main()
{
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d %d", &a[i].x, &a[i].y);
if(n == 1)
{
puts("1");
continue;
}
ans = 0;
for(int k = 1; k <= 1000; ++k)
{
int x = rand() % n + 1;
int y = rand() % n + 1;
while(x == y)
{
x = rand() % n + 1;
y = rand() % n + 1;
}
int res = 2;
for(int i = 1; i <= n; ++i)
if(i ^ x && i ^ y)
if(1LL * (a[i].y - a[x].y) * (a[i].x - a[y].x) == 1LL * (a[i].y - a[y].y) * (a[i].x - a[x].x))
++res;
chkmx(ans, res);
}
printf("%d\n", ans);
}
return 0;
}
P3567 [POI2014]KUR-Couriers
Problem
给一个长度为 \(n\) 的正整数序列 \(a\)。共有 \(m\) 组询问，每次询问一个区间 \([l,r]\) ，是否存在一个数在 \([l,r]\) 中出现的次数严格大于一半。如果存在，输出这个数，否则输出 \(0\)。
\(1 \leq n,m \leq 5 \times 10^5\)，\(1 \leq a_i \leq n\)。
Solution
主席树当然是可以的。这里讲随机化做法。
先设计朴素算法：枚举区间内的每个数，统计该数在区间内的出现次数。时间复杂度 \(O(mn^2)\)。
改为 Mante Carlo 算法，随机选择区间内的一个数。
如果询问答案不为 \(0\)，则选到正确答案的概率不小于 \(\frac{1}{2}\)。
如果随 \(k\) 次，那么正确率不小于 \(1 - (\frac{1}{2})^{k}\)。
\(O(km\log{n})\)。其中 \(\log{n}\) 可以用 STL 乱搞一下卡过去。
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, Q, a[N];
vector<int> vec[N];
int main()
{
scanf("%d %d", &n, &Q);
for(int i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
vec[a[i]].push_back(i);
}
while(Q--)
{
int l, r;
scanf("%d %d", &l, &r);
int times = 19;
int ans = 0;
int len = r - l + 1;
while(times--)
{
int pos = l + rand() % len;
int x = a[pos];
if((int)vec[x].size() <= len / 2) continue;
vector<int>::iterator rr = upper_bound(vec[x].begin(), vec[x].end(), r);
vector<int>::iterator ll = lower_bound(vec[x].begin(), vec[x].end(), l);
if(rr - ll > len / 2)
{
ans = x;
break;
}
}
printf("%d\n", ans);
}
return 0;
}
CF364D Ghd
Problem
定义一个集合的Ghd为 所有大小至少为一半的子集的\(\mathrm{gcd}\) 的最大值。
给定集合\(a\)，求\(a\)的Ghd。
Solution
一个想法是从答案上枚举数 \(x\)，统计数列中有多少个数是 \(x\) 的倍数，如果 \(\ge \frac{|S|}{2}\) 就更新答案为 \(x\)。（实际上 \(x\) 不一定是符合条件的 ghd）显然答案一定是所有数的因数的集合中的某一个，因此可以从这里面进行枚举。过不了。
另一个想法是从数列中枚举数 \(a_x\)，去找集合 \(S^{'}\) 中包含 \(a_x\) 的最大 ghd。
记 \(g_i\) 表示 \(a_x\) 与 \(a_i\) 的最大公约数。那么在假定 \(a_x\) 必选的条件下，如果 \(a_i\) 也被选择，那么答案只可能在 \(g_i\) 的因子中出现。
对 \(a_x\) 的每一个因子 \(d\) 记录 \(cnt_d\)，表示（最多）有多少个数加进 \(S^{'}\) 内 ghd 可以为 \(d\)。对所有 \(g_i\) 的每一个因子 \(p\)，将 \(cnt_p\) 加一。
设 \(\tau(x)\) 为 \(x\) 的因子个数，则算法的时间复杂度为 \(O(n(\sqrt{a_x}+\tau^2(a_x)+nlog{n}))\)。其中 \(\tau^{2}(a_x)\) 是考虑用递推优化时间复杂度。\(10^{12}\) 范围内的因数最多的数是 \(963761198400\)，有 \(6720\) 个因子。
现在考虑加上随机化减少枚举次数。不难发现，一个数在答案存在的 \(S^{'}\) 中的概率至少为 \(\frac{1}{2}\)，那么枚举 \(10\) 次的正确率至少为 \(\frac{1023}{1024}\)。
TKCONVEX
Problem
Solution
首先考虑如何判断 \(k\) 条边是否能构成一个凸多边形，再考虑 \(2k\) 条边是否能构成两个凸多边形。
假设给定 \(k\) 条边的边长 \(a_1, a_2, \cdots, a_k\)，\(C = \sum\limits_{i = 1}^{k}a_i\)。
构成多边形的条件：\(\forall i\in [1, k], i\in \N_{+}\)，\(a_i < \frac{C}{2}\)。即 \(\max\limits_{i = 1}^{k}a_i < \frac{C}{2}\)。
由三角形的构成条件可以推广到多边形的构成条件，即一条边的长度小于其他边长度的总和。
\(a_i < C - a_i\)，移项可得。
任意非凸多边形都可以通过对其边的平移和旋转得到一个凸多边形。
只能感性理解了（，这条引理说明第一条引理即可判断是否能构成凸多边形。
还是考虑朴素算法，暴力枚举判断，共有 \(\binom{n}{2k}\binom{2k}{k}\) 种情况。
论文又给出了如下定理：
将线段长度排序，若 \(n\) 条线段中存在可以构成凸多边形的大小为 \(k\) 的子集，那么也一定存在一个子集，满足其中的元素在排序后的序列上对应一段区间。
证明：
运用了反证法。任选一个可以构成凸多边形的大小为 \(k\) 的子集，记为 \(S\)。记排序后的序列为 \(p\)，假设 \(S\) 中的元素对应到 \(p\) 上不是一段区间，则一定存在两个 \(i(i < n)\)，满足 \(p_i\in S\) 且 \(p_{i + 1}\not\in S\)。这里要注意的是由于 \(2k \le n\)，因此上述才成立。
找到满足上述条件的第二大的 \(i\)，并从 \(S\) 中删去 \(p_i\)，再加入 \(p_{i + 1}\)，由第一条引理，此时 \(\max{a_i}\) 不变，\(C\) 增加，因此仍然满足 \(\max{a_i} < \frac{C}{2}\)，能构成凸多边形。重复这样做直到无法操作，发现最后的 \(S\) 中的元素对应到 \(p\) 上就是一段区间。
接下来的思路是什么呢？
首先把原线段集合分成两个集合，然后在这两个集合分别按上述方法将元素从小到大排序后扫一遍，找出符合条件的一段长度为 \(k\) 的区间。注意到时间复杂度的瓶颈在于枚举子集，因此考虑在这上面加入随机化改造成 Monte Carlo 算法。
具体地，假设两个线段集合分别为 \(S\) 和 \(T\)，则一个线段均有 \(\frac{1}{2}\) 的概率被分配到 \(S\) 或 \(T\)。那么我们就随机线段的分配情况。每一次随机分配后查找答案的时间复杂度为 \(O(n)\)。
现在来分析算法的正确度如何。总共有 \(2^n\) 种子集划分情况（每个元素有两种归属方式），考察有解的最坏情况，即有且仅有两个大小为 \(k\) 的不相交集合 \(X\) 和 \(Y\) 均满足能构成凸多边形。则一个划分有解，当且仅当 \(X \cap S = X,Y \cap S = \empty\) 或 \(X \cap S = \empty, Y \cap S = Y\)。方案数为 \(2^{n - 2k} \times 2\)。即除了那 \(2k\) 条钦定线段外的线段可以随意分配，且 \(X\) 和 \(Y\) 所在集合可以交换。一次正确的概率为 \(\frac{1}{2^{2k - 1}}\)。
假设随 \(t\) 次，那么总正确率为 \(1 - (1 - \frac{1}{2^{2k - 1}})^t\)。
由于总的时间复杂度为 \(O(n\log{n} + tn)\)，因此不要命的话 \(t\) 最大可以取 \(2\times 10^5\)。
当 \(k = 10\) 的时候正确率也不过 \(0.32\)。所以我想说明随机化在骗分上的作用显然更广泛。
正解是 dfs，哈哈。
下为随机化的实现，当个乐子看：六十多个点，这辈子都过不了。
#include<bits/stdc++.h>
#define PII pair<int, int>
#define MP make_pair
#define LL long long
using namespace std;
const int N = 1e3 + 5;
int n, k;
int len[N];
int acnt, bcnt, ida, idb;
PII a[N], b[N];
LL sa, sb, ma, mb;
bool flag = 0;
void work()
{
flag = 1;
puts("Yes");
for(int i = ida; i <= ida + k - 1; ++i)
printf("%d ", a[i].second);
for(int i = idb; i <= idb + k - 1; ++i)
printf("%d ", b[i].second);
}
int main()
{
srand(time(0));
scanf("%d %d", &n, &k);
for(int i = 1; i <= n; ++i)
scanf("%d", &len[i]);
sort(len + 1, len + n + 1);
int times = 200000;
while(times-- && !flag)
{
acnt = bcnt = 0;
for(int i = 1; i <= n; ++i)
{
int x = rand() & 1;
if(x & 1) a[++acnt] = MP(len[i], i);
else b[++bcnt] = MP(len[i], i);
}
if(acnt < k || bcnt < k) continue;
ida = idb = 0;
sa = sb = ma = mb = 0;
for(int i = 1; i <= k; ++i)
sa += a[i].first, sb += b[i].first;
ma = a[k].first, mb = b[k].first;
if(2 * ma < sa) ida = 1;
if(2 * mb < sb) idb = 1;
for(int i = k + 1; i <= acnt && !ida; ++i)
{
ma = a[i].first, sa += a[i].first - a[i - k].first;
if(2 * ma < sa) ida = i - k + 1;
}
for(int i = k + 1; i <= bcnt && !idb; ++i)
{
mb = b[i].first, sb += b[i].first - b[i - k].first;
if(2 * mb < sb) idb = i - k + 1;
}
if(ida && idb) work();
}
if(!flag) puts("No");
return 0;
}
P1224 [NOI2013] 向量内积
Problem
两个 \(d\) 维向量 \(A=[a_1,a_2,\ldots,a_d]\) 与 \(B=[b_1,b_2,\ldots,b_d]\) 的内积为其相对应维度的权值的乘积和，即：
\[(A,B)=\sum_{i=1}^d a_ib_i=a_1b_1+a_2b_2+\ldots+a_db_d \]现有 \(n\) 个 \(d\) 维向量 \(x_1,\ldots,x_n\) ，小喵喵想知道是否存在两个向量的内积为 \(k\) 的倍数。请帮助她解决这个问题。
Solution
从判断无解入手降低复杂度。
具体地，要判断第 \(i\) 个向量与之前的一堆向量中是否有一组向量点积为 \(2\) 或 \(3\) 的倍数，用这个向量乘之前向量的平方的和，结果为 \(x\)。如果没有方案，则 \(x \equiv (i - 1) \pmod k\)。
分类讨论：
当 \(k = 2\) 时，之前的每个向量与该向量内积均 \(\bmod 2 = 1\)，则之前的向量相加后与该向量的内积应为 \((i - 1) \bmod 2\)，相当于之前的每一组向量都剩了一个 \(1\)，一共剩出 \(i - 1\) 个 \(1\)。反之，若和向量与该向量的内积不等于 \((i - 1) \bmod 2\)，一定有解。
当 \(k = 3\) 时，之前的每个向量与该向量内积 \(x\) 均 \(\bmod 3 = 1,2\)，则 \(x^2 \bmod 3 = 1\)，那么我们判断前 \(i - 1\) 个向量与 \(i\) 的内积的平方和与 \((i - 1) \bmod 3\) 是否同余。分析一下，\((\sum\limits_{x = 1}^{d}a_{i, x}a_{j, x})^2 = \sum\limits_{x = 1}^{d}\sum\limits_{y = 1}^{d}a_{i, x}a_{i, y}a_{j, x}a_{j, y}\)。因此我们维护出 \(b_{x, y} = \sum\limits_{i}{a_{i, x} a_{i, y}}\)。
对于 \(k = 2\)，其实也可以用 \(k = 3\) 的方法，只不过时间复杂度上多了个 \(d\) 倍。
然后我们用 random_shuffle 随几次就可以了。
为什么还要随呢？因为被我们判断成无解的情况中也有可能有解，但有解被完全误判的概率由于 random_shuffle 的存在还是比较小的。
但看起来原数据并没有给无解的点？
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e5 + 5;
const int M = 105;
int n, d, k;
int a[N][M];
int id[N];
int b[N][M];
int get(int x)
{
int res = 0;
for(int i = 1; i <= d; ++i)
for(int j = 1; j <= d; ++j)
{
res += a[x][i] * a[x][j] * b[i][j] % k;
b[i][j] += a[x][i] * a[x][j] % k;
}
return res % k;
}
int check(int i, int j)
{
int res = 0;
for(int x = 1; x <= d; ++x)
res += a[i][x] * a[j][x];
return res % k;
}
int main()
{
scanf("%d %d %d", &n, &d, &k);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= d; ++j)
scanf("%d", &a[i][j]);
if(n <= 1000)
{
bool flag = 0;
for(int i = 2; i <= n && !flag; ++i)
for(int j = 1; j < i && !flag; ++j)
{
LL res = 0;
for(int x = 1; x <= d; ++x)
res += 1LL * a[i][x] * a[j][x];
if(res % k == 0)
{
flag = 1;
printf("%d %d\n", j, i);
}
}
if(!flag) puts("-1 -1");
return 0;
}
for(int i = 1; i <= n; ++i)
id[i] = i;
int T = 1;
while(T--)
{
memset(b, 0, sizeof(b));
random_shuffle(id + 1, id + n + 1);
for(int i = 1; i <= n; ++i)
{
int w = get(id[i]);
if(w == (i - 1) % k)
continue;
for(int j = 1; j < i; ++j)
if(!check(id[i], id[j]))
{
if(id[i] > id[j]) swap(id[i], id[j]);
printf("%d %d\n", id[i], id[j]);
return 0;
}
}
}
puts("-1 -1");
return 0;
}
CF329C Graph Reconstruction
Problem
现有一 \(n\) 个点 \(m\) 条边的简单无向图 \(G\)，保证每个点的度数均不超过 \(2\)，试求一与 \(G\) 点集相同而边集不相交的简单无向图 \(G'\) 使得 \(G'\) 中每个点度数均不超过 \(2\)，且 \(G'\) 的边数与 \(G\) 相同。
无解请输出\(-1\)。
\(1\le m\le n\le 10^5\)
Solution
对于第三个条件，即新图中不含原图中的边，等价于从原图的补图中选一个子图满足条件一和二。
而第二个条件，每个点的度数小于等于 \(2\)，容易想到链和环是满足的（且没有其他满足条件的情况），因此新图应该是一些链和环的组合。
又因为原图每个点的度数也小于等于 \(2\)，因此补图每个点的度数 \(\ge n - 3\)。
现在在补图中选 \(m\) 条边，求具体方案，若没有则判无解。
首先考虑什么时候可能会无解。
Ore's Theorem：对于一个含 \(n\) 个点的无向图，其存在哈密尔顿回路的一个充分条件是：对于任意两个不相邻的点 \(u, v\)，均满足：
\[d_u + d_v \ge n \]其中 \(d_x\) 表示点 \(x\) 的度数。
放在这道题的补图上，让两个的度数和大于 \(n\)，即 \(2(n - 3) \ge n\)，解得 \(n\ge 6\)。即对于任意 \(\ge 6\) 的补图，均能找到一个哈密尔顿回路，而哈密尔顿回路显然是合法的。
\(n < 6\) 的情况，我们可以暴力。
于是现在带着必然有解的想法分析 $n \ge 6 $ 的情况。既然有加强限制去找哈密尔顿回路的想法，我们不妨按照这个思路求出具体方案。
在一个给定的图中寻找哈密尔顿回路是
NPC问题。
没关系随机一下很简单。
随机一个排列，然后按顺序连一个环就行了。最后判断一下是否环内的所有边都没有在原图中出现过。如果是，那么就找到了一组合法解。
我们想知道正确率如何。
考虑随一次，\(f^{n}_{i}\) 表示排列长度为 \(n\) 的情况下，确定的排列的前 \(i\) 位后尚未产生错误的概率。
\(f^{n}_{1} = 1\)，一条边都没有，产生错误的概率为 \(0\)。然后转移，对 \(i > 1\)：
\[\begin{aligned} f^{n}_i &= f^{n}_{i - 1}\frac{1}{\binom{n - 1}{2}}\left(\binom{i - 2}{2} + (i - 2)(n - i + 1)\frac{n - i}{n - i + 1} + \binom{n - i + 1}{2}\frac{n - i - 1}{n - i + 1} \right) \\ &= \left(\frac{n - 3}{n - 1} \right)^n \end{aligned} \]需要指出，只是 近似估计，并不考虑实际取了哪些点，只关心一次选择中不产生错误的概率。（不会:(
当 \(n \ge 9\) 时，已经有 \(f^{n}_{n} \ge 0.1\)，因此随 \(10\) 次差不多可。
小范围暴力即可。或者多随几次也可以。
标签：信息学,竞赛,frac,int,复杂度,ge,算法,向量 From： https://www.cnblogs.com/Schucking-Sattin/p/17032095.html