2021牛客多校10 - Browser Games(哈希)

题目链接：点击查看

题目大意：给出 $n$ 个字符串，对于每个 $i$ ，输出最少需要用多少个前缀，可以表示第 $1\sim i$ 个字符串而不能表示第 $i+1\sim n$ 个字符串

题目分析：银川原题的数据加强版，正着模拟的思路被推翻，看了蒋佬队伍的代码用哈希倒着模拟的，太妙了。

简单翻译一下题面就是，对于每个 $i$ 来说，需要在第 $1\sim i$ 个字符串中分别找到一个前缀，满足：

这 $i$ 个前缀去重后数量最少

这 $i$ 个前缀不会作为前缀出现在第 $i+1\sim n$ 个字符串中

如果是用字典树正着考虑的话，不难看出每个前缀的长度是逐渐变短的，所以利用这个性质去模拟。

首先考虑 $i=n$ 时的答案，不难想到将 $n$ 个字符串的第一个字母去重后就是 $ans[n]$ 了。这里的 $n$ 个首字母代表的本质上是 $n$ 个长度为 $1$ 的前缀。

然后考虑删除掉第 $n$ 个字符串会造成的影响，对于第 $n$ 个字符串的所有前缀 $pre$ 来说，如果在字符串 $1\sim n-1$ 中，存在着一个前缀 $s$ 和 $pre$ 相等，那么需要将 $s$ 加长，这样 $s$ 才不会作为前缀出现在第 $n$ 个字符串中。

用哈希优化一下空间，上述做法的空间复杂度和时间复杂度就都是 $O(\sum |S|)$ 的了

代码：

// Problem: Browser Games // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/11261/A // Memory Limit: 65536 MB // Time Limit: 4000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; struct Hash {static const int mod1=1e9+7,mod2=1e9+9;int x,y;Hash(int x=0,int y=0):x(x),y(y){}Hash operator+(const Hash& t)const {return Hash((x+t.x)%mod1,(y+t.y)%mod2);}Hash operator*(const Hash& t)const {return Hash(1LL*x*t.x%mod1,1LL*y*t.y%mod2);}LL val() {return 1LL*x*mod2+y;} }base(2333,23333),h[N]; unordered_map<LL,vector<int>>mp; char s[N][110]; int pos[N],ans[N]; int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;read(n);for(int i=1;i<=n;i++) {scanf("%s",s[i]);h[i]=Hash(s[i][0],s[i][0]);mp[h[i].val()].push_back(i);pos[i]=0;}for(int i=n;i>=1;i--) {ans[i]=mp.size();int len=strlen(s[i]);Hash tmp;for(int j=0;j<len;j++) {tmp=tmp*base+Hash(s[i][j],s[i][j]);auto it=mp.find(tmp.val());if(it!=mp.end()) {for(auto k:it->second) {if(k!=i) {pos[k]++;h[k]=h[k]*base+Hash(s[k][pos[k]],s[k][pos[k]]);mp[h[k].val()].push_back(k);}}mp.erase(it);}}}for(int i=1;i<=n;i++) {printf("%d\n",ans[i]);}return 0; }

总结

以上是生活随笔为你收集整理的2021牛客多校10 - Browser Games(哈希)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。