来自 [bento] 的全部文章

bzoj 3238 差异

题目传送门:https://www.lydsy.com/JudgeOnline/problem.php?id=3238 后缀数组+单调队列 这是一道后缀数组的模板题。 简单来说,就是先用后缀数组求出h数组。 然后利用单调队列在o(n)的时间复杂度下求出任意两个后缀的最大公共前缀长度的和。 大家看代码理解吧。 #include<cstdio> #include<algorithm> #include<cstring> using namespace std; long long ans; char st[510000]; int sum[510000],c[510000],h[510000],sa[2][510000],rk[2][510000]; in ......

HDU 3746 Cyclic Nacklace

我能表示自己不会做吗。 好吧。 其实这道题就是个裸的KMP 但我一开始竟然没有看出来 显而易见的是,如果要添加几个字符的话,肯定是字符串的循环节缺了一部分 所以答案是 (n-fail[n])-n%(n-fail[n]) Code: #include<cstdio> #include<cstring> #include<algorithm> using namespace std; char st[210000]; int n; int s[210000]; int main() { int T; scanf("%d",&T); while (T--) { scanf("%s",st+1); n=st ......

HDU 2594 Simpsons’ Hidden Talents

这道就是纯KMP,QAQ。 你只要把这两个字符串合在一起求一遍KMP就可以了 注意最后输出的总长度必须小于等于min(len1,len2). Code: #include<cstdio> #include<cstring> #include<algorithm> using namespace std; char st[110000],st1[110000],st2[110000]; int s[110000]; int n,cnt,n1,n2; int main() { while (scanf("%s%s",st1+1,st2+1)!=EOF) { n1=strlen(st1+1); n2=strlen(st2+1); for (int i=2;i<=n1;i++) { int t=s[i-1]; while (t ......

HDU 2434 Period

继续切水题的我。 这道题算法KMP 然后你只需要在做KMP的时候看一下i%(i-next[i])是否等于0且next[i]不为0 如果是0说明这里有循环节(不信你可以自己模拟一下QAQ) Code: #include&lt;cstdio&gt; #include&lt;algorithm&gt; using namespace std; char st[1100000]; int s[1100000]; int n,cnt; int main() { scanf("%d",&amp;n); while (n) { cnt++; printf("Test case #%d\n",cnt); scanf("%s",st+1); for (int i=2;i&lt;=n ......

BZOJ 2434 阿狸的打字机

感觉最近只有我在写博客啊。 这道题的方法是AC自动机+dfs序+树状数组。 你扫描字符串,遇到‘P’就把当前节点设为危险节点,遇到‘B’就返回它的父亲,否则正常转移 于是一个AC自动机就建出来了。 然后你就是跑出以fail数组为连边的树的DFS 离线操作,将询问按y排序, 再次扫描字符串 如果为P,则求出y==当前P的次数的所在节点的子树大小。 如果为B,删去当前节点的影响,返回它的父亲 否则 加入,加上当前节点的影响 可以用树状数组维护 Code: #include<cstdio> #include<algorithm> #in ......

BZOJ 2746 旅行问题

这是一道AC自动机QAQ. 题意是求任意两个字符串前缀的最大公共后缀,并且这个后缀要在一个字符串里出现过,输出这个后缀转化成十进制后的答案。 显而易见的是,先建个AC自动机,然后求出fail数组。 你的问题其实就是求两个字符串前缀所在的节点的LCA,然后输出根到它路径上所形成的字符串即可(这个可以预处理)   Code: #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MOD=1e9+7; int pos[2100000],dep[1100000],q[1100000], ......

BZOJ 1009 GT考试

这道可以用KMP 很显然又是一个模板题 只不过因为n太大了,于是用了矩阵乘法 你只要先预处理出fail数组, 然后转移矩阵也就可以求出来了, 你只需要枚举每个前缀的转移,假设枚举前缀i,有一个转移是j,你就在g[i][j]上+1 不过注意如果转移为m的话就continue 代码还是很短。 Code: #include<cstdio> #include<algorithm> using namespace std; int n,m,MOD; char st[22]; int s[22]; long long f[22][22],df[22][22],dg[22][22],dgg[22][22],g[22][22]; int main() { scan ......

BZOJ 1030 文本生成器

啦啦啦,我这种蒟蒻也只能写这些水题了。 话说czy的模板并不是特别好懂诶@RetardedZY。 这道题其实就是你先把这些合法字符串放进AC自动机。 由于要求的是长度为m的包涵其中一个合法字符串的方案数, 则你可以用AC自动机求出不合法的方案数, 然后用总方案数减去它就可以了。 代码也很短。 Code: #include&lt;cstdio&gt; #include&lt;algorithm&gt; #include&lt;cstring&gt; using namespace std; const int MOD=10007; int ans,n,m,num; int trans[6100][27],pre[6100],f ......

BZOJ 3561 DZY Loves Math VI

题目传送门 Solution 很明显是莫比乌斯反演啦 令p=gcd(i,j),且n<m $$=\sum_{i=1}^{n}\sum_{j=1}^{m}{(\frac{i}{p})}^p{(\frac{j}{p})}^{p}{p}^{p}$$ $$=\sum_{p=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}{(ijp)}^p\cdot\varepsilon(gcd(i,j))$$ $$=\sum_{p=1}^{n}p^p\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}{(ij)}^p\cdot\mu(gcd(i,j))\ast\mathrm{1}$$ $$=\sum_{p=1}^{n}p^p\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\fra ......

HDU—5017 Ellipsoid

初来乍到,这是我第一次写博客啦。。。 Solution:玄学的模拟退火一般只能拿部分分,但是如果有spj的题就比较有可能满分了。 话说这道题真是不靠谱,本来说是用模拟退火做的,结果只求局部最优解反而过了,跳出局部最优求全局最优反而超时。 因此模拟退火果然不是什么靠谱的算法。。。 这是我求局部最优解的代码: #include<cstdio> #include<algorithm> #include<cmath> #include<cstdlib> #define eps 1e-8 using namespace std; double ans,sum,a,b,c,d,e,f; int ......