淘先锋技术网

首页 1 2 3 4 5 6 7


好奇怪的游戏(bfs

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int x1,x2,y1,y2;
queue<int>qx;
queue<int>qy;
int xx[15] ={1,1,2,2,-1,-1,-2,-2,2,2,-2,-2};
int yy[15] ={2,-2,1,-1,2,-2,-1,1,2,-2,-2,2};
int dis[120][120];
int main()
{
	int T = 2;
	while(T--)
	{
		scanf("%d%d",&x1,&y1);
		while(!qx.empty())	qx.pop();
		while(!qy.empty())  qy.pop();
		memset(dis,0,sizeof(dis));
		qx.push(x1);
		qy.push(y1);
		dis[x1][y1] = 0;
		while(!qx.empty())
		{
			int x = qx.front();
			int y = qy.front();
			qx.pop();
			qy.pop();
			if(x == 1 && y == 1)
			{
				printf("%d\n",dis[1][1]);
				break;
			}
			for(int i=0;i<12;i++)
			{
				int tx = x + xx[i];
				int ty = y + yy[i];
				if(tx>=1 && tx <= 50 && ty >= 1 && ty <= 50 && dis[tx][ty] == 0)
				{
					dis[tx][ty] = dis[x][y] + 1;
					qx.push(tx);
					qy.push(ty);
				}
			}
		}
	}	
	return 0;
}

神奇的四次方数

思路:(来自题解。。。

完全背包固然是正解,但万一比赛时我们脑子瓦特想不出正解怎么办呢?

那就是我们的爆搜出场的时候了!(滑稽)

但是纯爆搜显然是不行的,m<=100000,这个数据范围很有可能得不了高分甚至爆0,所以我们就要进行一些优化。

首先是剪枝。我们可以用 ans 存下当前的最好答案,如果在搜索时当前选的数的数量已经大于ans了,那肯定就没必要找了,这样是白费力气。另外,1^4+2^4和2^4+1^4是一样的,我们用一个last让选出的数列变成升序,同样可以减少时间消耗。

另外搜的顺序非常重要。如果我们从1往上搜,那第一个选出来的肯定是全1的序列。这种情况我们肯定不想要,希望直接将其剪枝。那么怎么操作呢?结合刚才说的,我们可以确定一个娇小较小的ans,然后之后的搜索肯定不会超过这个步数。没错,从最大往小的搜可以很好地完成这个任务。如果不这样的话只会有30分。

#include<bits/stdc++.h>
using namespace std;
int n;
int ans=999999;
void dfs(int tot,int k,int last)
{
    if(k>ans) return; 
    if(tot>n) return; 
    if(tot==n) 
    {
        if(ans>k) ans=k;
        return;
    }
    int i;
    for(i=last;i*i*i*i<=n-tot;) i++;
    for(;i>=last;i--) 
        dfs(tot+i*i*i*i,k+1,i);
}
int main()
{
    cin>>n;
    dfs(0,0,1); 
    cout<<ans;
    return 0;
}

江湖数(dfs

#include<iostream>
#include<cstdio>
using namespace std;
char a[120][120];
bool vis[120][120]; 
int n,m;
int xx[8] = {0,0,1,1,1,-1,-1,-1};
int yy[8] = {1,-1,1,0,-1,1,0,-1};
void dfs(int x,int y)
{
	for(int i=0;i<8;i++)
	{
	int tx = x + xx[i];
	int ty = y + yy[i];
	if(!vis[tx][ty] && a[tx][ty] == 'W' && tx >=1 && tx <= n && ty >=1 && ty <= m)
	{
		vis[tx][ty] = 1;
		dfs(tx,ty);
	}	
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	int ans = 0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j] == 'W' && !vis[i][j])
			{
				dfs(i,j);
				ans ++;
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

选数

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int ans=0,n,k,x,a[21],num=0;
bool p(int q)
{
    int i;
    if(q==2) return true;
    for(i=2;i*i<=q;i++)
    {
        if(q%i==0) return false;
    }
    return true;
}
void dfs(int x,int y)//定义深搜的函数,y是当前最后选过的数在数组中的位置,x是当前正在选择第几个数,和用num变量储存
{
    int i,j;
    if(x > k){//如果选的数已经比k多了,就检测总和num是否为质数
        if(p(num)) ans++; //是就增加ans
        return ;
    }
    for(i=y+1;i<=n;i++)//否则继续搜索下一个数
    {
        num+=a[i];//取数
        dfs(x+1,i);//搜索
        num-=a[i];//回溯
    }
}
int main()
{
    int i,j;
    scanf("%d%d",&n,&k);//输入,不解释
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    dfs(1,0);//开始深搜,选择第一个数,由于没有选过任意一个数,y=0
    printf("%d",ans);//输出答案
    return 0;
}

字符串(bfs

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,ans;
void dfs(int now,int s,int l) // now 表示0 or 1  s 表示相邻的个数   l 判断是否结束 
{
	if(l == n)
	{
		ans ++;
		return ;
	}
	if(s<2) dfs(now,s+1,l+1);
	dfs(now^1,1,l+1);
}
int main()
{
	scanf("%d",&n);
	if(n == 0)
	ans = 0;
	else
	dfs(0,1,1),dfs(1,1,1);
	printf("%d\n",ans);
	return 0;
}

去看电影(dfs

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[20];
bool vis[20];
int n,m,maxx=-1;
void dfs(int k,int ans)
{
	for(int i=k;i<=m;i++)
	{
		if(!vis[i])
		{
			vis[i] = 1;
			ans += a[i];
			if(ans <= n)
			{
				maxx = max(ans,maxx);
				dfs(i+1,ans);
			}
			vis[i] = 0;
			ans -= a[i];
		}
	} 
} 
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&a[i]);
	}
	dfs(1,0);
	cout<<maxx<<endl;
	return 0;
}

传球( 搜索 40分。。。

#include<iostream>
#include<cstdio>
#include<queue> 
using namespace std;
int n,m,ans = 0;
queue<int>q1,q2;
void bfs()
{
	while(!q1.empty())
	{
		int now = q1.front();
		q1.pop();
		int step = q2.front();
		q2.pop(); 
		if(step > m)
		return ;
		step ++;
		int ne = now +1;
		if(ne == n +1)
			ne = 1;
		if(ne == n && step == m)
			ans ++;
		q1.push(ne);
		q2.push(step);
		int nne = now -1;
		if(nne == 0)
			nne = n;
		if(nne == n && step == m)
			ans ++;
		q1.push(nne);
		q2.push(step);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	q1.push(n);
	q2.push(0);
	bfs();
	cout<<ans<<endl;
}

约瑟夫问题(搜索

#include<iostream>
#include<cstdio>
#include<queue>
#include<map>
using namespace std;
int a[120];
int n,m;
queue<int>q;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		q.push(i);
	}
	if(n == 0)
	return 0;
	while(!q.empty())
	{
		for(int i=1;i<=m-1;i++)
		{
			int a = q.front();
			q.pop();
			q.push(a);
		}
		cout<<q.front()<<" ";
		q.pop();
	}
	return 0;
} 

超级书架2(dfs

#include<iostream>
#include<cstdio>
using namespace std;
int a[120];
bool vis[120];
int n,m;
int ans = 1e9;
void dfs(int sum)
{
	if(sum >= m) 
	{
		ans = min(sum,ans);
		return ;
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			vis[i] = 1;
			dfs(sum + a[i]);
			vis[i] = 0;
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	dfs(0);
	cout<<ans - m<<endl;
	return 0;
}

放苹果(递归

这道题其实就是一个分类讨论+递归,你可以选择有一个盘子一个苹果都不放,然后盘子数减1,或者(不可能两种方案都不选)每个盘子都放一个苹果,即苹果减去盘子的数量,就一直这样递归下去,就得到了最终的答案。注意:有0个苹果或1个盘子时,只有一种方案,所以(n==0||m==1)return 1,当n<0或m<1时,因为根本不存在这种情况,所以返回一个0

#include<iostream>
#include<cstdio>
using namespace std;
int T,n,m;
int solve(int n,int m)
{
	if(n == 0 || m == 1)
	return 1;
	if(n<0||m<1)
	return 0;
	return solve(n,m-1) + solve(n-m,m);
}
int main()
{
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		cout<<solve(n,m)<<endl;
	}
	return 0;
}

游戏(bfs

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
char a[2010][2010];
bool vis[2010][2010];
int dis[2010][2010];
int n,m;
int xx[4] = {0,0,1,-1};
int yy[4] = {1,-1,0,0};
queue<int>qx,qy; 
int pd(int x,int y)
{
	if( x>=1 && x<=n && y>=1&& y<=m && !vis[x][y] && a[x][y] != '#')
		return 1;
	return 0;
}
void bfs()
{
	while(!qx.empty())
	{
		int x = qx.front();
		int y = qy.front();
		qx.pop();
		qy.pop();
		for(int i=0;i<4;i++)
		{
			int tx = x + xx[i];
			int ty = y + yy[i];
			if(pd(tx,ty))
			{
				qx.push(tx);
				qy.push(ty);
				vis[tx][ty] = 1;
				dis[tx][ty] = dis[x][y] + 1;
			}
		}
	}
}
int main()
{
	int tx,ty,enx,eny;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
			vis[i][j] = 0;
			dis[i][j] = 1e9;
			if(a[i][j] == 'm')
			{
				tx = i;
				ty = j;
			}
			if(a[i][j] == 'd')
			{
				enx = i;
				eny = j;
			}
		}
	}
	vis[tx][ty] = 1;
	dis[tx][ty] = 0;
	qx.push(tx);
	qy.push(ty);
	bfs();
	if(dis[enx][eny] == 1e9)
	cout<<"No Way!"<<endl;
	else 
	cout<<dis[enx][eny]<<endl;
	return 0;
}

海战(dfs

先预处理判断是否是不可行的情况,我们由题意可以知道,不可行的情况为两个船挨在了一起,即存在不是矩形的一个图案的情况。我们又可以知道,在一个 2*2 的矩形中,若在三个地方都是#,那么就一定存在不是矩形的情况,直接输出,Bad placement.

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int a[1010][1010];
bool vis[1010][1010];
int n,m;
int xx[4] = {0,0,1,-1};
int yy[4] = {1,-1,0,0}; 
int pd(int x,int y)
{
	if(x>=1&&x<=n&&y>=1&&y<=m&&a[x][y] == 1 &&!vis[x][y])
	return 1;
	return 0;
} 
void dfs(int x,int y)
{
	vis[x][y] = 1;
	a[x][y] = 0;
	for(int i=0;i<4;i++)
	{
		int tx = x + xx[i];
		int ty = y + yy[i];
		if(pd(tx,ty))
		{
			dfs(tx,ty);
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			char ch;
			cin>>ch;
			if(ch == '.')
			a[i][j] = 0;
			else a[i][j] = 1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			int sum = 0;
			if(a[i][j]) sum ++;
			if(a[i+1][j]) sum ++;
			if(a[i][j+1]) sum ++;
			if(a[i+1][j+1]) sum ++;
			if(sum == 3)
			{
				cout<<"Bad placement."<<endl;
				return 0;
			}
		}
	}
	int ans = 0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(!vis[i][j]&&a[i][j] == 1)
			{
				ans ++;
				dfs(i,j);
			}
		}
	}
	printf("There are %d ships.\n",ans);
	return 0;
}

自然数的拆分

简单的搜索,要求下一个大于等于上一个即可

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int a[15];
int n,m;
void print(int k)
{
	for(int i=1;i<=k-1;i++)
	{
		cout<<a[i]<<"+";
	}
	cout<<a[k]<<endl;
}
void dfs(int s,int t)
{
	if(s == 0)
	{
		print(t-1);
		return ;
	}
	for(int i=1;i<=s;i++)
	{
		if(a[t-1] <= i && i < n)
		{
			a[t] = i;
			s -= i;
			dfs(s,t+1);
			s += i;
		}
	}
}
int main()
{
	cin>>n;
	dfs(n,1);
	return 0;
}
 

Catch That Cow(改错改了好久,**!

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;

int visit[100005] = {0};
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m) != EOF)
    {
        memset(visit,0,sizeof(visit));
        queue<int> q;
        q.push(n);
        int t;
        while(!q.empty())
        {
            t = q.front();
            q.pop();
            if(t == m)
            {
                break;
            }
            if(t > 0 && !visit[t-1])
            {
                visit[t-1] = visit[t]+1;
                q.push(t-1);
            }
            if(t < m &&!visit[t+1])
            {
                visit[t+1] = visit[t]+1;
                q.push(t+1);
            }
            if(t*2 < 100005 && !visit[t*2])
            {
                visit[2*t] = visit[t]+1;
                q.push(2*t);
            }
        }
        printf("%d\n",visit[m]);
    }
    return 0;
}
poj 1426(枚举 0 1 字符串即可

博客地址

#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
struct node
{
    string s;
    int mod;
}cur,nxt;
bool v[1000001];
queue<node>q;
int main()
{
    int n;
    scanf("%d",&n);
    cur.s="1";cur.mod=1;
    q.push(cur);
    while(!q.empty())
    {
        cur=q.front();
        q.pop();
        nxt.mod=(cur.mod*10)%n;
        nxt.s=cur.s+'0';
        if(nxt.mod==0)
        {
            cout<<nxt.s;
            return 0;
        }
        if(!v[nxt.mod])
        {
            q.push(nxt);
            v[nxt.mod]=true;
        }
        nxt.mod=(cur.mod*10+1)%n;
        nxt.s=cur.s+'1';
        if(nxt.mod==0)
        {
            cout<<nxt.s;
            return 0;
        }
        if(!v[nxt.mod])
        {
            q.push(nxt);
            v[nxt.mod]=true;
        }
    }
    return 0;
}

迷宫问题(打印路径
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue> 
using namespace std;
const int N = 7;
int a[N][N];
bool vis[N][N];
int prex[N*N];
int prey[N*N];
int xx[4] = {0,0,1,-1};
int yy[4] = {1,-1,0,0};
struct Node{
	int x;
	int y;
	int to;
	int nex;
}node[50];
int pd(int x,int y)
{
	if(x >= 0 && x < 5 && y >= 0 && y <5 && a[x][y] == 0)
	return 1;
	return 0;
}
void BFS(int x,int y)
{
	queue<Node>q;
	int tot = 0;
	Node st;
	node[0].x = node[0].y = 4;
	node[0].to = node[0].nex = 0;
	q.push(node[0]);
	vis[4][4] = 1;
	while(!q.empty())
	{
		Node now = q.front();
		q.pop();
		if(now.x == 0 && now.y == 0)
		{
			int t = now.to;
			while(1)
			{
				printf("(%d, %d)\n",node[t].x,node[t].y);
				if(!t)
				{
					return ;
				}
				t = node[t].nex;
			}
		}
		for(int i=0;i<4;i++)
		{
			int tx = now.x + xx[i];
			int ty = now.y + yy[i];
			if(pd(tx,ty) && !vis[tx][ty])
			{
				vis[tx][ty] = 1;
				node[++tot].x = tx;
				node[tot].y = ty;
				node[tot].to = tot;
				node[tot].nex = now.to;
				q.push(node[tot]);
			}
		}
	}
}
int main()
{
	for(int i=0;i<5;i++)
	{
		for(int j=0;j<5;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	BFS(0,0);
	return 0;
}