codevs 搜索题汇总(青铜+白银级)

 时间限制: 1 s
 空间限制: 128000 KB
 题目等级 : 青铜 Bronze
 
题目描述 Description

编写一个把整数N分解为质因数乘积的程序。

输入描述 Input Description

输入一个整数 N

输出描述 Output Description

输出 分解质因数 。拆成几个质数相乘的形式,质数必须从小到大相乘

样例输入 Sample Input

756

样例输出 Sample Output

756=2*2*3*3*3*7

数据范围及提示 Data Size & Hint

范围在longint内。不是高精度。

#include<cstdio>
#include<iostream>
#include<cstdlib>
using namespace std; int n;
int ss[];
bool ff[];
int a[];
int head; bool sss(int k)
{
bool yes=true;
for(int i=;i<k;i++)
if(k%i==)
yes=false;
if(yes==false)
{
ff[k]=;
return ;
}
else
{
head++;
a[head]=k;
for(int i=;i*k<=;i++)
ff[i*k]=;
return ;
}
} void print(int pp)
{
printf("%d=",n);
for(int i=;i<pp;i++)
{
printf("%d*",ss[i]);
}
printf("%d\n",ss[pp]);
} void dfs(int k,int m,int p)
{
for(int i=m;i<=head;i++)
if(k%a[i]==)
{
if(k/a[i]==)
{
ss[p]=a[i];
print(p);
exit();
}
else
{
ss[p]=a[i];
dfs(k/a[i],i,p+);
}
}
} int main()
{
for(int i=;i<=;i++)
if(ff[i]==)
sss(i);
scanf("%d",&n);
dfs(n,,);
return ;
}

3411 洪水

CodeVS原创

 时间限制: 1 s
 空间限制: 64000 KB
 题目等级 : 青铜 Bronze
题目描述 Description

小浣熊松松和朋友到野外露营,没想到遇上了&pi;年一次的大洪水,好在松松是一只爱观察的小浣熊,他发现露营地的地形和洪水有如下性质:

①露营地可以被看做是一个N*M的矩形方阵,其中左上角坐标为(1,1),右下角坐标为(n,m),每个格子(i,j)都有一个高度h(i,j)。

②洪水送(r,c)开始,如果一个格子被洪水淹没,那这个格子四周比它低(或相同)的格子也会被淹没。

现在松松想请你帮忙算算,有多少个格子不会被淹没,便于他和朋友逃脱。

【原有误数据已删除】

输入描述 Input Description

第一行包含两个整数n,m,表示矩形方阵右下角坐标。

以下n行,每行m个数,第i行第j个数表示格子(i,j)的高度。

最后一行包含两个整数r,c,表示最初被洪水淹没的格子。

输出描述 Output Description

输出仅一行,为永远不会被淹没的格子的数量。

样例输入 Sample Input

3 3

1 2 3

2 3 4

3 4 5

2 2

样例输出 Sample Output

5

思路:从开始点开始搜索四周所有比他低的方向,搜到的符合条件的就标记后再继续深搜,最后统计一下无论如何都不会搜索到的格子的数量就好了

#include<cstdio>
#include<iostream>
using namespace std;
int h[][];
bool g[][];
int p,n,m;
int a[]={,,,,-};
int b[]={,,-,,};
void input()
{
scanf("%d%d",&n,&m);
p=n*m;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&h[i][j]);
}
void water(int x,int y)
{
g[x][y]=true;
p--;
for(int i=;i<=;i++)
if((x+a[i]>=)&&(x+a[i]<=n)&&(y+b[i]>=)&&(y+b[i]<=m)&&(h[x+a[i]][y+b[i]]<=h[x][y])&&(g[x+a[i]][y+b[i]]==false))
water(x+a[i],y+b[i]);
}
int main()
{
int x,y;
input();
scanf("%d%d",&x,&y);
water(x,y);
printf("%d\n",p);
return ;
}

3410 别墅房间

CodeVS原创

 时间限制: 1 s
 空间限制: 64000 KB
 题目等级 : 青铜 Bronze
题目描述 Description

