ACM训练日记—4月22日（“今日头条杯”首届湖北省大学程序设计竞赛）

本文主要是介绍ACM训练日记—4月22日（“今日头条杯”首届湖北省大学程序设计竞赛），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

感觉这次练习赛状态真是谜，估计还是因为太菜了，也高估了B题的难度，C题没过是我2了，还是有两道能过的题没做出来。QAQ。

A—Srdce and Triangle

题意：给出角ADB,BDC,ADC，问用边长AD,BD,CD组成一个新三角形的内角分别是多少。

相当于一道中学几何题，将三角形ADC顺时针旋转60度，连接新D点与旧D点，右下角就能发现一个完全由AD,BD,CD边长组成的三角形，而左下角是个边长为AD的等边三角。剩下的就很明显了。

代码：

double ans[4];
int main()
{
double j1,j2,j3;
while(scanf("%lf%lf%lf",&j1,&j2,&j3)!=EOF)
{
ans[1]=j1-60;
ans[2]=360-j1-j2-60;
ans[3]=180-ans[1]-ans[2];
sort(ans+1,ans+4);
if(ans[1]<=0||ans[2]<=0||ans[3]<=0) cout<<-1<<" "<<-1<<" "<<-1<<endl;
else printf("%.10lf %.10lf %.10lf\n",ans[1],ans[2],ans[3]);
}
}

B—Salty Fish Go!

题意：就是给你n种速度，一段长为l的路，k个加油站（可以在加油站改变速度），m个宝藏。现在，你所在位置是随机出现，加油站分别在哪也是随机出现，你走的方向也是随机，宝藏位置随机，而且你不知道宝藏在哪（意思就是你随机跑），问这样找完所有宝藏的花费时间数学期望是多少。

这道题当我看到这么随机的题目时，确实是吓懵了，瞬间把学的概率全还给老师了。其实这题很水，就是因为全随机才简单了。

因为全部都是随机的，所以就是求一种平均情况。。。还是看代码吧。

代码：

int main()
{
int V,L,n,m;
while(~scanf("%d%d%d%d",&V,&L,&n,&m))
{
int sum=0;
for(int i=0;i<V;i++)
{
int x;
scanf("%d",&x);
sum+=x;
}
double v=sum*1.0/V;
printf("%.12f\n",m*1.0*L/(m+1)/v);//因为加油站随机，所以可以认为m各加油站把l长的路等分为m+1等份，每一份都用平均速度跑，然后m个宝藏
}
}

C— Who killed Cock Robin

题意：给你一棵树，问这棵树上有多少个子集（子集中的元素必须是连成一片的）。

其实直接分析每一个结点假如 i 结点有k个子分支（每一个分支有ai个集合），其中第i个结点是一个集合，然后第i各节点到每一个分支子集就有ai个，那么第i个分支到第j个分支有ai*aj个集合，那么i和j和k三个连起来，，，，k个分支通过结点就是a1*a2*...ak个。

做这道题是推到这步了，可就是没综合出来下面下面这个很明显的公式，我可能是个假的数学系学生。

(a1+1)(a2+1)...(ak+1)。这个公式经常见，组合公式，乘出来你就能发现了。1+a1+a2+...ak+a1a2+a1a3+...aiaj+....a1a2a3..ak。经常见的组合公式。QAQ，不甘心。

代码：

const int maxn = 2e5+10;
const int mod = 1e7+7;
ll ans[maxn];
vector<ll>p[maxn];
ll n;
ll DFS(ll x,ll fa){
for(int i=0;i<p[x].size();i++){
ll y=p[x][i];
if(y==fa){
continue;
}
ans[x]=(ans[x]*(DFS(y,x)+1))%mod;
}
return ans[x];
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n-1;i++){
int x,y;
scanf("%d%d",&x,&y);
p[x].push_back(y);
p[y].push_back(x);
}
for(int i=1;i<=n;i++){
ans[i]=1;
}
DFS(1,-1);
ll sum=0;
for(int i=1;i<=n;i++){
sum=(sum+ans[i])%mod;
}
printf("%lld\n",sum);
}

G—GSS and Simple Math Problem

大数乘法Java写

E—Flower Road

题意：就是给你一个大方阵，依次对里面可以对若干个小方阵进行四块旋转，最后问从（1,1）到(n,n)最短路中最大权值。

水题，模拟，简单dp。

代码：

int a[1505][1505];
int b[1505][1505];
int dp[1505][1505];
void solve(int x,int y,int l)
{
int t=l/2;
for(int i=x;i<=x+t-1;i++)
{
for(int j=y;j<=y+t-1;j++)
{
b[i][j+t]=a[i][j];
}
}
for(int i=x;i<=x+t-1;i++)
{
for(int j=y+t;j<=y+l-1;j++)
{
b[i+t][j]=a[i][j];
}
}
for(int i=x+t;i<=x+l-1;i++)
{
for(int j=y+t;j<=y+l-1;j++)
{
b[i][j-t]=a[i][j];
}
}
for(int i=x+t;i<=x+l-1;i++)
{
for(int j=y;j<=y+t-1;j++)
{
b[i-t][j]=a[i][j];
}
}
for(int i=x;i<=x+l-1;i++)
{
for(int j=y;j<=y+l-1;j++)
{
a[i][j]=b[i][j];
}
}
}
int main()
{
int n,m;
int x,y,l;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&l);
solve(x,y,2*l);
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];
}
}
cout<<dp[n][n]<<endl;
}