来自 [陈, 载元] 的全部文章

BZOJ5248[2018多省省队联测]一双木棋

题目传送门 方法一 看完题目,觉得这是一个神奇的博弈论题目,不会做……然后,看了一眼数据范围,n,m<=10?!好像可以暴力DP啊?来算一下可能的状态数量,同一行中放棋子的点一定是最左边的若干个,令A[i]表示第i行左边的A[i]个格子里放了棋子,根据题目要求不难发现这些性质:m>=A[1]>=A[2]>=A[3]>=…>=A[n-2]>=A[n-1]>=A[n]>=0,可以算出状态A[1~n]只有${n+m+1}\choose{m+1}$个,也就最多只有352716,可以放心的DP。 code: #include&lt;bits/stdc++.h&g ......

回文自动机

回文自动机Palindromic Automaton(又称回文树Palindromic Tree,简称pam)能干什么? 对于字符串S[1..n],比如它可以求出S的所有本质不同的回文子串,并求出每一个本质不同的子串在S中出现的次数,当然还能干别的很多事情。 现在来看回文自动机是如何构建的。 定义变量: cnt表示pam中的节点数,pam的每一个节点分别表示一个本质不同的回文串子串 trans[u][c]表示在节点u所对应的回文子串两边加入字符c时变成的回文串对应的节点(可能不存在) len[u]表示节点u表示的回文子串的长度 fail[u]表示结尾与u表示的回文子串相同,长度小 ......

BZOJ3676 [Apio2014]回文串

题目传送门 先来考虑如何快速的求出一个子串的出现次数,那就建一个后缀自动机,预处理出每一个节点的|right(x)|,然后找到子串对应的节点就好了。但是如果从root开始转移的话太慢了,而且不好优化,所以可以尝试倒着来。在建sam的时候顺便记录s[1..x]所对应的节点,对于子串s[l..r],其所对应的节点一定是s[1..r]所对应的点在parent树上的祖先。所以可以倍增求出s[l..r]所对应的节点。 题目还有回文串这个限制,由manacher算法的推论可知一个字符串的本质不同的回文子串只有O(len)个,因为只有当右端点右移的时候的回文串才是之前 ......

BZOJ3926[Zjoi2015]诸神眷顾的幻想乡

题目传送门 看到题目描述的最后一句话,意思是这棵树最多只有20个叶子节点,这个限制很奇怪,也是本题的突破口。考虑任意一条链组成的字符串,不难发现都会被起点为某一个叶子的字符串包含。由于叶子节点的个数非常少,所以可以将以这些节点为起点的路径组成的字符串全部加入到一个广义后缀自动机里,然后就可以直接统计答案了。时间复杂度为O(20nc),可以轻松通过此题。 code: #include&lt;bits/stdc++.h&gt; using namespace std; int en,head[100005],Next[200005],vet[200005],degree[ ......

计蒜客 A String Game

题目传送门 这道题是那场比赛里唯一一道比较容易的题目,也是我唯一那道AC的题…… 由于要在si后加字母,而且要保持si为t的子串,这很明显要用到SAM。任何这题就变成了在一张DAG中的某些点上有若干棋子,每次操作要把其中一个棋子沿着DAG的边移动一格,不能操作者负。这就是一个非常裸的博弈论问题了,求出DAG上每个点的SG函数,然后对每个棋子所在的点的SG函数求异或和,如果结果为0则Bob获胜,否则Alice获胜。 code #include&lt;cstdio&gt; #include&lt;cmath&gt; #include&lt ......

BZOJ4589 Hard Nim

题目传送门 只要知道NIM游戏是什么,就会发现这道题其实就是要求n个数异或和为0的方案数,其中这n个数能且只能取小于等于m的质数。 构造向量a[i]=[i为质数],将n个a做异或卷积得到的向量b,b[0]即为答案。 所以只要快速幂求异或卷积就行了。要注意的是,快速幂中求异或卷积的时候不用每次都FWT和UFWT,这样是两个log的,会TLE(观察代码会发现每次UFWT后就会紧接着做一次FWT……没有任何意义)。其实只要FWT一次,对a的每一位都求快速幂就行了,最后再UFWT。   code #include&lt;cstdio& ......

BZOJ2555 SubString

题目传送门 solution: 增量构建后缀自动机,对于一个询问串ch,从S(S为初始状态)开始根据trans函数进行转移,ch是原串的一个子串当且仅当转移没有被丢弃。如果被丢弃了,那么答案显然是零,否则假设最后转移到了状态T,那么答案为|endpos(T)|。那么怎么统计每一个节点的|endpos()|呢?所有状态根据slink连边显然会形成是一棵树,不难发现一个节点u的|endpos()|等于其儿子的|endpos()|的和或者儿子的|endpos()|的和加一。那么怎么判断是否要加一?一个状态的|endpos()|为其儿子的|endpos()|和再加一的充要条件是这个状态包含一个 ......

BZOJ1014 [JSOI2008]火星人prefix

题目传送门 大概看了一下题目一脸懵逼,后缀数组?怎么维护修改、插入??仔细看题目好像不是这样的。。。用splay维护字符串,同时维护hash值,然后询问时只要二分+hash判定就好了。时间复杂度O(n lg² n)。主要是代码细节比较多,还有卡常。。。 code #include&lt;cstdio&gt; #include&lt;cstring&gt; #include&lt;algorithm&gt; using namespace std; const int p=9875321; int fa[150005],son[150005][2],val[150005],root,mi[150005],n,m,hash[150005],Size[150005]; c ......

HihoCoder1036 AC自动机模板

这只是一份模板 AC自动机 code #include&lt;stdio.h&gt; #include&lt;cmath&gt; #include&lt;algorithm&gt; #include&lt;cstdlib&gt; #include&lt;cstring&gt; using namespace std; int n,len,num,son[1000005][26],que[1000005],head,tail,hz[1000005],k1,k2; char st[1000005],st1[1000005]; bool flag[1000005],val[1000005]; int main(){ scanf("%d",&amp;n); num=1; for(int i=1;i&lt;=n;i++){ scanf("%s",st); ......

BZOJ3786星系探索(DFS序+splay)

题目传送门 n个点,n-1条边而且没有环,所以这是一棵有根树。看到要修改连边,以为是Link-Cut tree,可是又要子树修改和链查询。。。好像行不通。由于这是一棵根节点固定的有根树,考虑DFS序。记录每一个点u的入栈时间戳in[u]和出栈时间戳out[u],任意一个在以u为根的子树中的节点v,都有in[v]∈[in[u],out[u]],out[v]∈[in[u],out[u]]。所以修改以u为根的子树时,只要把区间[in[u],out[u]]修改即可。再来考虑链查询,对于1号点到u号点的链,查询区间[in[1],in[u]]。观察可得,在这条链上的点的入栈时间戳一定在这段区间内,出栈时间 ......