A - 3:
Problem:
乘積尾零
如下的10行數(shù)據(jù)，每行有10個(gè)整數(shù)恢口，請(qǐng)你求出它們的乘積的末尾有多少個(gè)零呆躲？
5650 4542 3554 473 946 4114 3871 9073 90 4329
2758 7949 6113 5659 5245 7432 3051 4434 6704 3594
9937 1173 6866 3397 4759 7557 3070 2287 1453 9899
1486 5722 3135 1170 4014 5510 5120 729 2880 9019
2049 698 4582 4346 4427 646 9742 7340 1230 7683
5693 7015 6887 7381 4172 4341 2909 2027 7355 5649
6701 6645 1671 5978 2704 9926 295 3125 3878 6785
2066 4247 4800 1578 6652 4616 1113 6205 3264 2915
3966 5291 2904 1285 2193 1428 2265 8730 9436 7074
689 5510 8243 6114 337 4096 8199 7313 3685 211
注意：需要提交的是一個(gè)整數(shù)，表示末尾零的個(gè)數(shù)忍抽。不要填寫任何多余內(nèi)容八孝。
Solution:
任何一個(gè)數(shù)都可以分解為若干個(gè)素?cái)?shù)的乘積
每個(gè)數(shù)分別對(duì)2, 5取余,并計(jì)算全部數(shù)可被2和5取余的次數(shù) 即可算出0的個(gè)數(shù)
Code:
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int countTwo = 0;
int countFive = 0;
void check(int num);
int main(void) {
int data;
int temp = 1;
for (int i = 0; i < 100; i++) {
cin >> data;
check(data);
}
cout << min(countFive, countTwo);
return 0;
}
void check(int num) {
for (int i = 2; i <= 5; i++) {
for (; num % i == 0;) {
if (i == 2)
countTwo++;
else if (i == 5)
countFive++;
num /= i;
}
}
}
Ans
31
A - 4
Problem:
第幾個(gè)幸運(yùn)數(shù)
到x星球旅行的游客都被發(fā)給一個(gè)整數(shù)，作為游客編號(hào)鸠项。
x星的國(guó)王有個(gè)怪癖干跛，他只喜歡數(shù)字3,5和7。
國(guó)王規(guī)定祟绊，游客的編號(hào)如果只含有因子：3,5,7,就可以獲得一份獎(jiǎng)品楼入。
我們來(lái)看前10個(gè)幸運(yùn)數(shù)字是：
3 5 7 9 15 21 25 27 35 45
因而第11個(gè)幸運(yùn)數(shù)字是：49
小明領(lǐng)到了一個(gè)幸運(yùn)數(shù)字 59084709587505，他去領(lǐng)獎(jiǎng)的時(shí)候牧抽，人家要求他準(zhǔn)確地說(shuō)出這是第幾個(gè)幸運(yùn)數(shù)字嘉熊，否則領(lǐng)不到獎(jiǎng)品。
請(qǐng)你幫小明計(jì)算一下扬舒，59084709587505是第幾個(gè)幸運(yùn)數(shù)字阐肤。
需要提交的是一個(gè)整數(shù)，請(qǐng)不要填寫任何多余內(nèi)容讲坎。
Solution:
用篩法的思想
數(shù)組預(yù)置數(shù)字 1
對(duì)數(shù)組所有的數(shù) 不斷 * 3 把<=MAX 的數(shù)納入數(shù)組arr
對(duì)數(shù)組所有的數(shù) 不斷 * 5 把<=MAX 的數(shù)納入數(shù)組arr
對(duì)數(shù)組所有的數(shù) 不斷 * 7 把<=MAX 的數(shù)納入數(shù)組arr
ans = arr.size() - 1
Code:
long long MAXN = 59084709587505;
int main(void) {
vector<long long> arr(1,1);
int size;
bool flag = false;
int num[3] = { 3,5,7 };
int step = 0;
long long temp;
for (int i = 0; i < 3; i++) {
size = arr.size();
for (int j = 0; j < size; j++) {
for ( temp = arr[j] * num[i];temp<=MAXN;) {
arr.push_back(temp);
temp *= num[i];
}
}
}
cout << arr.size() - 1;
return 0;
}
Ans
1905
A - 5
Problem:
打印圖形
如下的程序會(huì)在控制臺(tái)繪制分形圖（就是整體與局部自相似的圖形）孕惜。
當(dāng)n=1,2,3的時(shí)候，輸出如下：
請(qǐng)仔細(xì)分析程序衣赶，并填寫劃線部分缺少的代碼诊赊。
n=1時(shí)：
o
ooo
o
n=2時(shí)：
o
ooo
o
o o o
ooooooooo
o o o
o
ooo
o
n=3時(shí)：
o
ooo
o
o o o
ooooooooo
o o o
o
ooo
o
o o o
ooo ooo ooo
o o o
o o o o o o o o o
ooooooooooooooooooooooooooo
o o o o o o o o o
o o o
ooo ooo ooo
o o o
o
ooo
o
o o o
ooooooooo
o o o
o
ooo
o
源程序：
#include <stdio.h>
#include <stdlib.h>
void show(char* buf, int w){
int i,j;
for(i=0; i<w; i++){
for(j=0; j<w; j++){
printf("%c", buf[i*w+j]==0? ' ' : 'o');
}
printf("\n");
}
}
void draw(char* buf, int w, int x, int y, int size){
if(size==1){
buf[y*w+x] = 1;
return;
}
int n = _________________________ ; //填空
draw(buf, w, x, y, n);
draw(buf, w, x-n, y ,n);
draw(buf, w, x+n, y ,n);
draw(buf, w, x, y-n ,n);
draw(buf, w, x, y+n ,n);
}
int main()
{
int N = 3;
int t = 1;
int i;
for(i=0; i<N; i++) t *= 3;
char* buf = (char*)malloc(t*t);
for(i=0; i<t*t; i++) buf[i] = 0;
draw(buf, t, t/2, t/2, t);
show(buf, t);
free(buf);
return 0;
}
注意：只提交劃線部分缺少的代碼，不要抄寫任何已經(jīng)存在的代碼或符號(hào)府瞄。
Sulotion:
size = 為整個(gè)圖形的高
由題分析可知 N++
則size*=3
Ans:
int n = size / 3;
A - 8
Problem:
你有一張某海域NxN像素的照片碧磅，"."表示海洋碘箍、"#"表示陸地，如下所示：
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四個(gè)方向上連在一起的一片陸地組成一座島嶼鲸郊。例如上圖就有2座島嶼丰榴。
由于全球變暖導(dǎo)致了海面上升，科學(xué)家預(yù)測(cè)未來(lái)幾十年秆撮，島嶼邊緣一個(gè)像素的范圍會(huì)被海水淹沒(méi)四濒。具體來(lái)說(shuō)如果一塊陸地像素與海洋相鄰(上下左右四個(gè)相鄰像素中有海洋)，它就會(huì)被淹沒(méi)职辨。
例如上圖中的海域未來(lái)會(huì)變成如下樣子：
.......
.......
.......
.......
....#..
.......
.......
請(qǐng)你計(jì)算：依照科學(xué)家的預(yù)測(cè)盗蟆，照片中有多少島嶼會(huì)被完全淹沒(méi)。
輸入
第一行包含一個(gè)整數(shù)N舒裤。 (1 <= N <= 1000)
以下N行N列代表一張海域照片绢彤。
照片保證第1行音念、第1列、第N行、第N列的像素都是海洋古程。
輸出
一個(gè)整數(shù)表示答案供常。
樣例輸入
7
.......
.##....
.##....
....##.
..####.
...###.
.......
樣例輸出
1
Solution:
DFS 數(shù)連通塊個(gè)數(shù) 并對(duì)可能會(huì)成為海洋的陸地進(jìn)行標(biāo)記并計(jì)數(shù) 再對(duì)原有陸地進(jìn)行計(jì)數(shù) 如果原有陸地個(gè)數(shù)和可能變成海洋的陸地個(gè)數(shù)相等 則該島嶼為沉沒(méi)島嶼
注意 有可能有些島嶼會(huì)因?yàn)樽兣兂蓛蓧K島嶼 所以通過(guò)變化前島嶼個(gè)數(shù)和變化后島嶼個(gè)數(shù)之差是不可行的
如果
Code:
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
int N;
int count1 = 0;
int count2 = 0;
int dirX[4] = { -1, 0, 1, 0 };
int dirY[4] = { 0, -1, 0, 1 };
void dfs(vector<string > & MAP, vector<vector<bool> > &from, int x, int y);
int main(void) {
int count = 0;
cin >> N;
string s;
vector<bool> arr(N, 0);
vector<vector<bool> > from(N, arr);
vector<string > MAP;
for (int i = 0; i < N; i++) {
cin >> s;
MAP.push_back(s);
}
for (int i = 1; i < N; i++) {
for (int j = 1; j < N; j++) {
if (MAP[i][j] == '#'&&from[i][j] == 0) {
count1 = 0;
count2 = 0;
dfs(MAP, from, i, j);
if (count1 == count2)
count++;
}
}
}
/*cout << endl;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << MAP[i][j];
}
cout << endl;
}
for (int i = 1; i < N; i++) {
for (int j = 1; j < N; j++) {
if (MAP[i][j] == '#'&&to[i][j] == 0) {
dfs(MAP, to, i, j);
count2++;
}
}
}*/
cout << count;
return 0;
}
void dfs(vector<string > & MAP, vector<vector<bool> > &from, int x, int y) {
from[x][y] = 1;
count1++;
int tempX;
int tempY;
for (int i = 0; i < 4; i++) {
tempX = x + dirX[i];
tempY = y + dirY[i];
if(MAP[tempX][tempY]=='#' && from[tempX][tempY] == 0)
dfs(MAP, from, tempX, tempY);
if (MAP[tempX][tempY] == '.') {
if (MAP[x][y] != '/')
count2++;
MAP[x][y] = '/';
}
}
}
