假做法水过,求hack或证明
查看原帖
假做法水过,求hack或证明
699380
A_Step_Back楼主2024/5/29 17:46
#include<bits/stdc++.h>
using namespace std;
string s;int print,len,dp[205][205][5],cnt[5],g[30][5];
int t[130];char c[]={'@','W','I','N','G'};
void solve(int l1,int r1,int l2,int r2){
	if(l1>r1||l2>r2)return;
	for(int i=1;i<=4;i++){
		for(int j=1;j<=4;j++){
			if(dp[l1][r1][i]&&dp[l2][r2][j]){
				for(int k=1;k<=4;k++){
					if(g[i*5+j][k])dp[l1][r2][k]=1;
				}
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	t['W']=1,t['I']=2,t['N']=3,t['G']=4;
	for(int i=1;i<=4;i++)cin>>cnt[i];
	for(int i=1;i<=4;i++){
		for(int j=1;j<=cnt[i];j++){
			char a,b;cin>>a>>b;
			g[t[a]*5+t[b]][i]=1;
		}
	}
	cin>>s;len=s.size();s=' '+s;
	for(int i=1;i<=len;i++)dp[i][i][t[s[i]]]=1;
	for(int l=1;l<=len;l++){
		for(int i=1;i+l<=len;i++){
			int j=i+l;
			solve(i,i,i+1,j);
			solve(i,i+1,i+2,j);
			solve(i,j-2,j-1,j);
			solve(i,j-1,j,j);
		}
	}
	for(int i=1;i<=4;i++){
		if(dp[1][len][i])cout<<c[i],print++;
	}
	if(!print)cout<<"The name is wrong!"; 
	cout<<'\n';
}
2024/5/29 17:46
加载中...