文章目錄

• CodeChef-Milestones
• • problem
  • solution
  • code
• CF364D-Ghd
• • problem
  • solution
  • code

設(shè)隨機(jī)化一次的正確率為 $p$，一次的復(fù)雜度為 $O(f(n))$。則隨機(jī)的期望次數(shù) $k$：
$$\begin{gathered} k=\sum _{i=1}^{\infty }p(1?p{)}^{i?1}i(1) \\ (1?p)k=\sum _{i=1}^{\infty }p(1?p{)}^{i}i=\sum _{i=2}^{\infty }p(1?p{)}^{i?1}(i?1)(2) \\ (1)?(2)?p?k=p+\sum _{i=2}^{\infty }p(1?p{)}^{i?1}?k=1+\sum _{i=2}^{\infty }(1?p{)}^{i?1}=\sum _{i=0}^{\infty }(1?p{)}^i \end{gathered}$$
由等比公式得： $k={\sum }_{i=0}^{\infty }(1?p{)}^i=\frac{1?(1?p{)}^{\infty }}{1?(1?p)}=\frac{1}{p}$。

綜上隨機(jī)算法求解的期望復(fù)雜度為 $O(p^{?1}f(n))$。

CodeChef-Milestones

problem

題目鏈接

solution

因?yàn)樽疃嘀挥衅邨l直線就可以覆蓋所有點(diǎn)，可以推出 覆蓋點(diǎn)最多的直線至少覆蓋 $?\frac{n}{7}?$ 個(gè)點(diǎn)。

也就是說，兩個(gè)點(diǎn)屬于同一直線的概率為 $\frac{1}{7}$。

期望來說，$7$ 次隨機(jī)化點(diǎn)就可以通過了，但是保險(xiǎn)起見，可以運(yùn)行 $1000$ 次。

時(shí)間復(fù)雜度 $O(Tnk)$，超了但是跑得很快》》o_o …

code

#include <bits/stdc++.h> using namespace std; #define maxn 10005 int T, n; double x[maxn], y[maxn];int main() {scanf( "%d", &T );while( T -- ) {scanf( "%d", &n );for( int i = 1;i <= n;i ++ ) scanf( "%lf %lf", &x[i], &y[i] );mt19937 wwl(time(0));uniform_int_distribution < int > range( 1, n );int ans = 0;for( int t = 1;t <= 1000;t ++ ) {int a = range( wwl ), b = range( wwl );int cnt = 0;if( x[a] == x[b] ) {for( int i = 1;i <= n;i ++ )if( x[i] == x[a] ) cnt ++;}else {cnt = 1;double k = ( y[a] - y[b] ) / ( x[a] - x[b] );for( int i = 1;i <= n;i ++ )if( x[i] != x[a] and ( y[i] - y[a] ) / ( x[i] - x[a] ) == k ) cnt ++;}ans = max( ans, cnt );}printf( "%d\n", ans );}return 0; }

CF364D-Ghd

problem

題目鏈接

solution

貪心地，$|S^{\prime }|$ 選出的子集大小應(yīng)該恰好為 $?\frac{n}{2}?$，因?yàn)檫x擇的數(shù)越多，$\gcd$ 只會(huì)受到更多限制變小而不會(huì)變大。

那么每個(gè)數(shù)都是 $\frac{1}{2}$ 的概率會(huì)屬于最后答案子集。

隨機(jī)化 $10$ 次，正確率 $1?(1?\frac{1}{2}{)}^{10}$ 已經(jīng)很優(yōu)秀了。

隨機(jī)化出一個(gè)數(shù) $a_x$ 假設(shè)其屬于最后答案子集。

先求出 $a_x$ 的所有因子數(shù)，最后的答案肯定是 $a_x$ 的因子。用桶 $cn{t}_p$ 記錄下來。

再求出與 $a_i$ 的 $\gcd$，枚舉 $\gcd$ 的因子數(shù)，找到因子所在的桶，$cn{t}_p++$。

最后進(jìn)行桶的合并，如果桶 $p$ 代表的因子是桶 $q$ 代表的因子倍數(shù)，則有 $cn{t}_q+=cn{t}_p$。

$1e12$ 內(nèi)因子數(shù)最多的不超過 $6800$ 個(gè)。

單次時(shí)間復(fù)雜度，假設(shè) $\delta (n)$ 為 $n$ 的因子個(gè)數(shù)，$O(\sqrt{a_x}+\delta (n{)}^2+n\log n)$。

code

#include <bits/stdc++.h> using namespace std; #define int long long #define maxn 1000005 int n, ans, tot; int a[maxn], d[maxn], cnt[maxn];int gcd( int x, int y ) {if( ! y ) return x;else return gcd( y, x % y ); }void divide( int x ) {tot = 0;for( int i = 1;i * i <= x;i ++ )if( x % i == 0 ) {d[++ tot] = i;if( i * i != x ) d[++ tot] = x / i;}sort( d + 1, d + tot + 1 ); }void solve( int x ) {divide( x );for( int i = 1;i <= tot;i ++ ) cnt[i] = 0;for( int i = 1;i <= n;i ++ ) {int g = gcd( x, a[i] );int pos = lower_bound( d + 1, d + tot + 1, g ) - d;cnt[pos] ++;}for( int i = 1;i <= tot;i ++ )for( int j = i + 1;j <= tot;j ++ )if( d[j] % d[i] == 0 ) cnt[i] += cnt[j];for( int i = tot;i;i -- ) {if( d[i] <= ans ) break;if( cnt[i] >= ( n + 1 >> 1 ) ) ans = max( ans, d[i] );} }signed main() {scanf( "%lld", &n );for( int i = 1;i <= n;i ++ ) scanf( "%lld", &a[i] );mt19937 wwl(time(0));uniform_int_distribution < int > range( 1, n );for( int t = 1;t <= 10;t ++ ) {int x = range( wwl );solve( a[x] );}printf( "%lld\n", ans );return 0; }

總結(jié)

以上是生活随笔為你收集整理的[骗分技巧——随机化Ⅰ]CodeChef-Milestones，CF364D-Ghd的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。