https://vjudge.net/problem/UVA-11971
题目
有一根长度为$n$的木条,随机选$k$个位置把他们切成$k+1$段木条,求这些小木条能组成一个多边形的概率。
题解
能组成多边形可以转化为最长的木条长度小于剩余木条长度的和。
先证明任意的$n$边形都能通过合并两条边转化为一个$(n-1)$边形
如图,AE,DE可以构成AF,DC=CF,就可以减少一条边,一直减少,就可以得到一个三角形,反过来,三角形也可以拆成多边形
如果每次都选择最长的边,那么最后就能得到一个三角形。根据三角形组成的充要条件,就可以得到整个多边形最长的边小于其他边之和。
于是问题就变成了一个线段上面随机切$K$次,求最长的线段长度大于等于$frac{1}{2}$的概率。
那么只算在线段的1/2长度外面切
下面用了一个构造,先把线段拼成一个圆,然后只在圆的一半部分切,然后选一个端点拆成线段
概率就是$1-frac{1}{2}^K imes (k+1)$(此处存疑= =)
AC代码
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #define REP(i,a,b) for(register int i=(a); i<(b); i++) #define REPE(i,a,b) for(register int i=(a); i<=(b); i++) #define PERE(i,a,b) for(register int i=(a); i>=(b); i--) #ifdef sahdsg #define DBG(...) printf(__VA_ARGS__) #else #define DBG(...) (void)0 #endif #define ln log using namespace std; typedef long long LL; int n,k; LL gcd(LL a, LL b) { return b==0?a:gcd(b,a%b); } int main() { int T; scanf("%d", &T); int kase=0; while(0<T--) { scanf("%d%d", &n, &k); //(2^k-1+k)/(2^k) LL a=(1ULL<<k)-1-k; LL b=1ULL<<k; LL g=gcd(a,b); a/=g, b/=g; printf("Case #%d: %lld/%lld ", ++kase, a, b); } return 0; }