不关同步流 tg 上面会 TLE,关了之后小点会 WA,你们有什么头猪吗?
原 TLE 代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx int
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
const int Ratio=0;
const int N=1e7+5,M=1e5+5;
const int mod=998244353;
int len,n;
string s,ss[M];
int t[N][26],fail[N],ed[N],tot;
bool yz[N];
namespace Wisadel
{
void Wins(string s)
{
int len=s.size(),now=0;
fo(i,0,len-1)
{
int c=s[i]-'A';
if(!t[now][c]) t[now][c]=++tot;
now=t[now][c];
}
ed[now]++;
}
void Wbuild()
{
queue<int>q;
fo(i,0,25) if(t[0][i]) q.push(t[0][i]);
while(q.size())
{
int u=q.front();q.pop();
fo(i,0,25)
if(t[u][i]) fail[t[u][i]]=t[fail[u]][i],q.push(t[u][i]);
else t[u][i]=t[fail[u]][i];
}
int now=0;
fo(i,0,len-1)
{
now=t[now][s[i]-'A'];
for(int k=now;k&&!yz[k];k=fail[k]) yz[k]=1;
}
}
int Wq(string s)
{
int len=s.size(),now=0,res=0;
fo(i,0,len-1)
{
now=t[now][s[i]-'A'];
if(yz[now]) res=i+1;
}
return res;
}
short main()
{
// freopen(".in","r",stdin),freopen(".out","w",stdout);
len=qr,n=qr;
cin>>s;
fo(i,1,n) cin>>ss[i],Wins(ss[i]);
Wbuild();
fo(i,1,n) printf("%d\n",Wq(ss[i]));
return Ratio;
}
}
int main(){return Wisadel::main();}
只在主函数里关了同步流,改后如下:
点击查看代码
short main()
{
// freopen(".in","r",stdin),freopen(".out","w",stdout);
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
len=qr,n=qr;
std::cin>>s;
fo(i,1,n) std::cin>>ss[i],Wins(ss[i]);
Wbuild();
fo(i,1,n) printf("%d\n",Wq(ss[i]));
return Ratio;
}
战绩如下: