T1匹配
签到大水题,这里有hash,kmp,ac自动机,还有后缀数组,后缀自动机任您挑选.
不过这个数据范围有些坑啊,re就很不爽.做法我还是比较倾向hash的,毕竟不论神魔字符算法,hash大都能莽过(我才不会说kmp忘了呢............)
code
#include<bits/stdc++.h>
using namespace std;
unsigned long long hash1[210001],hash2[210001],len[210000],ji;
int T,la,lb;
char a[210000];
inline bool check(int len1)
{ if(len1==0)return 1;
return hash1[len1]==hash2[lb+1]-hash2[lb+1-len1]*len[len1];
}
int main()
{ //freopen("c.in","r",stdin);
scanf("%d",&T);
len[0]=1;
for(int i=1;i<=200110;++i)len[i]=len[i-1]*131;
while(T--)
{ char s;
scanf("%d%d",&la,&lb);
scanf("%s",a+1);
scanf(" %c",&s);
for(int i=1;i<=la;++i)
{ hash1[i]=hash1[i-1]*131+a[i]-'a';
if(i<=lb)
hash2[i]=hash2[i-1]*131+a[i]-'a';
if(i==lb+1)
hash2[i]=hash2[i-1]*131+s-'a';
}
if(la<lb+1)hash2[lb+1]=hash2[lb]*131+s-'a';
int l=0,r=min(la,lb+1);
for(int i=r;i>=0;--i)
if(check(i)){printf("%d\n",i);break;}
}
}
T2回家
tarjan板子题.可惜我割点不会.现在倒是会了,暴搜就AC了.
code
#include<bits/stdc++.h>
using namespace std;
int T,n,m,cnt,tot,dfn[500010],low[500010],head[500010],ans;
bool bo[500010],vis[500010];
struct jjj
{int to,next;}bian[1000100];
inline void add(int u,int v)
{ bian[++cnt].to=v;
bian[cnt].next=head[u];
head[u]=cnt;
}
inline void tarjan(int x)
{ dfn[x]=low[x]=++tot;
for(int i=head[x];i;i=bian[i].next)
{ int v=bian[i].to;
if(!dfn[v])
{ tarjan(v);
low[x]=min(low[x],low[v]);
if(low[v]>=dfn[x] and x!=1 and bo[v])
{ vis[x]=1;
++ans;
}
if(bo[v])bo[x]=1;
}
else
low[x]=min(low[x],dfn[v]);
}
}
inline void clear()
{ memset(head,0,sizeof(head));
memset(bo,0,sizeof(bo));
memset(vis,0,sizeof(vis));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
cnt=0;tot=0;ans=0;
}
int main()
{ scanf("%d",&T);
while(T--)
{ clear();
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)
{ int a,b;
scanf("%d%d",&a,&b);
if(a==b)continue;
add(a,b);add(b,a);
}
bo[n]=1;
tarjan(1);
cout<<ans<<endl;
for(int i=1;i<=n;++i)
if(vis[i])printf("%d ",i);
cout<<endl;
}
}
T3寿司
不想多说什么,考场上又看错题啦.其实已经搞出O(n)前缀后缀维护了,但就是没jb看环.
遇到环,退环成链.对于不同断点的链,你可以去二分,可以三分,可以O(1)查询直接取中点.单调性显然的,不再证明了,这个题主要是预处理麻烦,一个大串,你只能去O(n)预处理,且用到的还是中间一段,真是麻烦,搞前缀的前缀,还得减去前缀,还得减去前面R对后面B的贡献.我用了8个数组维护数据,大神都是两个就搞定,我太菜了.
搞了一下午,发现预处理时有个数组忘了加一,我TMD气啊.断网之后才是考验代码能力之时啊,自己想自己码就是爽.
code 有点丑,常数飞天
#include<bits/stdc++.h>
#define N 2100001
#define m(x) memset(x,0,sizeof(x))
using namespace std;
char a[N];
int r,b,T;
long long lb[N],rb[N],rib[N],hl[N],lib[N],hr[N],ans=9999999999999999,zhi=0,len,zuob[N],youb[N];
int jir,jib;
inline long long minn(long long a,long long b)
{ if(a<b)return a;
return b;
}
inline long long check(int qi,int i)
{return lib[i]-lib[qi-1]-hl[qi-1]*(zuob[i]-zuob[qi-1])+rib[i+1]-rib[len+qi]-hr[len+qi]*(youb[1+i]-youb[len+qi]);}
inline void work(int qi)
{ int mid=(qi-1+qi-1+len)>>1;
ans=minn(ans,check(qi,mid));
}
int main()
{ freopen("c.in","r",stdin);
scanf("%d",&T);
while(T--)
{ r=0;b=0;jir=0;jib=0;ans=999999999999999;
m(lb);m(rb);m(zuob);m(youb);m(hr);m(hl);m(rib);m(lib);
scanf("%s",a+1);
len=strlen(a+1);
for(int i=1;i<=len;++i)a[i+len]=a[i];
for(int i=1;i<=2*len;++i)
{ if(a[i]=='B')lb[i]=hl[i]=r,zuob[i]=zuob[i-1]+1;
if(a[i]=='R')++r,hl[i]=hl[i-1]+1,zuob[i]=zuob[i-1];
}
r=0;
for(int i=2*len;i;--i)
{ if(a[i]=='B')rb[i]=hr[i]=r,youb[i]=youb[i+1]+1;
if(a[i]=='R')++r,hr[i]=hr[i+1]+1,youb[i]=youb[i+1];
}
for(int i=1;i<=2*len;++i)lib[i]+=lib[i-1]+lb[i];
for(int i=2*len;i;--i)rib[i]+=rib[i+1]+rb[i];
for(int i=1;i<=len;++i)
work(i);
printf("%lld\n",ans);
}
}