阶乘末尾0的个数
分析
考虑0是5和2贡献出来的，但是因子2出现的频率高得多，所以统计因子5的个数就好了。给了多种写法。
参考代码
//第一种
#include <iostream>
#include <cstdio>
using namespace std;
int solve(int n){
int cnt = 0;
while(n){
cnt += n / 5;
n = n / 5;
}
return cnt;
}
int main(){
int n;
cin >> n;
cout << solve(n) << endl;
}
//第二种
#include <iostream>
#include <cstdio>
using namespace std;
int solve(int n){
int cnt = 0;
for(int i = 5; i <= n; i += 5){
int res = i;
while (res % 5 == 0){
cnt++;
res /= 5;
}
}
return cnt;
}
int main(){
int n;
cin >> n;
cout << solve(n) << endl;
}
#数据范围比较小,直接用python也是可以的
n = int(raw_input())
ans = 1;
for i in range(1,n+1):
ans *= i
count = 0
for i in range(len(str(ans))-1,-1,-1):
if(str(ans)[i] == '0'):
count += 1
else:
break
print count
地下迷宫
分析
根据题设，可以简单证明最短路径一定体力消耗最小的路径。因为横向移动m-1是必须的，而纵向的路径越短，需要的体力就越少。
直接bfs然后记录一下路径即可,dfs应该也是可以的吧。
参考代码
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int _map[15][15];
int vis[15][15];
int m,n,P;
struct node{
int x,y,v;
}ans[15][15];
bool bfs(){
queue<node> q;
node tmp;
tmp.x = 0,tmp.y = 0,tmp.v = P;
q.push(tmp);
while(!q.empty()){
node tmp = q.front();
q.pop();
if(tmp.x == 0 && tmp.y == m - 1 && tmp.v >= 0) return true;
if(tmp.x + 1 <= n - 1 && _map[tmp.x + 1][tmp.y] && !vis[tmp.x + 1][tmp.y]){
node temp;
temp.x = tmp.x + 1;
temp.y = tmp.y;
temp.v = tmp.v;
ans[temp.x][temp.y].x = tmp.x;
ans[temp.x][temp.y].y = tmp.y;
vis[temp.x][temp.y] = 1;
q.push(temp);
}
if(tmp.y + 1 <= m - 1 && _map[tmp.x][tmp.y + 1] && !vis[tmp.x][tmp.y + 1] && tmp.v > 0){
node temp;
temp.x = tmp.x;
temp.y = tmp.y + 1;
temp.v = tmp.v - 1;
ans[temp.x][temp.y].x = tmp.x;
ans[temp.x][temp.y].y = tmp.y;
vis[temp.x][temp.y] = 1;
q.push(temp);
}
if(tmp.x - 1 >= 0 && _map[tmp.x - 1][tmp.y] && !vis[tmp.x - 1][tmp.y] && tmp.v >= 3){
node temp;
temp.x = tmp.x - 1;
temp.y = tmp.y;
temp.v = tmp.v - 3;
ans[temp.x][temp.y].x = tmp.x;
ans[temp.x][temp.y].y = tmp.y;
vis[temp.x][temp.y] = 1;
q.push(temp);
}
if(tmp.y - 1 >= 0 && _map[tmp.x][tmp.y - 1] && !vis[tmp.x][tmp.y - 1] && tmp.v > 0){
node temp;
temp.x = tmp.x;
temp.y = tmp.y - 1;
temp.v = tmp.v - 1;
ans[temp.x][temp.y].x = tmp.x;
ans[temp.x][temp.y].y = tmp.y;
vis[temp.x][temp.y] = 1;
q.push(temp);
}
}
return false;
}
void pri(int sx,int sy) {
if( sx == 0 && sy == 0) {
printf("[0,0]");
return ;
}
pri(ans[sx][sy].x,ans[sx][sy].y);
printf(",[%d,%d]", sx,sy);
}
int main(){
cin >> n >> m >> P;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> _map[i][j];
}
}
if(bfs()){
pri(0, m - 1);
printf("\n");
}
else cout << "Can not escape!" << endl;
return 0;
}
#滴滴##Java工程师##C++工程师##安卓工程师##前端工程师##算法工程师#
查看4道真题和解析