给定一个长度为 n 的序列和 m 个询问, 求某些区间内的最大连续异或和. (n ≤ 12000, m ≤ 6000)
[bzoj 2959] 长跑
n 个节点的无向图, 支持三类共 m 个操作: - 连接 A,B - 修改 A 的点权为 B - 给边任意定向, 从 A 走到 B, 边和点的经过次数不限, 求所到点点权之和的最大值; 或报告 A,B 不连通
(m ≤ 5n, 每个点的点权始终不超过 10^4, n ≤ 1.5*10^5)
[bzoj 1112] [POI2008]砖块Klo
n 个数 { hi }, 每次可以选一个 +1 或 -1. 希望存在连续 k 个大小相等的数, 求最少操作次数. (1 ≤ k ≤ n ≤ 10^5, 0 ≤ hi ≤ 10^6)
[bzoj 3574] [Hnoi2014]抄卡组
通配符 '*' 可以匹配任意个字符 (包含0个). 给出 n 个字符串, 问是否能两两匹配. (n ≤ 10^5, 数据组数 T = 10, 输入文件不超过 10M, n * 最长字符串 ≤ 2*10^8)
[bzoj 3881] [Coci2015]Divljak
有 n 个字符串 S[1],S[2],...,S[n], 一个字符串集合 T, 初始为空. q 个操作: - 往 T 中添加字符串 P - S[x] 是 T 中多少个元素的子串?
(1 ≤ n,q ≤ 10^5, Σ|S[i]|, Σ|P| ≤ 2*10^6)
一道差不多的题: [bzoj 2754] [SCOI2012]喵星球上的点名
[bzoj 3172] [Tjoi2013]单词
一篇文章由一些单词以空格分隔连接而成. 问每个单词在文章中出现多少次. (字符集=小写字母, 单词数 n ≤ 200, Σ 单词长度 ≤ 10^6)
[NOI 2011] 阿狸的打字机
有一台打字机: - 输入小写字母, 该字母入栈 - 按一下 'B', 最后一个字母弹栈 - 按一下 'P', 从栈底到栈顶打印字母并换行, 不修改栈
给出输入序列, 设打印出 n 个字符串, 现有 m 个询问: 第 x 个打印的字符串在第 y 个打印的字符串中出现了多少次? (1 ≤ n,m ≤ 10^5, |输入序列| ≤ 10^5)
[bzoj 1100] [POI2007]对称轴osi
求简单多边形对称轴的数量. (1 ≤ 数据组数 t ≤ 10, 3 ≤ 顶点 n ≤ 10^5, |坐标| ≤ 10^8)
[bzoj 3620] 似乎在梦中见过的样子
给一个字符串 s 和常数 k, 问有多少个子串可以拆分成 A+B+A, 其中 |A| ≥ k, |B| ≥ 1. (子串不同当且仅当位置不同; 如果一个子串有多个拆分, 视作同一个) (n ≤ 15000, k ≤ 100)
[Usaco2015 Feb]Censoring
给出 S,T 两串, 构造一个新串 U. 往 U 的尾部依次添加 S 的字符, 若 U 的后缀为 T, 删掉这个后缀继续流程. (|S|,|T| < 10^6, 保证每次删除后 U 不会为空)
[OEIS A183135] 引号序列
定义引号序列为:
- 空串
- 引号序列前后各添加一个相同的字符
- 两个引号序列连接起来
给定
OEIS 上对引号序列的定义: > the number of length 2n k-ary words (n,k>=0) that can be built by repeatedly inserting doublets into the initially empty word
[雅礼1706 Day 8] route
平面上 n 个点 (无3点共线, 无2点重合), 编号 1~n. 按照一个排列依次走过所有点, 形成 (n-1) 条线段构成的路径. 根据每条线段的转向, 可以得到长度为 n-2, 由 'L','R' 构成的字符串. 现在给出 n 个点的位置和字符串, 求一个符合字符串的排列, 且线段之间除端点外不能相交. (1 ≤ n ≤ 5000, 坐标绝对值 ≤ 10^9, 保证有解)
[雅礼1706 Day 8] infection
n 个人, 第 i 个初始在数轴 xi 处, 以 vi 的速率向正方向逃离. 某一时刻, 正常人和病人处于同一位置, 则正常人被感染. 问 2^n 种初始感染情况中, 有多少种, 在足够长的时间后, 所有人都被感染, 模 10^9 + 7. (1 ≤ n ≤ 2*10^5, |xi| ≤ 10^9, 1 ≤ vi ≤ 10^9, xi,vi 两两不同)
[雅礼1706 Day 8] gcd
定义