Main » 2013 October 22 » [模拟赛NOIP2010]老师的奖金
3:44 PM [模拟赛NOIP2010]老师的奖金 |
简单的概率题，注意用分数运算#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #include<cmath> #define N 1010 #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) typedef long long LL; using namespace std; struct num{LL c,p;}; int g[N][N],value[N],n,m; LL gcd(LL a,LL b){if (a%b==0) return b;return gcd(b,a%b);} LL lcm(LL a,LL b){return a*b/gcd(a,b);} num operator+(num A,num B) { num C; LL G=lcm(A.p,B.p); A.c*=G/A.p;B.c*=G/B.p; C.c=A.c+B.c;C.p=G; return C; } void add(int x,int y){g[x][++g[x][0]]=y;} num DFS(int x) { if (g[x][0]==0) { num tmp; tmp.c=value[x];tmp.p=1; return tmp; }else { int i; num tmp;tmp.c=0;tmp.p=1;int L=g[x][0]; FOR(i,1,L) tmp=tmp+DFS(g[x][i]); LL G=gcd(tmp.c,L); L/=G;tmp.c/=G; tmp.p*=L; return tmp; } } int main() { scanf("%d%d",&n,&m); int i,tt,ttt; FOR(i,2,n) { int fff; scanf("%d",&fff); add(fff,i); } FOR(i,1,m) scanf("%d%d",&tt,&ttt),value[tt]=ttt; num ans=DFS(1); printf("%lld\n",ans.c); printf("%lld\n",ans.p); } |
|
|
| Total comments: 0 | |