可以发现第一件物品的获得和第二件物品的获得是独立事件。所以N件物品的总期望步数就是每一件的期望步数之和。
而每一件物品最多失败100次，所以可以直接算。
其实就是模拟手算过程，考察代码能力。 可以想想拿到样例手算是怎么算的。
基本思路就是自底向上递推。
5在最左边，所以5的父节点肯定是2。
6和5的距离是2，所以5和6肯定有公共父节点。于是6的父节点也是2。
7和6的距离大于2，所以7和6肯定没有公共父节点。于是7的父节点是4（3是叶子结点，所以不会是7的父节点）。
8和7距离是2，所以8的父节点也是4。
同理一层一层向上推就行了。
这题数据范围非常小，节点数只有100。所以可以各种暴力做...
数据范围很小，暴搜+最优化剪枝就行。
有点类似整数划分的动态规划。
觉得思路应该没错，但是总是WA，不知道哪里错了，哪位能指出来吗？思路是先求以P概率开始拿到第一个item的期望步数p1，然后求以p/2概率开始拿到第二个item的期望步数p2,然后得到总的期望步数p1+（n-1）*p2
#include <iostream>
#include <cmath>
using namespace std;
int main(){
int p,q,n;
while (cin>>p>>q>>n) {
double p1=0,p2=0,a=1;
int b=p;
for(int i=1;;i++){
if(b<100){
p1+=a*b*i/(double)100;
a*=(100-b)/(double)100;
b+=q;
}else{
p1+=a*i;
break;
}
}
a=1;b=p/2;
for(int i=1;;i++){
if(b<100){
p2+=a*b*i/(double)100;
a*=(100-b)/(double)100;
b+=q;
}else{
p2+=a*i;
break;
}
}
printf("%.2f",p1+p2*(n-1));
}
return 0;
}
求问第一题错哪里了
double Exi(int P,int Q){
int k = ceil((100-P)*1.0/Q);
double tmp;
for(tmp = k+1 ; k >= 1;){
k--;
tmp = tmp * (100-P-k*Q)/100.0 + (k+1)*(P+k*Q)/100.0;
}
return tmp;
}
主函数里
cin>>p>>q>>N;
for(long long i = 0;i<=N-1;i++){
ans = ans + Exi(p>>i,q);
}
一直WA，实在不知道哪里错了。 那个Exi就是用来算E(Xi)的 最后的E(X) = E(X1)+E(X2)+....+E(XN)
def get(p, q, n):
p = float(p)
q = float(q)
return expectation(p/100, q/100, n, 0)
def expectation(prob, add, target, items = 0, count = -1):
count += 1
if prob >= 1:
# Must get
items += 1
prob = r(1, items)
# print("get: 1")
e = expectation(prob, add, target, items, count)
return e
# not must get
if items != target:
# not end node
# print("get" + str(r(prob, items)))
re = r(prob, items)
win = re*expectation(re, add, target, items+1, count)
# print("miss" + str(1-re))
miss = (1-re)*expectation(prob+add, add, target, items, count)
return win + miss
else:
# end node
# print("endnode" + str(count))
return count
while True:
try:
(p, q, n) = (int(x) for x in raw_input().split())
print(get(p, q, n))
except EOFError:
break
来围观的。朋友刚刚告诉我这道题，稍微写了一下思路（意在清晰，不在优化）。 结果发现不给提交了。 不知道对不对？
你可在题库里提交
//有大神帮忙看一下我的第二题吗，不知道错在哪里了，哭……
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
#include <string>
#include <sstream>
#include <stack>
#include <queue>
using namespace std;
#define MAXN 105
int dis[MAXN][MAXN];
int a[MAXN];
int f[MAXN];
int leaves[MAXN];
int father[MAXN];
int l[MAXN], r[MAXN];
int N, M, K;
int main(){
int tmp;
cin >> N >> M >> K;
l[1] = 1;
for(int i=1; i <= M; i++){
cin >> tmp;
r[i] = l[i] + tmp;
l[i + 1] = r[i];
}
for(int i=1; i <= N; i++){
cin >> a[i];
}
memset(f, 0, sizeof(f));
for(int i=1; i <= K; i++){
cin >> leaves[i];
f[leaves[i]] = 1;
}
memset(dis, 0, sizeof(dis));
for(int i=1; i <= K; i++){
for(int j = 1; j <= K; j++){
cin >> dis[leaves[i]][leaves[j]];
}
}
for(int i=M; i > 1; i--){
int up_node = l[i-1];
while(f[up_node]) up_node++;
father[l[i]] = up_node;
for(int k = 1; k <= N; k++){//补充距离
int tmp_dis = dis[l[i]][k] - 1;
if (tmp_dis < 0) tmp_dis = 0;
dis[up_node][k] = dis[k][up_node] = tmp_dis;
}
for(int j=l[i]+1; j < r[i]; j++){
if (dis[j-1][j] <= 2)
father[j] = father[j-1];
else{
int tmp_up_node = up_node;
while(f[++up_node]);
father[j] = up_node;
dis[tmp_up_node][up_node] = dis[up_node][tmp_up_node] = dis[j-1][j] - 2;
for(int k = 1; k <= N; k++){ //补充距离
int tmp_dis = dis[j][k] - 1;
if (tmp_dis < 0) tmp_dis = 0;
dis[father[j]][k] = dis[k][father[j]] = tmp_dis;
}
}
}
}
for(int i=1; i < N; i++ ){
cout << father[i] << ' ';
}
cout << father[N] << endl;
return 0;
}
//有大神帮忙看一下我的第二题吗，不知道错在哪里了，哭……
using namespace std;
int dis[MAXN][MAXN]; int a[MAXN]; int f[MAXN]; int leaves[MAXN]; int father[MAXN]; int l[MAXN], r[MAXN]; int N, M, K; int main(){ int tmp; cin >> N >> M >> K; l[1] = 1; for(int i=1; i <= M; i++){ cin >> tmp; r[i] = l[i] + tmp; l[i + 1] = r[i]; } for(int i=1; i <= N; i++){ cin >> a[i]; } memset(f, 0, sizeof(f)); for(int i=1; i <= K; i++){ cin >> leaves[i]; f[leaves[i]] = 1; } memset(dis, 0, sizeof(dis)); for(int i=1; i <= K; i++){ for(int j = 1; j <= K; j++){ cin >> dis[leaves[i]][leaves[j]]; } } for(int i=M; i > 1; i--){ int up_node = l[i-1]; while(f[up_node]) up_node++; father[l[i]] = up_node; for(int k = 1; k <= N; k++){//补充距离 int tmp_dis = dis[l[i]][k] - 1; if (tmp_dis < 0) tmp_dis = 0; dis[up_node][k] = dis[k][up_node] = tmp_dis; } for(int j=l[i]+1; j < r[i]; j++){ if (dis[j-1][j] <= 2) father[j] = father[j-1]; else{ int tmp_up_node = up_node; while(f[++up_node]); father[j] = up_node; dis[tmp_up_node][up_node] = dis[up_node][tmp_up_node] = dis[j-1][j] - 2; for(int k = 1; k <= N; k++){ //补充距离 int tmp_dis = dis[j][k] - 1; if (tmp_dis < 0) tmp_dis = 0; dis[father[j]][k] = dis[k][father[j]] = tmp_dis; } } } } for(int i=1; i < N; i++ ){ cout << father[i] << ' '; } cout << father[N] << endl; return 0; }
试着做去年题时还能过两三道呢，心理落差太大了/(ㄒoㄒ)/~~
+1...
＋2...
唉 有点出乎意料。一开始都觉得出简单了... 程序都没有超过100行的...
+3。。。
第一题不是独立事件吧……取得第一个物品后就reset到新的initial P了……
你reset和前一个物品没关系啊 直接除以2啊
嗯对……我是指初始P不同，不是直接加就行……独立的话好像是的
之前我也考虑的很简单，结果发现这个貌似也很复杂，首先重置后的概率分布是跟之前找到物品个数有关的
都说的很明白了，获得每个物品是独立的，所有的期望是每个物品获得期望的和。不知道为什么重置后的概率会很难求。。就一个for循环从1到N结束了，每次循环计算一下期望，然后求一下和。
E(X2)=E(X3)=...E(Xn),E(X1)单独算。