【各种深搜 题解】Luogu P¥%……

P1454

#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
bool map[110][110],vis[110][110];
int ans=0;
void search(int x,int y){
	bool f=false;
    if(x-2>0){
        if(map[x-2][y]==true&&vis[x-2][y]==false){
            vis[x-2][y]=true;
            search(x-2,y);
            f=true;
        }
    }
    if(x+2<=n){
        if(map[x+2][y]==true&&vis[x+2][y]==false){
            vis[x+2][y]=true;
            search(x+2,y);
            f=true;
        }
    }
    if(y-2>0){
        if(map[x][y-2]==true&&vis[x][y-2]==false){
            vis[x][y-2]=true;
            search(x,y-2);
            f=true;
        }
    }
    if(y+2<=m){
        if(map[x][y+2]==true&&vis[x][y+2]==false){
            vis[x][y+2]=true;
            search(x,y+2);
            f=true;
        }
    }
    if(y-1>0){
        if(map[x][y-1]==true&&vis[x][y-1]==false){
            vis[x][y-1]=true;
            search(x,y-1);
            f=true;
        }
    }
    if(y+1<=m){
        if(map[x][y+1]==true&&vis[x][y+1]==false){
            vis[x][y+1]=true;
            search(x,y+1);
            f=true;
        }
    }
    if(x-1>0){
        if(map[x-1][y]==true&&vis[x-1][y]==false){
        	vis[x-1][y]=true;
        	search(x-1,y);
        	f=true;
		}
        if(y-1>0){
            if(map[x-1][y-1]==true&&vis[x-1][y-1]==false){
            	vis[x-1][y-1]=true;
            	search(x-1,y-1);
            	f=true;
			}
        }
        if(y+1<=m){
            if(map[x-1][y+1]==true&&vis[x-1][y+1]==false){
            	vis[x-1][y+1]=true;
            	search(x-1,y+1);
            	f=true;
			}
        }
    }
    if(x+1<=n){
        if(map[x+1][y]==true&&vis[x+1][y]==false){
        	vis[x+1][y]=true;
        	search(x+1,y);
        	f=true;
		}
        if(y-1>0){
            if(map[x+1][y-1]==true&&vis[x+1][y-1]==false){
            	vis[x+1][y-1]=true;
            	search(x+1,y-1);
            	f=true;
			}
        }
        if(y+1<=m){
            if(map[x+1][y+1]==true&&vis[x+1][y+1]==false){
            	vis[x+1][y+1]=true;
            	search(x+1,y+1);
            	f=true;
			}
        }
    }
}
int main(){
    char c;
    scanf("%d%d",&n,&m);
    scanf("%c",&c);
    scanf("%c",&c);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%c",&c);
            if(c=='-')
                map[i][j]=false;
            else if(c=='#')
                map[i][j]=true;
        }
        scanf("%c",&c);
        scanf("%c",&c);
    }
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=m;j++){
    		if(map[i][j]==true&&vis[i][j]==false){
    		    ans++;
    			search(i,j);
    		}
		}
	}
    printf("%d",ans);
    return 0;
}

P1294

#include<cstring>
#include<cstdio>
using namespace std;
int n,m;
int map[30][30];
bool vis[30];
int maxn=0,now=0;
void search(int k){
	vis[k]=true;
	for(int i=1;i<=n;i++){
		if(map[k][i]<0x3f3f3f3f-10&&vis[i]==false){
			now+=map[k][i];
			if(now>maxn)
				maxn=now;
			search(i);
			now-=map[k][i];
		}
	}
	vis[k]=false;
}
int main(){
	memset(map,0x3f3f3f3f,sizeof(map));
	memset(vis,false,sizeof(vis));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int l,r,d;
        scanf("%d%d%d",&l,&r,&d);
        map[l][r]=d;
        map[r][l]=d;
    }
    for(int i=1;i<=n;i++)
    	search(i);
    printf("%d",maxn);
    return 0;
}

P1088

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
int a[10010];
void search(int k){
	if(k==0){
		printf("%d",a[1]);
		for(int i=2;i<=n;i++)
			printf(" %d",a[i]);
		return ;
	}
	for(int i=n;i>=1;i--){
		if(a[i]>a[i-1]){
			for(int j=n;j>=i;j--){
				if(a[j]>a[i-1]){
					int change=a[j]; a[j]=a[i-1]; a[i-1]=change;
					break;
				}
			}
			sort(a+i,a+n+1);
			break;
		}
	}
	search(k-1);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    	scanf("%d",&a[i]);
    search(m);
    return 0;
}

