90分,WA了第九个点
查看原帖
90分,WA了第九个点
103465
Knight_Master楼主2020/11/27 14:02
#include<bits/stdc++.h>
#define R register
#define next fghsfh
using namespace std;
typedef long long ll;

inline ll read(){
	ll x=0,t=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') t=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*t;
}
inline void write(ll x){
	if(x<0) {
		x=-x;
		putchar('-');
	}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
inline void writelp(ll x){
	write(x);putchar(' ');
}
inline void writeln(ll x){
	write(x);putchar('\n');
}
const ll M = 2e6+10;
ll n;
char s[210],c[210][50];
ll v[M],p,cnt=0;
ll t[500010][50];
ll rg[50][10];
inline void build(){
	for(R ll i=1;i<=n;i++){
		p=0;
	for(R ll j=0;j<strlen(c[i]);j++){
		if(!t[p][(ll)(c[i][j]-'a')]) t[p][(ll)(c[i][j]-'a')]=++cnt;
		p=t[p][(ll)(c[i][j]-'a')]; 
		}
		v[p]=i;
	}
}
bool f=0;
ll m;
inline void init(){
	rg[1][1]=0;rg[1][2]=1;rg[1][3]=2;
	rg[2][1]=3;rg[2][2]=4;rg[2][3]=5;
	rg[3][1]=6;rg[3][2]=7;rg[3][3]=8;
	rg[4][1]=9;rg[4][2]=10;rg[4][3]=11;
	rg[5][1]=12;rg[5][2]=13;rg[5][3]=-1;
	rg[6][1]=14;rg[6][2]=15;rg[6][3]=16;
	rg[7][1]=17;rg[7][2]=18;rg[7][3]=19;
	rg[8][1]=20;rg[8][2]=21;rg[8][3]=22;
	rg[9][1]=23;rg[9][2]=24;rg[9][3]=25;
}
ll dis[M];
ll a[M];
ll upp;
inline void dfs(ll cur,ll kk){
	if(f) return;
	if(cur==m && kk==0){
		if(!upp) return;
		for(R ll i=1;i<upp;i++){
			printf("%s ",c[dis[i]]);
		}
		printf("%s",c[dis[upp]]);
		exit(0);
	}
	if(cur==m) return;
	for(R ll i=1;i<=3;i++){ 
	if(rg[a[cur]][i]==-1) continue;
	if(v[t[kk][rg[a[cur]][i]]]) {
	dis[++upp]=v[t[kk][rg[a[cur]][i]]];
	dfs(cur+1,0);
	dis[upp]=0;
	upp--;
	}
	if(t[kk][rg[a[cur]][i]]) {
	dfs(cur+1,t[kk][rg[a[cur]][i]]);
	}
	}
	return;
}
int main(){
	n=read();
	scanf("%s",&s);
	m=strlen(s);
	for(R ll i=0;i<m;i++) a[i]=(ll)(s[i]-'0');
	for(R ll i=1;i<=n;i++){
		scanf("%s",&c[i]);
	}
	build();
	init();
	dfs(0,0);
	printf("No Solutions!");
}
2020/11/27 14:02
加载中...