2015浙江财经大学ACM有奖周赛（一） 题解报告
命题：丽丽&&黑鸡 这是命题者原话。
题目涉及的知识面比较广泛，有深度优先搜索、广度优先搜索、数学题、几何题、贪心算法、枚举、二进制等等...
有些题目还需要大家对程序的效率做出优化..大一的小宝宝可能有一些吃不消..当成是一种体验就好了。
题解目录：
ZUFE OJ 2307: 最长连续不下降子串
ZUFE OJ 2308: Lucky Number
ZUFE OJ 2309: 小明爱吃面
ZUFE OJ 2310: 小明爱消除
ZUFE OJ 2311: 找数字
ZUFE OJ 2312: 简单数学题
ZUFE OJ 2313: 字符串还原
ZUFE OJ 2314: 矩形周长
ZUFE OJ 2315: 小明的智力
ZUFE OJ 2316: 水题
ZUFE OJ 2317: 画个圈圈
ZUFE OJ 2318: 跳格子
ZUFE OJ 2320: 高中几何没学好
ZUFE OJ 1606: 清洁公司
ZUFE OJ 2323: 黑鸡跑1000
/*
ZUFE OJ 2307: 最长连续不下降子串
时间复杂度：o(n)
题解：输入a[1]到a[n]
补上a[0]为负无穷大，a[n+1]为无穷大
初始化k为1，ans为0
然后一个一个a[i]扫下去 (1<=i<=n+1)
如果a[i]<a[i-1]，那么更新ans=max(ans,k);
否则k=k+1;
最后ans就是答案
*/ #include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std; const int maxn=+;
const int INF=0x7FFFFFFF;
int a[maxn],ans,k,n; void init()
{
for(int i=; i<=n; i++) scanf("%d",&a[i]);
a[]=INF;a[n+]=-INF;
} void slove()
{
while(~scanf("%d",&n))
{
init();
ans=;
k=;
for(int i=; i<=n+; i++)
{
if(a[i]<a[i-])
{
ans=max(ans,k);
k=;
}
else k++;
}
printf("%d\n",ans);
}
} int main()
{
slove();
return ;
}
/*
ZUFE OJ 2308: Lucky Number
题解：设输入的n有x位，设Q等于10的x次方
n*n最后的x位就是 (n*n)%Q
那么只要判断 (n*n)%Q 和 n 是否相等就可以了
要注意的一点就是 0<n<1e9
n*n会超出int范围，所以用long long存储
*/ #include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std; long long n;
long long _n;
long long n2;
int x;//n有x位 void slove()
{
while(~scanf("%lld",&n))
{
_n=n; x=;
while(_n) x=x+, _n=_n/; //得到n有几位
if((n*n)%((long long)pow(10.0,x))==n) printf("Yes\n");
else printf("No\n");
}
} int main()
{
slove();
return ;
}
/*
ZUFE OJ 2309: 小明爱吃面
时间复杂度：o(n)
题解：一个简单的贪心题
对于第i天，简单的说就是：是今天买，还是之前买？
当然是要选择从第1天到当前天，价格最小的那一天买下今天所需的粮食。 今天吃的价格其实就是之前那些天中最小的价格
处理出每天的价格之后，求和即可。 PS：语文不好...描述的可能不是很清楚。
*/ #include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std; const int maxn=+;
int a[maxn],p[maxn];
int n,ans; void init()
{
for(int i=;i<=n;i++)
scanf("%d%d",&a[i],&p[i]);
ans=;
} void slove()
{
while(~scanf("%d",&n))
{
init(); for(int i=;i<=n;i++)
p[i]=min(p[i-],p[i]);//找出每一天的价格 for(int i=;i<=n;i++)
ans=ans+a[i]*p[i]; printf("%d\n",ans);
}
} int main()
{
slove();
return ;
}
/*
ZUFE OJ 2310: 小明爱消除
时间复杂度：o(n)
题解：此题属于脑洞题，需要细细咀嚼
（描述起来比较费劲，略）
*/ #include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std; const int maxn=+;
int tot[maxn*];
int ans,n; void init()
{
memset(tot,,sizeof tot);
ans=;
} void slove()
{
while(~scanf("%d",&n))
{
init();
for(int i=; i<=n; i++)
{
int x;
scanf("%d",&x);
tot[x]++;
}
int k=,m;
while(k<*maxn)
{
m=tot[k]/;
tot[k]=tot[k]%;
tot[k+]=tot[k+]+m;
k++;
}
for(int i=; i<*maxn; i++)
ans=ans+tot[i];
printf("%d\n",ans);
}
} int main()
{
slove();
return ;
}
/*
ZUFE OJ 2311: 找数字
时间复杂度：o(n*n)
题解：开一个数组记录每个数字有几个
tot[x]=y 代表x有y个！
然后两层循环枚举B和C
枚举到的时候 tot[B]--,tot[C]--;
然后验证tot[B+C]是否大于0，即A是否存在
大于零则表示存在。
否则不存在。
*/ #include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std; const int maxn=+;
int tot[maxn],a[maxn];
int n; void slove()
{
while(~scanf("%d",&n))
{
memset(tot,,sizeof tot);
for(int i=; i<=n; i++)
{
scanf("%d",&a[i]);
tot[a[i]]++;
}
int ans=;
for(int i=; i<=n; i++)
{
for(int j=i+; j<=n; j++)
{
tot[a[i]]--;
tot[a[j]]--;
if(tot[a[i]+a[j]]>)
{
ans=;
break;
}
tot[a[i]]++;
tot[a[j]]++;
}
if(ans==) break;
}
if(ans==) printf("NO\n");
else printf("YES\n");
}
} int main()
{
slove();
return ;
}
/*
ZUFE OJ 2312: 简单数学题
题解：数学题，a的b次方和c的d次方都很大，直接判断是做不出来的。
如果我们能找到一个函数F(x)是单调的，
而F(X)的值又比较好算，那么可以通过比较F(X)的大小来判断自变量的大小。 令F(X)=log(X)，a的b次方和c的d次方当做自变量。
那么接下来只要判断log(a的b次方)和log(c的d次方)的大小
就可以判断a的b次方和c的d次方的大小了。 而log(a的b次方)=b*log(a)，log(c的d次方)=d*log(c)，很容易计算。 判断相等的时候注意一下精度问题。
*/ #include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std; double a,b,c,d; int main()
{
while(~scanf("%lf%lf%lf%lf",&a,&b,&c,&d))
{
double ans1=b*log(a);
double ans2=d*log(c); if(fabs(ans1-ans2)<0.000001) printf("=\n");
else if(ans1>ans2) printf(">\n");
else printf("<\n");
}
return ;
}
/*
ZUFE OJ 2313: 字符串还原
时间复杂度：o(n)
题解：水题，搞之...
*/ #include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std; const int maxn=+;
char s[maxn];
int T; void slove()
{
scanf("%d",&T);
while(T--)
{
scanf("%s",s);
int len=strlen(s);
for(int i=;i<len;i++)
if(i%==) printf("%c",s[i]);
printf("\n"); for(int i=len-;i>=;i--)
if(i%==) printf("%c",s[i]);
printf("\n");
}
} int main()
{
slove();
return ;
}
/*
ZUFE OJ 2314: 矩形周长
时间复杂度：o(sqrt(n))
题解：枚举一下边长就可以了
*/ #include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std; const int INF=0x7FFFFFFF;
int T,n; void slove()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int MaxL=sqrt(1.0*n);
int ans=INF;
for(int i=;i<=MaxL;i++)
{
if(n%i!=) continue;
else
{
if(*(i+n/i)<ans)
ans=*(i+n/i);
}
}
printf("%d\n",ans);
}
} int main()
{
slove();
return ;
}
/*
ZUFE OJ 2315: 小明的智力
时间复杂度：o(n)
题解：简单的贪心题
先排序，然后吃2，最后吃1
找到第一个比p大的位置
从这个位置开始吃2，吃完2 最后吃1
*/ #include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std; const int maxn=+;
int a[maxn];
bool flag[maxn];
int T,n,p; void slove()
{
scanf("%d",&T);
while(T--)
{
memset(flag,,sizeof flag);
scanf("%d%d",&n,&p);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
sort(a+,a+n+);
int now=n+;
for(int i=;i<=n;i++)
{
if(a[i]>p)
{
now=i;
break;
}
} for(int i=now;i<=n;i++)
if(a[i]>p)
flag[i]=,p=p+; for(int i=;i<=n;i++)
if(flag[i]==) p=p+;
printf("%d\n",p);
}
} int main()
{
slove();
return ;
}
/*
ZUFE OJ 2316: 水题
时间复杂度：o(n)
题解：水题，搞之...
*/ #include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std; const int INF=0x7FFFFFFF;
const int maxn=+;
int T,ans,n;
int a[maxn]; void slove()
{
scanf("%d",&T);
while(T--)
{
ans=-INF;
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=n;i++)
if(a[i]-a[i-]>ans)
ans=a[i]-a[i-];
printf("%d\n",ans);
}
} int main()
{
slove();
return ;
}
/*
ZUFE OJ 2317:画个圈圈
*/
#include<stdio.h>
#include<math.h>
#include<map>
#include<algorithm>
#include<string.h>
using namespace std; const int maxn=+;
int ans,N,M;
char Map[maxn][maxn];
bool flag[maxn][maxn];
char sign;
int dir[][]= {{-,},{,},{,-},{,}}; void init()
{
memset(flag,,sizeof flag);
ans=;
} void dfs(int x,int y,int Dir)
{
if(flag[x][y]==&&Dir!=-)
{
ans=;
return;
}
flag[x][y]=;
for(int i=; i<; i++)
{
int NewX=x+dir[i][];
int NewY=y+dir[i][]; if(Dir==&&i==) continue;
if(Dir==&&i==) continue;
if(Dir==&&i==) continue;
if(Dir==&&i==) continue;
if(Map[NewX][NewY]!=sign) continue;
if(NewX<||NewX>=N) continue;
if(NewY<||NewY>=M) continue; dfs(NewX,NewY,i);
if(ans) return;
}
} void slove()
{
while(~scanf("%d%d",&N,&M))
{
for(int i=; i<N; i++)
scanf("%s",Map[i]);
init();
for(int i=; i<N; i++)
{
for(int j=; j<M; j++)
{
sign=Map[i][j];
memset(flag,,sizeof flag);
dfs(i,j,-);
if(ans) break;
}
if(ans) break;
}
if(ans==) printf("Yes\n");
else printf("No\n");
}
} int main()
{
slove();
return ;
}
/*
ZUFE OJ 2318: 跳格子
时间复杂度：不会算
题解：BFS
*/ #include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std; const int INF=0x7FFFFFFF;
int dir[][]={{-,},{,},{,-},{,}};
const int maxn=+;
int N,M,ans;
int Sx,Sy,Ex,Ey;
int Map[maxn][maxn];
int flag[maxn][maxn];
struct Point
{
int x,y;
int tot;
};
queue<Point>Q; void BFS()
{
while(!Q.empty()) Q.pop();
for(int i=;i<maxn;i++)
for(int j=;j<maxn;j++)
flag[i][j]=INF;
Point p;
p.x=Sx; p.y=Sy; p.tot=;
Q.push(p);
ans=-;
flag[Sx][Sy]=;
while(!Q.empty())
{
Point h=Q.front(); Q.pop();
if(h.x==Ex&&h.y==Ey)
{
ans=h.tot;
break;
}
for(int i=;i<;i++)
{
int NewX=h.x+dir[i][];
int NewY=h.y+dir[i][]; if(NewX>=&&NewX<=N)
{
if(NewY>=&&NewY<=M)
{
if(Map[NewX][NewY]!=)
{
if(flag[NewX][NewY]>h.tot+)
{
flag[NewX][NewY]=h.tot+;
Point x;
x.x=NewX;
x.y=NewY;
x.tot=h.tot+;
Q.push(x);
}
}
}
}
}
}
printf("%d\n",ans);
} void slove()
{
while(~scanf("%d%d",&N,&M))
{
for(int i=;i<=N;i++)
for(int j=;j<=M;j++)
scanf("%d",&Map[i][j]); for(int i=;i<=N;i++)
for(int j=;j<=M;j++)
{
if(Map[i][j]==) Sx=i,Sy=j;
if(Map[i][j]==) Ex=i,Ey=j;
} BFS();
}
} int main()
{
slove();
return ;
}
/*
ZUFE OJ 2320: 高中几何没学好
时间复杂度：o(1)
题解：连接AX
设三角形AFX面积为e，三角形AXE面积为f
得到三个方程
e+f=d
f/c=(a+d)/(b+c)
e/a=(c+d)/(a+b)
三个未知量都可以解出来
*/
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std; double a,b,c,k;
double e,f; int main()
{
while(~scanf("%lf%lf%lf",&a,&b,&c))
{
k=(a+b)/(b+c);
f=(a*c)/(b-c*k);
e=k*f;
printf("%.4lf\n",e+f);
}
return ;
}
/*
ZUFE OJ 1606: 清洁公司
题解：DFS求连通块
*/
#include<stdio.h> char gird[][];
int m,n;
int dir[][]= {{-,-},{-,},{-,},{,}
,{,},{,},{,-},{,-}}; void dfs(int x,int y)
{
int i,xx,yy;
gird[x][y]='#';
for(i=; i<; i++)
{
xx=x+dir[i][];
yy=y+dir[i][];
if(xx<||yy<||xx>=m||yy>=n) continue;
if(gird[xx][yy]=='@') dfs(xx,yy);
}
}
int main()
{
int i,j;
int count;
while( scanf("%d%d",&m,&n)!=EOF)
{
for(i=; i<m; i++) scanf("%s",gird[i]);
count=;
for(i=; i<m; i++)
{
for(j=; j<n; j++)
{
if(gird[i][j]=='@')
{
dfs(i,j);
count++;
}
}
}
printf("%d\n",count);
}
return ;
}
/*
ZUFE OJ 2323: 黑鸡跑1000
题解：水题..搞之..
*/
#include <stdio.h> double a,b; int main()
{
while(~scanf("%lf%lf",&a,&b))
printf("%.2lf\n",500.0/a+500.0/b);
return ;
}