问判断环?暴力25分求助
查看原帖
问判断环?暴力25分求助
936120
1711Elegy楼主2023/10/27 17:19

没想到怎么递归,手写的k从1~10的情况

代码:

#include<bits/stdc++.h>
#define repeat(i,x) for(ll i=1;i<=x;i++)
using namespace std;
typedef long long ll;
const int maxn=500005;
inline ll read(){
	ll x=0;bool k=true;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-') k=false;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	if(k) return x;
	else return ~(x-1);
}
ll mod=1000000007;
ll tot;//步数
//以下数据均为题中数据 
ll n,k;
ll w[12],c[maxn];
bool d[maxn];
ll a[12];
bool out(){//判断是否出界 
	for(ll i=1;i<=k;i++){
		if(a[i]<1||a[i]>w[i]) return true;
	}
	return false;
}
void walk(){
	//ans表示当前位置能走多少步 
	ll ans=0,r=0;//r指示第几步,到了k就从头开始 
	while(!out()){
		ans++;
		if(r!=n) r++;
		else r=1;
		
		if(d[r]) a[c[r]]++;
		else a[c[r]]--;
	}
	tot=(tot+ans)%mod;
	return;
}
int main(){
	n=read(),k=read();
	repeat(i,k){
		w[i]=read();
		a[i]=1;
	} 
	repeat(i,n){
		c[i]=read();
		int y=read();
		if(y==1) d[i]=true; 
	}
	if(k==1){
		repeat(aa,w[1]){
			a[1]=aa;
			walk();
		}
	}
	if(k==2){
		repeat(aa,w[1]){
			repeat(bb,w[2]){
				a[1]=aa;a[2]=bb;
				walk();
			}
		}
	}
	if(k==3){
		repeat(aa,w[1]){
			repeat(bb,w[2]){
				repeat(cc,w[3]){
					a[1]=aa;a[2]=bb;a[3]=cc;
					walk();
				}
			}
		}
	}
	if(k==4){
		repeat(aa,w[1]){
			repeat(bb,w[2]){
				repeat(cc,w[3]){
					repeat(dd,w[4]){
						a[1]=aa;a[2]=bb;a[3]=cc;a[4]=dd;
						walk();
					}
				}
			}
		}
	}
	if(k==5){
		repeat(aa,w[1]){
			repeat(bb,w[2]){
				repeat(cc,w[3]){
					repeat(dd,w[4]){
						repeat(ee,w[5]){
							a[1]=aa;a[2]=bb;a[3]=cc;a[4]=dd;a[5]=ee;
							walk();
						}
					}
				}
			}
		}
	}
	if(k==6){
		repeat(aa,w[1]){
			repeat(bb,w[2]){
				repeat(cc,w[3]){
					repeat(dd,w[4]){
						repeat(ee,w[5]){
							repeat(ff,w[6]){
								a[1]=aa;a[2]=bb;a[3]=cc;a[4]=dd;a[5]=ee;a[6]=ff;
								walk();
							}
						}
					}
				}
			}
		}
	}
	if(k==7){
		repeat(aa,w[1]){
			repeat(bb,w[2]){
				repeat(cc,w[3]){
					repeat(dd,w[4]){
						repeat(ee,w[5]){
							repeat(ff,w[6]){
								repeat(gg,w[7]){
									a[1]=aa;a[2]=bb;a[3]=cc;a[4]=dd;a[5]=ee;a[6]=ff;a[7]=gg;
									walk();
								}
							}
						}
					}
				}
			}
		}
	}
	if(k==8){
		repeat(aa,w[1]){
			repeat(bb,w[2]){
				repeat(cc,w[3]){
					repeat(dd,w[4]){
						repeat(ee,w[5]){
							repeat(ff,w[6]){
								repeat(gg,w[7]){
									repeat(hh,w[8]){
										a[1]=aa;a[2]=bb;a[3]=cc;a[4]=dd;a[5]=ee;a[6]=ff;a[7]=gg;a[8]=hh;
										walk();
									}
								}
							}
						}
					}
				}
			}
		}
	}
	if(k==9){
		repeat(aa,w[1]){
			repeat(bb,w[2]){
				repeat(cc,w[3]){
					repeat(dd,w[4]){
						repeat(ee,w[5]){
							repeat(ff,w[6]){
								repeat(gg,w[7]){
									repeat(hh,w[8]){
										repeat(ii,w[9]){
											a[1]=aa;a[2]=bb;a[3]=cc;a[4]=dd;a[5]=ee;a[6]=ff;a[7]=gg;a[8]=hh;a[9]=ii;
											walk();
										}
										
									}
								}
							}
						}
					}
				}
			}
		}
	}
	if(k==10){
		repeat(aa,w[1]){
			repeat(bb,w[2]){
				repeat(cc,w[3]){
					repeat(dd,w[4]){
						repeat(ee,w[5]){
							repeat(ff,w[6]){
								repeat(gg,w[7]){
									repeat(hh,w[8]){
										repeat(ii,w[9]){
											repeat(jj,w[10]){
												a[1]=aa;a[2]=bb;a[3]=cc;a[4]=dd;a[5]=ee;a[6]=ff;a[7]=gg;a[8]=hh;a[9]=ii;a[10]=jj;
												walk();
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
	cout<<tot;
} 
2023/10/27 17:19
加载中...