P2386

#include<cstdio>
using namespace std;
int k;
int n,m;
int ans=0;
void search(int last,int a,int k){
	if(k==1){
		ans++;
		return ;
	}
	for(int i=last;i<=a-i;i++)
		search(i,a-i,k-1);
}
int main(){
	scanf("%d",&k);
	for(int i=1;i<=k;i++){
	    scanf("%d%d",&n,&m);
	    search(0,n,m);
	    printf("%d\n",ans);
	    ans=0;
	}
    return 0;
}

P1025

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
int ans=0;
void search(int last,int a,int k){
	if(k==1){
		ans++;
		return ;
	}
	for(int i=last;i<=a-i;i++)
		search(i,a-i,k-1);
}
int main(){
    scanf("%d%d",&n,&m);
    search(1,n,m);
    printf("%d",ans);
    return 0;
}

P1219

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int x[200];
bool y[200];
bool tan[200];
bool atan[200];
int ans=0;
int n;
void queen(int m){
	if(m>n){
		ans++;
		if(ans<=3){
			for(int i=1;i<=n;i++){
				cout<<x[i]<<" ";
			}
			cout<<endl;
		}
		return;
	}
	for(int i=1;i<=n;i++){
		if(!y[i]&&!tan[i+m]&&!atan[i-m+n]){
			x[m]=i;
			y[i]=1;
			tan[i+m]=1;
			atan[i-m+n]=1;
			queen(m+1);
			y[i]=0;
			tan[i+m]=0;
			atan[i-m+n]=0;
		}
	}
}
int main(){
	cin>>n;
	queen(1);
	cout<<ans;
	return 0;
}

P1865

#include<cstdio>
#include<algorithm>
using namespace std;
int s[1000010],k=0;
bool a[1000010]={true,true};
int num[1000010];
void prime(int m){
	for(int i=2;i<=m;i++){
		if(a[i]==false){
			s[++k]=i;
			for(int j=i+i;j<=m;j+=i)
				a[j]=true;
		}
	}
}
int main(){
	int n,m;
    scanf("%d%d",&n,&m);
	prime(m);
	for(int i=1;i<=m;i++){
		if(a[i]==false)
			num[i]=num[i-1]+1;
		else
			num[i]=num[i-1];
	}
	for(int i=1;i<=n;i++){
		int ans,l,r;
		scanf("%d%d",&l,&r);
		if(l<1||r>m||r<l){
			printf("Crossing the line\n");
			continue;
		}
		if(a[l]==false)
			ans=num[r]-num[l]+1;
		else
			ans=num[r]-num[l];
		printf("%d\n",ans);
	}
    return 0;
}

P1443

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int x,y,a,b;
int map[500][500];
bool m[500][500];
void search(int a,int b,int walk){
	if(walk<map[a][b]){
		map[a][b]=walk;
		m[a][b]=1;
		if(a>2&&b>1)    search(a-2,b-1,walk+1);
		if(a>2&&b+1<=y)    search(a-2,b+1,walk+1);
		if(a>1&&b>2)    search(a-1,b-2,walk+1);
		if(a>1&&b+2<=y)    search(a-1,b+2,walk+1);
		if(a+1<=x&&b>2)    search(a+1,b-2,walk+1);
		if(a+1<=x&&b+2<=y)    search(a+1,b+2,walk+1);
		if(a+2<=x&&b>1)    search(a+2,b-1,walk+1);
		if(a+2<=x&&b+1<=y)    search(a+2,b+1,walk+1);
	}
	else return;
}
int main(){
    cin>>x>>y>>a>>b;
    for(int i=1;i<=x;i++){
    	for(int j=1;j<=y;j++){
    		map[i][j]=999;
    	}
    }
    search(a,b,0);
    for(int i=1;i<=x;i++){
    	for(int j=1;j<=y;j++){
    		if(!m[i][j])    printf("-1   ");
    		else    printf("%-5d",map[i][j]);
		}
		cout<<endl;
	}
    return 0;
}

P1874

