文章目錄

• [Poi2014]Couriers
• • problem
  • solution
  • code
• CodeChef - TKCONVEX
• • problem
  • solution
  • code

隨機算法的典型套路：枚舉太花時，轉化為隨機一個數。然后通過對正確率的分析，選擇一個隨機的次數來卡。前提是要保證每一次檢驗隨機是否為答案的時間復雜度要能夠接受。一般不超過 $n\log n$。

[Poi2014]Couriers

problem

BZOJ 3524

solution

如果有解，也就是說區間內的隨機選擇一個數是答案的概率不大于 $\frac{1}{2}$。否則怎么隨機都無解。

可以預處理相同值的數出現位置，二分查找求出某個值在 $[l,r]$ 區間的出現次數。

所以一次判斷是 $O(\log n)$ 的。

隨機 $20$ 次，正確率就在 $1?10^{?5}$ 左右了。

code

#include <bits/stdc++.h> using namespace std; #define maxn 500005 int n, m; int a[maxn]; vector < int > pos[maxn];int find_l( int x, int p ) { int l = 0, r = pos[x].size() - 1, ans;while( l <= r ) {int mid = l + r >> 1;if( pos[x][mid] >= p ) ans = mid, r = mid - 1;else l = mid + 1;}return ans; }int find_r( int x, int p ) {int l = 0, r = pos[x].size() - 1, ans;while( l <= r ) {int mid = l + r >> 1;if( pos[x][mid] <= p ) ans = mid, l = mid + 1;else r = mid - 1;}return ans; }int main() {scanf( "%d %d", &n, &m );for( int i = 1;i <= n;i ++ ) {scanf( "%d", &a[i] );pos[a[i]].push_back( i );}mt19937 wwl(time(0));for( int i = 1, l, r;i <= m;i ++ ) {scanf( "%d %d", &l, &r );uniform_int_distribution < int > range( l, r );for( int k = 1;k <= 20;k ++ ) {int x = range( wwl ); x = a[x];int L = find_l( x, l );int R = find_r( x, r );if( R - L + 1 << 1 > r - l + 1 ) { printf( "%d\n", x ); goto next_turn; }}printf( "0\n" );next_turn:;}return 0; }

CodeChef - TKCONVEX

problem

vjudge鏈接

solution

定理1 能構成多邊形的線段，必須滿足任意一條邊長度都小于剩余所有邊長度的總和。

這是顯然的，因為要形成封閉的圖形，可以看作是這條邊是最后一條連接兩個端點的直線段，其余線段繞成了一個弧形。

事實上只需要長度最長的線段滿足這個性質即可。

此定理只能保證構成多邊形，但不保證是凸多邊形。所以提出下一個定理。

定理2 任意非凸多邊形都可以通過對邊的旋轉和平移構成一個新凸多邊形。

在本題中，可以選擇的集合為 $\left(\genfrac{}{}{0ex}{}{n}{2k}\right)\left(\genfrac{}{}{0ex}{}{2k}{k}\right)$，已經是非常大了，不可能一個一個檢驗。

定理3 假設有解，那么一定存在一個解(大小為 $k$ 的子集)滿足：對所有線段長度排序后，這個子集的元素對應排序后序列的一段連續區間。

證明：顯然。假設子集為 $S$，排序后的序列為 $P$。

如果其對應的元素構成不連續的區間。即 ${?}_i{P}_i\in S\wedge P_{i+1}\in /S$。

找到滿足條件的 $i$，則 $i$ 肯定是一段連續區間的右端點，保證 $i$ 不是若干個不連續區間的最右端點。

重復操作移除 $P_i$，加入 $P_{i+1}$。直到將左邊的若干個不連續區間和最右邊的一個連續區間拼接成一整個大連續區間。

這樣操作后，可以發現長度最大的依然是最右邊的端點，沒有移動過，但是其余線段的長度都有所增長。

既然原來都是符合條件的子集，那么現在肯定也是一個符合條件的子集。

題目要求兩個大小為 $k$ 的凸多邊形。

不妨設第一個凸多邊形從邊集合為 $S$ 中，選擇另一個凸多邊形從邊集合 $\bar{S}$ 中選擇。

滿足 $S?\bar{S}=?\wedge S?\bar{S}=\Omega$。

那么對于每一條線段，有 $\frac{1}{2}$ 的概率屬于 $S$，$\frac{1}{2}$ 的概率屬于 $\bar{S}$。換言之，選出任意一個子集的概率是相同的。

那么就對每條邊隨機其屬于哪個集合。

隨機劃分集合后，$O(n)$ 的可以做到快速判斷這個集合能否選出一個子集構成凸多邊形。

最后來分析一下這個隨機的正確率。

劃分的總方案數為 $2^n$。考慮極端最壞情況，有且僅有兩個互不相交的集合 $X,Y$ 可以構成凸多邊形。

那么一個隨機劃分方案有解，當且僅當 $S?X=X\wedge S?Y=?$ 或者 $S?Y=Y\wedge S?X=?$。

這樣的方案數為 $2^{n?2k}\times 2$。

因此在最壞情況下選出一個合法劃分的概率為 $\frac{1}{2^{2k?1}}$。

設隨機運行以上算法 $t$ 次，那么 $t$ 最多取到 $20000$ 左右，時間復雜度為 $O(n\log n+tn)$。

在 $k=6$ 時，正確率為 $1?(1?\frac{1}{2^{11}}{)}^t\approx 1?10^{?5}$。

注意：原題目 $k\in [3,10]$。這個隨機算法是不能通過的。所以下面的代碼不保證正確性。

code

#include <bits/stdc++.h> using namespace std; #define maxn 1005 #define int long long struct node { int val, id; }a[maxn]; int n, k; int s[2][maxn]; pair < int, int > ans[2];signed main() {scanf( "%lld %lld", &n, &k );for( int i = 1;i <= n;i ++ ) scanf( "%lld", &a[i].val ), a[i].id = i;sort( a + 1, a + n + 1, []( node x, node y ) { return x.val < y.val; } );mt19937 wwl;uniform_int_distribution < int > range( 0, 1 );for( int t = 1;t <= 20000;t ++ ) {s[0][0] = s[1][0] = 0;for( int i = 1;i <= n;i ++ ) {int x = range( wwl );s[x][++ s[x][0]] = i;}int cnt = 0;for( int j = 0;j <= 1;j ++ ) {for( int i = 1, len = 0, sum = 0;i <= s[j][0];i ++ ) {len ++, sum += a[s[j][i]].val;if( len > k ) sum -= a[s[j][i - k]].val;if( len == k and sum > (a[s[j][i]].val << 1) ) {ans[j] = make_pair( i - k + 1, i );cnt ++;break;}}}if( cnt == 2 ) goto yes;}no : return ! printf( "No\n" );yes :printf( "Yes\n" );for( int i = 0;i <= 1;i ++ )for( int j = ans[i].first;j <= ans[i].second;j ++ )printf( "%lld ", a[s[i][j]].id );return 0; }

總結

以上是生活随笔為你收集整理的[骗分技巧——随机化Ⅱ] [Poi2014]Couriers，CodeChef - TKCONVEX的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。