电子商务网站开发基本流程图,WordPress 网格布局,无锡做网站企业,佛山新网站建设服务公司概率期望学习笔记 POJ3869 题意#xff1a;两个人转左轮手枪#xff0c;朝自己打#xff0c;枪里保证至少有一个空的#xff0c;你的对手上一轮活下来了#xff0c;现在到你了#xff0c;问重新转左轮和直接打#xff0c;哪个概率高。 做法#xff1a;考虑00#xff0… 概率期望学习笔记 POJ3869 题意两个人转左轮手枪朝自己打枪里保证至少有一个空的你的对手上一轮活下来了现在到你了问重新转左轮和直接打哪个概率高。 做法考虑0010两种串即可计算不转时下一个为空的概率。重新转的概率就是这个手枪里所有空的位置比所有的口的个数。注意串是循环的。 #include cstdio
#include iostream
#include algorithm
#include cstring
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
#define pb push_back
typedef long long ll;
typedef double LD;
const int N 2000000;
using namespace std;
char s[N];
int main() {scanf( %s,s1);int n strlen(s1),l1,rn,num00,num10;rep(ti,1,n) {if(s[r-1]0s[r]0)num0;if(s[r-1]1s[r]0)num1;r; s[r]s[l]; l;}if(num0*n(num1num0)*(num1num0))puts(SHOOT);else if(num0*n(num1num0)*(num1num0))puts(ROTATE);else puts(EQUAL);return 0;
}POJ2794 题意有9组牌每组4张两张牌的大小一样时可以消掉每次只能消掉最上面的牌然后一个在玩的时候如果有多种消法就会随机选择其中一种问他将所有牌都消掉的几率是多少。 做法用一个9位5进制数表示当前的状态直接记忆化搜索即可。一开始的写法T了。 #include cstdio
#include iostream
#include algorithm
#include cstring
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
#define pb push_back
typedef long long ll;
typedef double LD;
const int N 2000000;
using namespace std;
int a[20][20], M[266], num[9], A[9], f[22], ST, vis[N];
LD dp[N];
char s1[4];
double solve(int s) {if(vis[s]) return dp[s];vis[s]1;int A[9],tmp0;rep(i,0,8) A[i](s/f[i])%5;rep(i,1,8)rep(j,0,i-1) {if(A[i]A[j]a[i][A[i]]a[j][A[j]]) {dp[s] solve(s-f[i]-f[j]);tmp;}}if(tmp)dp[s]/(double)tmp;return dp[s];
}int main() {f[0]1; rep(i,1,9)f[i]f[i-1]*5;ST f[9]-1;M[6]0;M[7]1;M[8]2;M[9]3;M[T]4;M[J]5;M[Q]6;M[K]7;M[A]8;rep(i,0,8)rep(j,1,4) {scanf( %s,s1);a[i][j] M[s1[0]];}vis[0]1; dp[0]1.0;cout solve(ST) \n;//TLE
// memset(dp,0,sizeof(dp));
// int x,y,t,z,tmp;LD tt;
// dp[ST]1.0;
// per(s,ST,0) {
// z 0;tmp0;
// rep(i,0,8) {
// x (s/f[i])%5;
// if(num[a[i][x]]0)num[a[i][x]]1,tmp;
// zx;
// }
// memset(num,0,sizeof(num));
// if(tmp9)continue;
// if(z1)continue;
// tmp0;
// rep(j,0,8) {x (s/f[j])%5; if(x0)num[a[j][x]];}
// rep(j,0,8) if(num[j]2) tmp (1*(num[j]*(num[j]-1))1);
// tt (LD)dp[s]/tmp;
//
// rep(j,0,8) A[j](s/f[j])%5;
// rep(j,1,8)rep(k,0,j-1) {
// xA[k], yA[j];
// if(x!0y!0a[j][y]a[k][x]){
// t s; t-(f[k]f[j]);
// dp[t] tt;
// }
// }
// }
// printf(%f\n,(double)dp[0]);return 0;
}Codeforces1009E 题意给定序列a要求把长度n划分成一些段每一段的值形如a1,a2,..求这些值和的期望。 做法考虑每一个位置的期望。对于位置i值为a1只有它的前面恰好是一个分界线值为a2即他向前一个的位置恰好是个分界线同理可以列数位置i的值的期望为\(E_i \frac{a_1}{2^{1}} \frac{a_2}{2^{2}} ... \frac{a_{i-1}}{2^{i-1}} \frac {a_i}{2^{i-1}}\)\(E_1 a_1\)\(E_2 \frac{a_1}{2^{1}} \frac {a_2}{2^{1}}\)\(E_3 \frac{a_1}{2^{1}} \frac{a_2}{2^{2}} \frac {a_3}{2^{2}}\) $E_4 \frac{a_1}{2^{1}} \frac{a_2}{2^{2}} \frac {a_3}{2^{3}} \frac {a_4}{2^{3}} $ 直接求和即可。 #include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
#define per(i,a,b) for(int ia;ib;--i)
#define pb push_back
typedef long long ll;
const int N 1e6 7;
const ll mod 998244353;
using namespace std;
int n;
ll a[N],ans0,f[N];int main() {scanf(%d,n);f[0]1;rep(i,1,n)f[i](f[i-1]*2LL)%mod;rep(i,1,n) scanf(%I64d,a[i]);rep(i,1,n) {ll t;if(in) t ((a[i]*f[n-i])%mod (a[i]*((f[n-i-1]*(n-i))%mod))%mod)%mod;else t (a[i]*f[n-i])%mod;ans(anst%mod)%mod;}printf(%I64d\n,ans);return 0;
}Codeforces930B 题意给定一个串对他循环移位通过首字母和一个后边的字母判断移了多少位问成功的概率。 做法对每种移位情况下枚举每次去查哪个位置对每种字母找到最好的位置。即使得尽可能多的情况下这个位置的字母是不同的使得成功的概率更高。设字母\(c_i\)的最优的情况后边有\(num_i\)个位置字母唯一\(c_i\)的个数为\(cnt(c_i)\)所以以这种字母开头成功概率为\(\frac{num_i}{cnt(c_i)}\)把所有字母累加起来就是\(\sum {\frac{num_i}{cnt(c_i)}·\frac {cnt(c_i)}{n}} \frac {\sum {num_i}}{n}\) #include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
#define per(i,a,b) for(int ia;ib;--i)
#define pb push_back
typedef long long ll;
const int N 5005;
using namespace std;
int n,ff[N],num[26];
char s[N1];
vectorint v[26];
int main() {scanf( %s,s1);n strlen(s1);rep(i,1,n) s[in]s[i];rep(i,1,n) v[s[i]-a].pb(i);rep(i,0,25)rep(x,1,n-1){int f0;memset(num,0,sizeof(num));for(auto p: v[i]) num[s[px]-a];int tt 0;rep(j,0,25)if(num[j]1)tt;ff[i]max(ff[i],tt);}int tmp 0;rep(i,0,25)tmpff[i];printf(%.10f\n,1.0*tmp/(double)n);return 0;
}Codeforces935D 题意给定两个序列S1, S2他们有一些位置的值是确定的一些是不确定的可以填入1~m中的数问S1比S2字典序高的概率。 做法从高位到低位递推dp[i][0]表示前i个位置S1等于S2的概率dp[i][1]表示前i个位置S1大于S2的概率。分情况讨论直接做即可。 #include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
#define per(i,a,b) for(int ia;ib;--i)
#define pb push_back
typedef long long ll;
const int N 1e5 7;
const int mod 1e9 7;
using namespace std;
ll n,m,a[N],b[N],dp[N][2],invm,invmm,inv2;
ll q_pow(ll a,ll b) {a%mod;ll ans 1;while(b) {if(b1) ans(ans*a)%mod;a(a*a)%mod;b1;}return ans;
}
ll P(int i,int opt) {if(!opt) {if(a[i]b[i]a[i]b[i]) return 1LL;if(a[i]b[i]a[i]!b[i]) return 0LL;if(!a[i]b[i]) return invm%mod;if(a[i]!b[i]) return invm%mod;if(!a[i]!b[i]) return invm%mod;}else {if(a[i]b[i]a[i]b[i]) return 1LL;if(a[i]b[i]a[i]b[i]) return 0LL;if(!a[i]b[i]) return ((m-b[i])%mod*invm)%mod;if(a[i]!b[i]) return ((a[i]-1LL)%mod*invm)%mod;if(!a[i]!b[i]) return ((((((m-1LL)%mod)*m)%mod*inv2)%mod)*invmm)%mod;}
}int main() {scanf(%I64d%I64d,n,m);inv2 q_pow(2LL,mod-2);invm q_pow(m,mod-2);invmm (invm*invm)%mod;rep(i,1,n)scanf(%I64d,a[n-i1]);rep(i,1,n)scanf(%I64d,b[n-i1]);dp[1][0]P(1,0), dp[1][1]P(1,1);rep(i,2,n) {dp[i][0] (P(i,0)*dp[i-1][0])%mod;dp[i][1] (P(i,1) (P(i,0)*dp[i-1][1])%mod)%mod;}(dp[n][1]mod)%mod;printf(%I64d\n,dp[n][1]);return 0;
}Codeforces280C 题意给定一棵树每次操作可以删除一颗子树。问期望的操作次数。 题解考虑每个点对答案的贡献点i最终一定会被删除如果删除它的时候是在删除它的祖先则他对答案无贡献如果是通过自己删的则对答案有贡献。能删除它的祖先共有这个点的深度-1 个点。所以点u的期望就是\(\frac{1}{deep[u]}\)最后累加起来。一开始推出了深度是1的树的公式然后推广了一下写的自底向上算。。结果gg这题思路真的有点神。 #include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
#define per(i,a,b) for(int ia;ib;--i)
typedef long long ll;
const int N 1e5 7;
using namespace std;
struct edge{int e,nxt;}E[N1];
int cc,h[N];
void add(int u,int v) {E[cc].ev;E[cc].nxth[u];h[u]cc;cc;}
int n,dep[N];
double ans 0;
void dfs(int u,int pre) {ans 1.0/dep[u];for(int ih[u];~i;iE[i].nxt) if(E[i].e!pre) {dep[E[i].e] dep[u] 1;dfs(E[i].e,u);}
}
int main() {scanf(%d,n);rep(i,1,n) h[i] -1;rep(i,1,n-1) {int x,y;scanf(%d%d,x,y);add(x,y), add(y,x);}dep[1] 1; dfs(1,0);printf(%.12f\n,ans);return 0;
}Codeforces452C 题意把n副一样的牌混在一起每副牌包含m张从其中选n张问取两次牌相同的概率。 做法考虑一种牌x的贡献枚举x的个数k现在先从n*m张牌中挑n张其中有k张x然后再考虑从中两次选出x的概率可以列出式子\[\sum_{k1}^{min(m,n)} \frac {C^k_m·C_{nm-m}^{n-k}·k^2}{C_{nm}^n·n}\] #include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
#define per(i,a,b) for(int ia;ib;--i)
typedef long long ll;
const int N 1e5 7;
using namespace std;
int n,m;
int main() {scanf(%d%d,n,m);double Cnmn 1.0, Cmx m, Cnm_x 1.0, ans 0;rep(i,1,n) Cnmn Cnmn * (n*m - i 1)/i;rep(i,1,n-1) Cnm_x Cnm_x * ((n-1.0)*m - i 1)/i;rep(i,1,min(n,m)) {ans Cmx*Cnm_x*i*i/Cnmn/n;Cmx Cmx * (m - (i1) 1.0)/(i1);Cnm_x Cnm_x * (n-(i1)1)/((n-1.0)*m - (n-(i1)1) 1);}printf(%.10f\n,ans);return 0;
}Codeforces261B \(f[i][j][k]\)表示前i个元素取j个构成体积k的方法数枚举最后放不进去的元素是哪个每种情况对答案的贡献就是\(\sum {f[n][j][k]·j!·(n-j-1)!}\)计算f[i][j][k]的时候记得不要放x最后的答案除\(n!\)和背包一样\(i\) 这一维可以去掉j和k都相当于一种体积。。。智商逐渐消失。。
#include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
#define per(i,a,b) for(int ia;ib;--i)
#define pb push_back
typedef long long ll;
const int N 52;
using namespace std;
int n,a[N],p,sum;
double f[N][N], ans, fc[N]; // (前i个元素)取j个,构成体积k的方法数int main() {scanf(%d,n);rep(i,1,n) scanf(%d,a[i]),suma[i];scanf(%d,p);fc[0] 1.0;rep(i,1,n) fc[i]fc[i-1]*i;if(sum p) {printf(%.10f\n,(double)n);}else {rep(x,1,n) { // 枚举那个恰好没被使用的元素memset(f,0,sizeof(f));rep(i,0,n) f[0][0] 1;rep(i,1,n) {per(k,p,a[i]) per(j,i,1) {if(i!x)f[j][k] f[j-1][k-a[i]];}}rep(i,0,n-1) rep(k,max(p-a[x]1,0),p) {ans f[i][k]*fc[i]*fc[n-i-1]*i;}}ans / fc[n];printf(%.10f\n,ans);}return 0;
}转载于:https://www.cnblogs.com/RRRR-wys/p/9385616.html