#include<cstdio>
#include<cstring>
int minans=0x3f3f3f3f;
char s[50];
int len,t;
bool f[50];
int change(int l,int r){
	int n=0;
	for(int i=l;i<=r;i++)
		n=n*10+(s[i]-'0');
	if(n<0)
		return 0x3f3f3f3f;
	return n;
}
int total(int k){
	int l=1;
	int m=0;
	for(int i=1;i<=k;i++){
		if(f[i]==true){
			m+=change(l,i);
			l=i+1;
		}
	}
	m+=change(k+1,len);
	return m;
}
int n(int k){
	int m=0;
	for(int i=1;i<=k;i++){
		if(f[i]==true)
			m++;
	}
	return m;
}
void search(int k){
	if(k==len)
		return ;
	for(int i=0;i<=1;i++){
		if(i==0){
			f[k]=true;
			if(total(k)<t){
				f[k]=false;
				continue;
			}
			else if(total(k)==t){
				if(n(k)<minans)
					minans=n(k);
				f[k]=false;
				continue;
			}
			else{
				search(k+1);
				f[k]=false;
			}
		}
		else if(i==1)
			search(k+1);
	}
}
int main(){
	scanf("%s",s);
	len=strlen(s);
	for(int i=len;i>=1;i--)
		s[i]=s[i-1];
	s[0]=' ';
	int p=1;
	while(s[p]=='0')
		p++;
	p--;
	len-=p;
	for(int i=1;i<=len;i++)
		s[i]=s[i+p];
	scanf("%d",&t);
	if(change(1,len)==t){
		printf("0");
		return 0;
	}
	search(1);
	if(minans>=40){
		printf("-1");
		return 0;
	}
	printf("%d",minans);
	return 0;
}

P1118

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int yh[13][13];
int maxn[13],maxx[13][13],minn[13],minx[13][13];
int n,num,now=0;
int a[13];
bool f[13],ff=false;
void start(){
	yh[1][1]=1;
	yh[2][1]=yh[2][2]=1;
	for(int i=3;i<=12;i++){
		for(int j=1;j<=i;j++)
			yh[i][j]=yh[i-1][j-1]+yh[i-1][j];
	}
	for(int i=1;i<=12;i++){
		int k=1;
		for(int j=1;j<=i;j+=2){
			maxx[i][k]=j;
			maxn[i]+=yh[i][k]*j;
			k++;
		}
		int j= i%2==0? i:i-1;
		for(;j>0;j-=2){
			maxx[i][k]=j;
			maxn[i]+=yh[i][k]*j;
			k++;
		}
	}
	for(int i=1;i<=12;i++){
		int k=i;
		int j= i%2==0? i:i-1;
		for(;j>0;j-=2){
			minx[i][k]=j;
			minn[i]+=yh[i][k]*j;
			k--;
		}
		for(j=1;j<=i;j+=2){
			minx[i][k]=j;
			minn[i]+=yh[i][k]*j;
			k--;
		}
	}
}
void search(int k){
	if(k>n)
		return;
	if(now>num)
		return;
	for(int i=1;i<=n;i++){
		if(f[i]==true)
			continue;
		else{
			a[k]=i;
			f[i]=true;
			now+=yh[n][k]*i;
			search(k+1);
        	if(k==n){
        		if(now==num){
        			printf("%d",a[1]);
        			for(int i=2;i<=n;i++)
        				printf(" %d",a[i]);
        			ff=true;
        		}
        	}
			now-=yh[n][k]*i;
			if(ff==true)
				return;
			f[i]=false;
		}
	}
	
}
int main(){
	start();
	scanf("%d%d",&n,&num);
	if(num<minn[n]||num>maxn[n])
		return 0;
	if(num==minn[n]){
		printf("%d",minx[n][1]);
		for(int i=2;i<=n;i++)
			printf(" %d",minx[n][i]);
		return 0;
	}
	if(num==maxn[n]){
		printf("%d",maxx[n][1]);
		for(int i=2;i<=n;i++)
			printf(" %d",maxx[n][i]);
		return 0;
	}
	memset(f,false,sizeof(f));
	search(1);
	return 0;
}

P1141

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
char s[1100][1100];
int map[1100][1100];
int anss[1000000];
int ans;
int k=1;
void search(int,int);
void u(int,int);
void d(int,int);
void l(int,int);
void r(int,int);
int main(){
    int x,y;
    scanf("%d %d\n",&n,&m);
    for(int i=0;i<n;i++){
		scanf("%s",s[i]);
	}
    for(int i=0;i<m;i++){
        cin>>x>>y;
        ans=0;
        if(!map[x-1][y-1]){
			search(x-1,y-1);
        	anss[k]=ans;
        	k++;
        }
        printf("%d\n",anss[map[x-1][y-1]]);
    }
    return 0;
}
void search(int x,int y){
    map[x][y]=k;
    ans++;
    for(int i=1;i<=4;i++){
        if(i==1)    u(x,y);
        if(i==2)    d(x,y);
        if(i==3)    l(x,y);
        if(i==4)    r(x,y);
    }
}
void u(int x,int y){
	if(x-1<0)    return;
	if(map[x-1][y]<k&&s[x][y]!=s[x-1][y])    search(x-1,y);
}
void d(int x,int y){
	if(x+1>=n)    return;
	if(map[x+1][y]<k&&s[x][y]!=s[x+1][y])    search(x+1,y);
}
void l(int x,int y){
	if(y-1<0)    return;
	if(map[x][y-1]<k&&s[x][y]!=s[x][y-1])    search(x,y-1);
}
void r(int x,int y){
	if(y+1>=n)    return;
	if(map[x][y+1]<k&&s[x][y]!=s[x][y+1])    search(x,y+1);
}

