111qqz的小窝

老年咸鱼冲锋!

codeforces round 530 div2

A,B,C:都很简单,不说了。 D:一棵树,给出树的结构,以及从树根到某个深度为偶数的节点的路径和,问能否构造一种所有节点点权和最小的树,输出

codeforces hello 2019

好久没玩cf了,竟然还能涨分(虽然我用的小号Orz) 三题,D应该是数学+DP…数学实在是忘干净了。。。 前面三题大体还好,都是1

codeforces 501 B. Obtaining the String

题目链接:http://codeforces.com/contest/1015/problem/B 题意: 给出字符串s和字符串t,问一个将s变

codeforces edu #51 C. Vasya and Multisets (思维题)

题目链接 题意:有n个数,现在要分成2个集合,使得2个集合中,仅出现1次的数的个数相同,问是否有解,以及具体的分法。 思路: 一开始考虑出现多个的

2017 ACM-ICPC Beijing Regional 总结

emmm 最后一场,果然还是写点什么记录一下吧。 DAY 0 到宾馆已经晚上八点了,惊讶得发现宾馆和15年来参加regional的是同一个,于是戳了下当时和我

2014 Xi'An ACM-ICPC Regional Contest Problem G. The Problem to Slow Down You (回文自动机(模块化写法))

http://codeforces.com/gym/100548 题意: 切换面板:标签 标签 添加新标签  回文自动机、 给2个字符串,问2个字符串中,相等并且都是回文串的对数。 思路: 构建2个PAM.然后奇偶起点

bzoj 2160: 拉拉队排练 (回文自动机+快速幂)

2160: 拉拉队排练 Time Limit: 10 Sec Memory Limit: 259 MB Submit: 1938 Solved: 743 [Submit][Status][Discuss] Description 艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点,好的拉拉队往往能帮助球

ural 1960. Palindromes and Super Abilities (回文自动机,统计本质不同的回文串个数)

http://acm.timus.ru/problem.aspx?space=1&num=1960 题意: 给一个字符串S,依次输出字符串S的所有前缀中,本质不同的回文串个数。 思路: 考虑构建PAM是一个增量算法…所以一边构建一

BZOJ 2565: 最长双回文串 (回文自动机)

Description 顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串,而abc不是(abc的顺序为“abc”,逆序为“cba”,不相同)。 输入长

hdu 3948 | 2011 Multi-University Training Contest 11 The Number of Palindromes (回文自动机模板题)

http://acm.hdu.edu.cn/showproblem.php?pid=3948 题意: 给一个字符串,问本质不同的回文子串的个数。 思路: 考虑回文自动机。 我们知道,对于PAM上的一个节点,表示的就是一个本质不同的回文串。 UPDATE:

UOJ #103. 【APIO2014】Palindromes (回文自动机模板题)

http://uoj.ac/problem/103 题意: 给你一个由小写拉丁字母组成的字符串 s。我们定义 s 的一个子串的存在值为这个子串在 s 中出现的次数乘以这个子串的长度。 对于给你的这个字符串

codeforces 123D. String(后缀自动机)

题目链接:http://codeforces.com/problemset/problem/123/D 题意: 如果字符串y在字符串x中出现n次

poj 3415 Common Substrings (后缀自动机+parent树上的lazy标记)

http://poj.org/problem?id=3415 题意: 给出两个字符串,问公共长度大于等于k的子串个数(只要两个串的位置不同就认为是不同) 思路: 考虑SAM的性质。 SAM上的一个节点所能接受

hdu 4416 Good Article Good sentence (后缀自动机)

http://acm.hdu.edu.cn/showproblem.php?pid=4416 题意: 给出一个字符串A和n个字符串B,问A的子串中,不在任何一个B中出现的本质不同的子串有多少。 思路: 还是根据len搞事情 我们知道,如果不

hdu 3518 Boring counting (后缀自动机)

http://acm.hdu.edu.cn/showproblem.php?pid=3518 题意: 给一个字符串,问字符串中,至少出现2次且不相交的本质不同的子串有多少个。本质不同给的子串是说存在至少一位的字母不同。 思路: 考虑SAM

hdu 6059 | 2017 Multi-University Training Contest - Team 3 Kanade's trio (trie)

http://acm.hdu.edu.cn/showproblem.php?pid=6059 题意: 含 N 个数字的 A 数组,求有多少个三元组 (i,j,k) 满足 i<j<k 且a[i]^a[j] < a[j]^a[k] 思路: 考虑a[i]和a[k]二进制不同位中的最高位,此时满足题意

hdu 5558 | 2015ACM/ICPC亚洲区合肥站 G Alice's Classified Message (后缀自动机)

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5558 题意: 说了一大堆。。其实就是询问位置i开始的后缀和以位置[0…i - 1]开始的所有后缀中最大匹配的公共前缀长度 思路:

SPOJ LCS2 Longest Common Substring 2[后缀自动机+dp]

题意: 求n个串的最长公共子串,n<=10 思路: 不会啊orz 先放一波参考资料&题解好了。 codeforces_Understanding Suffix Automaton in depth code风景区_spoj_lc

hdu 4819 2013 Asia Regional Changchun G (四叉树|| 二维线段树单点更新 模板题)

http://acm.hdu.edu.cn/showproblem.php?pid=4819 题意: 给你一个n*n的矩阵, 每个点是一个数字, Q个操作,每次选择一个子矩阵, 把中心元素替换成子矩阵中最大值和最小值之和的二分之一。 思路: 显

hdu 4436 | 2012 Asia Tianjin Regional Contest str2int (dp+后缀自动机,多串建立)

http://acm.hdu.edu.cn/showproblem.php?pid=4436 题意: 给出n个仅由数字组成的字符串,问n个字符串的所有不同子串的和。 思路: SAM水题 从初始状态开始,走过所有路径,就是该SAM表示的所有的