20221005
简单点
朴素算法
很容易想到存下每个位置后离它最近的各个字母的位置。然后再暴力地从答案区间\([l,r]\)的离左端点最近的\(e\)开始按\(e,a,s,y\)的顺序跳，每跳完一次就是答案加1。
有人可能就会问:从离左端点最近的\(e\)开始往后跳为甚么一定是正确的呢？
对于\(eaeasy\)这种在离左端点最近的位置的\(e\)没有成功构成\(easy\)时中间还有能构成\(easy\)的\(e\)时，因为第二个\(e\)被第一个\(e\)所能构成的\(easy\)包含，所以无论是第一个\(e\)还是第二个\(e\),都只能与同一个\(y\)组合构成\(easy\)，他们对答案的贡献是一样的。所以选最靠近左端点的\(e\)所得的答案一定不会更劣。
倍增
像朴素算法这样一个一个地跳肯定会超时，所以我们得想办法加快这个过程。在一个静态的东西上很快地跳无疑能让我们想到倍增。但是朴素算法存下的东西，貌似没有办法用倍增跳。我们也可以发现对于一个字母为\(e\)的位置，在跳跃时他只会用到它下一个\(y\)的位置。所以我们可以只取它有用的这部分，构成\(e\)->\(a\)->\(s\)->\(y\)->\(e\)的链，然后再在这部分进行倍增。答案就是我们总共跳跃的次数除以\(4\)，因为\(easy\)的长度是\(4\)。
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=3e5+5;
char s[N];
int n,m,t[N][4],fa[N][25];
int main(){
scanf("%s",s+1);
n=strlen(s+1);
for(int i=0;i<4;i++)t[n][i]=n+1,t[n+1][i]=n+1;
for(int i=n-1;i>=0;i--){
for(int j=0;j<4;j++)t[i][j]=t[i+1][j];
if(s[i+1]=='e')t[i][0]=i+1;
if(s[i+1]=='a')t[i][1]=i+1;
if(s[i+1]=='s')t[i][2]=i+1;
if(s[i+1]=='y')t[i][3]=i+1;
}
for(int i=1;i<=n;i++){
if(s[i]=='e')fa[i][0]=t[i][1];
if(s[i]=='a')fa[i][0]=t[i][2];
if(s[i]=='s')fa[i][0]=t[i][3];
if(s[i]=='y')fa[i][0]=t[i][0];
}
fa[n+1][0]=n+1;
for(int j=1;j<=20;j++)
for(int i=1;i<=n+1;i++)
fa[i][j]=fa[fa[i][j-1]][j-1];
scanf("%d",&m);
for(int i=1;i<=m;i++){
int l,r;
scanf("%d%d",&l,&r);
int x=t[l-1][0];
int num=1;
for(int j=20;j>=0;j--)if(fa[x][j]<=r)x=fa[x][j],num+=(1<<j);
printf("%d\n",num/4);
}
return 0;
}
树上异或
循环同构串
kmp
分段后，对第一段翻倍求出它的nex数组，然后与之后的段进行匹配，都能匹配就输出Yes。按理说，这貌似不能过，但是数据比较水所以还是可以水过的。
kmp(stl版)
使用\(string\)自带的两个函数\(substr()\)和\(find()\)，\(substr()\)用来截取子串，\(find()\)与\(kmp\)效果相同，但可能是因为\(string\)比较慢的原因，只能水到95pts。
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define fo(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
template<typename T>inline void in(T &x){
x=0;int f=0;char c=getchar();
for(;!isdigit(c);c=getchar())f|=(c=='-');
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=f?-x:x;
}
template<typename T>inline void out(T x){
if(x<0)x=~x+1,putchar('-');
if(x>9)out(x/10);
putchar(x%10^48);
}
int n,len;
bool flag;
string s,c,tmp;
int main(){
int t;
in(t);
while(t--){
in(n);
s.clear();
cin>>s;
flag=0;
fo(k,2,n){
if(n%k!=0)continue;
len=n/k;
c.clear();
c=s.substr(0,len);
bool f=0;
for(int i=len;i<n;i+=len){
tmp.clear();
tmp=s.substr(i,len);
tmp+=tmp;
if(tmp.find(c)==-1){
f=1;
break;
}
}
if(!f){
flag=1;
puts("Yes");
break;
}
}
if(!flag)puts("No");
}
return 0;
}
hash
枚举分的段数，O(1)地求出hash值然后存下第一段循环之后的所有状态的hash值，与之后几段的hash值比较，如果都相同，就说明它合法。
标签：20221005,hash,端点,int,len,easy,include From： https://www.cnblogs.com/thanktothelights/p/16777326.html