您现在的位置是：首页 >其他 >算法复习dfs bfs网站首页其他

# 【深基15.习9】验证栈序列

## 题目描述

给出两个序列 pushed 和 poped 两个序列，其取值从 1 到 $n(nle100000)$。已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出 `Yes`，否则输出 `No`。为了防止骗分，每个测试点有多组数据。

## 输入格式

第一行一个整数 $q$，询问次数。

接下来 $q$ 个询问，对于每个询问：

第一行一个整数 $n$ 表示序列长度；

第二行 $n$ 个整数表示入栈序列；

第三行 $n$ 个整数表示出栈序列；

## 输出格式

对于每个询问输出答案。

## 样例 #1

### 样例输入 #1

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

### 样例输出 #1

```
Yes
No
```

题解：直接就是出栈入栈简简单单

#include<stdio.h>
#define N 200000
struct stack
{
	int arr[N];
	int cot;
}a,b,c;
int main()
{
	int T,n,i;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(i=0;i<n;i++)
			scanf("%d",&a.arr[i]);
		for(i=0;i<n;i++)
			scanf("%d",&b.arr[i]);
		a.cot=b.cot=0;c.cot=1;
		while(a.cot<n)
		{
			c.arr[c.cot]=a.arr[a.cot];
			while(b.arr[b.cot]==c.arr[c.cot])
			{
				b.cot++;c.cot--;
			}
			c.cot++;a.cot++;
		}
		if(c.cot<=1) printf("Yes
");
		else printf("No
");
	}
}

# 马的遍历

## 题目描述

有一个 $n imes m$ 的棋盘，在某个点 $(x, y)$ 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

## 输入格式

输入只有一行四个整数，分别为 $n, m, x, y$。

## 输出格式

一个 $n imes m$ 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 $-1$）。

## 样例 #1

### 样例输入 #1

```
3 3 1 1
```

### 样例输出 #1

```
0    3    2    
3    -1   1    
2    1    4
```

## 提示

### 数据规模与约定

对于全部的测试点，保证 $1 leq x leq n leq 400$，$1 leq y leq m leq 400$。

题解：就是bfs，简简单单，把上下左右的方向搞成马走的方向就ok

#include<stdio.h>
struct node
{
    int x,y;
    int s;//步数
}que[160001];
int M[8][2]={-2,-1,-2,1,-1,-2,-1,2,1,-2,1,2,2,-1,2,1};//八个方向
int map[1000][1000];
int book[1000][1000]={0};//标记走没走过
int nx,ny,sx,sy,n,m;
int head=1,tail=1;
 
void bfs()
{
    while(head<tail){
    for(int i=0;i<8;i++){
        nx=que[head].x+M[i][0];
        ny=que[head].y+M[i][1];
        if(nx<=0||ny<=0||nx>n||ny>m||book[nx][ny]==1)
            continue;
        if(book[nx][ny]==0){
            book[nx][ny]=1;//标记已经走过
            que[tail].x=nx;
            que[tail].y=ny;
            que[tail].s=que[head].s+1;//记录步数
            map[nx][ny]=que[tail].s;//标记走到这需要多少步
            tail++;
 
        }
    }
    head++;
    }
}
 
int main()
{
    scanf("%d%d%d%d",&n,&m,&sx,&sy);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            map[i][j]=-1;
    que[tail].x=sx;
    que[tail].y=sy;
    que[tail].s=0;
    map[sx][sy]=que[tail].s;
    book[sx][sy]=1;
    tail++;
    bfs();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            printf("%-5d",map[i][j]);
        printf("
");
    }
}
 

# 自然数的拆分问题

## 题目描述

任何一个大于 $1$ 的自然数 $n$，总可以拆分成若干个小于 $n$ 的自然数之和。现在给你一个自然数 $n$，要求你求出 $n$ 的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。

## 输入格式

输入：待拆分的自然数 $n$。

## 输出格式

输出：若干数的加法式子。

## 样例 #1

### 样例输入 #1

```
7
```

### 样例输出 #1

```
1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4
```

## 提示

数据保证，$2leq nle 8$。

题解:回溯与递归

#include <stdio.h>
int n;
int ans[101];
void dfs(int sum,int dep)
{
	if(sum>n) return;
	if(sum==n){
		for(int i=1;i<=dep-2;i++){
			printf("%d+",ans[i]);
		}
		printf("%d
",ans[dep-1]);
		return;
	}
	for(int i=ans[dep-1];i<n;i++){
		ans[dep]=i;
		dfs(sum+i,dep+1);
	}
}
int main()
{
	scanf("%d",&n);
	ans[0]=1;
	dfs(0,1);
	return 0;
}

下班下班，每天开始学java