编写一个把整数N分解为质因数乘积的程序。
输入一个整数 N
输出 分解质因数 。拆成几个质数相乘的形式，质数必须从小到大相乘
756
756=2*2*3*3*3*7
范围在longint内。不是高精度。
#include<cstdio> #include<iostream> #include<cstdlib> using namespace std; int n; int ss[520]; bool ff[65000]; int a[520]; int head; bool sss(int k) { bool yes=true; for(int i=2;i<k;i++) if(k%i==0) yes=false; if(yes==false) { ff[k]=1; return 0; } else { head++; a[head]=k; for(int i=1;i*k<=64000;i++) ff[i*k]=1; return 1; } } void print(int pp) { printf("%d=",n); for(int i=1;i<pp;i++) { printf("%d*",ss[i]); } printf("%d ",ss[pp]); } void dfs(int k,int m,int p) { for(int i=m;i<=head;i++) if(k%a[i]==0) { if(k/a[i]==1) { ss[p]=a[i]; print(p); exit(0); } else { ss[p]=a[i]; dfs(k/a[i],i,p+1); } } } int main() { for(int i=2;i<=300;i++) if(ff[i]==0) sss(i); scanf("%d",&n); dfs(n,1,1); return 0; }
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[1001][1001]; bool g[1001][1001]; int p,n,m; int a[5]={0,0,0,1,-1}; int b[5]={0,1,-1,0,0}; void input() { scanf("%d%d",&n,&m); p=n*m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&h[i][j]); } void water(int x,int y) { g[x][y]=true; p--; for(int i=1;i<=4;i++) if((x+a[i]>=1)&&(x+a[i]<=n)&&(y+b[i]>=1)&&(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 ",p); return 0; }
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[5]={0,0,0,1,-1}; int dy[5]={0,1,-1,0,0}; int n,m,head,tail,ans; int a[2150][2150]; int tx[2250],ty[2250]; void bfs(int x,int y) { while(head<=tail) { int xx=tx[++head]; int yy=ty[head]; for(int i=1;i<=4;i++) { xx+=dx[i]; yy+=dy[i]; if(a[xx][yy]==1) { tail++; tx[tail]=xx; ty[tail]=yy; a[xx][yy]=2; xx-=dx[i]; yy-=dy[i]; } else { xx-=dx[i]; yy-=dy[i]; } } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { char l; cin>>l; if(l=='#') a[i][j]=2; else a[i][j]=1; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]==1) { ans++; memset(tx,0,sizeof(tx)); memset(ty,0,sizeof(ty)); head=0; tail=1; tx[1]=i; ty[1]=j; a[i][j]=2; bfs(i,j); } printf("%d",ans); return 0; }
把自然数Ｎ分解为若干个自然数之和，输出方案数。
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[10000]; void print(int l) { ans++; } void sousuo(int k,int m) { for(int i=a[k-1];i<=n;i++) if(i<=m) { a[k]=i; m-=i; if(m==0) { print(k); } if(m<0) return; if(m>0) { sousuo(k+1,m); m+=i; } } } int main() { scanf("%d",&n); a[0]=1; sousuo(1,n); printf("%d",ans); return 0; }
一个朋友网络，如果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[1010][1010]; int main() { int n,m,a,b; scanf("%d%d",&n,&m); for(int i=0;i<m;i++) scanf("%d%d",&a,&b),t[a][b] = 1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(t[j][i]==1) for(int k=1;k<=n;k++) if(t[i][k]==1) t[j][k]=1; } for(int i=1;i<=n;i++) { if(t[i][i]==1) printf("T "); else printf("F "); } return 0; }
有一个矩形房间，覆盖正方形瓷砖。每块瓷砖涂成了红色或黑色。一名男子站在黑色的瓷砖上，由此出发，可以移到四个相邻瓷砖之一，但他不能移动到红砖上，只能移动到黑砖上。编写一个程序，计算他通过重复上述移动所能经过的黑砖数。
输入包含多个数据集。一个数据集开头行包含两个正整数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[21][21],flag[21][21],sw,sh,tot; //map记录砖色，flag统计是否走过 int opw[]={1,-1,0,0},oph[]={0,0,-1,1}; char tmp; void dfs(int cw,int ch) { int tmpw,tmph; tot++; for(int i=0;i<4;i++) { tmpw=cw+opw[i]; tmph=ch+oph[i]; //不能出界，不能走红砖，不能统计已经走的地方 if(tmph<=0||tmph>h||tmpw<=0||tmpw>w||flag[tmpw][tmph]==1||map[tmpw][tmph]==-1) continue; flag[tmpw][tmph]=1; dfs(tmpw,tmph); } } int main() { while(true) { memset(map,0,sizeof(map)); memset(flag,0,sizeof(flag)); tot=0; //循环前清变量！！ cin>>h>>w; if(w==0&&h==0) break; for(int i=1;i<=w;i++) for(int j=1;j<=h;j++) {cin>>tmp; if(tmp=='@') {sw=i;sh=j;map[i][j]=1;flag[i][j]=1;}//起点也算一个 else if(tmp=='#') map[i][j]=-1; } dfs(sw,sh); cout<<tot<<endl; } return 0; }
给出一个二叉树，输出它的最大宽度和高度。
第一行一个整数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[20];//定义树 int deep[20],wide[20];//定义宽度，深度 void build(int now,int fa) { deep[now]=deep[fa]+1;//现在的深度等于父亲的深度+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=1;i<=n;i++) { scanf("%d%d",&d[i].lson,&d[i].rson);//输入编号为i的左儿子和右儿子 } build(1,0);//从头开始 int w=0,p=0; for(int i=1;i<=n;i++) w=max(w,wide[i]); for(int i=1;i<=n;i++) p=max(p,deep[i]); printf("%d %d",w,p); return 0; }
求一棵二叉树的前序遍历，中序遍历和后序遍历
第一行一个整数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[1000]; void qianxu(int p) { if(a[p]==0) return; printf("%d ",a[p]); qianxu(2*p); qianxu(2*p+1); } void zhongxu(int p) { if(a[p]==0) return; zhongxu(2*p); printf("%d ",a[p]); zhongxu(2*p+1); } void houxu(int p) { if(a[p]==0) return; houxu(2*p); houxu(2*p+1); printf("%d ",a[p]); } int main() { scanf("%d",&n); a[1]=1; for(int i=1;i<=n;i++) { scanf("%d%d",&l,&r); for(int j=1;j<=1000;j++) if(a[j]==i) { a[2*j]=l; a[2*j+1]=r; } } qianxu(1); printf(" "); zhongxu(1); printf(" "); houxu(1); return 0; }
汉诺塔问题（又称为河内塔问题），是一个大家熟知的问题。在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=1; void hanoi(int n,char a,char b,char c) { if(n==1)printf("%d from %c to %c ",n,a,c); else { hanoi(n-1,a,c,b); printf("%d from %c to %c ",n,a,c); hanoi(n-1,b,a,c); } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) p*=2; printf("%d ",p-1); hanoi(n,'A','B','C'); return 0; }
有一个未完成的等式：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=0; if(t==n&&s>9) { ans++; return; } else { for(int i=s;i<=9;i++) { m=m*10+i; dfs(i+1,t+m); if(s!=1) dfs(i+1,t-m); } } } int main() { cin>>n; dfs(1,0); cout<<ans<<endl; return 0; }
输入一棵二叉树的先序和中序遍历序列，输出其后序遍历序列。
共两行，第一行一个字符串，表示树的先序遍历，第二行一个字符串，表示树的中序遍历。
仅一行，表示树的后序遍历序列。
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+1,l+y-ll,ll,y-1); if(y<rr)dfs(l+y-ll+1,r,y+1,rr); cout<<a[l]; } int main() { cin>>a>>b; len=a.size()-1; dfs(0,len,0,len); return 0; }
已知某开放授权人员名叫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)>10000000) cout<<"NO"; else cout<<"YES"; return 0; }
小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[100000+10]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); for(int i=1;i<n;i++) printf("%d ",a[i]); printf("%d",a[n]); return 0; }