LP3234 [HNOI2014]抄卡组
本题很有问题...
Solution
网上用 Hash 大部分都是如下步骤:
- 不带
*
hash 判不同 - 带
*
判前后缀 - 带
*
和不带*
暴力匹配(可以 hash/kmp)
在第三步的时候,可能会出现最坏 $O(Tn|S|_{max})$ 的情况,因此是复杂度错误的解。
以下程序可以提供 hack 数据:
#include<bits/stdc++.h>
using namespace std;
int main() {
freopen("in","w",stdout);
ios::sync_with_stdio(false), cin.tie(0);
cout<<10<<endl;
for(int i=0;i<10;i++) {
int n=100000;
cout<<n<<endl;
for(int i=0;i<n-1;i++) cout<<"*b*"<<endl;
for(int i=0;i<1999;i++) cout<<'a';
cout<<'b'<<endl;
}
return 0;
}
然而网上的题解并没有找到更好的解法(我找到的都被卡了)
loj 的前二都能通过此数据
由于发现这个问题的时候已经打了一半了所以顺手打完了(顺便复习了 KMP)所以干脆将错就错了...
希望有能人士能给出复杂度正确的题解,非常感谢
常数过大导致无法通过 loj 的第四组数据。
Code
// Code by ajcxsu
// Problem: kazu
#include<bits/stdc++.h>
using namespace std;
vector<string> ps, ls, str;
const int mo[]={1000000007, 1000000009};
pair<int, int> ghash(string x) {
int a=0, b=0;
for(auto it=x.begin(); it!=x.end(); it++) a=(1ll*a*50+*it)%mo[0], b=(1ll*b*50+*it)%mo[1];
return make_pair(a, b);
}
string tmp; pair<int, int> ha;
bool cmp(const string &a, const string &b) { return a.size()>b.size(); }
vector<int> nex;
int find(string s, string t, int pos) {
nex.clear();
int lens=s.size(), lent=t.size(), t1=0, t2=-1;
nex.push_back(-1);
while(t1<lent) {
if(t2==-1 || t[t1]==t[t2]) nex.push_back(++t2), ++t1;
else t2=nex[t2];
}
int i=pos, j=0;
while(i<lens) {
if(j==-1 || s[i]==t[j]) i++, j++;
else j=nex[j];
if(j==lent) return i-lent;
}
return -1;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int t; cin>>t;
while(t--) {
int n; cin>>n;
string s;
vector<string>().swap(ps), vector<string>().swap(ls), vector<string>().swap(str);
tmp="", ha.first=-1;
int f, l;
bool ok=1;
for(int i=0;i<n;i++) {
cin>>s;
f=s.find('*');
if(f!=-1) {
l=s.rfind('*');
if(f) ps.push_back(s.substr(0, f));
if(s.size()-l-1) ls.push_back(s.substr(l+1, s.size()-l-1));
str.push_back(s);
}
else if(ha.first==-1) ha=ghash(s), tmp=s;
else if(ghash(s)!=ha) ok=0;
}
if(!ok) { cout<<'N'<<endl; continue; }
sort(ps.begin(), ps.end(), cmp);
sort(ls.begin(), ls.end(), cmp);
if(ps.size())
for(int i=0; i<ps[0].size(); i++) {
for(int j=1; j<ps.size(); j++)
ok&=(i>=ps[j].size() || ps[j][i]==ps[0][i]);
}
for(int j=0; j<ls.size(); j++) reverse(ls[j].begin(), ls[j].end());
if(ls.size())
for(int i=0; i<ls[0].size(); i++) {
for(int j=1; j<ls.size(); j++)
ok&=(i>=ls[j].size() || ls[j][i]==ls[0][i]);
}
if(!ok) { cout<<'N'<<endl; continue; }
if(ha.first!=-1) {
int ap, bp, np;
for(int i=0; i<str.size(); i++) {
ap=bp=0;
while(1) {
np=str[i].find('*', ap);
if(np==ap) { ap=np+1; continue; }
else if(np==-1) break;
bp=find(tmp, str[i].substr(ap, np-ap), bp);
ap=np+1;
if(bp==-1) { ok=0; break; }
bp++;
}
np=str[i].size();
if(ap!=np) {
bp=find(tmp, str[i].substr(ap, np-ap), bp);
if(bp==-1) { ok=0; break; }
}
}
}
if(!ok) cout<<"N"<<endl;
else cout<<"Y"<<endl;
}
return 0;
}
本文链接:https://pst.iorinn.moe/archives/sol-luogu-3234.html
许可: https://pst.iorinn.moe/license.html若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