相关总结：http://www.cnblogs.com/mcflurry/p/3724649.html#3395978
A.angry_birds_again_and_again（定积分）
B.Circle（高斯消元？/递推）
C.Colorful Cupcakes（dp？）
D.Devour Magic（线段树）
E.Factorial（10以内阶乘）
F.Full Binary Tree（二叉树）
G.Hearthstone II（dp）
H.Painting Cottages（几何）
I.Tree（）
J.Weighted Median（sort排序）
A.angry_birds_again_and_again
d.求面积
s.设抛物线方程y=a*x^2+bx+c，求出a、b，定积分求面积。
#include<iostream> #include<stdio.h> #include<math.h> using namespace std; int main(){ int T; double px,tx,alfa; double a,b; double area,area1,area2; scanf("%d",&T); while(T--){ scanf("%lf%lf%lf",&px,&tx,&alfa); b=tan(alfa); a=(b*px)/(tx*tx-2*tx*px); area1=(a/3)*(tx*tx*tx)+(b/2)*(tx*tx);//抛物线面积 area2=((a*(tx*tx)+b*tx)*(px-tx))/2;//三角形面积 area=area1+area2; printf("%.3f ",area); } return 0; }
B.Circle
d.n个数围成一个圈，编号0~n-1，从一个数到其上一个和下一个的数的概率相同（即都是0.5）。给出n，求从0出发到达一个数x所需要的步数的数学期望。
s.据说可以用高斯消元？
这里用递推可以水一下。
首先可以确定三个结论(1.d[i]=0.5*d[i+1]+0.5*d[i-1] , 2.d[n]=d[0]=0 , 3.d[i]=d[n-i])
另外，某大神从小数找到一个规律。。。
d[0]=0,d[1]=n-1,d[2]=(n-1)+(n-3),d[3]=(n-1)+(n-3)+(n-5),……。
这样就可以递推了。
ps:遇到这种像是数学的题，找不到什么思路时，写出一些小的数据，发现有没有什么规律！
第六届的时候，我记得那个像是博弈的题，虎三就从中找到规律。。。当大于某个数的时候，答案就确定了！！
所以说，记得找规律。
c.递推水一下。。。
#include<iostream> #include<stdio.h> using namespace std; int main(){ int T; int n,x; int i; double d[1005]; d[0]=0; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&x); if(x>n/2){ x=n-x; } for(i=1;i<=x;++i){ d[i]=d[i-1]+(n-(2*i-1));//这个递推公式很神奇。。。 } printf("%.4f ",d[x]); } return 0; }
C.Colorful Cupcakes
http://blog.csdn.net/cds225255/article/details/43805745
http://blog.csdn.net/codebattle/article/details/43820359
D.Devour Magic
d.n个单位，每个单位每秒增加1法力，在某些时间取走一些区间的法力值（取走之后该区间所有单位的法力变为0），求取得的所有法力值。
s.线段树。区间更新，区间求和。不过这个题来说，区间求和之后要把该区间清零。set+add操作，set在先，add在后
c.注意一下要用long long。敲了一天，终于敲对了~
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; #define L(root) ((root)<<1) #define R(root) (((root)<<1)|1) const int MAXN=1e5+10;// int numbers[MAXN];//初始值 struct node{ int left,right;// long long sum; int delta; int v;//区间里的数设为v bool flag;//标记是否设置为v int mid(){ return left+((right-left)>>1); } }tree[MAXN*4];//4倍空间 void pushUp(int root){ tree[root].sum=tree[L(root)].sum+tree[R(root)].sum; } void pushDown(int root){ if(tree[root].flag){ tree[L(root)].delta=tree[R(root)].delta=0; tree[L(root)].v=tree[R(root)].v=tree[root].v; tree[L(root)].flag=tree[R(root)].flag=true; tree[L(root)].sum=tree[root].v*(tree[L(root)].right-tree[L(root)].left+1); tree[R(root)].sum=tree[root].v*(tree[R(root)].right-tree[R(root)].left+1); tree[root].flag=false; } if(tree[root].delta){ tree[L(root)].delta+=tree[root].delta; tree[R(root)].delta+=tree[root].delta; tree[L(root)].sum+=tree[root].delta*(tree[L(root)].right-tree[L(root)].left+1); tree[R(root)].sum+=tree[root].delta*(tree[R(root)].right-tree[R(root)].left+1); tree[root].delta=0; } } void build(int root,int left,int right){ tree[root].left=left; tree[root].right=right; tree[root].delta=0; tree[root].flag=false; if(left==right){ tree[root].sum=numbers[left]; return; } int mid=tree[root].mid(); build(L(root),left,mid); build(R(root),mid+1,right); pushUp(root); } long long query(int root,int left,int right){ if(tree[root].left==left&&tree[root].right==right){ return tree[root].sum; } pushDown(root); int mid=tree[root].mid(); if(right<=mid){ return query(L(root),left,right); } else if(left>mid){ return query(R(root),left,right); } else{ return query(L(root),left,mid)+query(R(root),mid+1,right); } } void update(int root,int left,int right,int add){ if(tree[root].left==left&&tree[root].right==right){ tree[root].delta+=add; tree[root].sum+=add*(right-left+1); return; } pushDown(root); int mid=tree[root].mid(); if(right<=mid){ update(L(root),left,right,add); } else if(left>mid){ update(R(root),left,right,add); } else{ update(L(root),left,mid,add); update(R(root),mid+1,right,add); } pushUp(root); } void setf(int root,int left,int right,int v){ if(tree[root].left==left&&tree[root].right==right){ tree[root].delta=0; tree[root].sum=v*(right-left+1); tree[root].v=v; tree[root].flag=true; return; } pushDown(root); int mid=tree[root].mid(); if(right<=mid){ setf(L(root),left,right,v); } else if(left>mid){ setf(R(root),left,right,v); } else{ setf(L(root),left,mid,v); setf(R(root),mid+1,right,v); } pushUp(root); } int main(){ memset(numbers,0,sizeof(numbers)); int T; int n,m; int t,l,r; int i; int lastTime; long long sum; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); build(1,1,n); lastTime=0; sum=0; for(i=0;i<m;++i){ scanf("%d%d%d",&t,&l,&r); update(1,1,n,t-lastTime); sum+=query(1,l,r); setf(1,l,r,0);//l到r区间设为0 lastTime=t; } printf("%lld ",sum); } return 0; }
E.Factorial
d.求10以内的阶乘
s.打表
#include<iostream> #include<stdio.h> using namespace std; int main(){ int factorial[11]; int i; int T; int n; factorial[0]=1; for(i=1;i<=10;++i){ factorial[i]=factorial[i-1]*i; } scanf("%d",&T); while(T--){ scanf("%d",&n); printf("%d ",factorial[n]); } return 0; }
F.Full Binary Tree
d.在满二叉树中求两个节点的最近距离
s.顺着向上找，直到找到最近公共祖先即可。
#include<iostream> #include<stdio.h> using namespace std; int main(){ int n; int u,v; int ans; scanf("%d",&n); while(n--){ scanf("%d%d",&u,&v); ans=0; while(u!=v){ if(u>v){ u/=2; } else{ v/=2; } ++ans; } printf("%d ",ans); } return 0; }
G.Hearthstone II
d.n场比赛，m个场地，m<=n，1场比赛只能选择1个场地，要求每个场地必须使用过一次，求所有的方案数。
s.乍一看有点像组合数学，应该也能解吧？
这里可以用动态规划来做，
法1：
dp[i][j]表示：前i场比赛用了j个场地的情况数
dp[i][j]=dp[i-1][j]*j+dp[i-1][j-1]*(m-j+1);
法2：
dp[i][j]表示：前i场比赛用了‘前’j个场地的情况数
注意是‘前’j个场地，这样的话，最后需要乘上场地数目的全排列
dp[i][j]=dp[i-1][j]*j+dp[i-1][j-1];
c.法1
/* dp[i][j]=dp[i-1][j]*j+dp[i-1][j-1]*(m-j+1); */ #include<iostream> #include<stdio.h> #include<string.h> using namespace std; const int MOD=1e9+7; int main(){ int n,m; long long dp[105][105];//dp[i][j]表示：前i场比赛用了j个场地的情况数 int i,j; while(~scanf("%d%d",&n,&m)){ memset(dp,0,sizeof(dp)); for(i=1;i<=n;++i){ //j=1; //前i场比赛用了1个场地，初始化为m dp[i][1]=m; } for(i=2;i<=n;++i){ for(j=2;j<=i&&j<=m;++j){ dp[i][j]=((dp[i-1][j]*j)%MOD+(dp[i-1][j-1]*(m-j+1))%MOD)%MOD; } } printf("%lld ",dp[n][m]); } return 0; }
c2.法2
/* dp[i][j]=dp[i-1][j]*j+dp[i-1][j-1]; */ #include<iostream> #include<stdio.h> #include<string.h> using namespace std; const int MOD=1e9+7; int main(){ int n,m; long long dp[105][105];//dp[i][j]表示：前i场比赛用了‘前’j个场地的情况数 int i,j; long long factorial[105]; factorial[1]=1; for(i=2;i<105;++i){ factorial[i]=(factorial[i-1]*i)%MOD; } while(~scanf("%d%d",&n,&m)){ memset(dp,0,sizeof(dp)); for(i=1;i<=n;++i){ //j=1; //前i场比赛用了第1个场地，初始化为1 dp[i][1]=1; } for(i=2;i<=n;++i){ for(j=2;j<=i&&j<=m;++j){ dp[i][j]=((dp[i-1][j]*j)%MOD+dp[i-1][j-1])%MOD; } } printf("%lld ",(dp[n][m]*factorial[m])%MOD); } return 0; }
H.Painting Cottages
I.Tree
J.Weighted Median
d.求和
s.排序，求和
c.sum2>sum中，用>而不是>=，处理0.5的小数。下面的方法更方便，学习了！
#include<iostream> #include<stdio.h> #include<algorithm> using namespace std; const int MAXN=1e7+5; struct node{ long long x; long long w; }p[MAXN]; bool cmp(node a,node b){ return a.x<b.x; } int main(){ int n; long long x,w; int i; long long sum; long long sum2; while(~scanf("%d",&n)){ sum=0; for(i=0;i<n;++i){ scanf("%lld",&x); p[i].x=x; } for(i=0;i<n;++i){ scanf("%lld",&w); p[i].w=w; sum+=w; } sort(p,p+n,cmp); sum/=2; sum2=0; for(i=0;i<n;++i){ sum2+=p[i].w; if(sum2>sum)break;//此处大于号是因为处理0.5的小数 } printf("%lld ",p[i].x); } return 0; }
ps:==...，好像不对，比如这组数据
4
1 2 3 4
1 1 1 1
正确答案为：2
上述代码为：3
GG，仗着数据弱，过了。。。汗。
还是直接用下面的方法吧。
c2.直接*2处理，避免了总和为奇数。
#include<iostream> #include<stdio.h> #include<algorithm> using namespace std; const int MAXN=1e7+5; struct node{ long long x; long long w; }p[MAXN]; bool cmp(node a,node b){ return a.x<b.x; } int main(){ int n; long long x,w; int i; long long sum; long long sum2; while(~scanf("%d",&n)){ sum=0; for(i=0;i<n;++i){ scanf("%lld",&x); p[i].x=x; } for(i=0;i<n;++i){ scanf("%lld",&w); p[i].w=w*2;//*2处理 sum+=w*2;//*2处理 } sort(p,p+n,cmp); sum/=2; sum2=0; for(i=0;i<n;++i){ sum2+=p[i].w; if(sum2>=sum)break;//由于上面*2处理了，此处要用>=了 } printf("%lld ",p[i].x); } return 0; }