编写一个把整数N分解为质因数乘积的程序。
输入一个整数 N
输出 分解质因数 。拆成几个质数相乘的形式，质数必须从小到大相乘
756
756=2*2*3*3*3*7
范围在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原创
小浣熊松松和朋友到野外露营，没想到遇上了π年一次的大洪水，好在松松是一只爱观察的小浣熊，他发现露营地的地形和洪水有如下性质：
①露营地可以被看做是一个N*M的矩形方阵，其中左上角坐标为(1,1)，右下角坐标为(n,m)，每个格子(i,j)都有一个高度h(i,j)。
②洪水送(r,c)开始，如果一个格子被洪水淹没，那这个格子四周比它低（或相同）的格子也会被淹没。
现在松松想请你帮忙算算，有多少个格子不会被淹没，便于他和朋友逃脱。
【原有误数据已删除】
第一行包含两个整数n，m，表示矩形方阵右下角坐标。
以下n行，每行m个数，第i行第j个数表示格子(i,j)的高度。
最后一行包含两个整数r，c，表示最初被洪水淹没的格子。
输出仅一行，为永远不会被淹没的格子的数量。
3 3
1 2 3
2 3 4
3 4 5
2 2
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原创
小浣熊松松到他的朋友家别墅去玩，发现他朋友的家非常大，而且布局很奇怪。具体来说，朋友家的别墅可以被看做一个N*M的矩形，有墙壁的地方被标记为’#’，其他地方被标记为’.’。两个格子(a,b)和(c,d)被当做在同一个房间内，当且仅当|a-c|+|b-d|=1。现在松松想知道，有多少个房间。
第一行包含两个整数，N和M。
接下来N行描述别墅的情况，只包含’*’和’.’。
输出仅一行，为房间数。
3 3
.#.
#.#
.#.
5
对于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 ;
}
把自然数Ｎ分解为若干个自然数之和，输出方案数。
N,（1≤n≤50）
方案数
5
7
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 ;
}
一个朋友网络，如果a认识b，那么如果a第一次收到某个消息，那么会把这个消息传给b，以及所有a认识的人。
如果a认识b，b不一定认识a。
所有人从1到n编号，给出所有“认识”关系，问如果i发布一条新消息，那么会不会经过若干次传话后，这个消息传回给了i，1<=i<=n。
第一行是n和m，表示人数和认识关系数。
接下来的m行，每行两个数a和b，表示a认识b。1<=a, b<=n。认识关系可能会重复给出，但一行的两个数不会相同。
一共n行，每行一个字符T或F。第i行如果是T，表示i发出一条新消息会传回给i；如果是F，表示i发出一条新消息不会传回给i。
4 6
1 2
2 3
4 1
3 1
1 3
2 3
T
T
T
F
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 ;
}
有一个矩形房间，覆盖正方形瓷砖。每块瓷砖涂成了红色或黑色。一名男子站在黑色的瓷砖上，由此出发，可以移到四个相邻瓷砖之一，但他不能移动到红砖上，只能移动到黑砖上。编写一个程序，计算他通过重复上述移动所能经过的黑砖数。
输入包含多个数据集。一个数据集开头行包含两个正整数W和H，W和H分别表示矩形房间的列数和行数，且都不超过20.
每个数据集有H行，其中每行包含W个字符。每个字符的含义如下所示：
'.'——黑砖
'#'——红砖
'@'——男子（每个数据集仅出现一次）
两个0表示输入结束。
对每个数据集，程序应该输出一行，包含男子从初始瓷砖出发可到达的瓷砖数。
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0
45
59
6
13
无
#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 ;
}
给出一个二叉树，输出它的最大宽度和高度。
第一行一个整数n。
下面n行每行有两个数，对于第i行的两个数，代表编号为i的节点所连接的两个左右儿子的编号。如果没有某个儿子为空，则为0。
输出共一行，输出二叉树的最大宽度和高度，用一个空格隔开。
5
2 3
4 5
0 0
0 0
0 0
2 3
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 ;
}
求一棵二叉树的前序遍历，中序遍历和后序遍历
第一行一个整数n，表示这棵树的节点个数。
接下来n行每行2个整数L和R。第i行的两个整数Li和Ri代表编号为i的节点的左儿子编号和右儿子编号。
输出一共三行，分别为前序遍历，中序遍历和后序遍历。编号之间用空格隔开。
5
2 3
4 5
0 0
0 0
0 0
1 2 4 5 3
4 2 5 1 3
4 5 2 3 1
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 ;
}
汉诺塔问题（又称为河内塔问题），是一个大家熟知的问题。在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，求出最少步数的移动序列
一个整数n
第一行一个整数k，代表是最少的移动步数。
接下来k行，每行一句话，N from X to Y，表示把N号盘从X柱移动到Y柱。X,Y属于{A,B,C}
3
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
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 2 3 4 5 6 7 8 9=N 空格（1前面没有空格）内可以填入+,-,也可以不填。 编程找出输入某个整数 N 后使等式成立的所有方案的总数。保证有解。
输入一个数N。
输出一个数。所有的方案数。
108
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 ;
}
输入一棵二叉树的先序和中序遍历序列，输出其后序遍历序列。
共两行，第一行一个字符串，表示树的先序遍历，第二行一个字符串，表示树的中序遍历。
仅一行，表示树的后序遍历序列。
abdehicfg
dbheiafcg
dhiebfgca
输入长度不大于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 ;
}
已知某开放授权人员名叫Serb,由于经常修改各种数据，因此开发人员们都喊他SB.现在他和许多人一起过飞机安检，排成了一长队列，请问SB.是否在队列中。
第一行：SB.所代表的某个符号
第二行：一排等待飞机安检的人所代表的符号(小于等于100，大于等于1)
YES或NO
1
2356@Qfrr
NO
一排等待飞机安检的人所代表的符号数量小于等于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 ;
}
小X从美国回来后，成为了USACO中国区的奶牛销售代理商，专门出售质优价廉的“FJ”牌奶牛，因此生意很好。还记得那个巨大的牛棚吗？由于年久失修，牛棚被拆。她建了一个新的、现代化牛棚。这个牛棚采用数字化管理，因此每头奶牛都有一个编号i，第i头奶牛对应第i间牛棚。由于奶牛数量十分庞大，又打乱了顺序，所以必须由你进行升序排序。
我们保证第N（2<=N<=1000000）头奶牛一定有且仅有一间牛棚住,且奶牛编号一定连续。
注意：奶牛编号是可能大于N、但一定是INT范围内的整数
本周内将加强数据，坚决反对快排！
第一行：一个正整数N
第二行：N头奶牛编号
奶牛编号升序排列
10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
还是那句话，请搜索：奶牛代理商以获得更多信息；
我们不推荐快排，原因见样例。
如果你只读入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 ;
}