P1434

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int nx,ny;
int map[110][110];
int m[110][110];
int maxn=0;
bool biger(int a,int b){
	return a>b;
}
int maxx(int a,int b){
	if(a>b)    return a;
	return b;
}
int max_(int a,int b,int c,int d){
	return maxx(maxx(a,b),maxx(c,d));
}
int search(int x,int y){
	int u=0,d=0,l=0,r=0;
	for(int i=0;i<4;i++){
		if(i==0&&x>0&&map[x][y]>map[x-1][y]){
			if(m[x-1][y]>1)    u=m[x-1][y];
			else    u=search(x-1,y);
		}
		if(i==1&&x+1<nx&&map[x][y]>map[x+1][y]){
			if(m[x+1][y]>1)    d=m[x+1][y];
			else    d=search(x+1,y);
		}
		if(i==2&&y>0&&map[x][y]>map[x][y-1]){
			if(m[x][y-1]>1)    l=m[x][y-1];
			else    l=search(x,y-1);
		}
		if(i==3&&y+1<ny&&map[x][y]>map[x][y+1]){
			if(m[x][y+1]>1)    r=m[x][y+1];
			else    r=search(x,y+1);
		}
	}
	m[x][y]=max_(u,d,l,r)+1;
	if(maxn<m[x][y])    maxn=m[x][y];
	return m[x][y];
}
int main(){
	cin>>nx>>ny;
	for(int i=0;i<nx;i++){
		for(int j=0;j<ny;j++){
			cin>>map[i][j];
		}
	}
	for(int i=0;i<nx;i++){
		for(int j=0;j<ny;j++){
			search(i,j);
		}
	}
	cout<<maxn;
	return 0;
}

P1784

#include<cstdio>
using namespace std;
int map[10][10];
bool n[10][10],m[10][10],s[10][10],ff=false;
int squre(int x,int y){
	if(x>6){
		if(y>6)
			return 9;
		else if(y>3)
			return 8;
		else
			return 7;
	}
	else if(x>3){
		if(y>6)
			return 6;
		else if(y>3)
			return 5;
		else
			return 4;
	}
	else{
		if(y>6)
			return 3;
		else if(y>3)
			return 2;
		else
			return 1;
	}
}
void fill(int x,int y){
	n[x][map[x][y]]=true;
	m[y][map[x][y]]=true;
	s[squre(x,y)][map[x][y]]=true;
}
void remove(int x,int y){
	n[x][map[x][y]]=false;
	m[y][map[x][y]]=false;
	s[squre(x,y)][map[x][y]]=false;
}
void search(int x,int y){
	if(x>9||y>9)
		return ;
	int x1=x+y/9,y1=y%9+1;
	if(map[x][y]!=0){
	    if(x==9&&y==9){
	        for(int a1=1;a1<=9;a1++){
				for(int a2=1;a2<=9;a2++)
					printf("%d ",map[a1][a2]);
				printf("\n");
	        }
	    }
	    else
		    search(x1,y1);
		return ;
	}
	for(int i=1;i<=9;i++){
		if(n[x][i]==false&&m[y][i]==false&&s[squre(x,y)][i]==false){
			map[x][y]=i;
			fill(x,y);
			if(x==9&&y==9){
				for(int a1=1;a1<=9;a1++){
					for(int a2=1;a2<=9;a2++)
						printf("%d ",map[a1][a2]);
					printf("\n");
				}
				ff=true;
				return ;
			}
			search(x1,y1);
			if(ff==true)
				return ;
			remove(x,y);
			map[x][y]=0;
		}
	}
}
int main(){
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			scanf("%d",&map[i][j]);
			if(map[i][j]!=0)
				fill(i,j);
		}
	}
	search(1,1);
	return 0;
}

 

发布者:Viva_Hurricane

我觉得站主素质极低!

留下评论

电子邮件地址不会被公开。 必填项已用*标注