小浣熊松松到他的朋友家别墅去玩,发现他朋友的家非常大,而且布局很奇怪。具体来说,朋友家的别墅可以被看做一个N*M的矩形,有墙壁的地方被标记为’#’,其他地方被标记为’.’。两个格子(a,b)和(c,d)被当做在同一个房间内,当且仅当|a-c|+|b-d|=1。现在松松想知道,有多少个房间。

输入描述 Input Description

第一行包含两个整数,N和M。

接下来N行描述别墅的情况,只包含’*’和’.’。

输出描述 Output Description

输出仅一行,为房间数。

样例输入 Sample Input

3 3

.#.

#.#

.#.

样例输出 Sample Output

5

数据范围及提示 Data Size & Hint

对于90%的数据,1<=N,M<=1000;

对于100%的数据,1<=N,M<=2000。

#include<cstdio>
#include<cstring>
#include<iostream> using namespace std; int dx[]={,,,,-};
int dy[]={,,-,,}; int n,m,head,tail,ans;
int a[][];
int tx[],ty[]; void bfs(int x,int y)
{
while(head<=tail)
{
int xx=tx[++head];
int yy=ty[head];
for(int i=;i<=;i++)
{
xx+=dx[i];
yy+=dy[i];
if(a[xx][yy]==)
{
tail++;
tx[tail]=xx;
ty[tail]=yy;
a[xx][yy]=;
xx-=dx[i];
yy-=dy[i];
}
else
{
xx-=dx[i];
yy-=dy[i];
}
}
}
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
char l;
cin>>l;
if(l=='#') a[i][j]=;
else a[i][j]=;
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(a[i][j]==)
{
ans++;
memset(tx,,sizeof(tx));
memset(ty,,sizeof(ty));
head=;
tail=;
tx[]=i;
ty[]=j;
a[i][j]=;
bfs(i,j);
}
printf("%d",ans);
return ;
}
 时间限制: 1 s
 空间限制: 32000 KB
 题目等级 : 白银 Silver
 
 
题目描述 Description

把自然数N分解为若干个自然数之和,输出方案数。

输入描述 Input Description

N,(1≤n≤50)

输出描述 Output Description

方案数

样例输入 Sample Input

5

样例输出 Sample Output

7

数据范围及提示 Data Size & Hint

5 可分为

1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
1 4
2 3
5

思路:从小到大分解和,深搜就好,思路应该没问题

#include<cstdio>

int n,ans;
int a[]; void print(int l)
{
ans++;
} void sousuo(int k,int m)
{
for(int i=a[k-];i<=n;i++)
if(i<=m)
{
a[k]=i;
m-=i;
if(m==)
{
print(k);
}
if(m<)
return;
if(m>)
{
sousuo(k+,m);
m+=i;
}
}
} int main()
{
scanf("%d",&n);
a[]=;
sousuo(,n);
printf("%d",ans);
return ;
}
 时间限制: 1 s
 空间限制: 128000 KB
 题目等级 : 白银 Silver
 
题目描述 Description

一个朋友网络,如果a认识b,那么如果a第一次收到某个消息,那么会把这个消息传给b,以及所有a认识的人。

如果a认识b,b不一定认识a。

所有人从1到n编号,给出所有“认识”关系,问如果i发布一条新消息,那么会不会经过若干次传话后,这个消息传回给了i,1<=i<=n。

输入描述 Input Description

第一行是n和m,表示人数和认识关系数。

接下来的m行,每行两个数a和b,表示a认识b。1<=a, b<=n。认识关系可能会重复给出,但一行的两个数不会相同。

输出描述 Output Description

一共n行,每行一个字符T或F。第i行如果是T,表示i发出一条新消息会传回给i;如果是F,表示i发出一条新消息不会传回给i。

样例输入 Sample Input

4 6

1 2

2 3

4 1

3 1

1 3

2 3

样例输出 Sample Output

T

T

T

F

数据范围及提示 Data Size & Hint

n<=1000

1<=a, b<=n

#include<iostream>
#include<cstdio>
using namespace std;
bool t[][];
int main()
{
int n,m,a,b;
scanf("%d%d",&n,&m);
for(int i=;i<m;i++)
scanf("%d%d",&a,&b),t[a][b] = ;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
if(t[j][i]==)
for(int k=;k<=n;k++)
if(t[i][k]==)
t[j][k]=;
}
for(int i=;i<=n;i++)
{
if(t[i][i]==)
printf("T\n");
else
printf("F\n");
}
return ;
}
 时间限制: 1 s
 空间限制: 64000 KB
 题目等级 : 白银 Silver
 
