相关总结：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-*tx*px); area1=(a/)*(tx*tx*tx)+(b/)*(tx*tx);//抛物线面积
area2=((a*(tx*tx)+b*tx)*(px-tx))/;//三角形面积
area=area1+area2; printf("%.3f\n",area); } return ;
}
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[];
d[]=; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&x); if(x>n/){
x=n-x;
} for(i=;i<=x;++i){
d[i]=d[i-]+(n-(*i-));//这个递推公式很神奇。。。
} printf("%.4f\n",d[x]); } return ;
}
C.Colorful Cupcakes
http://blog.****.net/cds225255/article/details/43805745
http://blog.****.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+;//
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)>>);
}
}tree[MAXN*];//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=;
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+);
tree[R(root)].sum=tree[root].v*(tree[R(root)].right-tree[R(root)].left+);
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+);
tree[R(root)].sum+=tree[root].delta*(tree[R(root)].right-tree[R(root)].left+);
tree[root].delta=;
}
} void build(int root,int left,int right){
tree[root].left=left;
tree[root].right=right;
tree[root].delta=;
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+,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+,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+);
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+,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=;
tree[root].sum=v*(right-left+);
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+,right,v);
}
pushUp(root);
} int main(){ memset(numbers,,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(,,n); lastTime=;
sum=;
for(i=;i<m;++i){
scanf("%d%d%d",&t,&l,&r); update(,,n,t-lastTime);
sum+=query(,l,r);
setf(,l,r,);//l到r区间设为0 lastTime=t;
} printf("%lld\n",sum); } return ;
}
E.Factorial
d.求10以内的阶乘
s.打表
#include<iostream>
#include<stdio.h>
using namespace std; int main(){ int factorial[];
int i;
int T;
int n; factorial[]=;
for(i=;i<=;++i){
factorial[i]=factorial[i-]*i;
} scanf("%d",&T); while(T--){
scanf("%d",&n);
printf("%d\n",factorial[n]);
} return ;
}
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=;
while(u!=v){
if(u>v){
u/=;
}
else{
v/=;
}
++ans;
} printf("%d\n",ans); } return ;
}
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+; int main(){ int n,m;
long long dp[][];//dp[i][j]表示：前i场比赛用了j个场地的情况数
int i,j; while(~scanf("%d%d",&n,&m)){ memset(dp,,sizeof(dp));
for(i=;i<=n;++i){
//j=1;
//前i场比赛用了1个场地，初始化为m
dp[i][]=m;
}
for(i=;i<=n;++i){
for(j=;j<=i&&j<=m;++j){
dp[i][j]=((dp[i-][j]*j)%MOD+(dp[i-][j-]*(m-j+))%MOD)%MOD;
}
} printf("%lld\n",dp[n][m]);
} return ;
}
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+; int main(){ int n,m;
long long dp[][];//dp[i][j]表示：前i场比赛用了‘前’j个场地的情况数
int i,j;
long long factorial[]; factorial[]=;
for(i=;i<;++i){
factorial[i]=(factorial[i-]*i)%MOD;
} while(~scanf("%d%d",&n,&m)){ memset(dp,,sizeof(dp));
for(i=;i<=n;++i){
//j=1;
//前i场比赛用了第1个场地，初始化为1
dp[i][]=;
}
for(i=;i<=n;++i){
for(j=;j<=i&&j<=m;++j){
dp[i][j]=((dp[i-][j]*j)%MOD+dp[i-][j-])%MOD;
}
} printf("%lld\n",(dp[n][m]*factorial[m])%MOD);
} return ;
}
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+; 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=; for(i=;i<n;++i){
scanf("%lld",&x);
p[i].x=x;
}
for(i=;i<n;++i){
scanf("%lld",&w);
p[i].w=w;
sum+=w;
} sort(p,p+n,cmp); sum/=;
sum2=;
for(i=;i<n;++i){
sum2+=p[i].w;
if(sum2>sum)break;//此处大于号是因为处理0.5的小数
} printf("%lld\n",p[i].x); } return ;
}
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+; 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=; for(i=;i<n;++i){
scanf("%lld",&x);
p[i].x=x;
}
for(i=;i<n;++i){
scanf("%lld",&w);
p[i].w=w*;//*2处理
sum+=w*;//*2处理
} sort(p,p+n,cmp); sum/=;
sum2=;
for(i=;i<n;++i){
sum2+=p[i].w;
if(sum2>=sum)break;//由于上面*2处理了，此处要用>=了
} printf("%lld\n",p[i].x); } return ;
}