【HHHOJ】ZJOI2019模拟赛（十三）03.10 解题报告

点此进入比赛

得分： \(97+0+10=107\)

排名： \(Rank\ 3\)

\(Rating\)：\(+47\)

\(T1\)：【HHHOJ187】Hashit（点此看题面）

容易想到可以用后缀自动机来做，结果比赛时被\(Hack\)了。（后缀自动机题解详见博客【BZOJ5084】hashit）

正解貌似是后缀数组，但实际上\(X\_o\_r\)神仙的后缀自动机也能过。

反正我的是过不了。

这里贴出被\(Hack\)掉的代码：

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N 100000

#define LL long long

using namespace std;

char s[N+5];

class SuffixAutomation//后缀自动机

{

	private:

		#define F5(x,op) (void)(ans+=1LL*(op)*(O[x].L-O[GetFa(x)].L))//更新答案

		#define Co(x,y) (void)(++O[O[x].F=y].Sz)//连边

		static const int SZ=N,C=26;int tot;LL ans;

		struct SAM {int L,F,Sz,Ex,Nxt,S[C+5];}O[(SZ<<1)+5];

		I int GetFa(CI x) {return O[O[x].F].Ex?O[x].F:O[x].F=GetFa(O[x].F);}//求第一个存在的父亲

		I int GetNxt(int& x) {return O[x].Ex?x:x=GetNxt(O[x].Nxt);}//求出第一个存在的后继

	public:

		int ExSt[N+5],SamP[N+5],TwoP[N+5];//ExSt为一个记录存在节点的栈，SamP和TwoP分别存储一个字符在SAM中建的两个节点的编号

		I SuffixAutomation() {O[0].Ex=O[SamP[0]=tot=1].Ex=1;}//初始化后缀自动机

		I void Insert(CI x,CI id,CI lst)//插入字符

		{

			RI p=lst,q,k,now=SamP[id]=++tot;O[now].L=O[p].L+1,O[now].Ex=1;

			W(p&&!GetNxt(O[p].S[x])) O[p].S[x]=now,p=O[p].F;

			if(!p) return Co(now,1),F5(now,1);

			if(O[p].L+1==O[q=O[p].S[x]].L) return Co(now,q),F5(now,1);

			O[k=TwoP[id]=++tot]=O[q],O[k].L=O[p].L+1,O[k].Sz=0,O[k].Ex=1,O[k].Nxt=q,

			F5(q,-1),Co(now,k),Co(q,k),F5(q,1),F5(k,1),F5(now,1);//删除原来的贡献，更新新的贡献

			W(p&&!(GetNxt(O[p].S[x])^q)) O[p].S[x]=k,p=O[p].F;

		}

		I void Delete(CI x) {O[x].Ex=0,F5(x,O[x].Sz-1),O[GetFa(x)].Sz+=O[x].Sz-1;}//删除字符

		I LL GetAns() {return ans;}//求答案

}S;

int main()

{

	RI i,len,x,T=0;for(scanf("%s",s+1),len=strlen(s+1),i=1;i<=len;++i)

	{

		if(s[i]^'-') S.Insert(s[i]&31,i,S.SamP[S.ExSt[T]]),S.ExSt[++T]=i;//加入字符，更新栈

		else//删除字符

		{

			S.TwoP[S.ExSt[T]]&&(S.Delete(S.TwoP[S.ExSt[T]]),0),//若插入了两个节点，则删除第二个插入的节点

			S.Delete(S.SamP[S.ExSt[T]]),--T;//删除第一个插入的节点

		}printf("%lld\n",S.GetAns());//输出答案

	}return 0;

}

\(T2\)：【HHHOJ188】Polycomp（点此看题面）

多项式神仙题，题目都看不懂。

\(T3\)：【HHHOJ189】Garrafeira（点此看题面）

也是神仙题，比赛时就写了一个\(10\)分的大暴力。。。

巴特西

【HHHOJ】ZJOI2019模拟赛（十三）03.10 解题报告

\(T1\)：【HHHOJ187】Hashit（点此看题面）

\(T2\)：【HHHOJ188】Polycomp（点此看题面）

\(T3\)：【HHHOJ189】Garrafeira（点此看题面）

最新文章

热门文章