题目描述 Description

有一个矩形房间,覆盖正方形瓷砖。每块瓷砖涂成了红色或黑色。一名男子站在黑色的瓷砖上,由此出发,可以移到四个相邻瓷砖之一,但他不能移动到红砖上,只能移动到黑砖上。编写一个程序,计算他通过重复上述移动所能经过的黑砖数。

输入描述 Input Description

输入包含多个数据集。一个数据集开头行包含两个正整数W和H,W和H分别表示矩形房间的列数和行数,且都不超过20.
每个数据集有H行,其中每行包含W个字符。每个字符的含义如下所示:
'.'——黑砖
'#'——红砖
'@'——男子(每个数据集仅出现一次)
两个0表示输入结束。

输出描述 Output Description

对每个数据集,程序应该输出一行,包含男子从初始瓷砖出发可到达的瓷砖数。

样例输入 Sample Input

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0

样例输出 Sample Output

45
59
6
13

数据范围及提示 Data Size & Hint

#include <iostream>
#include <memory.h>
using namespace std;
int w,h,map[][],flag[][],sw,sh,tot; //map记录砖色,flag统计是否走过
int opw[]={,-,,},oph[]={,,-,};
char tmp;
void dfs(int cw,int ch)
{
int tmpw,tmph;
tot++;
for(int i=;i<;i++) {
tmpw=cw+opw[i];
tmph=ch+oph[i];
//不能出界,不能走红砖,不能统计已经走的地方
if(tmph<=||tmph>h||tmpw<=||tmpw>w||flag[tmpw][tmph]==||map[tmpw][tmph]==-) continue;
flag[tmpw][tmph]=;
dfs(tmpw,tmph);
}
} int main()
{ while(true)
{
memset(map,,sizeof(map));
memset(flag,,sizeof(flag));
tot=; //循环前清变量!!
cin>>h>>w;
if(w==&&h==) break;
for(int i=;i<=w;i++)
for(int j=;j<=h;j++)
{cin>>tmp;
if(tmp=='@') {sw=i;sh=j;map[i][j]=;flag[i][j]=;}//起点也算一个
else if(tmp=='#') map[i][j]=-;
}
dfs(sw,sh);
cout<<tot<<endl;
}
return ;
}
 时间限制: 1 s
 空间限制: 128000 KB
 题目等级 : 白银 Silver
题目描述 Description

给出一个二叉树,输出它的最大宽度和高度。

输入描述 Input Description

第一行一个整数n。

下面n行每行有两个数,对于第i行的两个数,代表编号为i的节点所连接的两个左右儿子的编号。如果没有某个儿子为空,则为0。

输出描述 Output Description

输出共一行,输出二叉树的最大宽度和高度,用一个空格隔开。

样例输入 Sample Input

5

2 3

4 5

0 0

0 0

0 0

样例输出 Sample Output

2 3

数据范围及提示 Data Size & Hint

n<16

默认第一个是根节点

以输入的次序为编号

2-N+1行指的是这个节点的左孩子和右孩子

注意:第二题有极端数据!

          1

          0 0

这题你们别想投机取巧了,给我老老实实搜索!

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
struct tree{
int lson,rson;
}d[];//定义树
int deep[],wide[];//定义宽度,深度
void build(int now,int fa)
{
deep[now]=deep[fa]+;//现在的深度等于父亲的深度+1
wide[deep[now]]++;//现在深度上的宽度+1
if(d[now].lson)//如果现在有左儿子
build(d[now].lson,now);
if(d[now].rson)
build(d[now].rson,now);
return;
}
int main()
{
int n,l,r;
cin>>n;
for(int i=;i<=n;i++)
{
scanf("%d%d",&d[i].lson,&d[i].rson);//输入编号为i的左儿子和右儿子
}
build(,);//从头开始
int w=,p=;
for(int i=;i<=n;i++)
w=max(w,wide[i]);
for(int i=;i<=n;i++)
p=max(p,deep[i]);
printf("%d %d",w,p);
return ;
}
 时间限制: 1 s
 空间限制: 32000 KB
 题目等级 : 白银 Silver
