题目描述

Anihc国提高社会生产力水平.落实好以人民为中心的发展思想。决定进行供给侧结构性改革。

为了提高供给品质.你调查了某个产业近来 $ n $ 个时期的供求关系平衡情况.每个时期的情况都用 $ 0 $ 或 $ 1 $ 中的一个数字来表示.于是这就是—个长度为 $ n $ 的 $ 01 $ 字符串 $S$ 。为了更好的了解这一些数据.你需要解决一些询问.我们令 $ data(l,r) $ 表示：在字符串 $S$ 中.起始位置在$ [l,r] $之间的这些后缀之中，具有最长公共前缀的两个后缀的最长公共前缀的长度。

对于每一个询问 $ L $ , $ R $ .求

$ ans = \sum\limits_{ L \le i \lt R } data(i, R) $

数据范围$100000$

由于你其实根本没有时间调查，所以这些数据都是乱编的，即串S中的每一位都是在 $ 0 $ 和 $ 1 $ 之间随机产生的。

题目描述

数据范围100000

算法讨论

对于前两种情况，马拉车即可

对于第三种情况，我们考虑枚举这个回文串的中点位置。

题目大意

给定n个基本词汇和m个禁忌词汇，求用这n个串组成长度l的串的方案数

「雅礼集训 2017 Day1」字符串

%%% ???

emmmm…

这个题一眼看上去是个神题，结果看了题解。。发现就是个暴力 做法十分神奇~~

%%%imortalCO

题目描述!

有一个n个结点的树，每个节点有权值v，有以下操作：

• Change x y，将编号为 x的结点的权值修改为 y。
• Query k，询问有多少棵 T 的非空连通子树，满足其价值恰好为 k。

数据规模 n,m <= 30000,v <= 128且m为2的幂次

算法讨论

考虑没有修改操作, 我们可以定以下状态

$$f[i][k]表示以i为根，异或值为k的答案$$

转移的时候就是一个背包

$$当前讨论到子树u ：f[i][k] += \sum_{j = 0}^{128}f[u][j]*f[i][k\ xor\ j]$$

%%%Sparrow…

T 1

题意是给你一个图中两两点间的最小割，要你构造出这个图

看到这个题一开始想到6号讲过的”CQOI2016不同的最小割”

然后看了一眼样例，发现一定可以构造出一个满足条件的树

然后就没往下想了。。

最后发现随便搞搞就可以过很多点。。

thh && why : 最大生成树就好啦！

sparrow :贪心选最小的边，割开就好啦！

T 2

题意是在树上选k个点，求$min(\sum_{i=1}^{k-1}dis(i,i+1))$

发现就是找一个k个点连通块，其中只有一条链权值只算一遍，其他边权值算两遍，求最小值

然后想到了“摧毁树状图”，迪屁一下就好啦！

Hoodles!

斜率优化+平衡树

然而一看到就想到了cash，事实上这道题凸包上倍增就可以，写了个cdq跑得贼慢

Math!

找规律？

证明：

$$\begin{aligned} 若&n\%k+m\%k>=k,有\lfloor \frac{n+m}{k}\rfloor-\lfloor \frac n k \rfloor-\lfloor \frac m k\rfloor=1\\原式 &=\sum_{k=1}^{n+m}\phi(k)\lfloor \frac{n+m}{k}\rfloor-\sum_{k=1}^{n}\phi(k)\lfloor \frac n k \rfloor-\sum_{k=1}^{m}\phi(k)\lfloor \frac m k\rfloor\\ &=\sum_{k=1}^{n+m}k-\sum_{k=1}^{n}k-\sum_{k=1}^{m}k\\ &=n*m\\ \end{aligned}$$

Help!

%%%Sparrow

T1:PAM (PWJ AutoMaton)

T1就是求两个字符串有多少个相同子序列传送門

DP：$f[i][j]=(\sum f[u][k]) +1\ u,k为i,j扩展出的子序列$

提到一个新东西，pwj发明的 序列自动机pam

机动训练

题目描述

整个岛可以看作一片 n*m 的区域，每个格子有自己的地形。

一条路径由一系列八连通的格子组成，两个格子八连通当且仅当这两个格子拥有公共的

顶点。

定义一条“机动路径”如下：

1、它是一条不自交的路径，即路径上任意两个格子都不是同一个

2、它的起点和终点处于不同位置，换言之这条路径至少包含 2 个格子

3、从起点开始，任何一步只能向不远离终点的方向移动，这里不远离指的是 x 和 y 两

个方向都不远离

NKOJ4405 HNOI2007 最小矩形覆盖 传送门

居然是纸质题面，十年前的OI真是jin啊