大家好,又见面了,我是全栈君。
题目链接: https://vjudge.net/problem/LightOJ-1027
题目描述: 有N个门, 每个门的选择是等概率的, 如果选择到正数, 我将在正数秒后逃出迷宫, 如果是负数就重新选, 问逃离的期望时间是多少
解题思路: 我这道题犯蠢了, 我认为是…..说不太明白, 看程序吧, 一下子就能看懂, 其中涉及到了一个约分, 但是我没想到就算是long long 也会溢出, 那么我将约分放进每次mul中呢? 也是不行的, 因为都是素数呢, 不是一样会溢出? 自己在半个小时后才意识到这个蠢问题………
正确解法是 Y = P1 * T1 + P2 * (T2 + Y) 移项就可以整理出Y = 正数个数的倒数 * ∑abs(Xi) , 再将0的情况单独扣出去就可以了
代码: 下面第一个是我的错误代码, 谨记
#include <iostream> #include <cstdio> #include <string> #include <vector> #include <cstring> #include <iterator> #include <cmath> #include <algorithm> #include <stack> #include <deque> #include <map> #include <set> #include <queue> #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 #define mem0(a) memset(a,0,sizeof(a)) #define mem1(a) memset(a,-1,sizeof(a)) #define sca(x) scanf("%d",&x) //#define de printf("=======\n") typedef long long ll; using namespace std; ll x[103]; ll gcd(ll a, ll b) { return b==0 ? a : gcd(b, a%b); } struct node { ll nu; ll de; node() { nu = de = 1; } void mul(ll x, ll y) { nu *= x; de *= y; ll g = gcd(nu, de); nu /= g, de /= g; } void sim() { ll g = gcd(nu, de); nu /= g, de /= g; } }; int main() { int t; sca(t); int cases = 1; while( t-- ) { ll n; scanf( "%lld", &n ); ll cnt = 0; ll sum = 0; for( int i = 0; i < n; i++ ) { scanf( "%lld", &x[i] ); if( x > 0 ) { sum += x[i]; cnt++; } } if( cnt == 0 ) { printf( "Case %d: inf\n", cases++ ); continue; } else if( cnt == n ) { node temp; for( ll i = 0; i < n; i++ ) { temp.mul(x[i], n); } if( temp.nu == 0 || temp.de == 0 ) while(1) {} temp.sim(); printf( "Case %d: %lld/%lld\n", cases++, temp.nu, temp.de ); continue; } node res; res.mul(sum*n, cnt); res.mul(n-cnt, cnt); res.sim(); printf( "Case %d: %lld/%lld\n", cases++, res.nu, res.de ); } return 0; }
View Code
#include <iostream> #include <cstdio> #include <string> #include <vector> #include <cstring> #include <iterator> #include <cmath> #include <algorithm> #include <stack> #include <deque> #include <map> #include <set> #include <queue> #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 #define mem0(a) memset(a,0,sizeof(a)) #define mem1(a) memset(a,-1,sizeof(a)) #define sca(x) scanf("%d",&x) //#define de printf("=======\n") typedef long long ll; using namespace std; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); } int main() { int t; sca(t); int cases = 1; while( t-- ) { int n; sca(n); int sum = 0; int cnt = 0; for( int i = 0; i < n; i++ ) { int x; sca(x); sum += abs(x); if( x > 0 ) cnt++; } if( cnt == 0 ) { printf( "Case %d: inf\n", cases++ ); continue; } int g = gcd(sum, cnt); sum /= g; cnt /= g; printf( "Case %d: %d/%d\n", cases++, sum, cnt ); } return 0; }
AC
思考: 在想算法之后, 在写代码之前一定要这个算法代码到底能不能实现, 像我这个De了半个多小时的BUG才发现算法能算出来, 就是无法实现, 以后先公式, 看能不能公式出来, 概率题好多都是这样的
转载于:https://www.cnblogs.com/FriskyPuppy/p/7519995.html
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/108159.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...