题目描述 Description

求一棵二叉树的前序遍历,中序遍历和后序遍历

输入描述 Input Description

第一行一个整数n,表示这棵树的节点个数。

接下来n行每行2个整数L和R。第i行的两个整数Li和Ri代表编号为i的节点的左儿子编号和右儿子编号。

输出描述 Output Description

输出一共三行,分别为前序遍历,中序遍历和后序遍历。编号之间用空格隔开。

样例输入 Sample Input

5

2 3

4 5

0 0

0 0

0 0

样例输出 Sample Output

1 2 4 5 3

4 2 5 1 3

4 5 2 3 1

数据范围及提示 Data Size & Hint

n <= 16

#include<cstdio>
int n,l,r;
int a[];
void qianxu(int p)
{
if(a[p]==) return;
printf("%d ",a[p]);
qianxu(*p);
qianxu(*p+);
}
void zhongxu(int p)
{
if(a[p]==) return;
zhongxu(*p);
printf("%d ",a[p]);
zhongxu(*p+);
}
void houxu(int p)
{
if(a[p]==) return;
houxu(*p);
houxu(*p+);
printf("%d ",a[p]);
}
int main()
{
scanf("%d",&n);
a[]=;
for(int i=;i<=n;i++)
{
scanf("%d%d",&l,&r);
for(int j=;j<=;j++)
if(a[j]==i)
{
a[*j]=l;
a[*j+]=r;
}
}
qianxu();
printf("\n");
zhongxu();
printf("\n");
houxu();
return ;
}
 时间限制: 1 s
 空间限制: 32000 KB
 题目等级 : 白银 Silver
题目描述 Description

汉诺塔问题(又称为河内塔问题),是一个大家熟知的问题。在A,B,C三根柱子上,有n个不同大小的圆盘(假设半径分别为1-n吧),一开始他们都叠在我A上(如图所示),你的目标是在最少的合法移动步数内将所有盘子从A塔移动到C塔。

游戏中的每一步规则如下:

1. 每一步只允许移动一个盘子(从一根柱子最上方到另一个柱子的最上方)

2. 移动的过程中,你必须保证大的盘子不能在小的盘子上方(小的可以放在大的上面,最大盘子下面不能有任何其他大小的盘子)

如对于n=3的情况,一个合法的移动序列式:

1 from A to C

2 from A to B

1 from C to B

3 from A to C

1 from B to A

2 from B to C

1 from A to C

给出一个数n,求出最少步数的移动序列

输入描述 Input Description

一个整数n

输出描述 Output Description

第一行一个整数k,代表是最少的移动步数。

接下来k行,每行一句话,N from X to Y,表示把N号盘从X柱移动到Y柱。X,Y属于{A,B,C}

样例输入 Sample Input

3

样例输出 Sample Output

7

1 from A to C

2 from A to B

1 from C to B

3 from A to C

1 from B to A

2 from B to C

1 from A to C

数据范围及提示 Data Size & Hint

n<=10

#include<cstdio>
#include<iostream>
using namespace std;
int n,p=;
void hanoi(int n,char a,char b,char c)
{
if(n==)printf("%d from %c to %c\n",n,a,c);
else
{
hanoi(n-,a,c,b);
printf("%d from %c to %c\n",n,a,c);
hanoi(n-,b,a,c);
}
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
p*=;
printf("%d\n",p-);
hanoi(n,'A','B','C');
return ;
}
 时间限制: 1 s
 空间限制: 64000 KB
 题目等级 : 白银 Silver
题目描述 Description

有一个未完成的等式:1 2 3 4 5 6 7 8 9=N 空格(1前面没有空格)内可以填入+,-,也可以不填。 编程找出输入某个整数 N 后使等式成立的所有方案的总数。保证有解。

输入描述 Input Description

输入一个数N。

输出描述 Output Description

输出一个数。所有的方案数。

样例输入 Sample Input

108

样例输出 Sample Output

15

