本文主要是介绍2014年山东省第五届ACM大学生程序设计竞赛解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A angry_birds_again_and_again
http://www.sdutacm.org/sdutoj/problem.php?action=showproblem&problemid=2877
数学题，求抛物线和直线围成的面积，用积分来做。
设方程 y=ax^2+bx+c ，图中曲线经过原点，所以c=0.
对方程求导 y'=2ax+b , y'代表斜率，那么原点(0,0)这一点，代人y'=b,即该点的斜率，根据题意b=tan( α）
如图：在题目中x=tx这一点时，容易混，记tx为t， 图中曲线x=t这一点，该点的斜率为 2at+b . 注意斜率是负的
三角形竖着的直角边除以横着的直角边（p-t)的值的相反数即为斜率 2at+b
竖着的直角边值为 at^2+bt (将t带入原方程）,横着的直角边为p-t，则有式子
2at+b= - ( at^2+bt)/(p-t)
解出a，这样方程中a,b的值都有了。
那么题目所求的面积即为 曲线覆盖面积 从 0到t积分 积分函数为（ax^2+bx) ，再加上三角形的面积 0.5*(p-t)*(at^2+bt)
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;double px,tx,jiao;
double a,b;int main()
{int t;cin>>t;while(t--){cin>>px>>tx>>jiao;b=tan(jiao);double m=px-tx;a=(-b*tx-b*m)/(2*tx*m+tx*tx);double ans;ans=(1/3.0)*a*tx*tx*tx+0.5*b*tx*tx+0.5*(px-tx)*(a*tx*tx+b*tx);cout<<setiosflags(ios::fixed)<<setprecision(3)<<ans<<endl;}return 0;
}
B Circle
http://www.sdutacm.org/sdutoj/problem.php?action=showproblem&problemid=2878
期望题目，用高斯消元即可。
E[x]=0.5*(E[x-1]+1] + 0.5*(E[x+1]+1),E[x]为x点距离目的终点还需要走的平均步数，终点处期望为0，答案就为E[起点]。
#include <iostream>
#include <string.h>
#include <iomanip>
#include <cmath>
using namespace std;
const int maxn=1002;
const double eps=1e-12;
double a[maxn][maxn];
int equ,var;//equ个方程,var个变量
double x[maxn];//解集
bool free_x[maxn];
int n; int sgn(double x)
{ return (x>eps)-(x<-eps);
} int gauss()
{ equ=n,var=n; int i,j,k; int max_r; // 当前这列绝对值最大的行. int col; // 当前处理的列. double temp; int free_x_num; int free_index; // 转换为阶梯阵. col=0; // 当前处理的列. memset(free_x,true,sizeof(free_x)); for(k=0;k<equ&&col<var;k++,col++) { max_r=k; for(i=k+1;i<equ;i++) { if(sgn(fabs(a[i][col])-fabs(a[max_r][col]))>0) max_r=i; } if(max_r!=k) { // 与第k行交换. for(j=k;j<var+1;j++) swap(a[k][j],a[max_r][j]); } if(sgn(a[k][col])==0) { // 说明该col列第k行以下全是0了，则处理当前行的下一列. k--; continue; } for(i=k+1;i<equ;i++) { // 枚举要删去的行. if (sgn(a[i][col])!=0) { temp=a[i][col]/a[k][col]; for(j=col;j<var+1;j++) { a[i][j]=a[i][j]-a[k][j]*temp; } } } } for(i=k;i<equ;i++) { if (sgn(a[i][col])!=0) return 0; } if(k<var) { for(i=k-1;i>=0;i--) { free_x_num=0; for(j=0;j<var;j++) { if (sgn(a[i][j])!=0&&free_x[j]) free_x_num++,free_index=j; } if(free_x_num>1) continue; temp=a[i][var]; for(j=0;j<var;j++) { if(sgn(a[i][j])!=0&&j!=free_index) temp-=a[i][j]*x[j]; } x[free_index]=temp/a[i][free_index]; free_x[free_index]=0; } return var-k; } for (i=var-1;i>=0;i--) { temp=a[i][var]; for(j=i+1;j<var;j++) { if(sgn(a[i][j])!=0) temp-=a[i][j]*x[j]; } x[i]=temp/a[i][i]; } return 1;
} int t,xx; int main()
{ cin>>t; while(t--) { cin>>n>>xx; memset(a,0,sizeof(a)); for(int i=0;i<n;i++) { if(i==xx) { a[i][i]=1; a[i][n]=0; continue; } a[i][i]=1; a[i][n]=1; a[i][(i-1+n)%n]=-0.5; a[i][(i+1)%n]=-0.5; } gauss(); cout<<setiosflags(ios::fixed)<<setprecision(4)<<x[0]<<endl; } return 0;
}
D Devour Magic
http://www.sdutacm.org/sdutoj/problem.php?action=showproblem&problemid=2880
线段树，操作为：整体区间[1,n]同时加上一个数，查询指定区间的和，将该指定区间清0.
使用两个lazy，一个是增量，一个是是否清0，pushdown的时候，首先看是否清0,因为该区间清0标记了以后，下面子节点的增量标记即使有，也不起作用了，要去掉。
输出不能用I64d,换成cout就过了.....
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <cmath>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cctype>
using namespace std;
typedef long long ll;
const int maxn=100010;struct ST
{int l,r;ll sum;ll lazy;//懒惰标记ll lazy0;//该区间是否清0了
}st[maxn<<2];void pushUp(int i)
{st[i].sum=st[i<<1].sum+st[(i<<1)|1].sum;
}void pushDown(int i,int len)
{if(st[i].lazy0!=0){st[i<<1].lazy0=st[(i<<1)|1].lazy0=st[i].lazy0;st[i<<1].sum=0;st[(i<<1)|1].sum=0;st[i<<1].lazy=0;st[(i<<1)|1].lazy=0;st[i].lazy0=0;}if(st[i].lazy!=0){st[i<<1].lazy+=st[i].lazy;st[(i<<1)|1].lazy+=st[i].lazy;st[i<<1].sum+=ll(len-(len>>1))*st[i].lazy;st[(i<<1)|1].sum+=ll(len>>1)*st[i].lazy;st[i].lazy=0;}
}void build(int i,int l,int r)
{st[i].l=l;st[i].r=r;st[i].lazy=st[i].lazy0=0;st[i].sum=0;if(st[i].l==st[i].r)return;int mid=(st[i].l+st[i].r)>>1;build(i<<1,l,mid);build((i<<1)|1,mid+1,r);
}void update(int i,int l,int r,int val)
{if(val!=0){if(st[i].l==l&&st[i].r==r){st[i].lazy+=val;st[i].sum+=ll(r-l+1)*val;return;}}else{if(st[i].l==l&&st[i].r==r){st[i].sum=0;st[i].lazy0=1;st[i].lazy=0;//保证当前节点的维护的值正确，别忘了这一句return;}pushDown(i,st[i].r-st[i].l+1);int mid=(st[i].l+st[i].r)>>1;if(r<=mid)update(i<<1,l,r,val);else if(l>mid)update((i<<1)|1,l,r,val);else{update(i<<1,l,mid,val);update((i<<1)|1,mid+1,r,val);}pushUp(i);}
}ll query(int i,int l,int r)
{if(st[i].l==l&&st[i].r==r){return st[i].sum;}int mid=(st[i].l+st[i].r)>>1;pushDown(i,st[i].r-st[i].l+1);if(r<=mid)return query(i<<1,l,r);else if(l>mid)return query((i<<1)|1,l,r);elsereturn query(i<<1,l,mid)+query((i<<1)|1,mid+1,r);
}
int t[maxn];
int n,q;
ll ans;int main()
{int cas;t[0]=0;scanf("%d",&cas);while(cas--){ans=0;scanf("%d%d",&n,&q);build(1,1,n);for(int i=1;i<=q;i++){int l,r;scanf("%d%d%d",&t[i],&l,&r);update(1,1,n,t[i]-t[i-1]);ans+=query(1,l,r);update(1,l,r,0);}//printf("%I64d\n",ans);cout<<ans<<endl;}return 0;
}
E Factorial
水题，求10以内的阶乘
#include <iostream>
using namespace std;
int f[11]; void pre()
{ f[0]=1; for(int i=1;i<=10;i++) f[i]=f[i-1]*i;
} int main()
{ pre(); int t,n; cin>>t; while(t--) { cin>>n; cout<<f[n]<<endl; } return 0;
}
F Full Binary Tree
http://www.sdutacm.org/sdutoj/problem.php?action=showproblem&problemid=2882
满二叉树，两个节点的最短距离，先让下面的节点跳到上面的节点所在的那一层，记录步数，然后两个节点一起跳，直到相遇，记录步数，两个步数想加就可以了。
#include <iostream>
using namespace std;
int f[10000];
int len; void pre()
{ f[0]=1; for(int i=1;;i++) { f[i]=f[i-1]*2; if(f[i]>1e9) { len=i-1; break; } }
}
int a,b;
int t; int main()
{ pre(); cin>>t; while(t--) { cin>>a>>b; if(a>b) swap(a,b); int cnt=0; int l; for(int i=0;i<len;i++) { if(a>=f[i]&&a<f[i+1]) { l=i; break; } } while(1) { if(b>=f[l]&&b<f[l+1]) break; b/=2; cnt++; } while(a!=b) { a/=2; b/=2; cnt+=2; } cout<<cnt<<endl; } return 0;
}
G Hearthstone II
http://www.sdutacm.org/sdutoj/problem.php?action=showproblem&problemid=2883
题意为n个竞赛要用到m张桌子，每张桌子至少被用一次，桌子不同，问一共有多少种安排方法。
也就是把n个元素分到m个非空且不可区分的集合中去。第二类Stiring数 s(n,m)意思是把n个元素分到m个非空且不可区分的集合中去。本题集合（桌子）是可区分的，那么答案为m! *s(n,m).
#include <iostream>
#include <string.h>
using namespace std;
const int maxn=102;
const int mod=1e9+7;
typedef long long ll;
ll s[maxn][maxn];
int n, m; void init()
{ memset(s,0,sizeof(s)); s[1][1]=1; for(int i=2;i<=100;i++) for(int j=1;j<=i;j++) { s[i][j]=s[i-1][j-1]+j*s[i-1][j]; if(s[i][j]>=mod) s[i][j]%=mod; }
} ll solve(int n,int m)
{ ll ans=s[n][m]; for(int i=2;i<=m;i++) { ans*=i; if(ans>=mod) ans%=mod; } return ans;
} int main()
{ init(); while(cin>>n>>m) { cout<<solve(n,m)<<endl; } return 0;
}
J Weighted Median
http://www.sdutacm.org/sdutoj/problem.php?action=showproblem&problemid=2886
用的sort水过.
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int maxn=1e7+2;
int n;struct Node
{int x,w;
}node[maxn];bool cmp(Node a,Node b)
{if(a.x<b.x)return true;return false;
}int main()
{while(scanf("%d",&n)!=EOF){long long sum=0;for(int i=1;i<=n;i++)scanf("%d",&node[i].x);for(int i=1;i<=n;i++){scanf("%d",&node[i].w);sum+=node[i].w;}long double S=sum*0.5;sort(node+1,node+1+n,cmp);long long xiao=0,da=0;int ans;for(int i=1;i<=n-1;i++){xiao+=node[i].w;da=sum-xiao-node[i+1].w;if(xiao<S&&da<=S){ans=node[i+1].x;break;}}cout<<ans<<endl;}return 0;
}
这篇关于2014年山东省第五届ACM大学生程序设计竞赛解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
