Statement给 \(n\) 个串，问每个串有多少子串是所有 \(n\) 个串中至少 \(k\) 个串的子串。Solution1%%注意到\(\text{LCP}\)在后缀排序后一定是连续的一段，包含一个串的区间是连续的先预处理出对于所有左端点\(l\)，最左的\(r\)满足\([l..r]\)中出现了至少\(k\)个

Statement把\(S\)分成不超过\(k\)段，使每段的最大子串中的最大串最小。输出这个串。Solution按排名二分这个串，check中从右往左贪心地划分，需要实现\(O(1)\)比较两个子串大小。#include<bits/stdc++.h>usingnamespacestd;#definerep(i,j,k)for(inti=(j);i<

Statement问区间本质不同回文串数，强制在线，\(n\le10^5\).其实还有个四倍经验：BZOJ5384.Solution1考虑一个结论：\(s\)的所有回文后缀按长度排序后，可以划分为\(O(\log|s|)\)段等差数列。考虑离线怎么做：移动右端点\(i\)，新增一个串\(s\)，设其上一次出现的起点为\(q\)，则\([q+

Statement给\(S\)，令\(x\)为\(S\)的第\(k\)个字符，称\(T=S[i..j]\)为关于\(x\)的识别子串，当且仅当：\(i\lek\lej\)（含\(x\)这一位）\(T\)在\(S\)中只出现一次求\(S\)关于每一位字符的最短识别子串长度，\(|S|\le10^5\).Solution1以下是我没看题解瞎胡的首先

以下为自己口胡，未经网上搜索题解验证Statement一棵\(n\)个点的树，每条边有一个小写字母边权，\(m\)次询问，每次给定\(u,v,s\)，问字符串\(s\)在\(u\tov\)路径组成的字符串中出现了几次。\(n,m\le10^5,\sum|s|\le3\cdot10^5\).SolutionSol1把\(u\tov\)路径拆成\(u\t

妙妙数数题key：数数题通常是，对于特定形式的计数，就盯着这个模式观察，看出一些充要条件、计数形式的转化，然后想办法维护。优化的本质就是把难算的变成好算的，把不好一起统计的（只能一个个数的）以某种角度、用某些数据结构，一起统计（多个多个数）。我觉得难点通常在于“盯出一些充要条件”，

缅怀zxc

Description将数字N进行拆分.拆分出来的数字可以重复使用.FormatInput每一行给出一个数字N,3<=N<=500.整个测试以0代表结束.Output拆分的种数.这道题，看似变态难写，实则。。。一道******题。(观众：哇。。。。。。）这题是个简简单单的dp!N就是背包容量，但是物品体积在哪捏？？？就

BZOJ4403序列统计解析序列满足单调不降序列，所以每个数可以选多次，我们可以把不同位置的同一个数看成多个，这样把区间为\([L,R]\)中的每一个数加上\(i\),得到的区间大小为\([L+1,R+n]\),也就是从\(R-L+n\)个数中选\(n\)个。\[\begin{aligned}&{\sum^n_{i=1}C^{i

假设存在一个满足条件的长度为i的不下降序列（显然是一定存在的）那么只需要从中选出i个数即可（不必在意选出具体数的大小，可以把满足条件的序列写下来，选几个数感受一下）。但是$n\choosem$里的\(m\)的是就是\((r-l+1)\)吗?乍一看是这样的，但是这样会出现一个问题，单调不下降子序

攻略题面\(n(\le2\cdot10^5)\)个点的有根树，\(k(\len)\)次从根走到叶子，每个点有权值，求经过的点的权值和的最大值.（同一个点只能算一次）Sol1我们设想一个叶子一个叶子加进去的过程。如果有两个从某个点到叶子的路径，我们可以如图把他分成两条路径。那么他满足贪心，也就是每次

tg.BZOJ4403序列统计pj.BZOJ4403序列统计没啥用的题解\(QWQ\)——无脑思考首先要想怎么求单调不上升序列的个数，因为可能会有重复的数，所以不能直接用排列组合。那这道题怎么打呀？我不知道啊\(\dots\)\((~:\)因为原来是单调不下降序列，将第\(i\)位上的数加\(i\)，于是

bzoj#4069二进制？按位考虑。或操作而且最小？按位贪心。从最高位往下贪，记录一个\(x\)表示当前最高位确定了哪些位可以为\(0\)(其中存在为\(0\)方案的位上值为\(1\))考虑dp处理对于第\(t\)位能否为\(0\)：设计状态：设\(dp_{i,j}\)表示前\(i\)个数分成\(j\)个

bzoj#2863设\(dp_i\)表示\(i\)个点的DAG个数。发现一个DAG删去出度为\(0\)的点后显然还是一个DAG，因此不妨枚举出度为\(0\)的点的个数：\(dp_i=\sum\limits_{j=1}^idp_{i-j}\binom{i}{j}2^{j(i-j)}\)这么干显然不太对，因为我们不能保证每次删除时都能把图中的所

三倍经验：bzoj#3522P3565loj#2431加强版：bzoj#4543先看bzoj#3522这题。容易想到时间\(O(n^2)\)，空间\(O(n^2)\)的树形dp。设\(dp_{1/2/3,u,i}\)表示以\(u\)为根的子树中所有以\(u\)为一端点，长度为\(i\)的路径中选\(1/2/3\)条路径的方案数（

题目背景翰翰18岁生日的时候，达达给她看了一个神奇的序列$A_1,A_2,\dots,A_n$。她被允许从中选择不超过$M$个连续的部分作为自己的生日礼物。翰翰想要知道选择元素之和的最大值。你能帮助她吗？解题思路可以先合并序列中连续的同为正或负的值，使原序列变为一个一正一

题目链接description给定一个长度为\(n\)的数组\(a\)，求有多少对\(i,j,k(1\leqi<j<k\leqn)\)满足\(a_k-a_j=a_j-a_i\)\(n\leq10^5\)值域大小3e4.solution三个数，看起来就不好用数据结构维护。\(2a_j=a_i+a_k\)可以当做多项式两项的指数相加得到指数为\(2a_j\)的

题目链接description厉害题。给定一棵树，按照题面要求求一个错误点分治的期望执行次数。（不想描述题面了qwq）solution考虑拆开计算每个点期望几层点分治后被删除。这个期望值显然就是它对答案的贡献。我们不妨以这个点为根，那么相当于要求每次删除一个未被删除的点的子树，求删完

简述题意给出一个长度为\(n\)的序列\(A(A_1,A_2,\dots,A_n)\)。如果序列\(A\)不是非降的，你必须从中删去一个数，并重复这一操作，直到\(A\)非降为止。求有多少种不同的操作方案，答案模\(10^9+7\)。题面转换

考虑设计一个哈希函数\(hash(x)=f(x)\timesbase^x\)。其中\(f(x)\)表示\(\sum_{j=1}^{i-1}[j<i]\)。然后类似于滑动窗口计算区间哈希值，加入一个数就计算贡献，减去一个数就计算这个数产生了贡献，两个东西都可以树状数组维护，那么愉快做完了。#include<bits/stdc++.h>#de

BZOJ#3784.树上的路径题意给一颗树，求所有路径长度中前\(k\)大。题解首先对于前\(k\)大，我们有一个常见的方法，二分。二分第\(k\)大的路径长度，然后使用点分治统计，点分治内部还要二分，所以时间复杂度\(O(nolg^3n)\)。二分显然是行不通了，想一下就会发现外层和内层的二分

2140:稳定婚姻TimeLimit: 2Sec  MemoryLimit: 259MBSubmit: 764  Solved: 355[Submit][Status][Discuss]Description我国的离婚率连续7年上升，今年的头两季，平均每天有近5000对夫妇离婚，大城市的离婚率上升最快，有研究婚姻问题的专家认为，是与简化离婚手续有关。25

2427:[HAOI2010]软件安装TimeLimit: 10Sec  MemoryLimit: 128MBSubmit: 1275  Solved: 492[Submit][Status][Discuss]Description现在我们的手头有N个软件，对于一个软件i，它要占用Wi的磁盘空间，它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机

1042:[HAOI2008]硬币购物TimeLimit: 10Sec  MemoryLimit: 162MBSubmit: 2505  Solved: 1505[Submit][Status][Discuss]Description硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次

集合计数设fi表示恰好交集为k的方案数。设gi表示交集至少为k的方案数。\(g_i=\sum_{j=i}^{n}C(j,i)f_j\)由二项式反演得：\(f_k=\sum_{i=k}^{n}(-1)^{i-k}C(i,k)g_i\)考虑\(g_i\)的求出，钦定\(i\)个数必选那么剩下\(n-i\)个数每个数可选可不选\(2^{n-i}\)但这道题我们选出的