[警示后人]本题卡unordered_map,map要加O2才能过
查看原帖
[警示后人]本题卡unordered_map,map要加O2才能过
570330
CalmKin楼主2023/8/2 15:24
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef pair<int,PII> PIII;
typedef unsigned long long ULL;
typedef long long LL;
const int N = 201 , M=210, MOD = 19650827 ,INF=0x3f3f3f3f;

int arr[N],cnt[4];
bool dp[N][N][4];

string comp[4][18],des;
unordered_map<char,int> mp;


int main() {
	
	cin.tie(0), cout.tie(0);
	ios::sync_with_stdio(0);
	
	mp['W']=0;mp['I']=1,mp['N']=2,mp['G']=3;
	string book="WING",ret="";
	
	for(int i=0;i<4;i++)	cin>>cnt[i];
	
	for(int i=0;i<4;i++)
	for(int j=0;j<cnt[i];j++) 
	{
		cin>>comp[i][j];
	}
	
	cin>>des;
	
	int n=des.size();
	des = "*" + des;
	
	
	//预处理
	for(int i=1;i<=n;i++) dp[i][i][ mp[des[i]] ] = 1;
	
	for(int len=2;len<=n;len++)
	{
		for(int st=1;st+len-1<=n;st++)
		{
			int ed = st+len-1;
			for(int k=st;k<ed;k++)
			{
				for(int i=0;i<4;i++)
				{
					for(int j=0;j<cnt[i];j++)
					{
						int lef = mp[comp[i][j][0]] , rig= mp[comp[i][j][1]];
						dp[st][ed][i] |= (dp[st][k][lef] & dp[k+1][ed][rig]);
						if(dp[st][ed][i])
							break;
					}
				}
			}
		}
	}
	
	for(int i=0;i<4;i++)
	{
		if(dp[1][n][i])
			ret+=book[i];
	}
	
	if(ret.size())
		cout<<ret;
	else
		cout<<"The name is wrong!";
	
	return 0;
}
2023/8/2 15:24
加载中...