寒假集训day1

T2:画画
NOIPdp首先观察题目,发现走过去再走回来的操作像极了NOIP某年的dp题首先观察题目,发现走过去再走回来的操作像极了NOIP某年的dp题
所以运用套路走两次所以运用套路走两次
1我开始的想法是因为只会往右走或往下走,所以能走就一定走完,后来发现走两次,就以为不行,结果发现没法判断只有1条路径的情况我开始的想法是因为只会往右走或往下走,所以能走就一定走完,后来发现走两次,就以为不行,结果发现没法判断只有1条路径的情况
正解:正解:
对于第一条路径:能往下走就走,不能走就往右走对于第一条路径:能往下走就走,不能走就往右走
对于第二条路径,能往右走就往右走,不能走就往下对于第二条路径,能往右走就往右走,不能走就往下
2对于重合的点乘2,因为来到重合点的路径对于第一条和第二条可以互换对于重合的点乘2,因为来到重合点的路径对于第一条和第二条可以互换
注意点:注意点:

  1. 如果遇到连续的重合点只用乘1次2,因为对于连续的重合点,重合点之间的路径是唯一的,互换不会产生新的方案
  2. 收尾两个点的路径互换只能算一次,如果交换两次的话,和原来的方案是相同的(我代码中算的是尾点)
  3. 起点开始的连续路径不能计入答案(如果和我一样计算尾点的话)
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=1e5+5;//
int a[N],b[N],suma[N],sumb[N];
int n;
ll ans=1,mod=1e9+7;//
bool flag=false,flag2=false;//
void dfs(int x,int y,int xx,int yy,bool ff){//ff用来判断连续的重合点
	if(suma[x]>a[x]||sumb[y]>b[y]||suma[xx]>a[xx]||sumb[yy]>b[yy]) {if(x==xx&&y==yy) ans/=2;return;};
	if(x!=xx||y!=yy){
		flag=true;
	}
	if(x==n&&y==n&&xx==n&&yy==n){
		flag2=true;
		return;
	}
	if(suma[x]+1<=a[x]&&sumb[yy]+1<=b[yy]&&y+1<=n&&xx+1<=n){
		suma[x]++,sumb[yy]++;
		bool f=false;
		if(x!=xx+1||y!=yy+1)sumb[y+1]++,suma[xx+1]++;
		if(x==xx+1&&y+1==yy) {if(!ff) ans=ans*2%mod;f=true;};
		dfs(x,y+1,xx+1,yy,f);
		suma[x]--,sumb[yy]--;
		if(x!=xx+1||y!=yy+1)sumb[y+1]--,suma[xx+1]--;
	}
	if(suma[x]==a[x]&&x+1<=n&&xx+1<=n&&sumb[yy]+1<=b[yy]){
		suma[x+1]++,sumb[yy]++;
		bool f=false;
		if(x+1!=xx+1||y!=yy)suma[xx+1]++,sumb[y]++;
		if(x+1==xx+1&&y==yy){if(!ff) ans=ans*2%mod;f=true;}
		dfs(x+1,y,xx+1,yy,f);
		suma[x+1]--,sumb[yy]--;
		if(x+1!=xx+1||y!=yy)suma[xx+1]--,sumb[y]--;
	}
	if(sumb[yy]==b[yy]&&yy+1<=n&&y+1<=n&&suma[x]+1<=a[x]){
		suma[x]++,sumb[yy+1]++;
		bool f=false;
		if(x!=xx||y+1!=yy+1)suma[xx]++,sumb[y+1]++;
		if(x==xx&&y+1==yy+1){if(!ff) ans=ans*2%mod;f=true;}
		dfs(x,y+1,xx,yy+1,f);
		suma[x]--,sumb[yy+1]--;
		if(x!=xx||y+1!=yy+1)suma[xx]--,sumb[y+1]--;
	}
	if(sumb[yy]==b[yy]&&suma[x]==a[x]&&x+1<=n&&yy+1<=n){
		sumb[y]++;suma[xx]++;
		bool f=false;
		if(x+1!=xx||y!=yy+1)suma[x+1]++,sumb[yy+1]++;
		if(x+1==xx&&y==yy+1){if(!ff) ans=ans*2%mod;f=true;}
		dfs(x+1,y,xx,yy+1,f);
		sumb[y]--;suma[xx]--;
		if(x+1!=xx||y!=yy+1)suma[x+1]--,sumb[yy+1]--;
	}
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
	flag2=false;flag=false;
    memset(suma,0,sizeof(suma));
    memset(sumb,0,sizeof(sumb));
	scanf("%d",&n);	ans=1;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i]);
	}
	suma[1]++,sumb[1]++;
	dfs(1,1,1,1,1);
	if(!flag2){
		puts("0");
		continue;
	}
	if(!flag){
		puts("1");
		continue;
	}	
	printf("%lld\n",ans);
    }
}

寒假集训day1寒假集训day1 Dlkoiw 发布了82 篇原创文章 · 获赞 5 · 访问量 1466 私信 关注
上一篇:js加密(十二)yy.com rsa


下一篇:PostgreSQL操作-psql基本命令