C. Crossword Validation
题目前两段是故事没用
题意：给定一个矩阵，m个字符串与这m个字符串对应的数值，矩阵中含有字符’#‘，我们要取矩阵中每行从左到右，和每列从上到下，不包含字符’#'的尽可能长的子串与给定m个字符串匹配，匹配成功则在答案中加上对应的数值，匹配不成功则输出-1
比如:
ab
#d
在一行一行的看时，子串就有ab和d
在一列一列的看时，子串就有a和bd
给定m个字符串和对应的数值如下的话
ab 1
a 2
d 3
bd 4
答案就是
1+2+3+4=10
思路：首先用trie存储m个给定的字符串和对应的val值，再根据题意去分解矩阵中的子串来query字典树中是否有这个子串。
AC code
#include <bits/stdc++.h>
using namespace std;
const int N = 4e6+100;
int tree[N][27];
char mp[1000+100][1000+100];
int val[N];
int cnt;
int n,m;
void init()
{
for(int i=0;i<=cnt;i++)
{
memset(tree[i],0,sizeof tree[i]);
val[i]=0;
}
cnt=0;
}
void ins(string s,int x)
{
int p=0;
int len=s.length();
for(int i=0;i<len;i++)
{
int temp=s[i]-'a';
if(tree[p][temp]==0)
{
tree[p][temp]=++cnt;
}
p=tree[p][temp];
}
val[p]=x;
}
int query(string s)
{
int p=0;
int len=s.length();
for(int i=0;i<len;i++)
{
int temp=s[i]-'a';
if(tree[p][temp]==0)
{
return -1;
}
p=tree[p][temp];
}
if(val[p])
return val[p];
else
return -1;
}
int main()
{
int t;
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
for(cin>>t;t;t--)
{
init();
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>mp[i]+1;
}
for(int i=1;i<=m;i++)
{
string s;
int x;
cin>>s>>x;
ins(s,x);
}
long long sum=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
string s="";
if(mp[i][j]=='#')
continue;
while(mp[i][j]!='#'&&j<=n)
{
s+=mp[i][j];
j++;
}
int ans=query(s);
if(ans==-1)
{
cout<<"-1"<<endl;
goto xx;
}
else
{
sum+=ans;
}
}
}
for(int j=1;j<=n;j++)
{
for(int i=1;i<=n;i++)
{
string s="";
if(mp[i][j]=='#')
continue;
while(mp[i][j]!='#'&&i<=n)
{
s+=mp[i][j];
i++;
}
int ans=query(s);
if(ans==-1)
{
cout<<-1<<endl;
goto xx;
}
else
{
sum+=ans;
}
}
}
cout<<sum<<endl;
xx:;
}
return 0;
}
还有一版我总是WA的代码，我用的经典init方法不知道为啥总是会wa，可能是trie或者val有问题吧，，我也不知道
WA 10 code
#include <bits/stdc++.h>
using namespace std;
const int N = 4e6+100;
int tree[27][N];
char mp[1000+100][1000+100];
int val[N];
int cnt;
int n,m;
void init()
{
cnt=1;
for(int i=0;i<=26;i++)
{
tree[i][0]=0;
}
for(int i=0;i<=cnt;i++)
val[i]=0;
}
void ins(string s,int x)
{
int p=0;
int len=s.length();
for(int i=0;i<len;i++)
{
int temp=s[i]-'a';
if(tree[temp][p]==0)
{
for(int j=0;j<=26;j++)
{
tree[j][cnt]=0;
}
tree[temp][p]=cnt++;
}
p=tree[temp][p];
}
val[p]=x;
}
int query(string s)
{
int p=0;
int len=s.length();
for(int i=0;i<len;i++)
{
int temp=s[i]-'a';
if(tree[temp][p]==0)
{
return -1;
}
p=tree[temp][p];
}
if(val[p])
return val[p];
else
return -1;
}
int main()
{
int t;
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
for(cin>>t;t;t--)
{
init();
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>mp[i]+1;
}
for(int i=1;i<=m;i++)
{
string s;
int x;
cin>>s>>x;
ins(s,x);
}
long long sum=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
string s="";
if(mp[i][j]=='#')
continue;
while(mp[i][j]!='#'&&j<=n)
{
s+=mp[i][j];
j++;
}
int ans=query(s);
if(ans==-1)
{
cout<<"-1"<<endl;
goto xx;
}
else
{
sum+=ans;
}
}
}
for(int j=1;j<=n;j++)
{
for(int i=1;i<=n;i++)
{
string s="";
if(mp[i][j]=='#')
continue;
while(mp[i][j]!='#'&&i<=n)
{
s+=mp[i][j];
i++;
}
int ans=query(s);
if(ans==-1)
{
cout<<-1<<endl;
goto xx;
}
else
{
sum+=ans;
}
}
}
cout<<sum<<endl;
xx:;
}
return 0;
}