#include<cstdio>
#include<iostream> using namespace std; int ans,n; void dfs(int s,int t)
{
int m=;
if(t==n&&s>)
{
ans++;
return;
}
else
{
for(int i=s;i<=;i++)
{
m=m*+i;
dfs(i+,t+m);
if(s!=)
dfs(i+,t-m);
}
}
}
int main()
{
cin>>n;
dfs(,);
cout<<ans<<endl;
return ;
}
 时间限制: 1 s
 空间限制: 64000 KB
 题目等级 : 白银 Silver
题目描述 Description

输入一棵二叉树的先序和中序遍历序列,输出其后序遍历序列。

输入描述 Input Description

共两行,第一行一个字符串,表示树的先序遍历,第二行一个字符串,表示树的中序遍历。

输出描述 Output Description

仅一行,表示树的后序遍历序列。

样例输入 Sample Input

abdehicfg

dbheiafcg

样例输出 Sample Output

dhiebfgca

数据范围及提示 Data Size & Hint

输入长度不大于255。

#include<iostream>
#include<cstdio>
#include<cstring> using namespace std; string a,b;
int len; void dfs(int l,int r,int ll,int rr)
{
int y=b.find(a[l]);
if(y>ll)dfs(l+,l+y-ll,ll,y-);
if(y<rr)dfs(l+y-ll+,r,y+,rr);
cout<<a[l];
} int main()
{
cin>>a>>b;
len=a.size()-;
dfs(,len,,len);
return ;
}
 时间限制: 1 s
 空间限制: 16000 KB
 题目等级 : 白银 Silver
题目描述 Description

已知某开放授权人员名叫Serb,由于经常修改各种数据,因此开发人员们都喊他SB.现在他和许多人一起过飞机安检,排成了一长队列,请问SB.是否在队列中。

输入描述 Input Description

第一行:SB.所代表的某个符号

第二行:一排等待飞机安检的人所代表的符号(小于等于100,大于等于1)

输出描述 Output Description

YES或NO

样例输入 Sample Input

1

2356@Qfrr

样例输出 Sample Output

NO

数据范围及提示 Data Size & Hint

一排等待飞机安检的人所代表的符号数量小于等于100,大于等于1且为正整数。我们保证只有一个Serb。

C/C++:流输入有木有!

#include <iostream>
#include <cstdio>
#include <string> using namespace std; int main()
{
string s,s1;
cin>>s1>>s;
if(s.find(s1)>)
cout<<"NO";
else
cout<<"YES";
return ;
}
 时间限制: 1 s
 空间限制: 32000 KB
 题目等级 : 白银 Silver
题目描述 Description

小X从美国回来后,成为了USACO中国区的奶牛销售代理商,专门出售质优价廉的“FJ”牌奶牛,因此生意很好。还记得那个巨大的牛棚吗?由于年久失修,牛棚被拆。她建了一个新的、现代化牛棚。这个牛棚采用数字化管理,因此每头奶牛都有一个编号i,第i头奶牛对应第i间牛棚。由于奶牛数量十分庞大,又打乱了顺序,所以必须由你进行升序排序。

我们保证第N(2<=N<=1000000)头奶牛一定有且仅有一间牛棚住,且奶牛编号一定连续

    注意:奶牛编号是可能大于N、但一定是INT范围内的整数

 

本周内将加强数据,坚决反对快排!

输入描述 Input Description

第一行:一个正整数N

第二行:N头奶牛编号

输出描述 Output Description

奶牛编号升序排列

样例输入 Sample Input

10

1 2 3 4 5 6 7 8 9 10

样例输出 Sample Output

1 2 3 4 5 6 7 8 9 10

数据范围及提示 Data Size & Hint

还是那句话,请搜索:奶牛代理商以获得更多信息;

我们不推荐快排,原因见样例。

如果你只读入N而不排序,试图偷懒的话,有你好看!

注意:奶牛编号是可能大于N、但一定是INT范围内的整数

{

Build:G-308-2-F;

副标题:回家;

标签:这不需要!;
}

#include<cstdio>
#include<algorithm> using namespace std; int n;
int a[+]; int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
sort(a+,a+n+);
for(int i=;i<n;i++)
printf("%d ",a[i]);
printf("%d",a[n]);
return ;
}
上一篇:SVN clean up问题


下一篇:寻找子串位置