• 2024-09-22BZOJ 3277 串 题解
    Statement给 \(n\) 个串,问每个串有多少子串是所有 \(n\) 个串中至少 \(k\) 个串的子串。Solution1%%注意到\(\text{LCP}\)在后缀排序后一定是连续的一段,包含一个串的区间是连续的先预处理出对于所有左端点\(l\),最左的\(r\)满足\([l..r]\)中出现了至少\(k\)个
  • 2024-09-22BZOJ 4310 跳蚤 题解
    Statement把\(S\)分成不超过\(k\)段,使每段的最大子串中的最大串最小。输出这个串。Solution按排名二分这个串,check中从右往左贪心地划分,需要实现\(O(1)\)比较两个子串大小。#include<bits/stdc++.h>usingnamespacestd;#definerep(i,j,k)for(inti=(j);i<
  • 2024-09-22BZOJ 4932 = BZOJ 9434 = LOJ 6070 基因
    Statement问区间本质不同回文串数,强制在线,\(n\le10^5\).其实还有个四倍经验:BZOJ5384.Solution1考虑一个结论:\(s\)的所有回文后缀按长度排序后,可以划分为\(O(\log|s|)\)段等差数列。考虑离线怎么做:移动右端点\(i\),新增一个串\(s\),设其上一次出现的起点为\(q\),则\([q+
  • 2024-09-08BZOJ 1396 识别子串 题解
    Statement给\(S\),令\(x\)为\(S\)的第\(k\)个字符,称\(T=S[i..j]\)为关于\(x\)的识别子串,当且仅当:\(i\lek\lej\)(含\(x\)这一位)\(T\)在\(S\)中只出现一次求\(S\)关于每一位字符的最短识别子串长度,\(|S|\le10^5\).Solution1以下是我没看题解瞎胡的首先
  • 2024-09-08BZOJ 4231 回忆树
    以下为自己口胡,未经网上搜索题解验证Statement一棵\(n\)个点的树,每条边有一个小写字母边权,\(m\)次询问,每次给定\(u,v,s\),问字符串\(s\)在\(u\tov\)路径组成的字符串中出现了几次。\(n,m\le10^5,\sum|s|\le3\cdot10^5\).SolutionSol1把\(u\tov\)路径拆成\(u\t
  • 2024-09-08BZOJ 4502 串 题解
    妙妙数数题key:数数题通常是,对于特定形式的计数,就盯着这个模式观察,看出一些充要条件、计数形式的转化,然后想办法维护。优化的本质就是把难算的变成好算的,把不好一起统计的(只能一个个数的)以某种角度、用某些数据结构,一起统计(多个多个数)。我觉得难点通常在于“盯出一些充要条件”,
  • 2024-08-30BZOJ 4403序列统计题解
    缅怀zxc
  • 2024-06-17bzoj.org P07255 数字的拆分之二
    Description将数字N进行拆分.拆分出来的数字可以重复使用.FormatInput每一行给出一个数字N,3<=N<=500.整个测试以0代表结束.Output拆分的种数.这道题,看似变态难写,实则。。。一道******题。(观众:哇。。。。。。)这题是个简简单单的dp!N就是背包容量,但是物品体积在哪捏???就
  • 2024-04-15BZOJ 4403序列统计
    BZOJ4403序列统计解析序列满足单调不降序列,所以每个数可以选多次,我们可以把不同位置的同一个数看成多个,这样把区间为\([L,R]\)中的每一个数加上\(i\),得到的区间大小为\([L+1,R+n]\),也就是从\(R-L+n\)个数中选\(n\)个。\[\begin{aligned}&{\sum^n_{i=1}C^{i
  • 2024-04-13BZOJ 4403序列统计
    假设存在一个满足条件的长度为i的不下降序列(显然是一定存在的)那么只需要从中选出i个数即可(不必在意选出具体数的大小,可以把满足条件的序列写下来,选几个数感受一下)。但是$n\choosem$里的\(m\)的是就是\((r-l+1)\)吗?乍一看是这样的,但是这样会出现一个问题,单调不下降子序
  • 2024-01-26[Bzoj 3252] 攻略 题解
    攻略题面\(n(\le2\cdot10^5)\)个点的有根树,\(k(\len)\)次从根走到叶子,每个点有权值,求经过的点的权值和的最大值.(同一个点只能算一次)Sol1我们设想一个叶子一个叶子加进去的过程。如果有两个从某个点到叶子的路径,我们可以如图把他分成两条路径。那么他满足贪心,也就是每次
  • 2023-12-29【题解】BZOJ 4403序列统计
    tg.BZOJ4403序列统计pj.BZOJ4403序列统计没啥用的题解\(QWQ\)——无脑思考首先要想怎么求单调不上升序列的个数,因为可能会有重复的数,所以不能直接用排列组合。那这道题怎么打呀?我不知道啊\(\dots\)\((~:\)因为原来是单调不下降序列,将第\(i\)位上的数加\(i\),于是
  • 2023-10-28bzoj #4069. [Apio2015] 巴厘岛的雕塑
    bzoj#4069二进制?按位考虑。或操作而且最小?按位贪心。从最高位往下贪,记录一个\(x\)表示当前最高位确定了哪些位可以为\(0\)(其中存在为\(0\)方案的位上值为\(1\))考虑dp处理对于第\(t\)位能否为\(0\):设计状态:设\(dp_{i,j}\)表示前\(i\)个数分成\(j\)个
  • 2023-10-28bzoj #2863. 愤怒的元首
    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)}\)这么干显然不太对,因为我们不能保证每次删除时都能把图中的所
  • 2023-10-23P3565 [POI2014] HOT-Hotels
    三倍经验: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\)条路径的方案数(
  • 2023-09-24BZOJ 生日礼物
    题目背景翰翰18岁生日的时候,达达给她看了一个神奇的序列$A_1,A_2,\dots,A_n$。她被允许从中选择不超过$M$个连续的部分作为自己的生日礼物。翰翰想要知道选择元素之和的最大值。你能帮助她吗?解题思路可以先合并序列中连续的同为正或负的值,使原序列变为一个一正一
  • 2023-09-19BZOJ 3509
    题目链接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\)的
  • 2023-09-15BZOJ 3451
    题目链接description厉害题。给定一棵树,按照题面要求求一个错误点分治的期望执行次数。(不想描述题面了qwq)solution考虑拆开计算每个点期望几层点分治后被删除。这个期望值显然就是它对答案的贡献。我们不妨以这个点为根,那么相当于要求每次删除一个未被删除的点的子树,求删完
  • 2023-08-09[BZOJ 4361] isn
    简述题意给出一个长度为\(n\)的序列\(A(A_1,A_2,\dots,A_n)\)。如果序列\(A\)不是非降的,你必须从中删去一个数,并重复这一操作,直到\(A\)非降为止。求有多少种不同的操作方案,答案模\(10^9+7\)。题面转换
  • 2023-07-18BZOJ 1461 题解
    考虑设计一个哈希函数\(hash(x)=f(x)\timesbase^x\)。其中\(f(x)\)表示\(\sum_{j=1}^{i-1}[j<i]\)。然后类似于滑动窗口计算区间哈希值,加入一个数就计算贡献,减去一个数就计算这个数产生了贡献,两个东西都可以树状数组维护,那么愉快做完了。#include<bits/stdc++.h>#de
  • 2023-07-14BZOJ #3784. 树上的路径
    BZOJ#3784.树上的路径题意给一颗树,求所有路径长度中前\(k\)大。题解首先对于前\(k\)大,我们有一个常见的方法,二分。二分第\(k\)大的路径长度,然后使用点分治统计,点分治内部还要二分,所以时间复杂度\(O(nolg^3n)\)。二分显然是行不通了,想一下就会发现外层和内层的二分
  • 2023-07-07BZOJ 2140: 稳定婚姻 tarjan
    2140:稳定婚姻TimeLimit: 2Sec  MemoryLimit: 259MBSubmit: 764  Solved: 355[Submit][Status][Discuss]Description我国的离婚率连续7年上升,今年的头两季,平均每天有近5000对夫妇离婚,大城市的离婚率上升最快,有研究婚姻问题的专家认为,是与简化离婚手续有关。25
  • 2023-07-07BZOJ 2427: [HAOI2010]软件安装 树形背包
    2427:[HAOI2010]软件安装TimeLimit: 10Sec  MemoryLimit: 128MBSubmit: 1275  Solved: 492[Submit][Status][Discuss]Description现在我们的手头有N个软件,对于一个软件i,它要占用Wi的磁盘空间,它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机
  • 2023-07-07BZOJ 1042:[HAOI2008]硬币购物 容斥原理 背包dp
    1042:[HAOI2008]硬币购物TimeLimit: 10Sec  MemoryLimit: 162MBSubmit: 2505  Solved: 1505[Submit][Status][Discuss]Description硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。每次带di枚ci硬币,买si的价值的东西。请问每次
  • 2023-06-20bzoj 2839. 集合计数 二项式反演
    集合计数设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}\)但这道题我们选出的