哈希
哈希
感觉哈希不难，但是哈希运用到题目中就不一样了。这就需要一些巧妙的转化。
例题1 星战
P8819 [CSP-S 2022] 星战
高贵的总司令题。不可以！总司令！！！
哈希好题。知道了要用哈希感觉真的差不多绿及以下，主要是这个太难想了。
除了哈希，还有个就是内向基环森林的性质，in = out = n，但是 out = n 只是 in = n 的必要条件，所以加上哈希，表示从点 u 出发的哈希值，在修改后累加的哈希总和要等于原先所有 u 点的哈希之和才是一个内向基环森林。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 5e5+5;
int n,m,w[MAX],in[MAX],now[MAX],sum,ans;
// w[i]：存从 i 点出发的边的哈希值
// in：存原图入边的哈希值
// now：存修改后当前的哈希值
mt19937 rnd;
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
w[i]=rnd(),sum+=w[i];
while(m--)
{
int u,v;
scanf("%lld%lld",&u,&v);
now[v]+=w[u],in[v]+=w[u];
ans+=w[u];
}
scanf("%lld",&m);
while(m--)
{
int op,u,v;
scanf("%lld",&op);
if(op==1) // 这些操作都挺好推的，理解就行
scanf("%lld%lld",&u,&v),now[v]-=w[u],ans-=w[u];
else if(op==2)
scanf("%lld",&v),ans-=now[v],now[v]=0;
else if(op==3)
scanf("%lld%lld",&u,&v),now[v]+=w[u],ans+=w[u];
else if(op==4)
scanf("%lld",&v),ans+=in[v]-now[v],now[v]=in[v];
if(ans==sum)
puts("YES");
else puts("NO");
}
system("pause");
return 0;
}例题2 消消乐
说道哈希，就很容易想到这个题了
P9753 [CSP-S 2023] 消消乐
这个题容易想到用栈维护，然后可以发现，在两个时间点栈的状态相同时，那么这两个时间点中间的部分肯定都能被删除的。然后考虑将栈内元素进行哈希，开一个 unordered_map 来存某个哈希值所对的出现次数，最后统计答案。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
const int INF = 0x7fffffff;
const int mod = 998244353;
const int MAX = 2e6+5;
const int base = 1331;
int n,ans;
ull has[MAX]; // hash[i] 存到了第 i 个元素，此时栈内元素的哈希值
char s[MAX];
unordered_map<ull,int>mp; // 记录每一种 hash 值出现了多少次
stack<pair<int,int>>st; // pair < val, pos > 栈
set<ull>ss; // 记录出现过的，可能成为答案的 hash 值
signed main()
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
scanf("%lld",&n);
cin>>s+1;
ss.insert(0); // 记录初始栈的情况
mp[0]++;
for(int i=1;i<=n;i++)
if(!st.empty()&&st.top().first==s[i])
{
mp[has[st.top().second-1]]++; // 累加当前贡献
has[i]=has[st.top().second-1]; // 继承前面的哈希
st.pop();
}
else
{
st.push({s[i],i});
has[i]=has[i-1]*base+s[i]+1; // 处理哈希
ss.insert(has[i]),mp[has[i]]++; // 记录可能出现的答案并且累加当前贡献
}
for(int i:ss)
ans+=mp[i]*(mp[i]-1)/2; // 对于出现次数统计答案，式子很好推，就是这么多相同状态中选两个作为答案
printf("%lld\n",ans);
system("pause");
return 0;
}例题3 字符串匹配
P7114 [NOIP2020] 字符串匹配
算是一个自己如场切的哈希蓝。
这个题的话是有个超纲的
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int MAX = (1<<20) + 5;
const int mod = 998244353;
const int INF = 0x7fffffff;
const int base = 19491001;
inline int read(){
int x=0,y=1;char c=getchar();
for(;c<'0'||c>'9';c=getchar())if(c=='-')y=-1;
for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
return x*y;
}
ull has[MAX],b[MAX];
int T,n,fl[26],pre[MAX],suf[MAX],sum[MAX][27];
char s[MAX];
signed main()
{
// freopen("string.in","r",stdin),freopen("string.out","w",stdout);
T=read();
while(T--)
{
cin>>s+1;
int n=strlen(s+1);
for(int i=0;i<26;i++) fl[i]=0;
b[0]=1;
for(int i=1;i<=n;i++) has[i]=has[i-1]*base+1ull*s[i],b[i]=b[i-1]*base;
for(int i=1;i<=n;i++)
{
if(fl[s[i]-'a']==0) pre[i]=pre[i-1]+1;
else pre[i]=pre[i-1]-1;
fl[s[i]-'a']^=1;
}
for(int i=0;i<26;i++) fl[i]=0;
suf[n+1]=0;
for(int i=n;i>=1;i--)
{
if(fl[s[i]-'a']==0) suf[i]=suf[i+1]+1;
else suf[i]=suf[i+1]-1;
fl[s[i]-'a']^=1;
}
for(int i=1;i<=n;i++) for(int j=0;j<=26;j++) sum[i][j]=sum[i-1][j]+(pre[i]<=j);
long long ans=0;
for(int len=2;len<=n;len++)
{
ull x=has[len];
for(int i=len;i<n;i+=len) if(has[i]-has[i-len]==x*b[i-len])
ans+=sum[len-1][suf[i+1]];else break;
}
printf("%lld\n",ans);
}
return 0;
}例题 4
CF1977D
很好的一个哈希题。考虑对于每一列只填一个
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define ls (root << 1)
#define rs (root << 1 | 1)
#define mid ((l + r) >> 1)
#define fi first
#define se second
#define SZ(a) ((int)(a).size())
#define END(a) (prev((a).end()))
#define pc(a) putchar(a)
#define pb(a) push_back(a)
#define yes return puts("YES"),void()
#define no return puts("NO"),void()
typedef long long ll;
const int N = 3e5 + 5;
const int mod = 998244353;
const ll INFLL = LONG_LONG_MAX;
const int INF = INT_MAX;
inline int read()
{
int x=0,y=1;char c=getchar();
for(;c<'0'||c>'9';c=getchar())if(c=='-')y=-1;
for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
return x*y;
}
unordered_map<ull,int>f;
unordered_map<ull,pii>g;
mt19937 rnd;
int n,m,mx;
ull hs[N],mxhs;
vector<int>a[N];
string ans;
inline void solve()
{
n=read(),m=read(),ans.clear(),f.clear(),g.clear();
for(int i=1;i<=n;i++)hs[i]=1ull*rnd()*rnd();mx=mxhs=0;
for(int i=1;i<=n;i++){a[i].resize(m+5);for(int j=1;j<=m;j++)scanf("%1lld",&a[i][j]);}
for(int j=1;j<=m;j++){
ull now=(1-a[1][j])*hs[1];
for(int i=2;i<=n;i++)now+=a[i][j]*hs[i];f[now]++,g[now]={1,j};
for(int i=2;i<=n;i++)now+=hs[i-1]*((a[i-1][j]==1)?1:-1),now+=hs[i]*((a[i][j]==0)?1:-1),f[now]++,g[now]={i,j};
}
for(auto i:f)if(i.se>mx)mx=i.se,mxhs=i.fi;
printf("%lld\n",mx);
int x=g[mxhs].fi,y=g[mxhs].se;
for(int i=1;i<=n;i++)ans.pb((i==x&&a[i][y]||i!=x&&!a[i][y])?'0':'1');
cout<<ans<<'\n';
return ;
}
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int T=read();srand(time(0));while(T--) solve();system("pause");return 0;
}